Derek Wyatt's Blog

I’ve recently been devouring Learn You a Haskell for Great Good. I’ve been meaning to do it for ages, but a recent post by Debasish Ghosh pushed me to go through it cover to cover… I’m almost there :)

I was wrestling over the complexities of applying the sequence function to a list of functions. More succinctly, I was confused on the mechanics of how this worked:

ghci> sequence [(> 4), (< 10), odd] 7
[True, True, True]

To figure it out, all you have to do is reduce it, and then reduce it, and then reduce it some more. Let’s do that.

First, sequence is defined as (I’m using the definition of sequenceA from LYAH, as opposed to the definition of sequence from the Haskell API):

sequence :: (Applicative f) => [f a] -> f [a]
sequence = foldr (liftA2 (:)) (pure [])

And the definition of the Applicative Functor instance for functions is:

instance :: Functor ((->) r) where
    pure x = (\_ -> x)
    f <*> g = (\x -> f x (g x))

Now, let’s expand (note, I’m not going into nauseating detail here, and assume you’ve gone part of the way thus far):

sequence [(> 4), (< 10), odd]
-- becomes
foldr (liftA2 (:)) (pure []) [(> 4), (< 10), odd]
-- which becomes, due to the definition of liftA2
((:) . (> 4)) <*> (((:) . (< 10)) <*> (((:) . odd) <*> (pure [])))

Ok, so we’ve expanded the foldr and now we can expand the <*> and the pure []:

(\x -> ((:) . (> 4)) x (
    \x -> ((:) . (< 10)) x (
        \x -> ((:) . odd) x ((\_ -> []) x)) x) x)

Ok, that’s a bit rough to read… the key to it is noting how the 'x' gets propagated. Let’s take another look:

When we pass in the 7 it gets propagated to all of the little x‘s, and all of those little x‘s get passed to their composed functions, and each of those results in a new element on the list:

(\x -> ((:) . odd) x ((\_ -> []) x)) 7
-- reduces to
((:) . odd) 7 (\_ -> []) 7)
-- which reduces to
(: True [])
-- which becomes
[True]

-- Now, we use that to reduce the next level up
((:) . (< 10) 7) [True]
-- which becomes
(: True [True])
-- which becomes
[True, True]

-- And now our last level
((:) . (> 4) 7) [True, True]
-- which becomes
(: True [True, True])
-- which becomes
[True, True, True]

Ah, that’s better… now that I ‘get it’, I can move on.

Cheers!

A couple of people pointed out that my posting about why Monads are so awesome left a bit too much to the imagination. I tossed in an update that should make it less mysterious about what the heck I’m talking about.

Update: In the comments below, Alex is trying to educate me on something… I’m still not entirely sure what he’s on about but it’s been keeping me thinking about this post. I’ve modified it a bit here and there to try and be more correct. Essentially, I think I’ve been attributing too much to Monads where only part of what I like is attributed to them where the other part is attributed to partial functions (or function composition).

Ok, I’m no Monad expert by any stretch of the imagination… seriously. But, I did something today that has me so jazzed about Monads, partial functions and Scala in general, that I just gotta share.

So my task was to take some JSON and convert it to a structure of my own classes, but still really general – i.e. we’re not talking about “real” marshalling here.

So I took a simple approach, and used the Scala Library’s JSON Module. I had to deal with type-casting, defaulting of values, and constraint checking (i.e. field X must be defined). The code to do all of this is so simple and so awesome that it’s just hard to believe. Now, it’s not perfect… I’ll shore it up over the next while as need requires… but it’s passing all of my tests pretty nicely right now.

I want to convert the following JSON:

{
  "vendor"  : "Whoever", // required
  "colour"  : "blue",    // default to "None"
  "widgets" :            // default to Empty list of strings
  [
    {
      "name"    : "One",   // required
      "flavour" : "Lime"   // default to Strawberry
    },
    {
      "name"    : "Two",   // required
      "flavour" : "Banana" // default to Strawberry
    }
  ]
}

to the following concrete Scala:

case class Widget(name: String, flavour: String)
case class Contract(vendor: String, colour: String, widgets: List[Widget])
Contract("Whoever", "blue", List(Widget("One", "Lime"),
                                 Widget("Two", "Banana")))

I used a Pattern Matching example for this sort of thing from an awesome StackOverflow post as a starter and then fleshed it out to meet my requirements. Here it is:

// Types we need
case class Widget(name: String, flavour: String)
case class Contract(vendor: String, colour: String, widgets: List[Widget])

object Contract {
  // The class caster that came from the StackOverflow page
  // Yeah, this can throw exceptions... I don't care about
  // those for this example
  class ClassCaster[T] {
    def unapply(a: Any): Option[T] = Some(a.asInstanceOf[T])
  }

  // Concrete instances of the casters for pattern matching
  object AsMap extends ClassCaster[Map[String, Any]]
  object AsList extends ClassCaster[List[Any]]
  object AsString extends ClassCaster[String]

  // It can happen
  case class ContractException(message: String) extends Exception(message)

  // Returns an Either that is a hell of a lot more deterministic than
  // throwing exceptions around
  def fromJSON(json: String): Either[ContractException, Contract] = {
    // Helps us get rid of boilerplate
    def error[T](prefix: String): Option[T] =
      throw ContractException("%s must be specified".format(prefix))

    // Catch the exceptions and turn them into Left() instances
    try {
      val parsed = JSON.parseFull(json)
      if (parsed.isEmpty) throw ContractException("Unable to parse JSON.")

      // Here comes the monad / partial function love...
      val contract = for {
        Some(AsMap(map))  < - List(parsed)
        AsString(vendor)  <- map get "vendor" orElse error("vendor")
        AsString(colour)  <- map get "colour" orElse Some("None")
        AsList(widgets)   <- map get "widgets"
      } yield Contract(vendor, colour, for {
          AsMap(widget)     <- widgets
          AsString(name)    <- widget get "name" orElse error("name")
          AsString(flavour) <- widget get "flavour" orElse Some("Strawberry")
        } yield Widget(name, flavour)
      )
      Right(contract.head)
    } catch {
      case e: ContractException =>
        Left(e)
      case e =>
        Left(ContractException(e.getMessage))
    }
  }
}

It’s very impressive what this code actually handles when you start digging into it. I’m sure you can easily think about what it would be like to code this in Java (or spaghetti monster forbid C++) and know that it’s going to be a lot more verbose and probably a lot less reliable.

UPDATE: One of the key reasons why the above is so cool is this:

<- map get "colour" orElse Some("None")
<- widget get "name" orElse error("name")

By using a generator syntax (<-) and the get function on Map we get to work at a higher abstraction that allows us to chain the decision making process rather than what the imperative approach would demand of us. It’s the monadic and compositional nature of Option that allows us to do this. Consider:

String colour = map.get("colour");
if (colour == null)
  colour = "None";

String name = widget.get("name");
if (name == null)
  error("name");

I’m going to editorialise (I mean, this is my blog after all) and point out the following problems:

• It’s unclear. Sure, if you’ve seen it a million times (and let’s face, you have… we all have) you know exactly what this “means” but that’s not because its meaning is clear.
• It’s not syntactically atomic. Some nasty merge, or some careless programmer can easily insert something between lines 1 and 2 that uses colour.
• It’s repetitive in a bad way (is there a good way?). That pattern is going to be copy-pasted over and over again. How many times do you see “colour” in there? Yeah… three. So if I copy-paste that and forget to change the third one, you get this:

String flavour = widget.get("flavour");
if (flavour == null)
  colour = "None";

GHACK!

We need to program at a higher level.

I saw a post on Supuser.com that asked about how to go “back” to a directory rather than “up”. The right answer was “cd -“, of course, but I’ve been using a home-grown tool to do this for years and it works really well.

It started out as a Korn Shell so there are some remnants of that in it, but it does work for Bash.

It does the usual thing of replacing the ‘cd‘ built-in command with a function by aliasing it away. Every time you change directories, it saves the last place on the stack (up to a max of 15). You can look at the directory history and switch to any of them based on their number and also a regular expression.

This sort of functionality, whether you use mine or someone else’s or build your own, is vital to efficient command line kung-fu. How the hell have you been surviving this long without it???

Here’s the Gist of the code that you can grab.

• cd – You know what this does. And, yes, both cd - and cd {pat} {subst} should also work just fine.
• ss – Short for “show stack”.
• csd – Short for “change to stacked directory”. This is the fun one that I’ll show in an example below.

Here’s how you use it (I’ll leave it to you to read what I’m doing and figure out how you can use it):

--(/home/dwyatt/scala/scala/src/library/scala/collection/generic)--------------------------------------
--> ss
1) /home/dwyatt/scala/scala/src/library/scala
2) /home/dwyatt/scala/scala/src/library/scala/concurrent
3) /home/dwyatt/scala/scala/src/library/scala/collection/mutable
4) /home/dwyatt/scala/scala/src/library/scala/collection/immutable
5) /home/dwyatt/scala/scala
6) /home/dwyatt/scala
7) /home/dwyatt
--(/home/dwyatt/scala/scala/src/library/scala/collection/generic)--------------------------------------
--> csd 4
--(/home/dwyatt/scala/scala/src/library/scala/collection/immutable)------------------------------------
--> ss
1) /home/dwyatt/scala/scala/src/library/scala/collection/generic
2) /home/dwyatt/scala/scala/src/library/scala
3) /home/dwyatt/scala/scala/src/library/scala/concurrent
4) /home/dwyatt/scala/scala/src/library/scala/collection/mutable
5) /home/dwyatt/scala/scala
6) /home/dwyatt/scala
7) /home/dwyatt
--(/home/dwyatt/scala/scala/src/library/scala/collection/immutable)------------------------------------
--> csd ent$
--(/home/dwyatt/scala/scala/src/library/scala/concurrent)----------------------------------------------
--> ss
1) /home/dwyatt/scala/scala/src/library/scala/collection/immutable
2) /home/dwyatt/scala/scala/src/library/scala/collection/generic
3) /home/dwyatt/scala/scala/src/library/scala
4) /home/dwyatt/scala/scala/src/library/scala/collection/mutable
5) /home/dwyatt/scala/scala
6) /home/dwyatt/scala
7) /home/dwyatt
--(/home/dwyatt/scala/scala/src/library/scala/concurrent)----------------------------------------------
--> csd 5
--(/home/dwyatt/scala/scala)---------------------------------------------------------------------------
--> ss
1) /home/dwyatt/scala/scala/src/library/scala/concurrent
2) /home/dwyatt/scala/scala/src/library/scala/collection/immutable
3) /home/dwyatt/scala/scala/src/library/scala/collection/generic
4) /home/dwyatt/scala/scala/src/library/scala
5) /home/dwyatt/scala/scala/src/library/scala/collection/mutable
6) /home/dwyatt/scala
7) /home/dwyatt
--(/home/dwyatt/scala/scala)---------------------------------------------------------------------------
--> cd ~
--(/home/dwyatt)--------------------------------------------------------------------------------------------
--> cd -
--(/home/dwyatt/scala/scala)---------------------------------------------------------------------------
-->

I took a look at Scala Streams tonight (or was that last night? When am I posting this?) and thought I’d share what I learned from Literate Programs and the Scala source code.

Streams

For the uninitiated, a Stream in Scala helps realize one of the fundamental concepts of Functional Programming, that of laziness. In essence, a Stream as infinite – think of a collection that just goes on and on and on and on and on and on. It would be asinine to construct the entire collection before ever using it as that would only ensure that you never used it. A Stream is evaluated on an as-needed basis and only up to the point that you need it.

The Delicious, Delicious Code…

Let’s illustrate using good ol’ Fibonacci Numbers. We’ll construct a Stream recursively because that’s more fun and it gives more meat to discuss. (This example comes straight from the Literate Programs website but I’m hoping to explain it in a bit more depth, and not get it too wrong in the process)

import scala.math.BigInt
lazy val fibs: Stream[BigInt] = BigInt(0) #::
                                BigInt(1) #::
                                fibs.zip(fibs.tail).map { n => n._1 + n._2 }

(Note: The above must all be on one line or the compiler is going to have a tough time pimping it out)

Sweet and delicious, no?

Dissection

Let’s break it down:

lazy

Strictly speaking, this isn’t needed, but why not be as lazy as you can possibly be? For the truly uninitiated, this ensures that the fibs value is not evaluated until it’s actually used.

val fibs: Stream[BigInt]

“What the hell is this? I thought Scala inferred types!”, I hear you scream. Scala does infer types but we’re defining a recursive value here and Scala needs to understand that the recursive call is a recursive call on a Stream as opposed to a String or some other completely unrelated type.

BigInt(0) #:: BigInt(1) #::

The Fibonacci series starts with 0 and 1 so we shove those in right here. But what’s this #:: stuff? Here’s our first real magical point and even the somewhat initiated may be scratching their heads at this one.

If you look at the Stream api you won’t find the #:: member function anywhere, and indeed you shouldn’t as we’re not working with a Stream right now, but a BigInt.

So with that realization in place, we must also recognize that methods ending in : are right associative. What this means is that the object we’re calling the #:: method on is actually the Stream object that is returned from the map command at the end of the call (we’ll get back to that, just hang on). Remember how we had to declare that fibs was a Stream instead of letting Scala infer it? Well, that’s (one of the reasons) why we need to do that.

Now we know that the method is being called on the Stream but when we look at the api for Stream, again we don’t see that method call. So where is it?

This method gets pimped on through the implicit def consWrapper[A](stream: => Stream): ConsWrapper[A] method defined on the Stream companion object. Scala will resolve the lack of a #:: method on Stream by finding an implicit conversion to a type that does have that method, and this is the ConsWrapper. The result of that method is to return a new Stream.

Ok, but how’s that of any use? The conversion to ConsWrapper is going to kill us due to the fact that it’s going to call the recursive function… or is it? Well, of course it’s not. If you look at the paramter to the ConsWrapper you’ll see why this doesn’t cause immediate recursion: new ConsWrapper(tl: => Stream[A]). That’s a by-name parameter. This means that it’s not invoked until it’s used.

Wow, that’s a lot of stuff for one bullet point.

fibs.zip(fibs.tail)

Go look at the Stream api again, specifically the zip. I’ll wait.

You didn’t read it, did you? Fine… on your own head, be it.

The size of the Stream returned by tail is one-less than the size of the Stream itself. This means that the zipped result is going to be the size of the Stream returned by tail, not the size of the Stream itself. So, in the initial case (where the Stream is Stream(0, 1, [Stream]), the zipped result is actually Stream((0, 1), ([Stream])) because the tail, of one element, is paired with the head.

Stream.zip creates a Cons cell containing (this.head, that.head) as the Cons head and (this.tail zip that.tail) as the Cons tail but as a Stream of (A1, B) so we’re not evaluating it now – we’ll evaluate it when it gets called.

map { n => n._1 + n._2 }

Hmmm… I hesitate to say “duh?” but it really does seem appropriate to do so. I mean, if you’ve made it this far, you know what this does.

Use it

Ok, so what happens when we evaluate it? Let’s get the first 20 numbers:

scala> fibs take 20 foreach println
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
scala>

That looks right to me.

WTF?

Some of you may still be scratching your heads because I wasn’t terribly clear on how this actually works. How is it that each number is evaluated as needed? Well, first let’s prove that it is so. I’m going to modify the code slightly.

import scala.math.BigInt
lazy val fibs: Stream[BigInt] =
    BigInt(0) #::
    BigInt(1) #::
    fibs.zip(fibs.tail).map(n => {
      println("Evaluating: %s -> %s".format(n._1, n._2))
      n._1 + n._2
    })

Now let’s take the first 5:

scala> fibs take 5 foreach println
0
1
Evaluating: 0 -> 1
1
Evaluating: 1 -> 1
2
Evaluating: 1 -> 2
3
scala>

And let’s take them again…

scala> fibs take 5 foreach println
0
1
1
2
3
scala>

And let’s take the first 7…

scala> fibs take 7 foreach println
0
1
1
2
3
Evaluating: 2 -> 3
5
Evaluating: 3 -> 5
8
scala>

Ok, so it works; things are properly evaluated in a lazy manner. But how?

Why…

The culprit behind this magic appears to be the interplay between the Cons class, the StreamIterator class and the LazyCell class:

final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A]
// Note that the head is a value of type A and the tail is a by-name Stream

final class StreamIterator[+A](self: Stream[A]) extends Iterator[A] {
  class LazyCell(st: => Stream[A]) {
    // Note the laziness
    lazy val v = st
  }
  private var these = new LazyCell(self)
  def next: A =
    if (isEmpty) Iterator.empty.next
    else {
      // Evaluate the laziness
      val cur = these.v
      // And the concrete value of type A
      val result = cur.head
      // Assign the next lazy cell to be the Stream in the tail
      these = new LazyCell(cur.tail)
      result
    }
}

Couple that together with the recursively defined zip we saw earlier, and you’ve got your lazy Stream of Fibonacci numbers.

I love this stuff…

Note: This is C++0x stuff and it’s really just an investigation into some of the more obvious parts of it, including the auto keyword and lambda functions as well as working with higher kinded types (signified in C++ as template-template parameters).

I’ve been doing a lot of Scala recently and have thus become quite spoiled by its awesomeness. It’s made me look at C++ again with a different eye – a more functional eye. I’ve been doing C++ for so long, that I forget about that functional style of programming, and I also forget just how bad C++ is at functional programming – when you’re a multi-paradigm language, it’s hard to be great at all the paradigms simultaneously.

So, I took a stab at writing a more “functional” map function. C++ provides the transform function template in the functional header file but I find it lacking because you have to pre-create the container that will be mapped-to. This is an attempt at creating that inside the map function.

First, we’ll need some header files:

#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <functional>
#include <algorithm>
#include <iterator>
#include <boost/lexical_cast.hpp>

And now we can define the function.

template <typename InType,
  template <typename U, typename alloc = allocator<U>>
            class InContainer,
  template <typename V, typename alloc = allocator<V>>
            class OutContainer = InContainer,
  typename OutType = InType>
OutContainer<OutType> mapf(const InContainer<InType>& input,
                           function<OutType(const InType&)> func)
{
  OutContainer<OutType> output;
  output.resize(input.size());
  transform(input.begin(), input.end(), output.begin(), func);
  return output;
}

The idea is that the output container may be a different type of container from the input container and the output type may also be of a different type from the input type.

A really simple usage of this could be:

vector<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto v2 = mapf(v1, function<int(const int&)>([](const int& i) { return i + 9; }));

The reason it’s simple is that all it does is just take a vector of ints and map it to a vector of ints. That’s nothing flashy.

It’s more interesting if you do something like this:

auto v3 = mapf<float, vector, list>(
            mapf(
              mapf(v1, function<int(const int&)>([](const int& i) { return i + 9; })),
              function<float(const int&)>([](const int& i) {
                return i * 3.1415;
              })),
            function<string(const float&)>([](const float& i) {
              return string("\"" + lexical_cast<string>(i) + "\"");
            }));

This is the standard functional “chaining” we see with more fluid, immutable data structures. Futher, it is actually returning a list<string> instead of a vector<string>. In Scala (you could do something similar in Ruby or many other languages) this would be:

v1.map(_ + 9).map(_ * 3.1415).map(_.toString).toList

Now, I’m not exactly happy with what we’ve got here. It’s not that I can’t pimp the int and float types and thus make it more fluid (although that would be nice). It’s more that the template function specification is hideous. In order to actually use different output container types, you must specify too much in the template parameter list.

auto l1 = mapf<int, vector, list>(v1,
  function<int(const int&)>([](const int& i) { return i + 2; }));
copy(l1.begin(), l1.end(), ostream_iterator<int>(cout, "\n"));

Ideally we’d like to simply specify something like mapf<list>(...) instead. I need to work on this and see if I can come up with something nicer. Perhaps it’s as simple as wrapping it up with another function or a template class… when I get more time.

I’ve put my Vim configuration on GitHub now. Have a gander at http://github.com/derekwyatt/vim-config

The Vim ‘indent’ script for Scala that I’ve been working on is now starting to take some decent shape. If you’re a Scala coder and are working in Vim, I can now actually recommend this script :). It’s actually the least complicated one I’ve written that achieves this level of functionality; I’ve had a few kicks at this particular can and one of them in particular was way complicated and also slow.

Go grab it from Github.

Posted with WordPress for BlackBerry.

I found some time to update the indent file for Scala recently. It’s getting better and more complicated, unfortunately. Please feel free to fork it and make changes/fixes… I hate writing this thing :)

Grab it from my vim-scala repository on github.

Posted with WordPress for BlackBerry.

So, a little over a month ago, I changed departments where I work – I used to work in the Enterprise Software group and have moved to the System Architecture / Research group. There are some great things that go with this:

1. I get to work with Vim more than I used to because I now code a lot more than I used to.
2. I’ve effectively deleted Windows entirely and replaced it with Ubuntu (YAY!)
3. I’m getting a chance to deeply investigate Scala and Akka, which is a real treat! My research may not go anywhere, but the research itself is incredibly useful, I think – Scala and Akka are absolutely fantastic projects.

Once I figure out the right path to take in order to get some changes into the Scala repository for Vim, I’ll do that, but for the moment I’m just having a great time banging away at the docs and shoving things in my own repository.

What I’ve got at the moment is a 4000+ line reference file (in Vim help format, of course) that I’ve put together to help me better understand Scala, and give me a spot to put some critical information and tips / tricks I find as I go. I’ve also fixed up the indent file a bit and plan to enhance the syntax file when I get a chance too.

Because of Scala’s flexibility and terseness I find it a bit difficult to create code snippets for it, but I may do that in the future as well.

If you’re interested, head over to my vim-scala repository on GitHub and clone it down to your vim configuration.