Sunday, September 27, 2009

The Thrush combinator in Scala

In his book To Mock a Mockingbird, Raymond Smullyan teaches combinatory logic using songbirds in a forest. He derives important results combining various combinators, all using the birds of the enchanted forest. Combinators are an effective tool in designing abstractions with functional programming principles. They are reusable units, make you code very concise, without losing on the expressivity. More than the implementation, the names can go a long way in establishing a common vocabulary of programming idioms and techniques. In an earlier post, I talked about Kestrel, and its implementation in Scala for handling side-effects in an abstraction.

In this post, I look at Thrush, a permuting combinator. A Thrush is defined by the following condition: Txy = yx. Thrush reverses the order of evaluation. Raganwald talks about Thrush and its implementations in Ruby in an excellent post quite some time back.

Why would you want to reverse the order of evaluation in a computation ? Well, if you value readability of your code, and have been cringing at how a mix of expression oriented pipelines and nested function calls can make your code less readable, then a Thrush may be for you.

Consider the Ruby example that Raganwald discusses in his first example of Thrush implementation.

lambda { |x| x * x }.call((1..100).select(&:odd?).inject(&:+))

The argument to the proc is a pipeline expression that reads nicely from left to right : get the list of numbers from 1 to 100, select the odd ones and add them up. What the proc does is it finds the square of its input number. But the proc invocation is a function call, which, though is the last in sequence to be executed, has to be the first one that you read. You can find the Ruby implementation in Raganwald's blog that transforms the above code to a left-to-right pipeline expression using Thrush.

Let's try to see how we can do the same in Scala ..

In Scala, I can write the above as ..

((x: Int) => (* x))((1 to 100).filter(% 2 != 0).foldLeft(0)(_+_))

Almost the same as the Ruby code above, and has the similar drawback in readability.

Let's define the Scala Thrush combinator ..

case class Thrush[A](x: A) {
  def into[B](g: A => B): B = {
    g(x)
  }
}


Immediately we can write the above invocation as ..

Thrush((1 to 100)
  .filter(% 2 != 0)
  .foldLeft(0)(+ _))
  .into((x: Int) => x * x)


A very simple combinator, a permuting one that pushes the function to where it belongs in the line of readability. If you want to be more succinct, commit the sin of defining an implicit for your use case ..

implicit def int2Thrush(x: Int) = Thrush(x)

and immediately the above transforms to ..

(1 to 100)
  .filter(% 2 != 0)
  .foldLeft(0)(+ _)
  .into((x: Int) => x * x)


Does it read better ?

In fact with this implicit definition, you can go chaining into all the way ..

(1 to 100)
  .filter(% 2 != 0)
  .foldLeft(0)(+ _)
  .into((x: Int) => x * x)
  .into(* 2)


While designing domain APIs that need to be expressive, this technique can often come very handy. Here's an example that uses the Thrush combinator to ensure a clean pipeline expression flowing into a piece of DSL.

//..
accounts.filter(_ belongsTo "John S.") 
        .map(_.calculateInterest)
        .filter(> threshold)
        .foldLeft(0)(+ _)
        .into {x: Int =>
          updateBooks journalize(Ledger.INTEREST, x)
        }
//..

13 comments:

Slava Pestov said...

Welcome to concatenative programming :-)

USE: math.ranges

1 100 [a,b]
[ 2 mod 0 = not ] filter
0 [ + ] reduce
dup *
2 *

Unknown said...

I am truly interested in Concatenative Programming. I have done some dabbling with Joy as well .. looking forward to some time to start with Factor. I wrote a couple of blogs on concatenative programming as well .. http://debasishg.blogspot.com/2008/12/enjoy.html and http://debasishg.blogspot.com/2008/12/combinators-for-fun-and-profit.html

walterc said...

even better: implicit def any2Thrush[A](a: A) = Thrush(a)

Henry Ware said...

This closely resembles FunctionN's andThen.

Unknown said...

Very nice! I thought I've seen something like this, and I have: It's the $ operator from Haskell. You can even call it $ instead of 'into' if you like:

scala> (1 to 100).filter(_ % 2 != 0).foldLeft(0)(_+_) $ ((x: Int) => x * x)
res7: Int = 6250000

Unknown said...

What I wrote was not correct as $ in Haskell normally has a diffent meaning (basically syntactic sugar to get rid of paranthesis). Although I saw a library somewhere that made it behave like the Thrush combinator shown here...

Matt R said...

See also F#'s "forward pipe" operator.

Daniel Spiewak said...

I prefer F#'s pipeline operator (as mentioned in a previous comment):

implicit def pipelineSyntax[A](a: =>A) = new {
def |>[B](f: A => B) = f(a)
}

((1 to 100) filter { _ % 2 == 0 }) |>
(_.foldLeft(0) { _ + _ }) |>
(2 *)

Though, I will admit that it does work a lot better in a language which curries more heavily (e.g. ML derivatives like F#).

Robert Gould said...

Wow, first time I saw a thrush, it's quite a beautiful pattern, thanks for posting, looking forward to more :)

Anonymous said...

With that brackets and the kind of reversed notion it looks similar to LISP not?

Anonymous said...

Thrush in Haskell:

thrush = flip (.)

Doesn't this beauty inspire you to learn Haskell?

Ingo said...

If you have list comprehension, you can simply write:

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

mgm7734 said...

Thrush is a special case of match!

(1 to 100).
filter(_ % 2 == 0).
foldLeft(0)(_ + _) match {
case x => x * x
}

Too bad you can't use match with an arbitrary partial-function, i.e., x match y == y(x)