Re: [Caml-list] Unexpected restriction in "let rec" expressions

[Pal-Kristian Engstad <pal_engstad@naughtydog.com>]

Loup Vaillant wrote:
> loop :: ((a,c) -> (b,c)) -> a -> b
> loop f a = b
>   where (b,c) = f (a,c)
>   
Remember that values in Haskell are lazy, which simply means that they 
are pointers to things that is either a pointer to a function to 
evaluate it, or the cached value. (This works, since all Haskell values 
are immutable.)

So, what we have here is a specification on how to calculate (b,c) from 
(a, c), given a function f :: (a,c) -> (b, c), and a. In order to 
evaluate b, we must evaluate the pair (b, c), i.e. evaluate the function 
call. Here we're using the value c, which is undefined - except that we 
have one constraint. The second result value is the same as c, and since 
a value is always immutable, it means that the second result value must 
be the *same value* as the second input value.

In other words, we're telling the compiler: Given a function f :: (a, c) 
-> (b, c) and a value of type a, loop f a will give the result b by 
evaluating (b, c') = f (a, c) where c' == c always.

An example function is:

g (a, c) = (c a, (*2))

Here' the constraint is telling us that c == (*2), and since we're 
returning the first parameter, the result is [c a == (*2) a == a * 2].

Another:

g (a, c) = (a + c, 2)

Now, c == 2, thus loop g a == a + 2.

The other examples are of the same theme.

g (a, c) = (c, a : map (+a) c), means that c == a : map (+a) c, which 
again is a recursive definition, and since everything is lazy this 
works. The first element in the list is a, when the second element is 
requested, map (+a) c is requested, but that means requesting c again 
which equals a : map (+a) c, so we get map (+a) (a : map (+a) c), which 
requires just the head  of the cons-cell,which is a, so the result is 
(+a) a : map (+a) (map (+a) c), which is (a + a) : (map (+a) $ map (+a) c)

Hope it helps,

PKE

-- 
Pål-Kristian Engstad (engstad@naughtydog.com), 
Lead Graphics & Engine Programmer,
Naughty Dog, Inc., 1601 Cloverfield Blvd, 6000 North,
Santa Monica, CA 90404, USA. Ph.: (310) 633-9112.

"Most of us would do well to remember that there is a reason Carmack
is Carmack, and we are not Carmack.",
                       Jonathan Blow, 2/1/2006, GD Algo Mailing List