Deriving.hs

-- List in Scala
sealed trait List[+A]
case object Nil extends List[Nothing] 
case class Cons[+A](head: A, tail: List[A]) extends List[A

-- map in Scala
def map[A,B](as: List[A])(f: A => B): List[B] = as match {
  case Nil => Nil
  case x :: xs => f(x) :: map(xs)(f)
}

-- List in Haskell
data List a = Nil | Cons a (List a)

-- map in Haskell
map :: List a -> (a -> b) -> List b
map Nil f = Nil
map (Cons a xs) f = Cons (f a) (map xs f)


map (Cons 1 (Cons 2 Nil)) (+1) 
= 
map (Cons 2 (Cons 3 Nil))

-- However.. map is a very general function that can be writtng many many datatypes. 
-- In most cases, the definition of `map` is actually derivable for a type

-- In Haskell, a type which is `mappable` is a `Functor`
class Functor f where
  fmap :: f a -> (a -> b) -> f b

data List a = Nil | Cons a (List a) deriving Functor

fmap (Cons 1 (Cons 2 Nil)) (+1) 
= 
(Cons 2 (Cons 3 Nil))



-- here's an exaple for another type
sealed trait Tree[+A]
case object Leaf extends Tree[Nothing]
case class Branch[A](left: Tree[A], value: A, right: Tree[A]) extends Tree[A]


def map[A,B](tree: Tree[A])(f : A => B): Tree[B] = tree match {
  case Leaf => Leaf
  case Branch(l,a,r) => Branch(map(l)(f),f(a),map(r)(f))
}

val t = Branch(Branch(Leaf,1,Leaf),2,Branch(Leaf,3,Leaf))

map(t)(_+1)
=
Branch(Branch(Leaf,2,Leaf),3,Branch(Leaf,4,Leaf))




-- in Haskell

data Tree a = Leaf | Branch (Tree a) a (Tree a) deriving Functor

t = Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)

fmap t (+1)
=
 Branch (Branch Leaf 2 Leaf) 3 (Branch Leaf 4 Leaf)