Transform a tree in Haskell

user_12036912 0
Viewed 906
  data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
             deriving Show
  data RoseTree a = RoseNode a [RoseTree a]
     deriving Show
  binaryTreeToRose :: BinaryTree a -> RoseTree a
         binaryTreeToRose btree = case btree of
         Node Null a Null -> RoseNode a []
         Node left a Null -> RoseNode a [binaryTreeToRose left]
         Node Null a right -> RoseNode a [binaryTreeToRose right]
         Node left a right -> RoseNode a [binaryTreeToRose left]++[binaryTreeToRose right]

I try to write a function to transform Binary tree into Rose tree in Haskell. But I have not idea about how to solve this with recursion.

binary-tree tree recursion haskell
3 Answers

You are already solving this recursively. Indeed you call binaryTreeToRose on the children left and right. So you define binaryTreeToRose in terms of itself.

Your function is however not total. Since for binaryTreeToRose Null it will error. We can make the return type a Maybe (RoseTree a):

import Data.Maybe(catMaybes)

binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose Null = Nothing
binaryTreeToRose (Node l a r) = Just (RoseNode a (catMaybes (map binaryTreeToRose [l, r])))

or even shorter:

import Data.Maybe(mapMaybe)

binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose Null = Nothing
binaryTreeToRose (Node l a r) = Just (RoseNode a (mapMaybe binaryTreeToRose [l, r]))
user_675790

Change 

           [binaryTreeToRose left]++[binaryTreeToRose right]

(it's an error, anyway) in your last code line to 

           (binaryTreeToRose left ++ binaryTreeToRose right)

, change the function's type to 

binaryTreeToRose :: BinaryTree a -> [RoseTree a]

and amend the other cases accordingly (also adding a new clause, for the Null case).

Your BinaryTree can be empty (represented by Null), but RoseTree can't. This means we can't transform the former into the latter, but rather into a list of them.

The Haskell library calls the type [RoseTree a] a "Forest". So the result of the conversion will be a forest of rose trees, containing either one, or zero of them (representing the empty binary tree case).

Having an empty tree is like having no trees at all. There's no fruit either way.

user_8498910

If you want to have fun, you can use recursion-schemes for recursion. In this scenario, recursion schemes provides an automatic recursion by providing an one-layer deduction.

For example:

data BT a = BNil | BN (BT a) a (BT a)
             deriving Show
data RT a = RN a [RT a]
             deriving Show

-- data BTF a f = BNilF | BNF f a f deriving Functor
makeBaseFunctor ''BT   --BinaryTree

-- binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose :: BT a -> Maybe (RT a)
binaryTreeToRose = cata alg where
  alg BNilF = Nothing
  alg BNF l a r = Just $ RN a $ catMaybes (l ++ r)
user_16356720
Related