4/28/09

My take on 99 problems in Scala (first 22)

A while ago I saw 99 problems in Prolog they looked really good and I started trying to solve them in Scala. Now, thanks to Tony Morris I found that there's a Scala version!
Nice stuff to get your skills up to shape. It helped me to improve my understanding of folds, maps, flatMaps, zips, etc. Also I learned new pattern matching techniques (tuples and guards).
You must really give the exercises a shot!
Here are my solutions:



package exercises

object NinetyNine {
  //P01
  def last[A](xs: List[A]): A = xs match {
    case x :: Nil => x
    case x :: xs => last(xs)
    case Nil => throw new NoSuchElementException
  }

  //P02
  def penultimate[A](xs: List[A]): A = xs match {
    case x :: y :: Nil => x
    case x :: xs => penultimate(xs)
    case _ => throw new NoSuchElementException
  }

  //P03
  def nth[A](i: Int, xs: List[A]): A = xs match {
    case x :: xs => if (i == 0) x else nth(i - 1, xs)
    case _ => throw new NoSuchElementException
  }

  def nth2[A](i: Int, xs: List[A]): A = xs match {
    case x :: xs if (i == 0) => x
    case x :: xs if (i > 0) => nth(i - 1, xs)
    case _ => throw new NoSuchElementException
  }

  //P04
  def length[A](xs: List[A]): Int = xs match {
    case x :: xs => 1 + length(xs)
    case Nil => 0
  }

  //Although straight recursion is fun, using folds is more effective
  // folds are abstractions for recursion over data structures

  //P04
  def length1[A](xs: List[A]): Int = xs.foldLeft(0)((a, b) => a + 1)

  //P05
  def reverse[A](xs: List[A]): List[A] = xs.foldLeft(Nil: List[A])((a, b) => b :: a)

  //P06
  def isPalindrome[A](xs: List[A]): Boolean = reverse(xs) == xs

  //P07
  def flatten[A](xs: List[List[A]]): List[A] = xs.foldRight(Nil: List[A])(
    (xs, acc) => xs match {
      case ys: List[A] => ys ::: acc
      case y: A => y :: acc
    })

  //P08
  def compress[A](xs: List[A]): List[A] =
    xs.foldRight(List[A]())((y, ys) =>
      if (ys != Nil && ys.head == y) ys else y :: ys)

  //P09
  def pack[A](xs: List[A]): List[List[A]] = xs match {
    case Nil => Nil
    case _ => xs.takeWhile(_ == xs.head) :: pack(xs.dropWhile(_ == xs.head)) //can use span too, see P13
  }

  //P10
  def encode[A](xs: List[A]): List[(Int, A)] =
    pack(xs).map(y => (y.length, y.head))

  //P11
  def encodeModified[A](xs: List[A]): List[Any] =
    pack(xs).map(
      y => if (y.length == 1) y.head else (y.length, y.head))

  //Type safe version
  def encodeModifiedTypSafe[A](xs: List[A]): List[Either[A, (Int, A)]] =
    pack(xs).map(
      y =>
        if (y.length == 1) Left(y.head)
        else Right(y.length, y.head))

  //P12
  def decode[A](xs: List[(Int, A)]): List[A] = {
    def expand(i: Int, a: A): List[A] = if (i == 0) Nil else a :: expand(i - 1, a)
    flatten(xs.foldRight(List[List[A]]())((y, ys) => expand(y._1, y._2) :: ys))
  }
  //is better with flatMap
  def decode1[A](xs: List[(Int, A)]): List[A] =
    xs.flatMap(ny => List.make(ny._1, ny._2))

  //P13
  def encodeDirect[A](xs: List[A]): List[(Int, A)] = xs match {
    case Nil => Nil
    case _ => {
      val ys = xs.span(_ == xs.head)
      (ys._1.length, xs.head) :: encodeDirect(ys._2)
    }
  }

  //P14
  def duplicate[A](xs: List[A]): List[A] =
    xs.foldRight(Nil: List[A])((y, ys) => y :: y :: ys)
  //is better with flatMap
  def duplicate1[A](xs: List[A]): List[A] = xs.flatMap(y => y :: y :: Nil)

  //P15
  def duplicateN[A](n: Int, xs: List[A]): List[A] =
    xs.foldRight(Nil: List[A])((y, ys) => (1 to n).toList.map(_ => y) ::: ys)
  //is better with flatMap
  def duplicateN1[A](n: Int, xs: List[A]): List[A] =
    xs.flatMap(y => List.make(n, y))

  //P16
  def drop[A](n: Int, xs: List[A]): List[A] =
    xs.zipWithIndex.filter(_._2 % n != 0).map(_._1)

  //P17
  def split[A](n: Int, xs: List[A]): (List[A], List[A]) =
    xs.splitAt(n) // or (xs.take(n),xs.drop(n))

  //ok, that was too easy, let's try recursion
  def splitRec[A](n: Int, xs: List[A]): (List[A], List[A]) =
    (n, xs) match {
      case (0, _) => (Nil, xs)
      case (_, y :: ys) => {
        val rec = splitRec(n - 1, ys)
        (y :: rec._1, rec._2)
      }
      case (_, Nil) => (xs, Nil)
    }

  //P18
  def slice[A](s: Int, e: Int, xs: List[A]): List[A] =
    xs.slice(s, e) // or xs.drop(s).take(e-s)

  //with recursion
  def sliceRec[A](s: Int, e: Int, xs: List[A]): List[A] =
    (s, e, xs) match {
      case (0, 0, xs) => Nil
      case (0, _, y :: ys) => y :: sliceRec(0, e - 1, ys)
      case (_, _, y :: ys) => sliceRec(s - 1, e - 1, ys)
    }

  //P19
  def rotate[A](n: Int, xs: List[A]): List[A] = {
    val s = split((if (n > 0) n else n + xs.length), xs)
    s._2 ::: s._1
  }

  //P20
  def removeAt[A](n: Int, xs: List[A]): (List[A], A) = {
    val (heads, tails) = split(n, xs)
    (heads ::: tails.tail, tails.head)
  }

  //P21
  def insertAt[A](e: A, n: Int, xs: List[A]): List[A] = {
    val (heads, tails) = split(n, xs)
    heads ::: e :: tails
  }
  //with recursion
  def insertRecAt[A](e: A, n: Int, xs: List[A]): List[A] =
    (n, xs) match {
      case (0, ys) => e :: ys
      case (_, y :: ys) => y :: insertRecAt(e, n - 1, ys)
    }

  //P22
  def range[A](s: Int, e: Int): List[Int] = (s to e).toList

  //I don't think is the purpose of the exercise! Again, let's try recursion
  def rangeRec(s: Int, e: Int): List[Int] = if (e - s == 0) e :: Nil else s :: rangeRec(s + 1, e)

  //recursion and pattern matching with guards
  //a little more readable
  def rangeRecPm(s: Int, e: Int): List[Int] = (e - s) match {
    case x if (x > 0) => s :: rangeRecPm(s + 1, e)
    case x if (x == 0) => e :: Nil
    case _ => error("Invalid range")
  }
}
[EDIT: fixed problem 20 ]

4/7/09

Spare change at the whole Static-vs-Dynamic thingy


(NOTE: I'm a software developer, I have a blog, clearly I MUST write about static-vs-dynamic ... I guess soon I'll be writing a monads tutorial)

With all the fuss about Twitter migrating (the back-end) from Ruby to Scala (w00t!), the whole static-vs-dynamic debate has been re-ignited.
As a disclaimer, I'm in the static typing "camp". I've tried Ruby but didn't spark anything. In "dynamic languages", I have more experience with JavaScript (and for the record, I think is awesome: a true underdog of programming languages).
While I can appreciate the freedom and speed of development of dynamic languages, and I think is a matter of personal styles than about which one is better ("choose your own poison"), I think static typing suits better my frame of mind while creating software.
Anyhow, I felt something was missing in the debate and Twitter's use of "kind_of?" points to one of the reasons for static typing I been trying to articulate for a while.
(First and foremost: if you're going to complain "static typing forces me to add a lot of boilerplate and cruft", look into Haskell, ML, Scala, or F# and then come back or you'll force me to do evil things to cute creatures. And if you want to learn how a type system can be used to PROVE that a program is correct, look into Coq)

Types reduces the possible combinations between components
Any software program can be seen as a system of interconnected elements (modules/functions/objects, etc.), by adding type information you're restricting the ways those elements can connect to each other and the possible execution paths of the system. By doing that, you're loosing some of the valid combinations, you're also trimming many invalid ones.
The argument is with good unit tests you can check for the same things, but you have to actually write the code for that. While you should have unit tests for your module, without type restrictions, you have to write and test more execution paths. Moreover, writing the test, executing it and analyzing the result are separate steps, where your brain has to switch contexts.

Types as a Poka-Yoke
There's a lot of influence of Lean Manufacturing in software development (all the "Agile" stuff ), and from that perspective, having more restrictions on how you can use the available components acts like a poka-yoke mechanism: "a behavior-shaping constraint, or a method of preventing errors by putting limits on how an operation can be performed in order to force the correct completion of the operation". The same Lean / Total Quality Management recommends catching defects as early as possible and not use testing as a product quality measure. How more agile can you be when you don't have to write and run test to achieve a basic level of integration quality?

Types as (kind-of) contracts
By using static typing you get self-documenting self-enforcing operation contracts (for a price)
. I believe the larger and more complex the system, the more static typing can help than hinder your work.
NASA could have saved some money if they were able to write:

class MarsObiter {
def setThrust(v:Thrust[MetricUnits])= ...

There's no way you can use a Thrust[ImperialUnits] instead. (For extra points, you can define an implicit conversion in Scala :D )
But even if you have a basic type system like Java, don't just suffer it, use it at your advantage, create the types that can help you to write better code.
Check Stephan's excellent post on what do you loose if you use only primitive types with no semantic meaning (or no types at all)

Enough!
But enough babbling, I can show some examples using the "lowly" Java language:
Suppose we have a method to book a shipment for a customer and a container on a specific date.
Let's start without any typing information:


public bookShipment(customerId, containerId, shipmentDate){...


Totally valid, but... is "1234-321" a valid customerId? can I use a string as shipmentDate? in which format? What I get back?
Let's improve things a little by adding some basic typing information:


public boolean bookShipment(int customerId, int containerId, Date shipmentDate){...


Well, now I now that "X123Z" is not a valid customer or that "MRSK0023" is not a valid container, the date must be a proper date object, and it doesn't take a PhD to infer that will return true if the booking is successful.
But still, nothing prevents me to swap customerId with containerId and get a nasty but subtle bug. Wouldn't be nice if the compiler can prevent that? Well, it can if you don't use primitives and use more domain meaningful types, giving you a DDD flavor (and that's a win-win situation)


public boolean bookShipment(Customer customer, Container container, Date time){...


By examining the signature we know we can't pass a Container when a Customer is expected, and the method reflects better the domain of the application and tries to move towards "an ubiquitous language". But we can improve that:


public bookShipment(customer, container, shipmentDate) { ...


Here Hindley-Milner type inference takes care of identifying the input and output paremeters. No need to declare a thing and still type safe!
(although for documentation/readability purposes, I prefer explicit type declarations, and seems that the Haskell community agrees... that's why I don't mind typing the types of methods in Scala)



The whole point about all this? Go back and get things done, use whatever suites you best and don't waste your time reading blogs and stuff ;-)
If you excuse me, I need to step down from my tittle soapbox and go to do some coding...

4/1/09