CODEWITHSUNDEEP
haskellsummarizationtree-search
Dante Miller
Dante Miller

Reputation: 43

Haskell summarize all paths through a tree

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.

Upvotes: 3

Views: 1632

Answers (2)

yairchu
yairchu

Reputation: 24774

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.

Upvotes: 1

Gabriella Gonzalez
Gabriella Gonzalez

Reputation: 35089

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]

Upvotes: 5

Related Questions