Список Карта Над Tree

Question

Рассмотрим следующее определение дерева:

data Tree a = Leaf a | Node [Tree a] 

и дерево пример:

input :: Tree String 
input = Node [Leaf "a", Leaf "b", Node [Leaf "c", Leaf "d"]] 

Я пытаюсь 'карта' список по такому дереву, тогда как значения дерева должны быть отброшены. В случае [0..] быть в списке, результат должен выглядеть следующим образом:

output :: Tree Int 
output = Node [Leaf 0, Leaf 1, Node [Leaf 2, Leaf 3]] 

Так что я ищу функцию ..

seqTree :: [b] -> Tree a -> Tree b 
seqTree = undefined 

.. для которых справедливо следующее:

seqTree [0..] input == output 

Я пришел к выводу, что такая функция должна обернуть другую функцию, чтобы отслеживать элементы списка, которые еще не были «приняты»:

seqTree' :: [b] -> Tree a -> Tree ([b], b) 
seqTree' xxs@(x:xs) t = case t of 
    Leaf _ -> Leaf (xs, x) 
--Node ts = the tricky part... maybe something with foldr? 
seqTree' [] t = error "empty list." 

С этим я надеялся осуществить seqTree, что потребует некоторое окончательное отображение по всему дереву, я предполагаю, что есть лучшие способы сделать это, вот подробная версия:

finish :: Tree (a,b) -> Tree b 
finish t = case t of 
    Leaf v -> Leaf $ snd v 
    Node ts -> Node (map finish ts) 

И наконец:

seqTree xs t = finish $ seqTree' xs t 

компилируется, однако, как отмечается в комментарии, функция seqTree' является частичным. Кто-нибудь знает, как это исправить, и, кроме того, что было бы более подходящим, менее низким уровнем подхода для решения этого?

Answer 1

Я не понимаю, почему вам нужно «закончить», так сказать. Вы можете определить функцию:

seqTree' :: [b] -> Tree a -> ([b],Tree b) 

, который отображает часть последовательности на данном поддереве и возвращает полученное дерево вместе с не еще потребляли элементы. Таким образом, вы передаете список элементов через вызовы функций, так сказать, каждая функция «съедает» некоторые элементы из него и возвращает хвост, так что другие функции могут «съесть» следующие элементы.

Теперь, как и большинство рекурсивных функций, есть базовый случай, когда Tree a является Leaf x:

seqTree' (x:xs) (Leaf _) = (xs,Leaf x) 

Здесь, таким образом, вернуть Leaf x с данным элементом последовательности, и возвращает остаток последовательности.

Следующая есть также seqTree' случай для Node, в этом случае вы кормите последовательность для вызова seqTree' и вызов потребляет часть дерева, остальное используется в вызове для второго ребенка и так на. Таким образом, для дерева с тремя детьми, она будет выглядеть так:

--Example 
seqTree' xsa (Tree [na,nb,nc]) = (xsd,Tree [oa,ob,oc]) 
    where (xsb,oa) = seqTree' xsa na 
      (xsc,ob) = seqTree' xsb nb 
      (xsd,oc) = seqTree' xsc nc 

Хорошая вещь, существует уже такая функция: mapAccumL. Таким образом, вы можете написать:

seqTree' xsa (Node nodes) = (xsz,Node newnodes) 
    where (xsz,newnodes) = mapAccumL seqTree' xsa nodes 

Или полную функцию:

seqTree' (x:xs) (Leaf _) = (xs,Leaf x) 
seqTree' xsa (Node nodes) = (xsz,Node newnodes) 
    where (xsz,newnodes) = mapAccumL seqTree' xsa nodes 

Теперь нам нужно только построить звонок от seqTree к seqTree' который просто сбросив остальные корма:

seqTree xs tree = snd $ seqTree' xs tree 

или немного короче:

seqTree xs = snd . seqTree' xs 

Если добавить deriving Show к вашему Tree a определению, и я запустить программу, я получил:

*Main> seqTree [0..] input 
Node [Leaf 0,Leaf 1,Node [Leaf 2,Leaf 3]] 

Answer 2

Вы можете использовать State, где состояние содержит оставшийся список значений. Затем вы можете предоставить функцию, которая преобразует значения в дереве на основе текущего значения и следующего значения во входном потоке, например.

data Tree a = Leaf a | Node [Tree a] deriving (Show) 

input :: Tree String 
input = Node [Leaf "a", Leaf "b", Node [Leaf "c", Leaf "d"]] 

labelWithState :: (a -> l -> b) -> Tree a -> State [l] (Tree b) 
labelWithState f (Leaf v) = do 
    (l : ls) <- get 
    put ls 
    pure $ Leaf (f v l) 
labelWithState f (Node ts) = do 
    lts <- traverse (labelWithState f) ts 
    pure $ Node lts 

labelWith :: (a -> l -> b) -> [l] -> Tree a -> Tree b 
labelWith f ls t = evalState (labelWithState f t) ls 

, то вы можете определить seqTree как:

seqTree :: [b] -> Tree a -> Tree b 
seqTree = labelWith (\_ l -> l) 

Answer 3

Я думаю, что есть способ, чтобы просмотреть это как частный случай чего-то более общего: сохраняющее состояние вычисления, которое производит Дерево как результат, объединив множество меньших вычислений с учетом состояния на листьях исходного дерева. Ли предоставляет хороший способ реализовать это вручную, используя State и список меток, но мы можем упростить вещи и повторно использовать некоторые встроенные механизмы из Applicative и State, разделив работу на двухэтапный процесс: во-первых, fmap over ваше дерево, заменяя каждый узел одинаковым значением в монаде State s, а затем используя sequenceA :: Tree (State s a) -> State s (Tree a), чтобы запустить вычисление состояния через каждый из узлов в последовательности.

Конечно, это означает, что вам нужно будет реализовать Foldable and Traversable для вашего типа дерева, но это хорошие экземпляры для записи для типа дерева в любом случае. Предположив, что те, которые были написаны, вы могли бы реализовать свою функцию, как это:

seqTree :: [b] -> Tree a -> Tree b 
seqTree labels = evalState labels . sequenceA . (nextLabel <$) 
    where nextLabel = do 
    (x:xs) <- get 
    put xs 
    pure x 

или в качестве альтернативы, как указано в комментарии к предыдущей версии этого ответа, вместо sequenceA . (nextLabel <$), это, вероятно, чище писать traverse (const nextLabel) ,