Attempting to construct trees in Haskell

Question

I am trying to use an unfold function to build trees.

Tree t = Leaf | Node (Tree t) t (Tree t)

unfoldT :: (b -> Maybe (b, a, b)) -> b -> Tree a
unfoldT f b =
    case f b of
      Nothing -> Leaf
      Just (lt, x, rt) -> Node (unfoldT f lt) x (unfoldT f rt)

The build function needs to create a tree that has a height equal to the number provided, as well as be numbered in an in-order fashion. The base case being build 0 = Leaf and the next being build 1 = Node (Leaf 0 Leaf).

build :: Integer -> Tree Integer

My attempt at solving it:

build n = unfoldT (\x -> Just x) [0..2^n-2]

I am not entirely sure how to go about constructing the tree here. Would love it if somebody could point me in the right direction.

Edit 1:

If I was to use a 2-tuple, what would I combine? I need to be able to refer to the current node, its left subtree and its right subtree somehow right?

Answer 1

If I was to use a 2-tuple, what would I combine?

I would recommend to pass the remaining depth as well as the offset from the left:

build = unfoldT level . (0,)
  where
    level (_, 0) = Nothing
    level (o, n) = let mid = 2^(n-1)
                   in ((o, n-1), o+mid-1, (o+mid, n-1))

Answer 2

If I was to use a 2-tuple, what would I combine?

That's the key question behind the state-passing paradigm in functional programming, expressed also with the State Monad. We won't be dealing with the latter here, but maybe use the former.

But before that, do we really need to generate all the numbers in a list, and then work off that list? Don't we know in advance what are the numbers we'll be working with?

Of course we do, because the tree we're building is totally balanced and fully populated.

So if we have a function like

-- build2 (depth, startNum)
build2 :: (Int, Int) -> Tree Int

we can use it just the same to construct both halves of e.g. the build [0..14] tree:

build [0..14] == build2 (4,0) == Node (build2 (3,0)) 7 (build2 (3,8))

Right?

But if we didn't want to mess with the direct calculations of all the numbers involved, we could arrange for the aforementioned state-passing, with the twist to build2's interface:

--     depth, startNum    tree, nextNum
build3 :: (Int, Int) -> (Tree Int, Int)

and use it like

build :: Int -> Tree Int                 -- correct!
build depth = build3 (depth, 0)          -- intentionally incorrect

build3 :: (Int, Int) -> (Tree Int, Int)  -- correct!
build3 (depth, start) = Node lt n rt     -- intentionally incorrect
  where
       (lt, n) = build3 (depth-1, start)   -- n is returned
       (rt, m) = build3 (depth-1, n+1)     --  and used, next

You will need to tweak the above to make all the pieces fit together (follow the types!), implementing the missing pieces of course and taking care of the corner / base cases.

Formulating this as an unfold would be the next step.