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
-----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-----