Re: in defense of types

[Lauri Alanko <address@hidden>]

On Wed, May 29, 2002 at 10:55:05PM -0700, Michael Vanier wrote:
> BTW I'm not sure what you mean when you say that Y is not usable in eager
> languages.  You can define Y in scheme, which is eager.  Do you mean in
> eager statically-typed languages?

You can _define_ Y, but it's not usable: 

(define y (lambda (f)
            ((lambda (x) (f (x x)))
             (lambda (x) (f (x x))))))

You can see why:

(y f) 
-> ((lambda (x) (f (x x))) (lambda (x) (f (x x))))
-> (f ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
-> (f (f ((lambda (x) (f (x x))) (lambda (x) (f (x x))))
-> ...

Eager reduction requires that the argument in a function application is
reduced to a value before beta reduction, and here the argument keeps on
expanding.

In Haskell, which uses lazy evaluation, you can use the trick with
recursive types without resorting to eta expansion:

newtype I a = I (I a -> a)

y = \f -> (\(I x) -> (f (x (I x)))) (I (\(I x) -> (f (x (I x)))))

And this works with _all_ values, not just functions:

Y> :t y
y :: (a -> a) -> a
Y> y (\x -> 1 : x)
[1,1,1,1,1,1,1,....

This would be a bit like saying (letrec ((l (cons 1 l))) l) in scheme.
Ocaml, btw, has a fairly new extension, which allows just this, as long
as the recursive expression is a constructor invocation:

# let rec l = 1 :: l in l;;
- : int list =
[1; 1; 1; 1; 1; 1; 1; ....

This is nice, but not very useful, since recursive data structures
typically need more complicated initialization, and then you can't use
the letrec structure and have to resort to mutable data.


Lauri Alanko
la@iki.fi