Google Groups

Re: [scala-user] Anyone have some good Scala Occult Code?

Tony Morris Aug 11, 2011 1:10 AM
Posted in group: scala-user
Hash: SHA1

Case study/essay

Let us examine this piece of code:

Let us rename the identifiers to remove ourselves from the specific
problem at hand:

Let us now remove the instance methods f and g, and assume they are
regular object functions, for no other reason than for the simplicity of

What would be the most general type of such an expression assuming f, g
and x are free variables? That is to say, what is the type of this:

f => g => x => f(x)(g(x))

We can at least see that f is of the form ? => ? => ? while g is ? => ?
and x is ? but what types are represented by these question marks?

Given g: ? => ? then we know that its first argument is the same type as
the first argument to f and the same type as x itself. Let's call this
type X. So now we have:

f: X => ? => ?
g: X => ?
x: X

We now see that whatever f takes in its second argument is the same type
as the return type of g. Let's call this Y.

So now:
f: X => Y => ?
g: X => Y
x: X

The return of f is the same type as the entire expression. Let's call
that Z. So we have the expression:

f => g => x => f(x)(g(x))

has the type:

(X => Y => Z) => (X => Y) => X => Z

Let us now abstract on this type. Wherever X => appears, I will replace
it with F. So, for example, if X => Y will become F[Y]. To use a
different syntax, wherever I see Function1[X, Whatever], I will replace
it with F[Whatever]. Here goes:

F[Y => Z] => F[Y] => F[Z]

Look familiar?

What is the type of this expression:

f => a => for {
  ff <- f
  aa <- a
} yield ff(aa)

It has this type:
F[Y => Z] => F[Y] => F[Z]
(such that F has flatMap+map methods)

It's an applicative functor!

So if we suppose this function existed as, let's say, a method on F[Y =>
Z] with the name <*>, then we could write the original expression:

zip <*> tail

How handy is that!

The signature of F[Y => Z] => F[Y] => F[Z] has many possible values for
F, as you might know. There are many different values that satisfy the
constraint, "has flatMap+map methods" -- List, Option, Parser, etc. etc.

In our case, we have Function1[T, _], which is missing its flatMap
method in the standard libraries and has a map method but its name is
compose instead (take a close look at its type -- it is map in
disguise!). This special case of <*> to Function1[T, _] has special
significance in that it is the S combinator of the SKI combinator
calculus. Take a look

Hope this helps.

On 11/08/11 17:49, Adam Jorgensen wrote:
> That is very nice. Alas, my brain is still too busy imploding to fully
> comprehend it :-(
> On 10 August 2011 00:56, Daniel Sobral <> wrote:
>> On Tue, Aug 9, 2011 at 19:19, Lucas Torri <> wrote:
>>> wow... how this thing works?
>>> On Tue, Aug 9, 2011 at 4:36 PM, Josh Suereth <>
>>> wrote:
>>>> lazy val fib: Stream[Int] = 1 #:: 1 #:: { case
>> (a,b)
>>>> => a+b }
>> fib is a stream composed of 1, 1, and the stream resulting from a
>> computation. Since Stream is lazy, this computation is performed
>> on-demand.
>> The computation is fib itself paired with fib minus its first element,
>> and then both added together. The first element is fib(0) + fib(1),
>> that is, 2. The second element is fib(1) + fib(2) -- fib(2) is what we
>> have just computed: 2. So that's 1 + 2 == 3. Third element is fib(2) +
>> fib(3), which are the first two elements of this computation: 2 and 3.
>> And so on and on. But, remember, each element is computed *only* on
>> demand, because Stream's tail is non-strict.
>> --
>> Daniel C. Sobral
>> I travel to the future all the time.

- --
Tony Morris

Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla -