From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 400BABBCA for ; Wed, 27 Feb 2008 20:06:28 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAPBCxUfAXQInh2dsb2JhbACQaQEBAQgKKYENm1Y X-IronPort-AV: E=Sophos;i="4.25,414,1199660400"; d="scan'208";a="23123261" Received: from concorde.inria.fr ([192.93.2.39]) by mail4-smtp-sop.national.inria.fr with ESMTP; 27 Feb 2008 20:06:27 +0100 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m1RJ6R3A025018 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 27 Feb 2008 20:06:27 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAPBCxUegISwki2dsb2JhbACQaQEBAQgEBgcIGoENm1Y X-IronPort-AV: E=Sophos;i="4.25,414,1199660400"; d="scan'208";a="23123260" Received: from sdmx1.scea.com ([160.33.44.36]) by mail4-smtp-sop.national.inria.fr with ESMTP; 27 Feb 2008 20:06:26 +0100 Received: from edenfox.989studios.com (edenfox.989studios.com [160.33.45.60]) by sdmx1.scea.com (8.13.6/8.13.1) with ESMTP id m1RJ6Ne1025799; Wed, 27 Feb 2008 11:06:23 -0800 X-Envelope-From: X-Envelope-To: X-Envelope-To: Received: from postal1-dog.naughtydog.com (testmail.naughtydog.com [10.15.0.5]) by edenfox.989studios.com (8.13.7/8.13.7/SCEAint-1.0) with ESMTP id m1RJ6K1Z004126; Wed, 27 Feb 2008 11:06:21 -0800 Received: from [127.0.0.1] ([150.0.6.116]) by postal1-dog.naughtydog.com with Microsoft SMTPSVC(6.0.3790.3959); Wed, 27 Feb 2008 11:05:03 -0800 Message-ID: <47C5B3EC.1080206@naughtydog.com> Date: Wed, 27 Feb 2008 11:03:08 -0800 From: Pal-Kristian Engstad Reply-To: pal_engstad@naughtydog.com User-Agent: Thunderbird 2.0.0.9 (Windows/20071031) MIME-Version: 1.0 To: Loup Vaillant Cc: Caml List Subject: Re: [Caml-list] Unexpected restriction in "let rec" expressions References: <6f9f8f4a0802260424o5bce2fd9i89fbfa38bb239a6a@mail.gmail.com> In-Reply-To: <6f9f8f4a0802260424o5bce2fd9i89fbfa38bb239a6a@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-OriginalArrivalTime: 27 Feb 2008 19:05:03.0278 (UTC) FILETIME=[A85AC4E0:01C87973] X-Scanned-By: MIMEDefang 2.48 on 160.33.44.36 X-Scanned-By: MIMEDefang 2.62 on 160.33.45.60 X-BorderEnvelope-To: X-BorderEnvelope-To: X-Miltered: at concorde with ID 47C5B4B3.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; haskell:01 pointers:01 pointer:01 haskell:01 compiler:01 recursive:01 pke:01 dog:98 wrote:01 rec:01 caml-list:01 immutable:01 immutable:01 undefined:01 pair:01 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