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