Haskell summarize all paths through a tree

Question

I try to summarize ALL paths though a tree that expands every level between 1 and 10 times from the root to the lowest children. My function walks recursive to all children but I have the problem that when I try to make a List of the nodes and do this lists in a list, I become a List of a List of a List ... of a List. I think my problem is the combining step And I tried to make a pattern matching method but the method that should compare the lists when it becomes a lists of lists and should make new lists and compare them if it get's just one way( meets a list with the nodes and not a list with lists) doesn't work.

Your (non-working) code would probably make what you've tried a lot clearer :-) — gspr, Jul 06 '13 at 14:34

Gabriella Gonzalez · Answer 1 · 2013-07-06T20:10:57.547

5

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

Edit: Note that the above assumes the following definition for Tree:

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

Edit #2: This version of the code might be clearer:

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

This version has the nice property that it can be written as a list comprehension:

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

edited Jul 06 '13 at 20:10

answered Jul 06 '13 at 14:49

Gabriella Gonzalez

34,863
3
77
135

@rightfold That's not equivalent, though. Your version wraps the final result in a `return`. – Gabriella Gonzalez Jul 06 '13 at 19:16
@GabrielGonzalez Whoops, brainfart. Should pay more attention next time. :) – Jul 06 '13 at 19:18
@rightfold It's ok. I made the exact same mistake when writing up the answer the first time. :) – Gabriella Gonzalez Jul 06 '13 at 20:08

score 1 · Answer 2 · answered Jul 07 '13 at 20:33

A tree can be represented as a list-monadic-list (a list where there are several options for how it resumes at each point). Then, what you want is simply a fold on this monadic list.

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

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

To see all paths:

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]]

To sum all paths:

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

Wrt this representation of trees, the ListTree package offers combinators for tree operations (such as DFS/BFS iteration) on trees represented as ListT []s.

Haskell summarize all paths through a tree

2 Answers2