CODEWITHSUNDEEP
haskellrecursiontreebinary-tree
user65526
user65526

Reputation: 705

Defining a function from lists to binary and unary trees

Consider binary and unary trees, as defined by the following type, and a function flatten, which converts binary and unary trees to lists (e.g, flatten (Node (Leaf 10) 11 (Leaf 20)) is [10,11,20]):

data Tree a = Leaf a | Node (Tree a) a (Tree a) | UNode a (Tree a) deriving (Show)
flatten :: Tree a -> [a]
flatten (Leaf x) = [x] 
flatten (Node l x r) = flatten l ++ [x] ++ flatten r
flatten (UNode l x) = [l] ++ flatten x

I am trying to define a recursive function, reverseflatten, which converts lists to binary and unary trees, specifically in the manner of the following pattern, which works for lists of length <= 7. I can see how the pattern would go on, but not how to create a recursive function from my example:

reverseflatten :: [a] -> Tree a
reverseflatten [x] = (Leaf x)
reverseflatten [x,y] = UNode x (Leaf y)
reverseflatten [x,y,z] = Node (Leaf x) y (Leaf z)
reverseflatten [x,y,z,x'] = Node (Leaf x) y (UNode z (Leaf x') )
reverseflatten [x,y,z,x',y'] = Node (Leaf x) y ( Node (Leaf x') z (Leaf y'))
reverseflatten [x,y,z,x',y',z'] =  Node (Leaf x) y ( Node (Leaf x') z ( UNode y' (Leaf z')))
reverseflatten [x,y,z,x',y',z',x''] =  Node (Leaf x) y ( Node (Leaf x') z ( Node (Leaf z') y' (Leaf x'')))

How would I create such a recursive function, that for any finite list, forms a binary tree of the kind defined above? The answer below does not do this, since it does not follow the pattern above.

Edit: The procedure I followed for even lists > 2, should be fairly transparent (you take the tree corresponding to an odd list and then you add a unary node). The general procedure I followed for constructing a tree from an odd-numbered list was this. reverse flatten[x,y,z] is Node (Leaf x) y (Leaf z). Then for the next odd-numbered list up, [x, y, z, x', y'], I wanted to preserve z in its previous position in the case for reverseflatten [x,y,z] (in which z was the final bottom right leaf), and so position z as in Node (Leaf x') z (Leaf y'), in the second place, so that the tree for this case is just like the tree for reverseflatten [x,y,z], except that we add nodes surrounding the bottom right leaf, z. I then wanted x' and y' to surround z, in the order in which they are present in the list, hence Node (Leaf x') z (Leaf y'). Then for the next odd-numbered list reverseflatten [x,y,z,x',y',z',x''] , I had a similar idea in mind. I wanted y' to remain in its place in reverseflatten [x,y,z,x',y'] and reverseflatten [x,y,z,x',y',z', x'']) to be constructed by surrounding y' by z' and x'', in the order in which they are present in the list.

Upvotes: 0

Views: 272

Answers (1)

Koralp Catalsakal
Koralp Catalsakal

Reputation: 1124

I tried to change the code to capture the pattern you were asking for. My implementation is not very efficient, but could not think of any at the moment. I hope that I understood the pattern correctly.

reverseflatten :: [a] -> Tree a
reverseflatten [x] = (Leaf x)
reverseflatten [x,y] = UNode x (Leaf y)
reverseflatten [x,y,z] = Node (Leaf x) y (Leaf z)
reverseflatten (x:y:xs) = revflat2 (x:y:xs)

revflat2 :: [a] -> Tree a
revflat2 [x] = (Leaf x)
revflat2 [x,y] = UNode y (Leaf x)
revflat2 [x,y,z] = Node (Leaf x) y (Leaf z)
revflat2 (x:y:xs) = Node (Leaf x) y (revflat2 ([head $ tail xs] ++ [head xs] ++ tail (tail xs)))

Upvotes: 3

Related Questions