CODEWITHSUNDEEP
scalahaskell
Amit Dawle
Amit Dawle

Reputation: 13

Implementing map on a tree using fold

I am trying to implement a map using fold. I could do so in Haskell 

 data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)


 foldTree :: Tree a -> b -> (b -> a -> b -> b) ->  b   
 foldTree EmptyTree d _ = d
 foldTree (Node a l r) d f =  f (foldTree l d f)  a  (foldTree r d f)


 mapTree :: Tree a -> ( a -> b) -> Tree b
 mapTree tree f = foldTree tree EmptyTree (\l n r -> Node (f n)  l  r)

However when I tried to port it to Scala, I am a bit stuck

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Node[A](value: A , left: Tree[A], right: Tree[A]) extends Tree[A]


def fold[A, B](t:Tree[A] , z:B)(f:(B,A,B) => B) : B = t match {
    case EmptyTree => z 
    case Node(x,l,r) => f ( fold( l , z )(f) , x , fold( r , z )(f) )   
  }

  def map(tree:Tree[Int])(f:Int=>Int) : Tree[Int] = fold(tree , EmptyTree)((l,x,r) => Node(f(x),l,r))

The compiler complains that it is expecting an EmptyTree in function I pass to fold.

fold(tree , EmptyTree)((l,x,r) => Node(f(x),l,r))

The return type for the Map is Tree so I would have expected this to work. Any suggestions ?

Upvotes: 1

Views: 1116

Answers (2)

chi
chi

Reputation: 116174

As an alternative to @vitalii's solution, make the type parameters to fold explicit:

def map(tree: Tree[Int])(f: Int=>Int): Tree[Int] =
  fold[Int, Tree[Int]](tree, EmptyTree)((l, x, r) => Node[Int](f(x), l, r))
  //   ^^^^^^^^^^^^^^

Upvotes: 2

vitalii
vitalii

Reputation: 3365

Try to write your last line as

def map(tree:Tree[Int])(f:Int=>Int) : Tree[Int] = fold(tree , EmptyTree:Tree[Int])((l,x,r) => Node(f(x),l,r))

Scala's type inference is very limited compared to haskell, in this case it tries to infere type of fold from it's arguments left to right, and incorectly decides that result type of fold should be EmptyTree and not the Tree[Int]. Usually adding auxilary constructor to the companion object of the parent type helps in this situation a bit, for instance in the Option object there's a constructor

def empty[A]: Option[A]

which returns the parent type.

Upvotes: 2

Related Questions