Po pierwsze, listy są rodzajem drzew. Jeśli reprezentujemy listę jako listę połączoną , jest to tylko drzewo, którego każdy węzeł ma 1 lub 0 potomków.
Parsowanie drzew to tylko wykorzystanie drzew jako struktury danych. Drzewa mają wiele zastosowań w informatyce, w tym sortowanie, wdrażanie map, tablice asocjacyjne itp.
Ogólnie rzecz biorąc, lista, drzewa itp. Są rekurencyjnymi strukturami danych: każdy węzeł zawiera pewne informacje i inne wystąpienie tej samej struktury danych. Składanie to operacja na wszystkich takich strukturach, która rekurencyjnie przekształca węzły w wartości „oddolne”. Rozkładanie jest procesem odwrotnym, konwertuje wartości do węzłów „z góry na dół”.
Dla danej struktury danych możemy mechanicznie konstruować ich funkcje zwijania i rozwijania.
Jako przykład weźmy listy. (Użyję Haskell w przykładach, ponieważ jest wpisany, a jego składnia jest bardzo czysta.) Lista jest albo końcem, albo wartością i „ogonem”.
data List a = Nil | Cons a (List a)
Teraz wyobraźmy sobie, że składamy listę. Na każdym kroku mamy bieżący węzeł do złożenia i już złożyliśmy jego rekursywne podwęzły. Możemy reprezentować ten stan jako
data ListF a r = NilF | ConsF a r
gdzie rjest wartością pośrednią skonstruowaną przez złożenie podlisty. To pozwala nam wyrazić funkcję składania na listach:
foldList :: (ListF a r -> r) -> List a -> r
foldList f Nil = f NilF
foldList f (Cons x xs) = f (ConsF x (foldList f xs))
Przekształcamy Listsię ListFpoprzez rekurencyjne składanie jego podlisty, a następnie używamy funkcji zdefiniowanej na ListF. Jeśli się nad tym zastanowić, jest to kolejna reprezentacja standardu foldr:
foldr :: (a -> r -> r) -> r -> List a -> r
foldr f z = foldList g
where
g NilF = z
g (ConsF x r) = f x r
Możemy skonstruować unfoldListw ten sam sposób:
unfoldList :: (r -> ListF a r) -> r -> List a
unfoldList f r = case f r of
NilF -> Nil
ConsF x r' -> Cons x (unfoldList f r')
Ponownie, to tylko kolejna reprezentacja unfoldr:
unfoldr :: (r -> Maybe (a, r)) -> r -> [a]
(Zauważ, że Maybe (a, r)jest izomorficzny ListF a r.)
Możemy również zbudować funkcję wylesiania:
deforest :: (ListF a r -> r) -> (s -> ListF a s) -> s -> r
deforest f u s = f (map (deforest f u) (u s))
where
map h NilF = NilF
map h (ConsF x r) = ConsF x (h r)
Po prostu pomija element pośredni Listi łączy funkcje składania i rozkładania.
Tę samą procedurę można zastosować do dowolnej struktury danych rekurencyjnych. Na przykład drzewo, którego węzły mogą mieć 0, 1, 2 lub potomków z wartościami na 1- lub 0-rozgałęziających się węzłach:
data Tree a = Bin (Tree a) (Tree a) | Un a (Tree a) | Leaf a
data TreeF a r = BinF r r | UnF a r | LeafF a
treeFold :: (TreeF a r -> r) -> Tree a -> r
treeFold f (Leaf x) = f (LeafF x)
treeFold f (Un x r) = f (UnF x (treeFold f r))
treeFold f (Bin r1 r2) = f (BinF (treeFold f r1) (treeFold f r2))
treeUnfold :: (r -> TreeF a r) -> r -> Tree a
treeUnfold f r = case f r of
LeafF x -> Leaf x
UnF x r -> Un x (treeUnfold f r)
BinF r1 r2 -> Bin (treeUnfold f r1) (treeUnfold f r2)
Oczywiście możemy tworzyć deforestTreetak samo mechanicznie jak wcześniej.
(Zazwyczaj treeFoldwygodniej byłoby wyrazić jako:
treeFold' :: (r -> r -> r) -> (a -> r -> r) -> (a -> r) -> Tree a -> r
)
Pominę szczegóły, mam nadzieję, że wzór jest oczywisty.
Zobacz też: