Как создать древовидную иерархию в Haskell?

Я не вижу особенно умного однопроходного решения для этого. Вам просто нужно стиснуть зубы и сделать два прохода: один проход создает индекс формы Map Id [Node], в котором перечислены все дочерние элементы каждого узла. Затем второй проход использует этот индекс и преобразует его в Forest a. Обратите внимание, что это не Tree a, потому что в корне нет значения, а также потому, что, насколько нам известно, существует несколько корней.

import qualified Data.Map.Lazy as M
import qualified Data.Tree as T

newtype Id = Id Int deriving (Eq, Show, Ord)
data Node a = Node {id, parent :: Id, value :: a} deriving Show

input :: [Node String]
input = [ Node (Id 1) (Id 0) "1"
        , Node (Id 2) (Id 1) "1.1"
        , Node (Id 3) (Id 0) "2"
        , Node (Id 4) (Id 2) "1.1.1"
        , Node (Id 5) (Id 3) "2.1"
        , Node (Id 6) (Id 1) "1.2"
        ]

index :: [Node a] -> M.Map Id [Node a]
index m = M.fromListWith (++) $ do
  n@(Node this parent v) <- m
  pure (parent, [n])

recombine :: M.Map Id [Node a] -> T.Forest a
recombine m = go (Id 0) -- Implied root, but a more thorough solution would be explicit
  where go root = [ T.Node v (go idx)
                  | Node idx p v <- M.findWithDefault [] root m
                  ]

После этого у нас есть дерево, которое мы хотели:

> putStr . T.drawForest . recombine . index $ input
2
|
`- 2.1

1
|
+- 1.2
|
`- 1.1
   |
   `- 1.1.1