Learn You Scala for Great Good! Part 2

Learn You Scala for Great Good! Part 2

Last time I wrote about my experience in learning of functional programming basics using Learn You a Haskell for Great Good! with accent on Scala.

Today I’m going to use an example from the Recursion chapter.

Maximum awesome

In Haskell example the maximum function takes a list of things that can be ordered (e.g. instances of the Ord typeclass) and returns the biggest of them.


    maximum :: (Ord a) => [a] -> a  
    maximum [] = error "maximum of empty list"  
    maximum [x] = x  
    maximum (x:xs)   
        | x > maxTail = x  
        | otherwise = maxTail  
        where maxTail = maximum xs

 

As you can see, pattern matching goes great with recursion! Most imperative languages don’t have pattern matching so you have to make a lot of if else statements to test for edge conditions. Here, we simply put them out as patterns. So the first edge condition says that if the list is empty, crash! Makes sense because what’s the maximum of an empty list? I don’t know. The second pattern also lays out an edge condition. It says that if it’s the singleton list, just give back the only element.

Now the third pattern is where the action happens. We use pattern matching to split a list into a head and a tail. This is a very common idiom when doing recursion with lists, so get used to it. We use a where binding to define maxTail as the maximum of the rest of the list. Then we check if the head is greater than the maximum of the rest of the list. If it is, we return the head. Otherwise, we return the maximum of the rest of the list.

In my Scala examples, I’ll start with a simple one. My maximum function will take a list of integers and will return an integer.


    def maximum(l:List[Int]):Int = {

      l match {
        case Nil => throw new Exception("maximum of empty list")
        case x::Nil => x
        case x::xs if x > maximum(xs) => x
        case x::xs => maximum(xs)
      }
    }

How to make a generic function?

My example on Scala is very close, but not identical to the Haskell example.

As I have said above, a maximum function takes a list of integers and returns an integer. Is it possible to force the function to take a list of type A?

The straight-forward way doesn’t work:


    def maximum[A](l:List[A]):A = {
      l match { case Nil => throw new Exception("Nil")
        case x::Nil => x
        case x::xs if x > maximum(xs) => x
        case x::xs => maximum(xs)
      }
    }

This code returns an error:

error: value > is not a member of type parameter A

Obviously we need to convert our generic type to a type that has comparison tools.

There are two traits in Scala, that can help us: scala.Ordered and scala.math.Ordering

View Bound

A view bound is a mechanism introduced in Scala to enable the use of some type A as if it were some type B.

    
    def maximum[A <% Ordered[A]](l:List[A]):A = {
      l match { case Nil => throw new Exception("Nil")
        case x::Nil => x
        case x::xs if x > maximum(xs) => x
        case x::xs => maximum(xs)
      }
    }
    println(maximum[Char]('f'::'a'::'h'::Nil))

Note that view bounds are deprecated!

Context Bounds

A context bound describes an implicit value, instead of view bound’s implicit conversion. It is used to declare that for some type A, there is an implicit value of type B[A] available.


    def maximum[A](l: List[A])(implicit ord: Ordering[A]): A =
      l match {
        case Nil => throw new Exception("maximum of empty list")
        case x :: Nil => x
        case x :: xs => ord.max(x, maximum(xs))
    }
    println(maximum[Char]('f'::'a'::'h'::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!

Please follow and like us:

About Alexandre Kremlianski

Scala / Scala.js / JavaScript programmer

Leave a Reply

Your email address will not be published. Required fields are marked *