Transform a tree in Haskell

Question

  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.

Answer 1

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