Binary Tree pre order transversal

I have a data type for a binary tree and a function to calculate its pre order traversal:

data BT a = Empty | Fork a (BT a) (BT a)
  deriving (Show)

treePreOrder :: BT a -> [a] 
treePreOrder Empty = [] 
treePreOrder (Fork x l r) = 
  [x] ++ treePreOrder l ++ treePreOrder r

I am now trying to generate a list of all the possible trees from a pre order transversal.

preOrderTree :: [a] -> [BT a] 
preOrderTree [] = [Empty] 
preOrderTree (x:xs) = 
  [Fork x l r| i <- [0..length xs-1], let (ys, zs) = splitAt i xs, l <- preOrderTree ys , r <- preOrderTree zs]

but it gives an empty list of trees:

λ> preOrderTree [1,2,3]
λ> preOrderTree [1]


  • You're close. The problem is with:

    i <- [0..length xs-1]

    You have excluded length xs, but this is a valid split which would put all the items in the left branch.

    By omitting it, you've broken the function for singletons. When you evaluate:


    you get length xs-1 == -1, so the i <- [0..length xs-1] generates no trees. As a result, this small error causes the entire recursion to generate no trees.

    With this corrected:

    preOrderTree :: [a] -> [BT a]
    preOrderTree [] = [Empty]
    preOrderTree (x:xs) =
      [Fork x l r| i <- [0..length xs], let (ys, zs) = splitAt i xs
                 , l <- preOrderTree ys , r <- preOrderTree zs]

    it works fine:

    λ> preOrderTree [1]
    [Fork 1 Empty Empty]
    λ> preOrderTree [1,2,3]
    [Fork 1 Empty (Fork 2 Empty (Fork 3 Empty Empty)),Fork 1 Empty (Fork 2
    (Fork 3 Empty Empty) Empty),Fork 1 (Fork 2 Empty Empty) (Fork 3 Empty
    Empty),Fork 1 (Fork 2 Empty (Fork 3 Empty Empty)) Empty,Fork 1 (Fork 2
    (Fork 3 Empty Empty) Empty) Empty]