It’s my fourth post of the series where I told how I started studying Haskell in order to get knowledge in functional programming in Scala. You may see previous posts on this theme:

Learn You Scala for Great Good!

Learn You Scala for Great Good! Part 2

Learn You Scala for Great Good! Part 3

Today I want to take the three last examples from the Recursion Chapter.

 

zip function

It takes two lists and zips them together. zip [1,2,3] [2,3] returns [(1,2),(2,3)], because it truncates the longer list to match the length of the shorter one.

Haskell

   zip :: [a] -> [b] -> [(a,b)]  
   zip _ [] = []  
   zip [] _ = []  
   zip (x:xs) (y:ys) = (x,y):zip' xs ys

How about if we zip something with an empty list? Well, we get an empty list back then. So there’s our edge condition. However, zip takes two lists as parameters, so there are actually two edge conditions.

First two patterns say that if the first list or second list is empty, we get an empty list. The third one says that two lists zipped are equal to pairing up their heads and then tacking on the zipped tails. Zipping [1,2,3] and ['a','b'] will eventually try to zip [3] with []. The edge condition patterns kick in and so the result is (1,'a'):(2,'b'):[], which is exactly the same as [(1,'a'),(2,'b')].

 

Scala

def zip[A, B](a:List[A], b:List[B]):List[(A,B)] = {
  (a, b) match {
    case (_, Nil) => Nil
    case (Nil, _) => Nil
    case (x::xs, y::ys) => (x, y) :: zip(xs, ys)
  }
}

println(zip(List(1,2,3,4,5,6), List("One", "Two", "Tree", "Four", "Five")))

 

elem function

It takes an element and a list and sees if that element is in the list. The edge condition, as is most of the times with lists, is the empty list.

Haskell

    elem :: (Eq a) => a -> [a] -> Bool  
    elem a [] = False  
    elem a (x:xs)  
        | a == x    = True  
        | otherwise = a `elem` xs   

 

Scala

def elem[A](el: A, l: List[A]): Boolean = {
  (el, l) match {
    case (a, Nil) => false
    case (a, x::xs) if a == x => true
    case (a, x::xs) => elem(a, xs)
  }
}

println(elem(8, 1::3::4::5::6::9::8::12::Nil))

 

Quick sort

The Quick Sort algorithm:

a sorted list is a list that has all the values smaller than (or equal to) the head of the list in front (and those values are sorted), then comes the head of the list in the middle and then come all the values that are bigger than the head (they’re also sorted)

Haskell

    quicksort :: (Ord a) => [a] -> [a]  
    quicksort [] = []  
    quicksort (x:xs) =   
        let smallerSorted = quicksort [a | a  x]  
        in  smallerSorted ++ [x] ++ biggerSorted  

 

Scala
Let’s first implement this function for integers:

def quicksort(l:List[Int]):List[Int] = {
  def smallerSorted(el:Int, list:List[Int]):List[Int] = {
    quicksort(for {x  el} yield x)
  }
  l match {
    case Nil => Nil
    case x::xs => smallerSorted(x, xs) ::: x::Nil ::: biggerSorted(x, xs)
  }

}

println(quicksort(1::2::6::3::5::4::Nil))

 

The generic function:

def quicksort[A](l:List[A])(implicit ord: Ordering[A]):List[A] = {
  def smallerSorted(el:A, list:List[A]):List[A] = {
    quicksort(for {x  Nil
    case x::xs => smallerSorted(x, xs) ::: x::Nil ::: biggerSorted(x, xs)
  }

}

println(quicksort('b'::'e'::'a'::'d'::'x'::'z'::Nil))

The function takes an implicit parameter ord of type Ordering[A]. The good thing is: the Ordering companion object defines a bunch of implicit orderings!