Learn You Scala for Great Good! Part 5
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))