Binary Tree pre order transversal

Question

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]
[]

Answer 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:

preOrderTree[1]

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]