CODEWITHSUNDEEP
listhaskelltreehigher-order-functions
user3276667
user3276667

Reputation: 87

Haskell: build a tree from a list

Consider the following type:

data LTree a = Leaf a | Fork (LTree a) (LTree a)

Now consider the following function that lists the leaves of a tree, together with its depth

tolistdepth :: LTree a -> [(a,Int)]
tolistdepth (Leaf x) = [(x,0)]
tolistdepth (Fork e d) = map (\(x,n) -> (x,n+1)) (tolistdepth e ++ tolistdepth d)

I need help defining the following function

build :: [(a, Int)] -> LTree a

that calculates the inverse of the first function so that 

build (tolistdepth a) = a

I don't even know where to start :)

I have managed to do the following:

build :: [(a, Int)] -> LTree a
build xs = let ys= map (\(x, n) -> (Leaf x, n)) xs
           in SOMETHING iterateUntil SOMETHING (buildAssist ys)

buildAssist :: [(LTree a, Int)] -> [(LTree a, Int)]
buildAssist [] = []
buildAssist [x] = [x]
buildAssist (x@(t1, n1):y@(t2, n2):xs) = if n1 == n2 then ((Fork t1 t2), n1 - 1):buildAssist xs
                                                     else x:(buildAssist (y:xs))

This way, I think I have dealt with when to fork. Now, how do I use buildAssist in my original function (if buildAssist is of any use of course)?

I believe I have figured it out.

Please let me know if this works:

build :: [(a,Int)] -> LTree a
build l = fst (buildaccum 0 l)

buildaccum :: Int -> [(a,Int)] -> (LTree a, [(a,Int)])
buildaccum n l@((a,b):t) |n==b = (Leaf a,t)
                         |n<b = (Fork e d, l2)
     where (e,l1) = buildaccum (n+1) l
           (d,l2) = buildaccum (n+2) l1

Upvotes: 1

Views: 6442

Answers (1)

ErikR
ErikR

Reputation: 52057

I'll give you a hint which demonstrates a helpful technique when parsing lists.

What really is at work here is a function like this:

build' :: [(a,Int)] -> (LTree a, [(a,Int)])

That is, build' returns a LTree a and the rest of the input list it has not yet consumed.

In this form the definition of build' goes something like this:

build' [] = error "oops - bad input list"
build' ((a,n):xs) =
  if we are at a leaf node, return (LTree a, xs)
  if we decide we need to fork, then return (Fork e f,zs)
    where
      (e,ys) = build' ((a,n):xs)  -- parse the left branch
      (f,zs) = build' ys          -- parse the right branch

Note this is just pseudo-code, and there are important details missing which I am leaving as an exercise.

The interesting part is how the remaining input list is determined in the Fork case. ys is the remaining input after parsing the left branch, and this is fed as input to build' to get the right branch, and the remaining input of that call to build' (zs) is returned as the remaining input from the original build' call.

Update:

To iterate a function f with starting value x until a certain condition p, follow this formula:

iterateUntil p f x = if p x then x else iterateUntil p f (f x)

Upvotes: 6

Related Questions