Haskell суммирует все пути по дереву

Question

Я пытаюсь суммировать ВСЕ пути, хотя дерево, которое расширяет каждый уровень от 1 до 10 раз от корня до младших. Моя функция рекурсивно относится ко всем дочерним элементам, но у меня есть проблема, когда я пытаюсь создать список узлов и делать эти списки в списке, я становлюсь списком списка списка ... списка. Я думаю, что моя проблема - это комбинационный шаг. И я попытался создать метод сопоставления шаблонов, но метод, который должен сравнивать списки, когда он становится списком списков, и должен создавать новые списки и сравнивать их, если он получается только одним способом (соответствует список с узлами, а не список со списками) не работает.

Answer 1

summarize :: Tree a -> [[a]] 
summarize Leaf = [[]] 
summarize (Node a t1 t2) = do 
    t <- [t1, t2] 
    map (a:) (summarize t) 

Edit: Обратите внимание, что выше, предполагает следующее определение Tree:

data Tree a = Leaf | Node a (Tree a) (Tree a) 

Edit # 2: Эта версия кода может быть яснее:

summarize :: Tree a -> [[a]] 
summarize Leaf = [[]] 
summarize (Node a t1 t2) = do 
    t  <- [t1, t2] 
    summary <- summarize t 
    return (a:summary) 

Эта версия имеет хорошая характеристика, которую можно записать в виде списка:

summarize (Node a t1 t2) = [a:summary | t <- [t1, t2], summary <- summarize t] 

Answer 2

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

import Control.Monad.Trans.List.Funcs (repeatM) -- cabal install List 
import qualified Data.List.Class as L 

exampleTree = L.take 3 (repeatM [0, 1]) 

Чтобы увидеть все пути:

ghci> L.toList exampleTree 
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]] 

Суммируя все пути:

ghci> L.foldlL (+) 0 exampleTree 
[0,1,1,2,1,2,2,3] 

WRT это представление деревьев, то ListTree пакет предлагает комбинаторы для операций дерева (например, DFS/BFS) на деревьях, представленных как ListT [] s.