ListToTree Haskell Module

> {-# OPTIONS_GHC -fglasgow-exts #-}
> module ListToTree
>     ( Tree ( Tree )
>     , pairListToTreeList
>     , EmptyNode
>     , pairListToTree
>     )
> where
> import Data.Generics

There was a thread on haskell-cafe about doing this exact task. The code I wrote was embarassingly complicated compared to their simple answer, which inspired the below code. Thanks to Cale G. and Chris K.

> data Tree a = Tree a [Tree a]   deriving (Show, Eq, Data, Typeable)

Actual exported function

> pairListToTreeList             ::  [(Int, a)] -> [Tree a]
> pairListToTreeList []          =   []
> pairListToTreeList ((n,a):aa)  =
>     let (kids, sibs) = span (\x-> fst x > n) aa
>     in (Tree a (pairListToTreeList kids)) : pairListToTreeList sibs

Or straight to a tree, if an empty node for that tree type has meaning.

> class EmptyNode a where
>   empty :: a
>
> instance EmptyNode [a] where
>   empty = []
>
> pairListToTree :: EmptyNode a => [(Int, a)] -> Tree a
> pairListToTree list = Tree empty (pairListToTreeList list)

Example test code

> test = do print $ pairListToTree list
>
> list :: [(Int, String)]
> list = [(1, "topA"),
>             (2, "secondC"),
>             (2, "secondD"),
>                 (3, "thirdG"),
>                 (3, "thirdH"),
>             (2, "secondE"),
>         (1, "topB"),
>             (2, "secondF")]

yields

< Tree "" [Tree "topA" [Tree "secondC" [],
<                       Tree "secondD"
<                                     [Tree "thirdG" [],
<                                      Tree "thirdH" []],
<                       Tree "secondE" []]
<        , Tree "topB" [Tree "secondF" []]]

In JavaScript, this could be done like this:

// Tree data structure
class Tree {
  constructor(value, children = []) {
    this.value = value;
    this.children = children;
  }
}

// Converts a list of {level, text} objects to a list of Tree nodes
function pairListToTreeList(pairs, cons = (x, y) => new Tree(x, y)) {
  if (pairs.length === 0) return [];

  const [{ level, text }, ...rest] = pairs;
  const kids = [];
  let i = 0;

  // Find all children (where level > current level)
  while (i < rest.length && rest[i].level > level) {
    kids.push(rest[i]);
    i++;
  }

  const sibs = rest.slice(i);

  return [
    cons(text, pairListToTreeList(kids, cons)),
    ...pairListToTreeList(sibs, cons)
  ];
}

// Example usage:
const input = [
  { level: 1, text: 'a' },
  { level: 2, text: 'b' },
  { level: 3, text: 'c' },
  { level: 1, text: 'd' }
];

console.log(pairListToTreeList(input));

let str = pairListToTreeList(input,
        function(x, y) { return `<ul>\n<li>${x}</li>\n${y.join('\n')}</ul>` }
    ).join('');
console.log(str);

This prints:

[
  Tree { value: 'a', children: [ [Tree...] ] },
  Tree { value: 'd', children: [] }
]

Which makes HTML that renders like this:

• a
• b
• c

• d