W jaki sposób „wylesianie” usuwa „drzewa” z programu?

Myślę, że rozumiem, w jaki sposób wylesianie zużywa i tworzy listę w tym samym czasie (z funkcji składania i rozwijania - zobacz tę dobrą odpowiedź na CodeReview tutaj ), ale kiedy porównałem to z wpisem wikipedia o technice , o której mówił „usuwanie” drzewa ”z programu.

Rozumiem, w jaki sposób program można sparsować do składniowego drzewa parsowania (czy to prawda?), Ale jakie jest znaczenie tego użycia wylesiania dla pewnego rodzaju uproszczenia (prawda?) Programów? Jak mam to zrobić w moim kodzie?

Wygląda na to, że Yatima2975 obejmowała pierwsze dwa pytania, postaram się odpowiedzieć na trzecie. Aby to zrobić, zajmę się nierealistycznie prostą sprawą, ale jestem pewien, że będziesz w stanie wyobrazić sobie coś bardziej realistycznego.

Wyobraź sobie, że chcesz obliczyć głębokość pełnego drzewa binarnego rzędu . Typ (nieznakowanych) drzew binarnych to (w składni Haskella):$n$

type Tree = Leaf | Node Tree Tree

Teraz pełne drzewo rzędu to:$n$

full : Int -> Tree
full n | n == 0 = Leaf
full n = Node (full (n-1)) (full (n-1))

Głębokość drzewa jest obliczana przez

depth : Tree -> Int
depth Leaf = 0
depth (Node t1 t2) = 1 + max (depth t1) (depth t2)

Teraz możesz zobaczyć, że każde obliczenie najpierw skonstruuje pełne drzewo rzędu za pomocą a następnie zdekonstruuje to drzewo za pomocą . Wylesianie opiera się na spostrzeżeniu, że taki wzorzec (konstrukcja, po której następuje dekonstrukcja) często może być zwarty : możemy zastąpić każde wywołanie pojedynczym wywołaniem :n f u l l d e p t h d e p t h ( f u l l n ) f u l l _ d e p t $\mathrm{depth}\ (\mathrm{full}\ n)$$n$$\mathrm{full}$$\mathrm{depth}$$\mathrm{depth}\ (\mathrm{full}\ n)$$\mathrm{full\_depth}$

full_depth : Int -> Int
full_depth n | n == 0 = 0
full_depth n = 1 + max (full_depth (n-1)) (full_depth (n-1))

Pozwala to uniknąć alokacji pamięci pełnego drzewa i konieczności wykonywania dopasowywania wzorców, co znacznie poprawia wydajność. Ponadto, jeśli dodasz optymalizację

max t t --> t

Potem zamieniłeś wykładniczą procedurę czasową na liniową, czasową ... Byłoby fajnie, gdyby istniała dodatkowa optymalizacja, która rozpoznałaby, że to tożsamość liczb całkowitych, ale nie jestem pewien, czy takie optymalizacja jest stosowana w praktyce.$\mathrm{full\_depth}$

Jedynym głównym kompilatorem, który wykonuje automatyczne wylesianie, jest GHC, a jeśli dobrze pamiętam, jest to wykonywane tylko podczas komponowania wbudowanych funkcji (z przyczyn technicznych).

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ż:

• Katamorfizm
• Anamorfizm
• Hylomorfizm

Jest to trochę mylące, ale stosuje się wylesianie (w czasie kompilacji), aby wyeliminować drzewa pośrednie, które zostaną utworzone (w czasie wykonywania). Wylesianie nie polega na hakowaniu części abstrakcyjnego drzewa składni (to eliminacja martwej gałęzi :-)

Kolejną rzeczą, która mogła cię wyrzucić, jest to, że listy to drzewa, po prostu bardzo niezrównoważone!