I hinted at LambdaJam Australia back in my 2012 Highlights post and the dates are fast approaching so I thought appropriate to blog about it once more.

YOW! LambdaJam is a conference targeted at intermediate and advanced functional programmers and is organised in talks, jams and workshops.

• Talks are the traditional format and are 30 minutes long;
• Workshops aim to introduce a specific subjects to attendees in great detail and are up to two hours long;
• Jams are hands-on sessions. Participants will be guided through pre-defined problems around a given subject/technology and encouraged to work through the solutions either by themselves or ideally as small groups. Jams are also 2 hours long;

Sounds pretty amazing, doesn’t it?

If you’re still not convinced, check out the program.

The conference will run for 2 days, May 16-17, in Brisbane. Tickets are on sale.

Clojure

Besides the conference itself, Clojure/core will be giving an Intro to Clojure workshop in Sydney, Melbourne and Brisbane. It’s a great opportunity to learn from the language maintainers.

If you’re attending the conference already, you’re in luck because there is a 20% off discount on the link above if you attend both the conference and the workshop.

In case you’d like to attend the workshops only, you can buy individual tickets for Sydney, Melbourne and Brisbane.

Scala

Tony Morris will also be delivering a Functional Programming in Scala workshop in Brisbane and 20% off combo tickets can be bought from the EventBrite page for LambdaJam.

See you there

Got tickets yet? No? What are you waiting for?

Last week while attending Clojure/West in Portland I came across a paper called Why calculating is better than scheming. In a nutshell, this paper is a critique to Abelson and Sussman’s classic textbook SICP - Structure and Interpretation of Computer Programs, used by MIT for many years to teach their introductory programming course.

If you haven’t read SICP, you should. It’s an amazing book. It uses Scheme, a dialect of Lisp, as the vehicle to present fundamental programming concepts.

Philip Wadler - the author of this particular paper - contrasts teaching in Scheme to teaching using KRC and Miranda, pointing out four major features he considers important and lacking in Scheme. They are:

• Pattern matching
• A syntax close to traditional mathematical notation
• A static type discipline and user-defined types
• Lazy Evaluation

Note: KRC influenced Miranda which in turn influenced Haskell. Their syntax is similiar, so where Wadler used Miranda code snippets in the paper, I’ll be using Haskell in this post.

As an aside, although the paper talks specifically of Scheme, the term Lisp is used quite loosely and could lead the not-so-careful reader to be misled regarding a whole family of languages. Lisps have come a long way and modern dialects - of which I’ll be focusing on Clojure - address many of the concerns raised by Wadler.

Let us begin.

Pattern Matching

Here Clojure, and most - all? - Lisps, are out of luck.

The example used in the paper is that of summing all integers in a list. First in Haskell:

1
2

sum []   = 0
sum x:xs = x + sum xs

Now in Clojure:

1
2
3
4

(defn sum [coll]
  (if (empty? coll)
      0
      (+ (first coll) (sum (rest coll)))))

The question here is this: Which snippet is easier to read/reason about? the Haskell code!

I must confess that I, too, miss pattern matching sometimes. However we can still improve our Clojure version to read nicer on the eyes by using destructuring:

1
2
3
4

(defn sum [[first & rest :as coll]]
  (if (empty? coll)
      0
      (+ first (sum rest))))

And that’s pretty much it. Without proper pattern matching, we can’t get much better than that.

In addition to the Haskell snippet being easier to read, it’s also easier to prove correct by structural induction, as demonstrated in Wadler’s paper.

Note: core.match adds support to pattern matching in Clojure. At the time of this writing, it’s considered “alpha quality”

Data structures

The paper continues to discuss exercise 2-27 from the SICP, where the reader has to write code to represent a binary mobile, which consists of a left and right branch with each branch being a rod of certain length, from which hangs either a weight or another binary mobile.

Translating the Scheme example to Clojure, such a structure is represented using lists, like so:

1
2
3
4
5

(defn make-mobile [left right]
  (list left right))
  
(defn make-branch [length structure]
  (list length structure))

Wadler then contrasts this with the equivalent Miranda code, translated below to Haskell, taking advantage of algebraic data types:

1
2

data Structure = Weight Int | Mobile Branch Branch
data Branch = Branch Int Structure

The first claim is that the Haskell/Miranda data type declaration makes it clearer what the data structure looks like, which is fair.

Also, the compiler can catch errors early on.

However, when writing idiomatic Clojure code, here’s how I’d actually create this structure:

1
2
3
4
5

(defn make-mobile [left right]
  {:left left :right right})
  
(defn make-branch [length structure]
  {:length length :structure structure})

Granted, it’s still not as clear and the compiler can’t validate the shape of our data structure.

This is however cleaner than the previous version and drives home the point that Clojure isn’t limited to lists, having literals for other data types such as the hash maps used in this example.

The second part of this claim is that through custom data types and pattern mathing, extracting values from those structures becomes simpler:

1
2
3
4

totalWeight (Weight w) = w
totalWeight (Mobile l r) = totalWeightBranch l + totalWeightBranch r

totalWeightBranch(Branch d s) = totalWeight s

Once again Clojure can improve things by taking advantage of its builtin data structures and destructuring:

1
2
3
4
5
6
7
8

(defn total-weight [{:keys [left right] :as structure}]
  (if (number? structure)
      structure
      (+ (total-weight-branch left)
         (total-weight-branch right))))
      
(defn total-weight-branch [{structure :structure}]
  (total-weight structure))     

For a language with no pattern matching nor algebraic data types, this snippet is clear, concise and elegant - and a real improvement over the Scheme version discussed in the paper - which was essentially handicapped by the use of lists to simulate ‘structs’.

As far as Clojure goes, this claim ends here: the next point in the paper, about changing from using list to using cons, is rendered moot since we’re using hash maps to represent our mobiles.

Lisp lists are not self-escaping

Creating lists in Clojure goes like this:

1
2
3

(list (list 1 2) nil) ;; ((1 2) nil)

'((1 2) nil) ;; ((1 2) nil)

Both statements above are equivalent, with the second one being clearly more concise.

The claim here is that the fact that you need to either use the list function or quote the form is cumbersome and can be confusing to beginners.

Clojure solves this by providing literals to another data structure - vectors:

1

[[1 2] nil]

Simple and concise - in fact, in idiomatic Clojure code, you’ll rarely see quoted lists where a vector will do.

This is possible because both lists and vectors conform to a higher level abstraction called a Seq, in terms of which most list operations are defined.

This eliminates the two following points mentioned in the paper as it allows a beginner to defer his/her understanding of quoted forms to more advanced lessons/usages.

Programs that Manipulate Programs - the interpreter example

Here Wadler shows a simple grammar for an interpreter in both Miranda and Scheme.

He claims that since Haskell/Miranda have free data types, representing such grammar becomes simpler:

1
2
3
4
5
6

data Term = Var [Char]
          | Lambda Var Term
          | Apply Term Term
          | Closure Env Var Term
type Env = [(Var, Term)]
type Var = [Char]

This is true in that one can easily scan the snippet above and deduce quickly what Term looks like.

Then, by using pattern matching, eval could be implemented like so:

1
2
3
4
5

eval e (Var v) = lookup e v
eval e (Lambda v t) = Closure e v t
eval e (Apply t0 t1) = apply (eval e t0) (eval e t1)

...

I do believe this makes Haskell an excellent choice for writing interpreters and compilers.

However, the flip side is that entering such terms in Haskell is cumbersome. Consider the term below:

(λx.(x x)) (λx.(x x))

This is how to represent this term using the grammar defined above:

1
2

(apply (Lambda "x" (apply (Var "x") (Var "x")))
       (Lambda "x" (apply (Var "x") (Var "x"))))

The strength in Lisp lies elsewhere. Since we have quoted forms, entering a similar term is a lot less verbose and closer to its intended representation:

1

'((lambda [x] (x x)) (lambda [x] (x x)))

This is, of course, at the expense of making eval a more complicated function:

1
2
3
4
5
6
7
8
9
10

(defn eval [e t]
  (cond (variable? t)
        (lookup e (variable-name t))
        (lambda? t)
        (make-closure e (lambda-var t) (lambda-body t))
        (apply? t)
        (apply (eval e (apply-operator t))
               (eval e (apply-operand t)))))

...

The paper leaves out an important advantage of Lisps though:

Because we can write code for our made up language directly in its (almost)abstract syntax tree form, Lisps are the ideal choice when writing Internal Domain Specific Languages.

Lazy Evaluation

Lists

Haskell and Miranda are lazy languages and that yields a lot of power. This claim is more specific to the use of lazy lists - or sequences, streams - and starts off with a snippet that calculates the sum of squares of all odd numbers from 1 up to 100:

1

sum [ i*i | i <- [1..100], odd i ]

What follows in the paper is a not-so-clear snippet of equivalent functionality using Scheme streams.

Clojure features lazy sequences and list comprehensions, making the above Haskell example trivial to write:

1

(sum (for [i (range 100) :when (odd? i)] (* i i)))

If you’re following at home with the original paper you’ll see this is more readable and elegant than the equivalent Scheme example.

Another - also idiomatic - way to write the same expression is by using a combination of map/filter:

1

(sum (map #(* % %) (filter odd? (range 100))))

Deciding which one is clearer is left as an exercise to the reader.

Special forms and lazy evaluation

In this section, Wadler brings another example from SICP where the reader wishes to implement his/her own if form.

As we know, in order to implement our own version of if, we need to use macros. That is because in Lisps arguments to functions are eagerly evaluated.

One might implement it like this:

1
2
3

(defmacro my-if [pred then else]
  `(cond ~pred ~then
          :else ~else))

In Lazy languages, such as Haskell and Miranda, this problem doesn’t occur allowing such functions to be defined without the need for special and/or quoted forms:

1
2

myIf True  t e = t
myIf False t e = e

However this completely dismisses the power of macros which allow you to extend the language in ways no other language allows - as is extensively demonstrated in books such as On Lisp and Let Over Lambda.

As Guy Steele once put it: ”[…] If you give someone Lisp, he has any language he pleases”

Conclusion

Hopefully this post doesn’t come off as trying to invalidate Wadler’s paper - that is not my intention.

While I do think a few of the points discussed are only applicable to the domain in which his paper was written - teaching - they are still valid and worth understanding.

I do however expect to have given you a different perspective on it, showing the strengths of modern Lisps such as Clojure and how it approaches these issues - such as by using its rich set of data structures, literals and techniques such as destructuring.

Last year I started reading a book called Purely Functional Data Structures. It’s a fascinating book and if you’ve ever wondered how Clojure’s persistent data structures work, it’s mandatory reading.

However, all code samples in the book are written in ML - with Haskell versions in the end of the book. This means I got stuck in Chapter 3, where the ML snippets start.

I had no clue about Haskell’s - much less ML’s! - syntax and I was finding it very difficult to follow along. What I did notice is that their syntaxes are not so different from each other.

So I put the book down and read Learn You a Haskell For Great Good! with the hopes that learning more about haskell’s syntax - in particular, learning how to read its type signatures - would help me get going with Puretly Functional Data Structures.

Luckily, I was right - and I recommend you do the same if you’re not familiar with either of those languages. Learn You a Haskell For Great Good! is a great book and I got a lot out of it. My series on Monads is a product of reading it.

Enough background though.

The purpose of this post is two-fold: One is to share the github repository I created and that will contain the Clojure versions of the data structures in the book as well as most solutions to the exercises - or at least as many as my time-poor life allows me to implement.

The other is to walk you through some of the code and get a discussion going. Hopefully we will all learn something - as I certainly have when implementing these. Today, we’ll start with Leftist Heaps.

Leftist Heaps

Leftist Heaps - or trees - are a variant of binary heaps that can be used as priority queues. On top of the standard invariants of binary heaps, it obeys the leftist property:

• Every node has a rank, which is the distance from its right spine to the nearest leaf
• A node’s left child has a rank at least as large as its right child

In a nutshell, these are the operations we need to be able to perform on a leftist heap:

• insert a value into an existing heap
• merge two heaps
• find the minimum value in a heap
• delete the minimum value, returning a new heap

Since the book uses ML/Haskell, it starts with a data type definition for Heaps that exposes these and a couple of other auxiliary functions. I decided to take a stab at writing the solution using Clojure’s protocols and records:

1
2
3
4
5
6
7
8
9

(defprotocol Heap
  (is-empty?   [this])
  (insert      [this v])
  (merge       [this other])
  (rank        [this])
  (find-min    [this])
  (delete-min  [this]))

(defrecord LeftistHeap [rank value left right])

When implementing the algorithms the base case for the recursive solutions will involve dealing with nil values which at first seems like it wouldn’t be a problem. However, protocol functions dispatch on the type of its first argument so what happens if I call the function is-empty? on nil?

Luckily, Clojure allows us to extend a protocol to core types:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

(extend-protocol Heap
  nil
  (rank [_] 0)
  (merge [_ other] other)
  (is-empty? [_] true)

  LeftistHeap
  (is-empty? [this]
    (nil? this))

  (rank [this]
    (:rank this))

  (merge [{val-this :value left-this :left right-this :right :as this}
          {val-other :value left-other :left right-other :right :as other}]
    (cond
     (is-empty? other) this
     (<= val-this val-other) (ensure-leftist left-this
                                             (merge right-this other)
                                             val-this)
     :else (ensure-leftist left-other
                           (merge this right-other)
                           val-other)))

  (insert [this v]
    (merge (->LeftistHeap 1 v nil nil)
           this))

  (find-min [{v :value}] v)

  (delete-min [{left :left right :right}]
    (merge right left)))

Note how I extended a few of the protocol functions to the nil data type, allowing me to continue with this implementation with no nasty hacks.

There’s one last bit missing: a function that will ensure each heap retains the leftist property:

1
2
3
4
5
6
7

(defn ensure-leftist
 [this other v]
 (let [rank-this (rank this)
       rank-other (rank other)]
   (if (>= rank-this rank-other)
     (->LeftistHeap (inc rank-other) v this other)
     (->LeftistHeap (inc rank-this) v other this))))

The reason this function is isolated is that the Heap protocol defined above is fairly generic and could be used for defining other types of heaps - and I didn’t feel it warranted its own interface.

We can now play with it and create a new leftist heap:

1
2
3
4
5
6
7

(-> (->LeftistHeap 1 3 nil nil)
                   (insert 2)
                   (insert 7)
                   (insert 4)
                   (insert 10)
                   (insert 1)
                   (insert 20))

While I quite like this approach, I thought I’d also implement this solution using Clojure’s core data types - maps in this case - and no protocols. The code is shown below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

(defn mk-heap [rank value left right]
  {:rank rank :value value :left left :right right})

(defn heap-rank [heap]
  (if (nil? heap)
    0
    (:rank heap)))

(defn ensure-leftist-heap [value heap-a heap-b]
  (let [rank-a (heap-rank heap-a)
        rank-b (heap-rank heap-b)]
    (if (>= rank-a rank-b)
      (mk-heap (inc rank-b) value heap-a heap-b)
      (mk-heap (inc rank-a) value heap-b heap-a))))

(defn merge-heaps [{val-a :value left-a :left right-a :right :as heap-a}
                   {val-b :value left-b :left right-b :right :as heap-b}]
  (cond
   (nil? heap-a) heap-b
   (nil? heap-b) heap-a
   (<= val-a val-b) (ensure-leftist-heap val-a
                                         left-a
                                         (merge-heaps right-a heap-b))
   :else (ensure-leftist-heap val-b
                              left-b
                              (merge-heaps heap-a right-b))))

(defn heap-insert [value heap]
  (merge-heaps (mk-heap 1 value nil nil)
               heap))

(defn heap-find-min [{v :value}] v)

(defn heap-delete-min [{left :left right :right}]
  (merge-heaps right left))

Using it is equally simple:

1
2
3
4
5
6
7

(->> (mk-heap 1 3 nil nil)
                    (heap-insert 2)
                    (heap-insert 7)
                    (heap-insert 4)
                    (heap-insert 10)
                    (heap-insert 1)
                    (heap-insert 20))

That’s it for now.

As I implement more of the book’s code and exercises I’ll add them to the github repo - it also includes tests for all implementations.

Enjoy :)

Today I’m releasing bouncer, which was extracted from a project I’ve been working on.

It’s a validation library for Clojure apps and it lets you write code like this:

1
2
3
4
5

(def person {:name "Leo"})

(validate person
    :name required
    :age  [required number])

If you’d like to see more examples and a detailed guide check out the github repository. The README should get you started.

This post however isn’t only about announcing bouncer. It’s also about the motivation and implementation details behind it.

There are a couple of Clojure validation libraries already out there so why would I write a new one? Well…

• Writing Clojure is fun! (who knew? :P)

• Because I believe this problem can be solved more elegantly with the use of Monads

If you’ve been following me for a while, you’ll know that I spent most of 2012 deepening my knowledge about functional programming.

In that journey, the unavoidable subject of monads came about - and it was both interesting and enlightening enough that made me write a whole series of posts about it.

After learning what they are and then thinking about the validation problem for a while, I couldn’t help but notice that the problem had a lot in common with the State Monad.

In order to explain how the two relate, I’ll have to digress for a moment. It’ll all make sense in the end - or so I hope

Purity

In pure functional languages, such as Haskell, functions can’t have side effects. These include performing IO, changing global variables or launching missiles.

Because of that, functions in Haskell are pure: if you repeatedly call a function f with the same argument x over time you will always get the same result back.

Pure functions are not a feature of Haskell though. We, too, can write pure functions if we wish:

1
2

(defn double [x]
    (+ x x))

The function double above is pure. If we call it with 10, we can be sure the result will always be 20.

This leaves us with a question though: If we were to write our programs with pure functions only, how would we perform computations that need to carry state - state that needs to change over time - around?

A good example of such computation is generating random numbers.

Most programming languages provide generators capable of creating random numbers on demand. Using them is usually trivial. Here’s an example in Java:

1
2
3
4

Random gen = new Random();

gen.nextDouble(); // 0.0037635726242281065
gen.nextDouble(); // 0.15821091918430885

Impurity alert!

The function nextDouble above is obviously not pure. Multiple invocations of it with the same argument - in this case, none - returns different results.

nextDouble is keeping some sort of global state between function calls.

This is where the State Monad comes in. It allows such functions to remain pure.

The State Monad

The State Monad provides a way to abstract state from the function that needs to operate on it.

Sounds confusing? Hopefully an example will clear things up.

Let’s have a look at the clojure function rand:

1
2
3
4

(rand)
;; 0.04388682005715605
(rand)
;; 0.43057496371080517

rand suffers from the same problem as nextDouble we saw above. It keeps it’s own state that is shared across calls, therefore being an impure function.

Now let’s write a pure version of rand. We’ll call it pure-rand:

1
2
3
4
5
6
7
8
9
10

(def gen (java.util.Random.))

(defn pure-rand [g]
    [(.nextDouble g) g])

(pure-rand gen)
;; [0.5783608063218478 #<Random java.util.Random@7f30ab6>]

(pure-rand gen)
;; [0.9251968987499839 #<Random java.util.Random@7f30ab6>]

This is interesting. pure-rand now takes a generator as an argument and returns a two-element vector containing the random number itself - the result we’re actually interested in - and the generator that was passed in.

Recall however that the generator returned, albeit the same object, is in a new sate.

By re-writing the function like this, we’ve regained purity, as demonstrated below:

1
2
3
4
5

(pure-rand (java.util.Random. 100))
;; [0.7220096548596434 #<Random java.util.Random@bb14fe1>]

(pure-rand (java.util.Random. 100))
;; [0.7220096548596434 #<Random java.util.Random@bb14fe1>]

As you can see, as long as we provide the same generator - the same argument - we get the same result back.

If you’re wondering why I’m returning a two element vector from our little function, the answer lies in the State Monad implementation as found in the algo.monads library.

From its docstring:

State Monad: Monad describing stateful computations. The monadic values have the structure:

(fn [old-state] [result new-state]).

It expects a function that receives its old state and returns the result and the new state - these are called monadic values.

By designing the function to follow this contract, we can leverage the domonad macro - think of it as syntactic sugar for working with monads:

1
2
3
4
5
6
7
8
9
10
11

(require '[clojure.algo.monads :as m])

((m/domonad m/state-m
    [a pure-rand
     b pure-rand
     c pure-rand]
     [a b c])
     (java.util.Random. 100))

;; [[0.7220096548596434 0.19497605734770518 0.6671595726539502] 
;; #<Random java.util.Random@358ddfd6>]

In the example above, we’re using our pure-rand function in the context of the State Monad to generate 3 random numbers - based on some initial state - and returning them as a vector.

As we’ve seen before the result is itself in a vector alongside the new state.

This is where the State Monad and the validation problem meet:

In bouncer, each validation function is designed to be compatible with the State Monad, just like pure-rand above:

It receives an initial state - at first, the map to be validated - and returns a vector with the map of errors and the new state: the original map augmented with any errors from previous validators.

The end result, should one or more validations fail, is a map with all errors that might have happened, plus our new state.

Now if you head to the github repository and read the examples by keeping the State Monad and the above explanation in mind, the similarities should be obvious.

Wrapping up

As I mentioned in the beginning of the article, there are other validation libraries for Clojure and at the time of this writing they have more features than bouncer - by all means have a look at them.

However I will keep maintaining bouncer for a couple of reasons:

• That’s what I’m using in my current side project
• It takes a fundamentally different implementation approach that is in itself worthy of exploration
• If nothing else, this is yet another example of where Monads can be useful.

Acknowledgments

Thanks to Steve and Julian for reviewing early drafts of this post as well as Nick for being such a PITA :) - our discussions led to a considerably nicer design.

As usual, let me know your thoughts.

Keeping the tradition of end-of-year blog posts, here are my year highlights for 2012:

Clojure

I started clj-syd - the Sydney Clojure User Group - back in January and it has seen a major uptake. We consistently get an average of 25 people each month and there’s no shortage of talks and topics to discuss. It’s a great crowd and I’m proud to have started it and of being part of it.

Speaking

I spent most of the year studying functional programming and I tried to make my talks reflect that. Even the javascript talk I gave in April had a FP focus. Anyway, you can find some of the slides online:

• The many facets of code reuse in JavaScript - this was given at a ThoughtWorks technical event in April

• Continuation Passing Style and Macros in Clojure - this is the talk I gave at our first Clojure meetup in Sydney

• Clojure Reducers - Another preso I gave at the clojure user group, in August.

Books

As usual I read a number of books this year and these are my favourites:

• The Little Schemer

As they say, an oldie but a goodie. This is mandatory reading for anyone who consider themselves a serious programmer. The insights and techniques found here are invaluable. Do yourself a favor and buy it now.

For a Clojure take on it, check Julian Gamble’s series on The Little Schemer in Clojure

• The Joy of Clojure

This is pretty much how I learned Clojure. I actually started reading it in November 2011 but felt I needed to put it down from time to time to go and code on my own to solidify what I learned. That’s why I only finished it in 2012.

This book packs a great deal of info and is a great way to get into both functional programming and Clojure.

• Learn you a Haskell for Great Good

This is the best intro to Haskell ever. Hands down. ‘nuff said.

• Clojure Programming

I like reading different books about the same subject to get to see it from various perspectives. Clojure Programming takes a different approach to The Joy of Clojure in that, as it progresses through topics and code examples, it contrasts it with languages likely to be familiar to the reader, such as Java, Ruby and Python. Another great alternative if you’ve been thinking of getting into Clojure but didn’t know where to start.

Content

Here’s just a few of the posts visitors found most interesting this year:

• Monads in Small Bites Parts I, II, III & IV - Even though I only published this series in December, it quickly became one of the most read posts that month. And it’s also a personal favorite.

• Build Automation With XCode 4.3, KIF and Jenkins - This turned out to be very popular - build automation and testing are not among the top priorities within the iOS community so I’m glad this helped some people out. It’s getting way better now.

• Hiring Good People Is Really Simple - Another one high up in my analytics, and it still stands true.

• JRuby on Rails and Legacy Java Apps: Managing Dependencies - The JRuby enterprise world seems to be hotter than ever before. I wouldn’t think this post from 2009 would still get this many visits. I haven’t been involved much with JRuby as of late so I wonder if this is still the way to go?

LambdaJam

LambdaJam is a conference for functional programmers and although it’s set to happen in May 2013 the wheels have already started turning - thus I had to list it as a highlight.

I’m fortunate enough to be involved with the organization alongside very bright people from the Australian functional programming community as well as Dave Thomas from the YOW! Conference who’s leading the effort. We’re all really excited about it.

Stay tuned, lots more info to come!

Goals

No resolutions. Goals. And I wanna achieve them. They’re simple and I hope this post will keep me in check

Better utilize my free time

This is a bit abstract but will help me achieve the goals below. The output of this goal is a calendar with time slots assigned to each one of the next goals - I’ve just done this now actually so this is a good start. No more procrastinating.

Books

I got a big pile of books I wanted to have read in 2012 so I’ll be updating my good reads profile with them and make sure I just do it - with the help of my new calendar from the goal above.

Side projects

In 2012 I worked on two side project which are not ready yet, so I can’t comment a whole lot on them apart from saying that one is being developed in Clojure and the other in Ruby - in 2013, these two will see the light of day.

Here’s to a new year

I hope you all had a great 2012 and are as excited as I am for the new year.

Happy holidays, safe driving and awesome parties! :)

This is Part IV of my Monads tutorial. Make sure you read the previous parts:

• Part I - Functors

• Part II - Applicative Functors

• Part III - Monoids

• Part IV - Monads (this post)

A quick recap

In Part I we learned about Functors, which are things that can be mapped over using a normal function - fmap is used for that.

Part II tought us that when our Functors themselves contain functions and we want them applied to the values contained in other Functors, Applicatives come to the rescue - and bring theirs friends pure and <*>.

Part III introduced Monoids which model a special type of relationship involving binary functions and their identity values.

Now it’s time for what I hope is the post you have all been waiting for :)

Monads

A word on context

So far I’ve said things such as wrapping stuff in Functors, unwrapping functions from Applicatives and putting results into minimal Functors. All this really means is that [Applicative]Functors - and Monads - have associated contexts that model some sort of computation.

For lists, for example, this means they represent computations that can have several results - non-determinism.

These computations can have much greater implications though - they can represent failure (or not!), do IO and even launch nuclear missiles. The point is: when we combine Functors/Applicatives/Monads, we carry their context with us to the end - they are essentially sequenced together.

This will become clearer with an example. For once I won’t start with lists - w00t! - so get ready for it!

The Maybe Monad

The Maybe monad models computations that can fail. Let’s have a look at an example.

Say you have an e-commerce system. When placing an order, a few things need to get done:

• gather information about the order;
• calculate shipping rates;
• apply discount codes, if any, and;
• finally place the order.

The code below shows the supporting functions that will be orchestrated in order to achieve this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(defn calculate-shipping-rate [address]
    (if (= (:country address) "Australia")
        10.0
        nil))

(defn apply-shipping-costs [order shipping-rate]
    (assoc order :total (+ (:total order) shipping-rate)))

(defn lookup-discount-code [code]
    (if (= code "XMAS2012")
        5.0
        nil))

(defn apply-discount-code [order discount]
    (assoc order :total (- (:total order) discount)))

(defn place [order]
    (prn (str "Off you go! Order total: $" (:total order))))

Note that based on the code above, we can only ship to Australia and there is only one active discount code. Keep this in mind - you’ll see why later on.

Now let’s place an order for some Jalapeño sauce:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(def order {
    :items [{:name "Jalapeño sauce" :price 20.0}]
    :address {:country "Australia"}
    :discount-code "XMAS2012"
    :total 20.0
})

(def shipping-rate (calculate-shipping-rate (:address order)))
(def discount (lookup-discount-code (:discount-code order)))

(-> order
    (apply-shipping-costs shipping-rate)
    (apply-discount-code discount)
    (place))
;; "Off you go! Order total: $25.0"

Great! Soon I’ll be receiving some hot sauce to go with my burritos!

But wait, what if I had mistakenly set my address to somewhere other than Australia? How would this code behave?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(def another-order {
    :items [{:name "Jalapeño sauce" :price 20.0}]
    :address {:country "Brazil"}
    :discount-code "HACKERZ"
    :total 20.0
})


(def shipping-rate (calculate-shipping-rate (:address another-order)))
(def discount (lookup-discount-code (:discount-code another-order)))

(-> another-order
    (apply-shipping-costs shipping-rate)
    (apply-discount-code discount)
    (place))
;; NullPointerException   [trace missing]

Oops! Your e-commerce system just crashed! Not cool. But hey, this is easy to fix, right? We could just change our apply-shipping-costs function to something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13

(defn apply-shipping-costs [order shipping-rate]
    (if shipping-rate
        (assoc order :total (+ (:total order) shipping-rate))
        order))


;;Remember we only support one discount code so the same problem could happen again
;;We need to change the apply-discount-code function as well

(defn apply-discount-code [order discount]
    (if discount
        (assoc order :total (- (:total order) discount))
        order))

Now let’s see what happens:

1
2
3
4
5
6
7
8

(def shipping-rate (calculate-shipping-rate (:address another-order)))
(def discount (lookup-discount-code (:discount-code another-order)))

(-> another-order
    (apply-shipping-costs shipping-rate)
    (apply-discount-code discount)
    (place))
;; "Off you go! Order total: $15.0"

Well, it doesn’t crash but we can’t ship to Brazil anyway! So the code is still incorrect! What we really want is a way to halt the whole computation - placing an order - if any of those steps fail.

Of course we could fix it with a couple more if forms before trying to call the place function but you see where this is going.

Essentially our nice little functions became burdened with context: each of them is now aware that they can fail and need to cater for it.

Enter the Monad

I’ll jump straight to how the code could look like if we had monads - it won’t work now because we haven’t actually implemented the monad yet, but this should whet your appetite.

Also, assume we reversed the changes from before - the functions don’t have the if forms checking its arguments any longer, just like in the original version. Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(domonad maybe-monad
    [order order
     shipping-rate (calculate-shipping-rate (:address order))
     discount (lookup-discount-code (:discount-code order))]
     (-> order
        (apply-shipping-costs shipping-rate)
        (apply-discount-code discount)
        (place)))
;;"Off you go! Order total: $25.0"

(domonad maybe-monad
    [order another-order
     shipping-rate (calculate-shipping-rate (:address order))
     discount (lookup-discount-code (:discount-code order))]
     (-> order
        (apply-shipping-costs shipping-rate)
        (apply-discount-code discount)
        (place)))
;; nil

domonad receives the monad you want to operate on, a vector of bindings and an expression that’s the final result of the whole thing.

Is your mind blown yet? :) Somehow the whole operation fails and yields nil in the second call to domonad above - without any if forms and without crashing! To see why that is, I’ll now explain the monad type class from Haskell.

The Monad Type Class

Here’s the Haskell definition of the Monad type class (I left the fail function out so we can focus on the core of it):

1
2
3
4
5
6
7

class Monad m where
    return :: a -> m a

    (>>=) :: m a -> (a -> m b) -> m b

    (>>) :: m a -> m b -> m b
    x >> y = x >>= \_ -> y

Let’s distill those bad ass type signatures:

return - much like pure from Applicative Functors, return is responsible for wrapping a value of type a into a minimum context Monad that yields a value of type a - referred to as a monadic value.

(>>=) - often called bind - is a function of two arguments. The first is a monadic value of type a and the second is a function that receives a value of type a and returns a monadic value of type m b which is also the overall result of the function.

In other words: bind runs the monad m a, feeding the yielded a value into the function it received as an argument - any context carried by that monad will be taken into account.

(>>) - often called then - This function receives two monads, m a and m b, and returns a monad of type m b. It is generally used when you’re interested in the side effects - the context - carried out by the monad m a but doesn’t care about the value a it yields. It’s rarely implemented in specific monads because the type class provides a default implementation:

It applies bind to the monad x and a function that ignores its argument (\_ -> y) - which by convention is represented by an underscore - and simply yields the monad y: that’s the final result of the computation.

I won’t be implementing then in Clojure though - I’ll focus on return and bind, since then is essentially a helper function you could write yourself.

The Maybe Monad - Clojure edition

With definitions out of the way, let’s implement the Clojure version of the Maybe monad.

1
2
3
4
5
6

(def maybe-monad {
    :return (fn [v] v)
    :bind (fn [mv f]
            (if mv
                (f mv)
                nil))})

Yup. That’s it.

For the maybe monad, all its context needs to represent is a single value or the absence of value. We do this inside bind by checking if the monadic value mv is nil. If it isn’t, we apply f to it, which will yield another monadic value. If, on the other hand, mv IS nil, we just return nil, bypassing the function application entirely.

return, as we saw, wraps a value into a minimal monad. In this case this is the value itself, so we just return it untouched.

This is how one may go about using it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(-> another-order
    ((:bind maybe-monad)
     (fn [order]
       (-> (calculate-shipping-rate (:address order))
           ((:bind maybe-monad)
            (fn [shipping-rate]
              (-> (lookup-discount-code (:discount-code order))
                  ((:bind maybe-monad)
                   (fn [discount]
                     ((:return maybe-monad)
                      (-> order
                        (apply-shipping-costs shipping-rate) (
                        apply-discount-code discount)
                        (place))))))))))))
;; nil

WOW! That is awful! And I won’t blame you for not wanting to read through this aberration. But trust me, it does the job.

However, you’re probably thinking: that looks nothing like the nice little domonad notation we saw earlier!

Well, you’re right. That’s because domonad is a macro - it gives us some syntactic sugar that expands into the real code shown above. In order to be able to use the domonad notation, paste the following into your REPL:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(defn monad-steps
    ([monad steps expr]
        (if (seq steps)
            (let [fst (first steps)
                  snd (second steps)]
                  `((:bind ~monad)
                    (fn [~(symbol fst)]
                        (->  ~snd ~(monad-steps monad (subvec steps 2) expr)))))
            expr)))


(defmacro domonad [monad steps expr]
    (let [args (map first (partition 2 steps))
          forms (map second (partition 2 steps))
          new-steps (subvec (vec (interleave (cons nil args) forms)) 2)]
          `(let [m# ~monad]
            (-> ~(second steps)
                ~(monad-steps monad new-steps
                    `((:bind ~monad) (fn [~(symbol (last args))] ((:return ~monad) ~expr))))))))

All set! Now you should be able to run the examples that use domonad without any hiccups. Give it a shot:

1
2
3
4
5
6
7
8
9

(domonad maybe-monad
    [order another-order
     shipping-rate (calculate-shipping-rate (:address order))
     discount (lookup-discount-code (:discount-code order))]
     (-> order
        (apply-shipping-costs shipping-rate)
        (apply-discount-code discount)
        (place)))
;; nil

Note: macros can be daunting at times so don’t worry too much about its implementation. It’s way more important to me that you understand the end result than it is to be able to implement the macro yourself - but by all means dissect this implementation if you feel inclined to do so :)

Now that’s way better. The maybe monad abstracted away the logic behind computations that can fail so you don’t have to worry about it in your functions - you can just focus on writing them.

In the end I also believe it aids readability once you get used to it.

Don’t break the law

Monads have laws of their own too! Let’s have a look at them.

Right unit

Binding a monadic value m to return should be equal to m itself

In Haskell speak:

1

m >>= return =  m

The proof in Clojure:

1
2
3
4
5
6
7
8
9

(def m 10)
(def >>= (:bind maybe-monad))
(def return (:return maybe-monad))

;; given the above, this...
(>>= m return) ;; 10

;;is the same as
m ;; 10

Left unit

Applying return to x and then applying >>= to the resulting value and fshould be the same as applying f directly to x

In Haskell speak:

1

return x >>= f =  f x

The proof in Clojure:

1
2
3
4
5
6
7
8
9
10

(def x 10)
(def >>= (:bind maybe-monad))
(def return (:return maybe-monad))
(def f (fn [v] (* v 2)))

;; given the above, this...
(-> (return x) (>>= f)) ;; 20

;;is the same as
(f x) ;; 20

Associativity

Binding m to f and then applying >>= to the result and g should be the same as applying >>= to m and a function of argument x that first applies f to x and then binds it to g.

Phew…another mouthful, huh? Code should make it clearer. As usual, Haskell comes first:

1

(m >>= f) >>= g  =  m >>= (\x -> f x >>= g)

And now let’s prove it in Clojure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

(def >>= (:bind maybe-monad))
(def return (:return maybe-monad))

(def m 10)
(def f (fn [v] (* v 2)))
(def g (fn [v] (+ v 10)))

;; given the above, this...
(-> (>>= m f) (>>= g)) ;; 30

;;is the same as
(>>= m
     (fn [x]
        (>>= (f x) g))) ;; 30

Alright, we’re getting to the end now! Hold on just a little longer!

One last thing - The List Monad

Yeah, I’m sure you saw this coming. Lists are monads too! I’ll make this quick and show its implementation and usage in Clojure - bear with me one last time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(def list-monad {
    :return (fn [v] [v])
    :bind (fn [mv f]
        (if (seq mv)
            (apply concat (map f mv))
            []))
    })

;;let's play with it

(domonad list-monad
    [a [1 2]
     b [a, (- a)]]
     (* 3 b))
;; (3 -3 6 -6)

(domonad list-monad
    [a [1 2]
     b []]
     (* 3 b))
;; () - an empty list. 

This should look familiar if you’ve used list comprehensions in Clojure or other languages such as Python:

1
2
3
4

(for [a [1 2]
     b [a, (- a)]]
     (* 3 b))
;; (3 -3 6 -6)

See? You’ve been using monads all along and didn’t even know it! How awesome is that?

Also note that we didn’t need to re-implement domonad for the list monad. It’s a generic macro that will work with any monads you throw at it!

It’s interesting to see how the list and the maybe monads differ. This time, return puts the value v inside a list and returns it because for lists, a minimum monad is a list with a single element.

bind is a bit more interesting. It first checks to see if mv is empty, in which case it returns an empty list, causing the whole computation to stop. If, however, mv is NOT empty, it maps f over every element in mv.

The resulting list is potentially a list of lists, since functions fed to monads - such as f in this case - have to return monadic values. That’s why we then apply concat to the resulting list, effectively flattening it.

Final words

Hopefully you now have a much better understanding of Monads and should start seeing in your code use cases and/or opportunities for the monads shown here.

You’ll notice that this Clojure implementation of monads used only normal functions - that was by design since I wanted this implementation to be as close as possible to Clojure’s core.algo.monads library. You should have a look at it.

Also, bear in mind that this tutorial is by no means exhaustive - there’s a lot more about monads that I could possibly cover in a blog - it was hard enough ending it here! But if you want to study more about them, I’d recommend starting with these resources:

• Learn You a Haskell for Great Good - this book is an excellent intro to Haskell and it was the approach found there that made me grok monads - highly recommended and freely available online.

• The Monads Section on the Haskell wikibook - another free online resource

That’s it from me. I hope you enjoyed the read and if you made it until here, a big thank you.

This is Part III of my Monads tutorial. Make sure you read the previous parts:

• Part I - Functors

• Part II - Applicative Functors

• Part III - Monoids (this post)

• Part IV - Monads

Monoids

Simply put, Monoids describe types containing a binary function and an identity value.

When applied to the identity value and a random value x, said function leaves its argument x untouched, returning it as a result.

This short description should be enough to get the conversation started.

Here’s how Haskell defines a Monoid:

1
2
3
4
5

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat ms = foldr mappend mempty ms

This type introduces three new functions so let’s walk through each one of them:

mempty - I started with a lie since mempty isn’t actually a function. You can think of it as a constant of the same type of the Monoid m. It is this monoid’s identity value.

mappend - A poorly named function, mappend is the binary function I mentioned earlier. It receives two arguments of type m and returns a value of type m

mconcat - It receives a list of Monoids m and reduces them to a single Monoid of type m. What’s interesting about this snippet is that the Monoid type class provides a default implementation for mconcat: it simply calls foldr with the binary function mappend, a starting value of mempty and the list of Monoid values ms

Enough Haskell! Let’s have a look at a few examples.

Did you know that, in Clojure, the functions * and + are monoids? Yup. But don’t take my word for it. Let me prove it to you:

1
2
3
4
5
6
7
8

(def  mempty (+)) ;; 0
(def  mappend +)
(defn mconcat [ms]
    (reduce mappend mempty ms))

(mappend 3 4) ;; 7

(mconcat [2 3 4]) ;; 9

Whoa! What happened here? Am I just making this stuff up?

Not really. I only defined the same haskell names to their Clojure counterparts for clarity. Totally overkill. The code above is the same as:

1
2
3
4
5

(+) ;; 0

(+ 3 4) ;; 7

(reduce + [2 3 4]) ;; 9

Did you notice that on the second call to reduce we did not provide an initial value? That’s because reduce will attempt to get its initial accumulator by calling the reducing function without arguments - hence mempty == (+).

So that means we don’t even need an mconcat function since in Clojure, reduce works with monoids as well!

Update: this isn’t entirely true. When I wrote this post I had in mind the version of reduce provided by the Clojure (1.5+) reducers library. The source code shows how that is the case.

The implementation of reduce in clojure.core however uses the first element of the collection being reduced over as its seed.

But how the hell do you create a monoid in Clojure then? I’m glad you asked. Let’s create our own plus-monoid!

Your first monoid

In Part I I implemented Functors using protocols and records. In Part II I showed how Applicative Functors could be implemented using multimethods.

This time around I won’t be using any of these. I’ll implement Monoids using pure functions:

1
2
3
4
5
6
7
8
9
10
11

(defn plus-monoid
    ([]
        0)
    ([a b]
        (+ a b)))

(plus-monoid) ;; 0 - same as mempty

(plus-monoid 3 4) ;; 7 - same as mappend

(reduce plus-monoid [2 3 4]) ;; 9 - when working with monoids, reduce is the same as mconcat

We start by defining a function with multiple arities. The first body receives no arguments, so we just return the identity value for summation, which is 0 (zero). The second body receives two arguments so we can just add them up. Multiplication can be implemented in a similar fashion but obviously with the identity value of one.

Easy, huh?

Oh, by the way, lists are Monoids too! Who’d have thought?

Here’s its Clojure implementation:

1
2
3
4
5
6
7
8
9
10
11

(defn list-monoid
    ([]
        '())
    ([a b]
        (concat a b)))

(list-monoid) ;; () - remember, same as mempty

(list-monoid [1 2 3] [4 5 6]) ;; (1 2 3 4 5 6) - remember, same as mappend

(reduce list-monoid [[1 2 3] [4 5 6] [7 8 9]]) ;; (1 2 3 4 5 6 7 8 9) - mconcat in action

Same rules apply but for lists mappend is achieved by using concat inside our monoid function.

Also, since our binary function concatenates two lists together it makes sense that mempty is () (the empty list). Remember mempty is supposed to be an identity value so if we stitch () and [1 2 3] together, we’re left with [1 2 3] which is exactly what we’d expect.

You can see now why I said mappend was poorly named. While it makes sense when you think about lists, mappend doesn’t do any appending in our plus-monoid and in fact most monoids don’t append anything. Just keep this in mind if you see any haskell code using it: mappend is just a binary function.

Don’t break the law

You saw this coming, huh? Monoids also come with a couple of laws. You know the drill. Let’s prove they both hold.

Identity

Applying mappend to mempty and a monoid x should be the same as the original x monoid.

In Haskell:

1
2

mappend mempty x = x
mappend x mempty = x

And the proof in Clojure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

;; first, the plus-monoid
(def mempty (plus-monoid))

(def x 10)

;; This...
(plus-monoid mempty x) ;; 10

;; ...is the same as:
(plus-monoid x mempty) ;; 10

;;now, the list-monoid

(def mempty (list-monoid))
(def x [1 2 3])

;; This...
(list-monoid mempty x) ;; (1 2 3)

;; ...is the same as:
(list-monoid x mempty) ;; (1 2 3)

Associativity

Applying mappend to a monoid x and the result of applying mappend to the monoids y and z should be the same as first applying mappend to the monoids x and y and then applying mappend to the resulting monoid and the monoid z

In Haskell:

1

mappend x (mappend y z) = mappend (mappend x y) z

And the proof in Clojure - remember that calling the monoid function with two arguments is equivalent to mappend in haskell:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

;; first, the plus-monoid

(def x 10)
(def y 25)
(def z 40)

;; This...
(plus-monoid x (plus-monoid y z)) ;; 75

;; ...is the same as:
(plus-monoid (plus-monoid x y) z) ;; 75

;;now, the list-monoid

(def x [40])
(def y [10 25])
(def z [50])

;; This...
(list-monoid x (list-monoid y z)) ;; (40 10 25 50)

;; ...is the same as:
(list-monoid (list-monoid x y) z) ;; (40 10 25 50)

Almost there…

This puts an end to Part III. It’s time to head to the pub.

When you’re back look for the final post in these series - Part IV - where we will conclude our journey by finally introducing Monads!

This is Part II of my Monads tutorial. Make sure you read the previous parts:

• Part I - Functors

• Part II - Applicative Functors (this post)

• Part III - Monoids

• Part IV - Monads

Applicative Functors

In Part I I talked a little about Haskell type signatures and introduced Functors, which provide a way to map standard functions over values which are wrapped inside a Functor - we used fmap for that. You might want to skim through it again as a refresher.

Now suppose you have Functors that wrap functions and that you want to apply those wrapped functions to other Functors, maybe even composing new functions on the way!

What then?

Well you’re in luck! Applicative Functors do just that! They’re Functors on steroids.

Here’s how Haskell defines the Applicative data type:

1
2
3

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Based on our previous knowledge of Haskell’s type signatures, we can infer from this definition that in order for it to be an Applicative Functor, f must already be a Functor.

Let’s break this down and have a closer look at the two new functions this type introduces:

pure is a function that takes a value a and wraps it into a minimal Functor f.

<*> is a function that takes two arguments: the first is a Functor f that wraps a function of type a -> b. The second argument is a Functor f that wraps a value - which could be a function! - of type a. The final result is a Functor f that wraps some value of type b - which was obtained by somehow applying the function (a -> b) to the Functor f a.

pure has a straightforward explanation whereas <*> is a bit more involved.

To clear things up, I’ll show the type signatures again but this time as if they only worked with the List Functor that we’ve been working on:

1
2

pure :: a -> [a]
(<*>) :: [(a -> b)] -> [a] -> [b]

Let’s revisit those definitions:

pure is a function that takes a value a and puts it into an empty list, returning the resulting single element list.

<*> is a function that takes two arguments: the first is a list containing one or more functions of type a -> b. The second argument is a list of one or more values - or functions! - of type a. The final result is a list of one or more values of type b - which was obtained by somehow applying the function (a -> b) to the Functor f a.

Enough definitions though! Let’s extend our List Functor and make it an Applicative as well.

While we’ll still be using the List Functor we implemented in Part I, this time I’ll implement its Applicative version using multimethods for a change. Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13

;; it dispatches on the record type since we could have implementations of pure for List, Maybe, Either etc...
(defmulti pure (fn [f _] f))
(defmethod pure List [_ v]
    "Wraps value v in a list"
    (List. [v]))

;; it dispatches on the class of the Functor instance passed in the 1st argument
(defmulti <*> (fn [fs _] (class fs)))
(defmethod <*> List [fs xs]
    "Unwraps the functions in fs, applies them to the Functors in xs, wrapping the result at the end"
    (List. (for [f (:wrapped fs)
                 x (:wrapped xs)]
                (f x))))

By focusing on the List as an Applicative Functor we can more easily understand what these functions do. From the code above, pure’s job is a simple one: all it does is wrap it’s argument v into a minimal List functor which in our case means a Functor wrapping a one element list.

<*> on the other hand is responsible for somehow unwrapping the functions brought in by the Applicatives in fs and applying them to the [Applicative] Functors in xs. It does that by using list comprehensions and wraps the result into a new List Functor.

Study this code carefully. It can be tricky.

Note: When I first encountered <*> I had no idea what this function was called. I asked the twittersphere and it seems it’s called apply. In the process of figuring this out I was enlightened by this conversation. It turns out <*> has several names. Can you guess which one is my favorite? :)

With the Applicative functions defined for our List, let’s take it for a spin:

1
2
3
4
5
6
7
8

(def fs (List. [#(* 2 %) #(+ 10 %)]))
(def xs (List. [1 2 3]))

(<*> fs xs) ;; List{:wrapped (2 4 6 11 12 13)}


(def g (pure List #(* 50 %)))
(<*> g xs) ;; List{:wrapped (50 100 150)}

There should have been no surprises here. Read the code again and make sure it’s all fresh before moving along.

Don’t break the law

Just as Functors, Applicative Functors also need to obey some laws:

Identity

Feeding a function f to pure and applying the resulting Applicative to the Functor v should be the same as directly mapping f over the Functor v

In Haskell speak:

1

pure f <*> v = fmap f v

And this is the proof, in Clojure:

1
2
3
4
5
6
7
8
9

(def f #(+ 2 %))
(def v (List. [10]))

;; given the above, this...
(<*> (pure List f) v) ;; List{:wrapped (12)}


;; ...is the same as:
(fmap v f) ;; List{:wrapped (12)}

Composition

The result of applying an Applicative Functor that yields the function composition operator to the Applicative u, then apply the resulting Functor to v and finally applying that result to the final Applicative w should be the same as applying v to w and then applying u to the resulting Applicative.

That was a mouthful! Let’s see how Haskell tells this story:

In Haskell:

1

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

I needed to cheat a bit in Clojure to prove this law since functions are not curried by default like they are in Haskell. But this code should still clearly show how this law holds:

1
2
3
4
5
6
7
8
9
10
11
12

(def u (List. [#(* 2 %)]))
(def v (List. [#(+ 10 %)]))
(def w (List. [1 2 3]))

;; Given the above, this...
(-> (pure List (fn [x] (partial comp x)))
  (<*> u)
  (<*> v)
  (<*> w)) ;; List{:wrapped (22 24 26)}

;; ...is the same as:
(<*> u (<*> v w)) ;; List{:wrapped (22 24 26)}

Homomorphism

The result of applying the pure value of f to the pure value of x should be the same as applying f directly to x and then feeding that into pure.

In Haskell:

1

pure f <*> pure x = pure (f x)

And in Clojure:

1
2
3
4
5
6
7
8
9

(def f #(* 2 %))
(def x 10)

;; given the above, this...
(-> (pure List f)
  (<*> (pure List x))) ;; List{:wrapped (20)}

;; ...is the same as:
(pure List (f x)) ;; List{:wrapped (20)}

Interchange

The result of applying an Applicative Functor u to the pure value of y should be the same as taking the Applicative obtained by calling pure with a function that applies its argument to y and then applying that to u

In Haskell:

1

u <*> pure y = pure ($ y) <*> u

This type signature presents new syntax so before proving the law in Clojure, I want to explain what ($ y) means.

In Haskell, $ is the function application operator. So if we give y a value of 10, I can show you that in this law $ essentially translates to a single argument function that applies its argument to 10:

1
2
3
4
5
6
7
8

let double a = a * 2 -- helper function. it doubles its argument

-- given the above, this...
(($ 10) double) -- 20

-- ...is the same as:
let dollarTen = (\a -> (a 10))  -- this is Haskell's lambda syntax. It's equivalent to ($ 10)
((dollarTen) double) -- 20

Now, to the proof in Clojure:

1
2
3
4
5
6
7
8
9

(def u (pure List #(+ 10 %)))
(def y 50)

;; given the above, this...
(<*> u (pure List y)) ;; List{:wrapped (60)}

;; ...is the same as:
(def dollar-y #(% y)) ;; it's called dollar-y to show the correlation with the explanation above
(<*> (pure List dollar-y) u) ;; List{:wrapped (60)}

This brings us to the end or Part II. Two down and two to go.

I hope you’re still with me but go home now.

Or better yet go to the gym lift some weights and think about these Functors on steroids. When you’re back, look out for Part III.

Today I join the already bloated group of people who wrote monad tutorials. It’s a bit of a ritual, really.

Different than most tutorials though I aim to take a different approach. The good news is that I won’t be comparing monads to burritos :)

People say one needs to have his/her own epiphany in order to understand Monads and reading explanations from others is of little help. My goal is to disprove that.

To that end, this tutorial will be split in four parts:

• Part I - Functors (this post)

• Part II - Applicative Functors

• Part III - Monoids

• Part IV - Monads

You might want to bookmark this page - once the other parts are up, I’ll update the list above with the links to them.

Before we start

I know what you’re thinking: Do I really need to know Applicative Functors just to grasp Monads?

Well, no. However, I found that gradually building your knowledge from Parts I, II and III will allow you to fully grasp monads without the need for burritos or elephants.

You should also be familiar with a functional programming language. Any language should be fine but you’ll get the most out of this tutorial if you’re familiar with Haskell and/or Clojure.

If you’re not familiar with Clojure, fear not - Clojure is a small language and the code snippets should still make sense if you put your mind to it - they’re all short and sweet. I also encourage you to re-implement the examples in your language of choice to gain a deeper understanding on the subject.

Ready then? Let’s dive in.

Just enough Haskell

This is not a Haskell tutorial but trust me when I tell you that learning just enough about its type signatures will make all the difference in the world in understanding the concepts I’m about to present.

Although I’ll be using a little bit of Haskell syntax, I’ll also provide implementations in Clojure. They are in order so you should be able to paste all code sample in the REPL and follow along if you wish.

Type signatures

I’ll make this quick. Say you have a function called mk-vec that creates a 2D vector with x and y coordinates. Such function could easily be coded in Clojure like this:

1
2
3
4
5
6

(defn mk-vec [x y]
  {:x x :y y})

;; using it
(def my-vec (mk-vec 10 15))
(:x my-vec) ;; 10

As you can see, this function takes two arguments - x and y - and returns a map - or hash if you come from Ruby - that wraps those values in it, providing an easy way to retrieve them.

Now if this function had been implemented in haskell this would be its type signature - read the comments:

1
2
3
4
5
6
7
8
9
10

import qualified Data.Map as Map -- just giving Data.Map an alias
mkVec :: a -> a -> Map.Map [Char] a -- this is the type signature

mkVec x y = Map.fromList [("x", x), ("y", y)] -- this is the implementation. You can ignore this part.

-- using it
myVec = mkVec 10 15
Map.lookup "x" myVec -- Just 10 
--
-- ignore the actual value that is returned. Read it as 10 for now.

Whatever comes after the :: is part of the function type signature. Read it like this:

This is a function that receives two arguments of type a - which means any type - and returns a Map of key/value pairs where the key is of type [Char] - technically a list of Char values but for all effects and purposes just read it as String - and the value is of type a - the same type as its arguments.

It might help to see the type signature in this light:

1

mkVec :: a -> a -> (Map.Map [Char] a)

It highlights the return value in parenthesis.

Now let’s have a look at a built in function, *. As you know, it performs multiplication and this is its type signature:

1

(*) :: Num a => a -> a -> a

Can you guess now what it means? I’m sure you can. There’s one small difference though: this function has a type constraint - it’s that Num a => … part of the signature. Read it like this:

This is a function that receives two arguments of type a and returns a value of the same type, as long as the type of a is an instance of Num

And that’s it for now. Read it again to make sure it’s fresh in your mind and then continue.

As we encounter more type signatures, I’ll walk you through each one of them - but if you got it up until now, you’ll easily grasp the other type signatures.

Functors

In a nutshell Functors are things that can be mapped over.

Haskell defines Functors like this:

1
2

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Let’s dissect that type signature:

fmap is a function that receives two arguments: the first is a function that receives an argument of type a and returns a value of type b and the second is a Functor that contains a value of type a - represented by f a. The result of calling fmap is a Functor of same type - f - containing a value of type b, which is the result of applying the function to a.

Too much? Let’s have a look at an example: the List Functor.

If we rewrite the fmap type signature as if it only worked on lists, this is what we’d come up with:

1

  fmap :: (a -> b) -> [a] -> [b]

This new type signature allows us to rewrite that last definition:

fmap is a function that receives two arguments: the first is a function that receives an argument of type a and returns a value of type b and the second is a List of zero or more values of type a. The result of calling fmap is a List of zero or more values of type b, each of which is the result of applying the function to each a element.

Does this sound familiar to you? It should, because this is essentially what the map function available in most functional-ish languages does! It takes a function and a list, applies the function to every element in the list while putting the results into a new list, finally returning it.

In fact, the fmap implementation of the List Functor from Haskell is implemented in terms of map.

Let’s see how that could be done in Clojure. I’ll use protocols and records but they are not strictly required for this.

Here’s our Functor protocol:

1
2

(defprotocol Functor
    (fmap [functor f] "Maps fn over the functor f"))

And now our List Functor:

1
2
3
4

(defrecord List [wrapped]
    Functor
    (fmap [functor f]
        (List. (map f (:wrapped functor)))))

In the snippet above all we’re saying is that the List record must satisfy the Functor protocol, which makes sense. fmap then is responsible for unwrapping the value contained in the list functor and mapping f over it.

Give it a go!

1
2
3

(def my-list-functor (List. [1 2 3])) ;; List{:wrapped (1 2 3)}

(fmap my-list-functor #(* 2 %)) ;; List{:wrapped (2 4 6)}

We can now map arbitrary functions over the values wrapped in a Functor! Awesome!

Note: In our Clojure version of the List Functor, it is implemented as a Record that wraps a primitive Clojure list/vector - []. As I mentioned this is not necessary but I chose to do it here to explicitly show the relationship with the Haskell types.

Don’t break the law

Now that we got a feel for what Functors are, it’s worth noting that they must obey a few laws to be considered full-fledged Functors.

Identity

Mapping an identity function over a Functor is the same as applying identity to the Functor itself

This is how Haskell puts this law:

1

fmap id functor = id functor

Translating that to Clojure:

1
2
3
4
5

;;This...
(fmap my-list-functor identity) ;; List{:wrapped (1 2 3)}

;;is the same as:
(identity my-list-functor) ;; List{:wrapped [1 2 3]}

Composition

If you compose the functions f and g and map the resulting function over the Functor, that is the same as first mapping g over the Functor and then mapping f over the resulting Functor.

From the description you can see that this law involves function composition. In Clojure, that’s achieved with the comp function.

Again, let’s see how this law is defined in Haskell:

1

fmap (f . g) functor = fmap f (fmap g functor)

Note: The . operator denotes function composition in Haskell

And the proof in Clojure:

1
2
3
4
5
6
7
8

(def f #(+ 10 %))
(def g #(* 2 %))

;; given the above, this...
(fmap my-list-functor (comp  f g)) ;; List{:wrapped (12 14 16)}

;; is the same as:
(-> my-list-functor (fmap g) (fmap f)) ;; List{:wrapped (12 14 16)}

Note: make sure you’re familiar with Clojure’s threading macro: -> . I’ll be using it in most code snippets.

Nice! All laws hold so we can sleep peacefully in the knowledge that our Functor works as expected.

Now go get a drink and stay tuned for Part II, where I’ll introduce Applicative Functors.

Last week our current client - ninemsn - ran the 3rd edition of their HackDay.

It’s akin to Atlassian’s ShipIt days so if you’re not familiar with the concept, you should check their page but here’s the gist:

• We’re given 24 hours to work on whatever we like as long as it’s related somehow to the business

• We’re also free to use any technology we want

The team consisted of @romainprieto, Pranav Raja, @thepaddedcell, @stewgleadow and myself (@leonardo_borges).

The idea: Cool story, bro!

@romainprieto came up with it:

• A mobile app that could scan QR codes on a printed JIRA story card and provide features such as assigning a card to yourself, moving it between columns and adding comments to it.

This is a common need. Most people will manage their stories in some sort of software such as JIRA. But it’s also common to have a physical story wall.

The problem then is keeping them in sync. It’s all too common for people to move the cards on the well and forget all about JIRA.

Well, not anymore. This is exactly what our HackDay project tackles.

In 24 hours, we built two native mobile applications - Android and iPhone - that are able to scan QR Codes printed on the story cards and, through integrating with the JIRA REST API, provide all the necessary functionality needed for:

• Assigning a story to yourself - whoever is logged in to the app
• Moving the story between states - e.g.: In Analysis, Resolve Issue, Reopen Issue etc…
• Adding comments to a given story

All code is open source and on github. Check it out! - and bear in mind this was written in 24 hours… ;)

We didn’t stop there though. We actually finished early and had a couple of hours to spare so we shot a video - yes, a video!!! - about the app. I’m telling you, this is Hollywood quality:

Also, checkout some screenshots of the Android version: