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

Answer 2

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.