Scala and Haskell are both good for functional programming. And in some cases their approaches for problems solving are very similar. This is my fifth post of this theme.

The idea of writing this series appeared when I was looking for a book about functional programming in Scala. It happened that I found Learn You Haskell for Great Good – the great book about Haskell. I started reading it.

Today I want to take some examples from the Higher order functions Chapter of this book

Please look at my previous posts:

Learn You Scala for Great Good!

Learn You Scala for Great Good! Part 2

Learn You Scala for Great Good! Part 3

Learn You Scala for Great Good! Part 4

Functions can take functions as parameters and return functions as return values. A function that does either of those is called a higher order function.

 

zipWith function

It takes a function and two lists as parameters and then joins the two lists by applying the function between corresponding elements.

 

Haskell:

    zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]  
    zipWith _ [] _ = []  
    zipWith _ _ [] = []  
    zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys  

 

Scala:

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

val a = 1::2::3::4::5::Nil
val b = 3::4::5::6::7::Nil
val f = (x: Int, y: Int) => x * y

println(zipWith(f, a, b))

Lists don’t have to be of the same type, but they can.

 

map function

map takes a function and a list and applies that function to every element in the list, producing a new list.

Haskell:

    map :: (a -> b) -> [a] -> [b]  
    map _ [] = []  
    map f (x:xs) = f x : map f xs  

 

Scala:

def map[A, B](f: A => B, l: List[A]):List[B] = {
  (f, l) match {
    case (_, Nil) => Nil
    case (f, x::xs) => f(x) :: map(f, xs)
  }
}

println(map((a:String) => a + "!", List("BIFF", "BANG", "POW")))

 

filter function

filter is a function that takes a predicate (a predicate is a function that tells whether something is true or not, so in our case, a function that returns a boolean value) and a list and then returns the list of elements that satisfy the predicate

Haskell:

     filter :: (a -> Bool) -> [a] -> [a]  
    filter _ [] = []  
    filter p (x:xs)   
        | p x       = x : filter p xs  
        | otherwise = filter p xs  

 

Scala:

def filter[A](f: A => Boolean, l:List[A]):List[A] = {
  l match{
    case Nil => Nil
    case x::xs if f(x) => x :: filter(f, xs)
    case x::xs => filter(f, xs)
  }
}

println(filter((x: Int) => x % 2 == 0, (1 to 100).toList))

 

Now we can overwrite our quicksort function using the filter function:

def quicksort(l:List[Int]):List[Int] = {
  def smallerSorted(el:Int, list:List[Int]):List[Int] = {
    quicksort(filter ((x:Int) => x <= el, list)) } def biggerSorted(el:Int, list:List[Int]):List[Int] = { quicksort(filter ((x:Int) => x > el, list))
  }
  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))