Attraversare un albero di rose con Data.Tree.Zipper

Question

Ho una struttura ad albero di rose che sto rappresentando con Data.Tree. Ogni nodo nell'albero è etichettato con una coordinata (x, y). Devo implementare un modo per trovare il nodo nell'albero più vicino a una data coordinata della query e aggiungere un figlio a quel nodo.

immagino dividendo questo in due operazioni:

1. attraversare l'albero per trovare il nodo che è più vicina a una determinata query coordinata

2. prendono il nodo trovato nel attraversamento prima e aggiungi è un bambino etichettato con la query precedente coordinare

l'unico modo che posso pensare di fare questo è quello di attraversare l'albero al punto 1 utilizzando Data.Tree .Zipper, e quindi utilizzando quella cerniera nel passaggio 2 per inserire un nodo in una posizione specifica.

Ho due domande:

• questo è un modo efficace per affrontare il problema?

• In tal caso, come utilizzare le funzioni in Data.Tree.Zipper per implementare il passaggio 1 sopra? Sto trovando l'attraversamento dell'albero difficile da implementare perché richiede una ricorsione in due dimensioni: profondità e larghezza.

Answer 1

Ecco come è possibile implementare il passaggio 1 senza assumere nulla sul layout di un albero. Per semplicità, selezionerò il nodo minimale, piuttosto che il nodo che minimizza alcune funzioni, ma non è difficile modificare questa idea. Per qualche ragione, rosezipper non offre un'operazione per ottenere tutti i figli di una cerniera, quindi dobbiamo implementarla per prima. Una volta che l'abbiamo fatto, l'idea è piuttosto semplice: recita sui bambini, quindi scegli il minimo della posizione corrente o dei risultati della ricorsione.

import Data.List 
import Data.Ord 
import Data.Tree 
import Data.Tree.Zipper 

childrenAsList :: TreePos Full a -> [TreePos Full a] 
childrenAsList = go . children where 
    go z = case nextTree z of 
     Nothing -> [] 
     Just z -> z : go (nextSpace z) 

minZipper :: Ord a => Tree a -> TreePos Full a 
minZipper = go . fromTree where 
    go z = minimumBy (comparing (rootLabel . tree)) 
        (z:map go (childrenAsList z)) 

Certamente non c'è bisogno di utilizzare una cerniera per fare qualcosa di efficace, ma è certamente un modo ragionevole e buono per affrontare il problema. Un vantaggio di questo approccio rispetto all'approccio two-traversal è che dovrebbe avere la massima condivisione.

Answer 2

Non hai bisogno di chiusure lampo per eseguire semplici attraversamenti di alberi.

import Data.Foldable (minimumBy) 
import Data.Function (on) 
import Data.Tree 

addPt :: (Eq a, Ord b) => (a -> a -> b) -> a -> Tree a -> Tree a 
addPt dist p t = down t 
    where 
    down (Node a xs) 
     | a == closest = Node a (Node p []:xs) 
     | otherwise = Node a (map down xs) 
    closest = minimumBy (compare `on` dist p) t 

Questo aggiungerà il punto più volte se il punto più vicino restituita dalla minimumBy viene duplicato, e potrebbe essere reso un po 'più efficiente, in quanto down attraversa sempre l'albero completamente, anche se trova l'elemento in anticipo. Per risolvere entrambi i problemi, è possibile scrivere una funzione che esplora a turno ogni ramo, restituendo il ramo (eventualmente aumentato) più, ad esempio, un Bool per indicare se il punto è stato aggiunto. D'altra parte, addPt è naturalmente altamente parallelizzabile (modulo l'uso di elenchi collegati in Data.Tree, e la sostituzione di minimumBy da una versione parallela) e questo è perso se si tenta di salvare il lavoro sequenzialo. L'utilizzo di una cerniera potrebbe essere un po 'più efficiente nel caso sequenziale.