Haskell, a list of lists from a tree

Question

I have this data structure for a tree:

data Tree a = NodeT a (Tree a) (Tree a) | Emptyt

I need to create a function that returns a list of lists, where each list item represents a tree level. For example, from this:

1 / \ 2 3 / \ / \ 4 5 6 7 

to this: [[1], [2,3], [4,5,6,7]]

The function should look like this:

  f :: Tree a -> [[a]] 

How to do this using recursion?

is anyone

thanks

Answer 1

You recursively calculate levels and always merge lists of two subtrees by points (all slices at the same depth are combined together).

 f :: Tree a -> [[a]] f EmptyT = [] f (NodeT a t1 t2) = [a] : merge (f t1) (f t2) merge :: [[a]] -> [[a]] -> [[a]] merge [] ys = ys merge xs [] = xs merge (x:xs) (y:ys) = (x ++ y) : merge xs ys 

If the tree was complete (all paths from the root to the list are the same length), you can use zipWith (++) as merge .

Answer 2

Answer

 levels :: Tree a -> [[a]] levels t = levels' t [] levels' :: Tree a -> [[a]] -> [[a]] levels' EmptyT rest = rest levels' (NodeT alr) [] = [a] : levels' l (levels r) levels' (NodeT alr) (x : xs) = (a : x) : levels' l (levels' r xs) 

A slightly more complicated, but more lazy implementation of levels' :

 levels' EmptyT rest = rest levels' (NodeT alr) rest = (a : front) : levels' l (levels' r back) where (front, back) = case rest of [] -> ([], []) (x : xs) -> (x, xs) 

Fans of the folds noticed that they are structured as catamorphisms:

 cata :: (a -> b -> b -> b) -> b -> Tree a -> b cata ne = go where go EmptyT = e go (NodeT alr) = na (go l) (go r) levels t = cata br id t [] where br alr rest = (a : front) : l (r back) where (front, back) = case rest of [] -> ([], []) (x : xs) -> (x, xs) 

As chi points out , there seems to be some kind of connection between this general approach and the result of using Jakub Daniel's solution with difference lists as intermediate forms. It might look something like this:

 import Data.Monoid levels :: Tree a -> [[a]] levels = map (flip appEndo []) . (cata br []) where br :: a -> [Endo [a]] -> [Endo [a]] -> [Endo [a]] br alr = Endo (a :) : merge lr merge :: Monoid a => [a] -> [a] -> [a] merge [] ys = ys merge (x : xs) ys = (x <> y) : merge xs ys' where (y,ys') = case ys of [] -> (mempty, []) p : ps -> (p, ps) 

I'm not quite sure how this compares to more direct approaches.

Discussion

Kostiantyn Rybnikov answer quotes Okasaki Encryption of the first numbering: small maneuver lessons in the Design algorithm , an excellent article that emphasizes the blind spots of many functional programmers, and offers good arguments for making abstract data types easy enough to use, and they will not be missed. However, the problem described in the article is much more complicated than this; it requires not so much machinery. In addition, the document notes that level-oriented solutions are actually slightly faster than queue-based in ML; I expect to see a big difference in a lazy language like Haskell.

Jakub Daniel's answer tries to focus on the level, but unfortunately has a performance problem. He builds each level, repeatedly adding one list to another, and these lists can have the same length. Thus, in the worst case, if I calculate it correctly, O(n log n) is required to process the tree with elements n .

The approach I chose is level-oriented, but avoids the pain of concatenation by passing the levels of my right brother and cousins ​​to each left subtree. Each node / leaf of the tree is processed exactly once. This processing includes O(1) work: pattern matching on this node / leaf and, if it is a node, pattern matching in the list received from the right brother and cousins. Thus, the total time O(n) processes the tree with elements n .

Answer 3

A bit more complicated decision than accepted, but I think mine may be better in terms of memory consumption (this is a bit late, so please check it yourself).

The intuition comes from a wonderful article by Chris Okasaki "Encryption of the first numbering: lessons of small maneuver in the design of algorithms . " You can get a general intuition about the wide intersection of tree trees in functional languages ​​in detail.

I made a slightly ugly addition to add a “list of lists” schedule, there might be a better way:

 module Main where data Tree a = NodeT a (Tree a) (Tree a) | EmptyT -- 1 -- / \ -- 2 3 -- / \ / \ -- 4 5 6 7 f :: Tree a -> [[a]] ft = joinBack (f' [(t, True)]) type UpLevel = Bool f' :: [(Tree a, UpLevel)] -> [(a, UpLevel)] f' [] = [] f' ((EmptyT, _) : ts) = f' ts f' ((NodeT a t1 t2, up) : ts) = (a, up) : f' (ts ++ [(t1, up)] ++ [(t2, False)]) joinBack :: [(a, UpLevel)] -> [[a]] joinBack = go [] where go acc [] = [reverse acc] go acc ((x, False) : xs) = go (x : acc) xs go acc ((x, True) : xs) = reverse acc : go [] ((x, False):xs) main :: IO () main = do let tree = NodeT 1 (NodeT 2 (NodeT 4 EmptyT EmptyT) (NodeT 5 EmptyT EmptyT)) (NodeT 3 (NodeT 6 EmptyT EmptyT) (NodeT 7 EmptyT EmptyT)) :: Tree Int print (tail (f tree))