-----BEGIN PGP SIGNED MESSAGE-----

Hash: SHA1

Case study/essay

Let us examine this piece of code:

fib.zip(fib.tail)

Let us rename the identifiers to remove ourselves from the specific

problem at hand:

x.f(x.g)

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

explanation:

f(x)(g(x))

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 http://en.wikipedia.org/wiki/SKI_combinator_calculus

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 <dcso...@gmail.com> wrote:

>

>> On Tue, Aug 9, 2011 at 19:19, Lucas Torri <lucas...@gmail.com> wrote:

>>> wow... how this thing works?

>>>

>>> On Tue, Aug 9, 2011 at 4:36 PM, Josh Suereth <joshua....@gmail.com>

>>> wrote:

>>>>

>>>> lazy val fib: Stream[Int] = 1 #:: 1 #:: fib.zip(fib.tail).map { 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

http://tmorris.net/

-----BEGIN PGP SIGNATURE-----

Version: GnuPG v1.4.10 (GNU/Linux)

Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJOQ46OAAoJEPxHMY3rBz0PsIUH+wZG1Bs4csrDbAt1ezGaW/Ns

M6Ae93xKHihvkGnpr7TKtc30HuCzhosDVOZbOyFR67tsoOfVieRmN9qyCeSk8G1n

KXqjNZX8yAGz4JdwvuLpghizOtfax1MTaaqZTDsXH+vCWLJpSXShjNoV8MW0yt4u

43maM9JYPa+tQib7OufmJ192P8SfWUYdTyys8tRaU0BhKbw0PRL2MA9hpRsUvE5w

YJRr4feBujaiduixuLV7b/exnJZbmc3lRy5wQDDzuBt0QCRDXEIF1kyEX9SZoyJy

7YwFtGiI0Bu2Qsb0gpvrar+hx0gQmF1Zd90VKJzediII+6gUffJvvQ1UmaZyFVc=

=bvwI

-----END PGP SIGNATURE-----