From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 8225D7EE25 for ; Wed, 13 Nov 2013 09:01:36 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of grazingcows@yahoo.com) identity=pra; client-ip=98.136.216.226; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="grazingcows@yahoo.com"; x-sender="grazingcows@yahoo.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of grazingcows@yahoo.com) identity=mailfrom; client-ip=98.136.216.226; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="grazingcows@yahoo.com"; x-sender="grazingcows@yahoo.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@nm32-vm3.bullet.mail.gq1.yahoo.com) identity=helo; client-ip=98.136.216.226; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="grazingcows@yahoo.com"; x-sender="postmaster@nm32-vm3.bullet.mail.gq1.yahoo.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoMOAI4xg1JiiNjieWdsb2JhbABMDYJDfFMIjSkFnxWSYYEaFg4BAQkLDAgSKoIgBQEBBAELHAQVAQIVFgsBAQMLBgUlIS8BDgEGEgYBEhKHXAEBAgkGDa0hCYMAg3FBASMDASMDiWwBBgoBAQGPUgeEMQOHV4FrjlWBKIUONVWIcHCELQ X-IPAS-Result: AoMOAI4xg1JiiNjieWdsb2JhbABMDYJDfFMIjSkFnxWSYYEaFg4BAQkLDAgSKoIgBQEBBAELHAQVAQIVFgsBAQMLBgUlIS8BDgEGEgYBEhKHXAEBAgkGDa0hCYMAg3FBASMDASMDiWwBBgoBAQGPUgeEMQOHV4FrjlWBKIUONVWIcHCELQ X-IronPort-AV: E=Sophos;i="4.93,690,1378850400"; d="scan'208,217";a="35287561" Received: from nm32-vm3.bullet.mail.gq1.yahoo.com ([98.136.216.226]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 13 Nov 2013 09:01:28 +0100 Received: from [98.137.12.55] by nm32.bullet.mail.gq1.yahoo.com with NNFMP; 13 Nov 2013 08:01:25 -0000 Received: from [98.137.12.251] by tm15.bullet.mail.gq1.yahoo.com with NNFMP; 13 Nov 2013 08:01:25 -0000 Received: from [127.0.0.1] by omp1059.mail.gq1.yahoo.com with NNFMP; 13 Nov 2013 08:01:25 -0000 X-Yahoo-Newman-Property: ymail-3 X-Yahoo-Newman-Id: 638473.82282.bm@omp1059.mail.gq1.yahoo.com Received: (qmail 53596 invoked by uid 60001); 13 Nov 2013 08:01:25 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s1024; t=1384329685; bh=EsRybud7rLCyt0sCGJG0RWQlv5gxovu33VvfDLeMGc0=; h=X-YMail-OSG:Received:X-Rocket-MIMEInfo:X-Mailer:References:Message-ID:Date:From:Reply-To:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type; b=M85KSG9qa2B6TPlTGND4gWUe51vktv6rP8A6TlOplnnr6pqq1XcpwS2Tbybve5dY67eurmiJdhCxD9IY3+ywSqkeRA90dcHgNjpSm90gKJ5yj5JR+YXD6p0cFfPyM3CqGNHs6bY4IkgY8ssB5HDgf7BUGCKBRTIjtMLvBwrJF54= DomainKey-Signature:a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=X-YMail-OSG:Received:X-Rocket-MIMEInfo:X-Mailer:References:Message-ID:Date:From:Reply-To:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type; b=6LNWmZhgEjQ6B5NJVMHzifAWjtMnkMeac4RTcm4CY7fgo99OLjWnqEbcLpehpp9UzPyoSkfM9HryUKQJXQYgUT0q8Ygrp46RAOX4dN1/nnPFPg5Fu6LRUgxaS9KK+mcsPOD4RK0FxFroPxpA55wSoMTF3hkihQ+aok8DUIn9jhM=; X-YMail-OSG: OxH5trYVM1k.3OHwN5GMxMGkgcVNDljxVjdmnohzuUGK4pl aNHKT7YZ6QumOP8jSPxZB.5VeOWKhYQyIO7nyBiEbP9zukIacw04QTlWcEjl Xlcds4WWsxpXp2kK7hspsTNNy3HibJKT4E4n2zbif5mieYkpEnVLK4EROFVI o8x2KK5NTAnew_lpN9pJitrhxp_gDd9qB.s_bGmRHyFyjB32mKqZkuXDMlFS 8zgJ0KjZoPCbjQS1fUY2MYvifB0SZRr7OTq3uJYhPSvPQ2Es5L_T5JaJwIHH w58.2Iq2GXZKs70XUjQMqfX4YxngH7a8eMALoj_Czd00billuVXB7CeWrDj5 9Ga32k0Lgi3T5lU_eagaLOrviUxOe2Wd68XsXim4n9EApN1dE3dRnaDR8VnA HCk46XwYDj5UK7e1fuPpnzpAomR7vGECrNZPOvaSuv8sgL4VqqgGwuca8_Cs uZfjiVGP.KTQZd0BNgG_9uM7puMkh1Rs8_KLc3m4EjRdEOH6ZxVskwaEzsMp o4BfmVvgTPVSp6aKvFtmuvVfm9CcQZFXKr7SuuQ5E3tOSTOrtXwQEnx0x3zM Vvz8DaYbr3Yn_Vbtz54jm0N7LjtUuk06TqKo1RQUz7XeJnc_93QbzRh8txhd DwA0qo1wz2zw1tNQnxWUVEPjea8dIN7p_nTo79_PEqHKSoQ2R4zKDun_bY2t 5vZ7hakKYfZ4JPRqqMGi1WQMPICLJ5ZPF591zu83y5HW8QERFX1b58ujR9Hl UjcwR3irAyz5.Kw.V16BdGNVOmxg4ksUzbaZ1BLzo9Q-- Received: from [67.84.46.185] by web163403.mail.gq1.yahoo.com via HTTP; Wed, 13 Nov 2013 00:01:24 PST X-Rocket-MIMEInfo: 002.001,VGhlICJzaG9ydCIgYW5zd2VyIGlzIHRoZSBkZWZpbml0aW9uIG9mICdkZWxheScgZG9lcyBub3QgaGF2ZSBhIHR5cGUgYXNzb2NpYXRpdml0eSBvciBiaW5kaW5ncy4gRm9yIGEgcmVjdXJzaXZlIGRlZmluaXRpb24gdG8gd29yayB3ZWxsLCB5b3Ugd291bGQgbmVlZCB0byByZXNvbHZlIGludG8gcHJpbWl0aXZlIHR5cGVzLiBXaGVuIHlvdSB0cnkgdG8gYWNjdW11bGF0ZSBhIGRlZmluaXRpb24gaW50cm9kdWNpbmcgbW9yZSBsYXllcnMgb2YgY29tcGxleGl0eSwgb25lIHRoaW5nIGlzIGp1c3QgbGlrZSB0aGkBMAEBAQE- X-Mailer: YahooMailWebService/0.8.163.597 References: <527D452E.90701@cs.mcgill.ca> <20131109040201.50663.qmail@www1.g3.pair.com> Message-ID: <1384329684.46964.YahooMailNeo@web163403.mail.gq1.yahoo.com> Date: Wed, 13 Nov 2013 00:01:24 -0800 (PST) From: Arkady Andrukonis Reply-To: Arkady Andrukonis To: "oleg@okmij.org" , "bpientka@cs.mcgill.ca" Cc: "caml-list@inria.fr" In-Reply-To: <20131109040201.50663.qmail@www1.g3.pair.com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="729328464-2093658091-1384329684=:46964" Subject: Re: [Caml-list] recursive records --729328464-2093658091-1384329684=:46964 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable The "short" answer is the definition of 'delay' does not have a type associ= ativity or bindings. For a recursive definition to work well, you would nee= d to resolve into primitive types. When you try to accumulate a definition = introducing more layers of complexity, one thing is just like this other (e= xample, a candle is like a wax object with a wick), we see this every day w= ith compound "of" metaphors, the type engine gets confused. You are using a= constructor to define other items, therefore it fails. In natural language= s you can get away with it, but not in programming languages. Hope this helps. Arkady On Friday, November 8, 2013 11:02 PM, "oleg@okmij.org" wro= te: =20 Brigitte Pientka wrote: > type 'a susp =3D Susp of (unit -> 'a) > > type 'a str =3D {hd: 'a=A0 ; tl : ('a str) susp} > > let rec ones =3D {hd =3D 1 ; tl =3D Susp (fun () -> ones)} > > This works fine and many examples can be elegantly written this way.=A0 H= owever, > when I define the stream ones via the function delay, OCaml fails. > >=A0 let delay f =3D Susp f >=A0 =A0 let rec ones =3D {hd =3D 1 ; tl =3D delay (fun () -> ones)};; >=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > Error: This kind of expression is not allowed as right-hand side of `let = rec' > > Could someone explain why this fails? To be fair, OCaml already provides a few relaxations for let rec definitions, which are described in Sec 7.3 of =A0 =A0 =A0 =A0 http://caml.inria.fr/pub/docs/manual-ocaml/extn.html Alain Frisch has demonstrated one such extension: lazy. I believe though there is a better way to represent your co-patterns in OCaml -- using objects. Objects are already have a fix-points in them, and objects are naturally coinductive: an object receives a message, changes its state and results in an object ready for more messages. The only think we can do with objects is to observe them, but sending them messages. This sounds just like the definition of co-induction. Here how it looks like: (* defining the class type is not necessary, but helpful. =A0 It defines the type 'a str that is useful when writing signatures. =A0 I like to write signatures *) class type ['a] str =3D object ('self) =A0 =A0 =A0 =A0 method hd : 'a =A0 =A0 =A0 =A0 method tl : 'self end;; class ones =3D object (self)=20 =A0 method hd =3D 1 =A0 method tl =3D self end ;; let ones =3D new ones;; let take : int -> 'a str -> 'a list =3D fun n str -> let rec loop acc str =3D function =A0 | n when n <=3D 0 -> List.rev acc =A0 | n -> loop (str#hd :: acc) (str#tl) (n-1) (* Co-patterns! str#hd and = str#tl *) in loop [] str n ;; take 5 ones;; =A0 - : int list =3D [1; 1; 1; 1; 1] --=20 Caml-list mailing list.=A0 Subscription management and archives: https://sympa.inria.fr/sympa/arc/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs= --729328464-2093658091-1384329684=:46964 Content-Type: text/html; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable
The "short" answer is the definition of 'delay' does not have= a type associativity or bindings. For a recursive definition to work well,= you would need to resolve into primitive types. When you try to accumulate= a definition introducing more layers of complexity, one thing is just like= this other (example, a candle is like a wax object with a wick), we see th= is every day with compound "of" metaphors, the type engine gets confused. Y= ou are using a constructor to define other items, therefore it fails. In na= tural languages you can get away with it, but not in programming languages.=

Hope this helps.

Arkady


On Friday, November = 8, 2013 11:02 PM, "oleg@okmij.org" <oleg@okmij.org> wrote:

Brigitte Pientk= a wrote:

> type 'a susp =3D Susp of= (unit -> 'a)
>
> type 'a str = =3D {hd: 'a  ; tl : ('a str) susp}
>
> let rec ones =3D {hd =3D 1 ; tl =3D Susp (fun () -> ones)}>
> This works fine and many exampl= es can be elegantly written this way.  However,
>= when I define the stream ones via the function delay, OCaml fails.
>
>  let delay f =3D Susp f
>    let rec ones =3D {hd =3D 1 ; tl =3D delay (fun () -> ones)};;
>                  ^^^^^^= ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> Error: This kind of= expression is not allowed as right-hand side of `let rec'
>
> Could someone explain why this fails?

To be fair, OCaml already provides a few rela= xations for let rec
definitions, which are described in S= ec 7.3 of
        http://caml.inria.fr/pub/docs/manual-ocaml/extn.html
Alain Frisch has demonstrated one such extension: lazy.

I believe though there is a better way to represent y= our co-patterns
in OCaml -- using objects. Objects are al= ready have a fix-points in
them, and objects are naturally coinductive: an object rece= ives a
message, changes its state and results in an objec= t ready for more
messages. The only think we can do with = objects is to observe them,
but sending them messages. Th= is sounds just like the definition of
co-induction. Here = how it looks like:

(* defining the cla= ss type is not necessary, but helpful.
  It defines= the type 'a str that is useful when writing signatures.
=   I like to write signatures
*)
c= lass type ['a] str =3D object ('self)
     = ;   method hd : 'a
        metho= d tl : 'self
end;;

c= lass ones =3D object (self)
  method hd =3D 1
  method tl =3D self
end
;;

let ones =3D new ones;;

let= take : int -> 'a str -> 'a list =3D fun n str ->
let rec loop acc str =3D function
  | n when n &= lt;=3D 0 -> List.rev acc
  | n -> loop (str#h= d :: acc) (str#tl) (n-1) (* Co-patterns! str#hd and str#tl *)
in loop [] str n
;;

take 5 ones;;
  - : int list =3D [1; 1; 1; 1;= 1]



--
Caml-list mailing lis= t.  Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Begin= ner's list: h= ttp://groups.yahoo.com/group/ocaml_beginners
Bug repo= rts: http://caml.inria.fr/bin/caml-bugs
=

= --729328464-2093658091-1384329684=:46964--