Create arbitrarily nested list structure in Haskell

Question

given the problem from:

http://arunrocks.com/treeify_-_converting_tree_data_structures/

For a hobby project, I was faced with an interesting problem of converting a flat representation of a tree into a nested data structure. A flat representation of a tree looks like this:

0 0 1 1 2 3 2 1

Each number refers to the nesting level within a tree. After conversion to a nested structure, it should look as follows (square brackets is the Python syntax for a list):

[ 0, 0, [ 1, 1, [ 2, [ 3 ], 2], 1]]

How can I do this in Haskell?

Answer 1

In Haskell all elements of a list need to have the same type. So you can't have a list where one element is an integer and another element is a list. Therefore [1, [2, 3]] would cause a type error in Haskell.

So if you want to represent arbitrarily nested structures like this, you'll need to define your own type for that. That could look like this:

data Tree a =
    Leaf a
  | Branch [Tree a]

A value of that type could then look like this:

Branch [
  Leaf 0, Leaf 0,
  Branch [
    Leaf 1, Leaf 1, Branch [
      Leaf 2, Branch [
        Leaf 3],
      Leaf 2],
    Leaf 1]]