functors in scala and haskell part 1

2010-07-07 comments | scala, haskell, functors, programming

today I post some functor examples to show how to use them in haskell and in scala.

haskell functors are available in the Control.Monad and the Control.Monad.Instances module.

I won't reinvent the wheel so I use the scalaz library. This cool library provides a lot of handy features like functors, applicative functors or monads.

a good description what functors are, is the following sentence:

Functors are structure-preserving maps between categories.

so, here is a example which should illustrate this behavior.

first haskell:

-- the simple tree datastructure
data Tree a = Node a (Tree a) (Tree a)
                 | Empty
                 deriving (Show)

-- we need a functor instance for our Tree
instance Functor Tree where
    fmap f Empty        = Empty
    fmap f (Node v l r) = Node (f v) (fmap f l) (fmap f r)

-- our sample data
sampleTree :: Tree String
sampleTree = Node "Foo" (Node "Bar" Empty (Node "BlubBlub" Empty Empty)) Empty

main::IO()
main = do
    putStrLn $ show sampleTree
    putStrLn $ show $ fmap length sampleTree

generating the following output:

> runhaskell functorTree.hs
Node "Foo" (Node "Bar" Empty (Node "BlubBlub" Empty Empty)) Empty
Node 3 (Node 3 Empty (Node 8 Empty Empty)) Empty

you see, the sample tree containing the strings is mapped to a new tree containing the length of the several strings. the structure of the tree remain intact.

now scala using scalaz:

import Scalaz._

// the simple tree datastructure
sealed abstract class Tree[A]
case class Empty[Any]() extends Tree[Any]
case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]

// we need a functor instance for our Tree
implicit def TreeFunctor = new Functor[Tree] {
  def fmap[A, B](t: Tree[A], f: A => B): Tree[B] = t match {
    case Node(v, l, r) => Node(f(v), fmap(l, f), fmap(r, f))
    case Empty() => Empty()
  }
}

// our sample data
val sampleTree: Tree[String] =
    Node("Foo", Node("Bar", Empty(), Node("BlubBlub", Empty(), Empty())), Empty())

println(sampleTree)
println(sampleTree map (_.length))


:::bash
> scala functorTree.scala
Node(Foo,Node(Bar,Empty(),Node(BlubBlub,Empty(),Empty())),Empty())
Node(3,Node(3,Empty(),Node(8,Empty(),Empty())),Empty())

these both examples show, that for own types like our tree, special fmap or rather functor instances must be written. most times this is done easily, but those instance must follow some simple rules:

identity morphism: fmap id = id
composition morphism: fmap (f . g) = fmap f . fmap g

so functors are a awesome abstraction over data structures and a corner stone for monads.

enough for now...

hth

ps: I'm in the beginning of understanding the category theory, so please correct me if I'm wrong on something.