Как «вырубка леса» удаляет «деревья» из программы?

Я думаю, что понимаю, как вырубка лесов потребляет и производит список одновременно (из функции сгиба и разворачивания - посмотрите этот хороший ответ на CodeReview здесь ), но когда я сравнил это с записью в википедии о технике, о которой говорилось «удаление деревья из программы.

Я понимаю, как программа может быть проанализирована в синтаксическом дереве синтаксического анализа (верно?), Но в чем смысл такого использования обезлесения для какого-то упрощения (не так ли?) Программ? И как бы я сделал это с моим кодом?

Yatima2975, кажется, охватил ваши первые два вопроса, я постараюсь ответить на третий. Для этого я рассмотрю нереально простой случай, но я уверен, что вы сможете представить что-то более реалистичное.

Представьте, что вы хотите вычислить глубину полного двоичного дерева порядка . Тип (немаркированных) двоичных деревьев (в синтаксисе Haskell):$n$

type Tree = Leaf | Node Tree Tree

Теперь полное дерево порядка :$n$

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

И глубина дерева вычисляется

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

Теперь вы можете видеть, что любое вычисление сначала построит полное дерево порядка используя а затем разложит это дерево, используя . Вырубка лесов основывается на наблюдении, что такой шаблон (конструкция, сопровождаемая деконструкцией) часто может быть закорочена : мы можем заменить любые вызовы одним вызовом :н е у л л д е р т ч д е р т ч ( е ¯u л л н ) е ц л л _ д е р т $\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))

Это позволяет избежать выделения памяти для полного дерева и необходимости выполнять сопоставление с образцом, что значительно повышает производительность. Кроме того, если вы добавите оптимизацию

max t t --> t

Затем вы превратили процедуру экспоненциального времени в линейную процедуру времени ... Было бы здорово, если бы была дополнительная оптимизация, которая признала бы, что был тождеством на целых числах, но я не уверен, что какой-либо такой Оптимизация используется на практике.$\mathrm{full\_depth}$

Единственный основной компилятор, который выполняет автоматическую вырубку лесов, - это GHC, и, если я правильно помню, это выполняется только при составлении встроенных функций (по техническим причинам).

Во-первых, списки - это своего рода деревья. Если мы представляем список в виде связанного списка , это просто дерево , каждый узел которого имеет 1 или 0 потомков.

Деревья разбора - это просто использование деревьев в качестве структуры данных. Деревья имеют множество приложений в информатике, включая сортировку, реализацию карт, ассоциативные массивы и т. Д.

В общем, список, деревья и т. Д. Являются рекурсивными структурами данных: каждый узел содержит некоторую информацию и другой экземпляр той же структуры данных. Складывание - это операция над всеми такими структурами, которая рекурсивно преобразует узлы в значения «снизу вверх». Развертывание - это обратный процесс, он преобразует значения в узлы «сверху вниз».

Для заданной структуры данных мы можем механически построить их функции свертывания и разворачивания.

В качестве примера возьмем списки. (Я буду использовать Haskell для примеров, так как он напечатан, и его синтаксис очень чистый.) Список - это либо конец, либо значение, либо «хвост».

data List a = Nil | Cons a (List a)

Теперь давайте представим, что мы свернули список. На каждом шаге у нас есть текущий узел, который нужно свернуть, и мы уже свернули его рекурсивные подузлы. Мы можем представить это состояние как

data ListF a r = NilF | ConsF a r

где rпромежуточное значение, построенное путем складывания подсписка. Это позволяет нам выразить функцию сворачивания над списками:

foldList :: (ListF a r -> r) -> List a -> r
foldList f Nil            = f NilF
foldList f (Cons x xs)    = f (ConsF x (foldList f xs))

Мы конвертируем Listв ListF, рекурсивно сворачивая его подсписок, а затем используем функцию, определенную в ListF. Если вы думаете об этом, это просто еще одно представление стандарта 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

Мы можем построить unfoldListтаким же образом:

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')

Опять же, это просто еще одно представление unfoldr:

unfoldr :: (r -> Maybe (a, r)) -> r -> [a]

(Обратите внимание, что Maybe (a, r)это изоморфно ListF a r.)

И мы можем построить функцию обезлесения тоже:

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)

Он просто исключает промежуточное звено Listи объединяет функции складывания и раскладывания.

Та же процедура может быть применена к любой рекурсивной структуре данных. Например, дерево, узлы которого могут иметь 0, 1, 2 или потомков со значениями на 1- или 0-ветвящихся узлах:

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)

Конечно, мы можем создавать deforestTreeтак же механически, как и раньше.

(Обычно мы выражаемся treeFoldболее удобно как:

treeFold' :: (r -> r -> r) -> (a -> r -> r) -> (a -> r) -> Tree a -> r

)

Я опущу детали, я надеюсь, что картина очевидна.

Смотрите также:

• катаморфизм
• анаморфизм
• гилеморфизм

Это немного сбивает с толку, но вырубка лесов применяется (во время компиляции) для устранения промежуточных деревьев, которые будут созданы (во время выполнения). Вырубка лесов не предполагает взлома частей абстрактного синтаксического дерева (это устранение мертвых веток :-)

Еще одна вещь, которая может вас отбросить, это то, что списки - это деревья, просто очень несбалансированные!