spiegare l'ampiezza dell'Haskell primo codice di numerazione per attraversare gli alberi

Question

Sto leggendo this paper by Chris Okasaki; intitolato "Numerazione in ampiezza: lezioni da un piccolo esercizio di progettazione dell'algoritmo".

Una domanda è: come avviene la magia nell'algoritmo? Ci sono alcune figure (ad esempio la figura 7 intitolata "infilare l'output di un livello nell'ingresso del livello successivo") Sfortunatamente, forse sono solo io, ma quella figura mi ha completamente deluso. Non capisco come avviene la discussione?

Answer 1

Larghezza prima attraversamento significa attraversare i livelli di un albero uno per uno. Quindi supponiamo di sapere già quali sono i numeri all'inizio di ogni livello - il numero di elementi attraversati finora prima di ogni livello. Per il semplice esempio nel documento

import Data.Monoid 

data Tree a = Tree (Tree a) a (Tree a) 
      | Empty 
    deriving (Show) 

example :: Tree Char 
example = Tree (Tree Empty 'b' (Tree Empty 'c' Empty)) 'a' (Tree Empty 'd' Empty) 

le dimensioni sarebbero 0, 1, 3, 4. Sapendo questo, possiamo infilare tale elenco di dimensioni attraverso un albero dare (sub-tree) da sinistra a a destra: avanziamo del primo elemento della lista di uno per il nodo e infiliamo la coda della lista prima attraverso la sinistra e poi attraverso la sottostruttura destra (vedere thread di seguito).

Dopo averlo fatto, otterremo di nuovo lo stesso elenco di dimensioni, spostato solo di uno: ora abbiamo il numero totale di elementi dopo il ogni livello. Quindi il trucco è: supponiamo di avere un elenco di questo tipo, usarlo per il calcolo e quindi inserire l'output come input - tie the knot.

Un esempio di implementazione:

tagBfs :: (Monoid m) => (a -> m) -> Tree a -> Tree m 
tagBfs f t = let (ms, r) = thread (mempty : ms) t 
       in r 
    where 
    thread ms Empty = (ms, Empty) 
    thread (m : ms) (Tree l x r) = 
     let (ms1, l') = thread ms l 
      (ms2, r') = thread ms1 r 
     in ((m <> f x) : ms2, Tree l' m r') 

generalizzato per Monoid (per la numerazione da darle const $ Sum 1 come la funzione).

Answer 2

Un modo per visualizzare la numerazione degli alberi è in termini di attraversamento. Nello specifico, vogliamo attraversare l'albero nel primo ordine utilizzando State per contare. L'istanza Traversable necessaria è simile a questa. Nota che probabilmente vorrai definire questa istanza per un newtype come BFTree, ma sto semplicemente usando il tipo Tree non elaborato per semplicità. Questo codice è fortemente ispirato dalle idee in Cirdec's monadic rose tree unfolding code, ma la situazione qui sembra essere sostanzialmente più semplice. Spero di non aver perso qualcosa di orribile.

{-# LANGUAGE DeriveFunctor, 
      GeneralizedNewtypeDeriving, 
      LambdaCase #-} 
{-# OPTIONS_GHC -Wall #-} 

module BFT where 

import Control.Applicative 
import Data.Foldable 
import Data.Traversable 
import Prelude hiding (foldr) 

data Tree a = Tree (Tree a) a (Tree a) 
      | Empty 
    deriving (Show, Functor) 

newtype Forest a = Forest {getForest :: [Tree a]} 
    deriving (Functor) 

instance Foldable Forest where 
    foldMap = foldMapDefault 

-- Given a forest, produce the forest consisting 
-- of the children of the root nodes of non-empty 
-- trees. 
children :: Forest a -> Forest a 
children (Forest xs) = Forest $ foldr go [] xs 
    where 
    go Empty c = c 
    go (Tree l _a r) c = l : r : c 

-- Given a forest, produce a list of the root nodes 
-- of the elements, with `Nothing` values in place of 
-- empty trees. 
parents :: Forest a -> [Maybe a] 
parents (Forest xs) = foldr go [] xs 
    where 
    go Empty c = Nothing : c 
    go (Tree _l a _r) c = Just a : c 

-- Given a list of values (mixed with blanks) and 
-- a list of trees, attach the values to pairs of 
-- trees to build trees; turn the blanks into `Empty` 
-- trees. 
zipForest :: [Maybe a] -> Forest a -> [Tree a] 
zipForest [] _ts = [] 
zipForest (Nothing : ps) ts = Empty : zipForest ps ts 
zipForest (Just p : ps) (Forest ~(t1 : ~(t2 : ts'))) = 
    Tree t1 p t2 : zipForest ps (Forest ts') 

instance Traversable Forest where 
    -- Traversing an empty container always gets you 
    -- an empty one. 
    traverse _f (Forest []) = pure (Forest []) 

    -- First, traverse the parents. The `traverse.traverse` 
    -- gets us into the `Maybe`s. Then traverse the 
    -- children. Finally, zip them together, and turn the 
    -- result into a `Forest`. If the `Applicative` in play 
    -- is lazy enough, like lazy `State`, I believe 
    -- we avoid the double traversal Okasaki mentions as 
    -- a problem for strict implementations. 
    traverse f xs = (Forest .) . zipForest <$> 
      (traverse.traverse) f (parents xs) <*> 
      traverse f (children xs) 

instance Foldable Tree where 
    foldMap = foldMapDefault 

instance Traversable Tree where 
    traverse f t = 
     (\case {(Forest [r]) -> r; 
       _ -> error "Whoops!"}) <$> 
     traverse f (Forest [t]) 

Ora possiamo scrivere il codice per accoppiare ogni elemento della struttura ad albero con il suo numero in ampiezza in questo modo:

import Control.Monad.Trans.State.Lazy 

numberTree :: Tree a -> Tree (Int, a) 
numberTree tr = flip evalState 1 $ for tr $ \x -> 
     do 
     v <- get 
     put $! (v+1) 
     return (v,x)