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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id CE95B7EE94 for ; Fri, 28 Dec 2012 13:21:37 +0100 (CET) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of philippe.wang.lists@gmail.com) identity=pra; client-ip=209.85.212.176; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="philippe.wang.lists@gmail.com"; x-sender="philippe.wang.lists@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail1-smtp-roc.national.inria.fr: domain of philippe.wang.lists@gmail.com designates 209.85.212.176 as permitted sender) identity=mailfrom; client-ip=209.85.212.176; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="philippe.wang.lists@gmail.com"; x-sender="philippe.wang.lists@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-wi0-f176.google.com) identity=helo; client-ip=209.85.212.176; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="philippe.wang.lists@gmail.com"; x-sender="postmaster@mail-wi0-f176.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmcKAH+N3VDRVdSwk2dsb2JhbAA8CasTg0yPAAgWDgEBAQEJCQsJFAQjgh4BAQQBJxkBLQsBAwELAQUFCwMDBAEBAQ0hIhIBBQEKCggGExIJh2YDCQYMmRGPLoR4JwMKiGsBBQyLYWoFDQQFhCgDjVSGZoFSgRyKG4MxFimBV4I/gWQIFw X-IronPort-AV: E=Sophos;i="4.84,369,1355094000"; d="scan'208";a="187802365" Received: from mail-wi0-f176.google.com ([209.85.212.176]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 Dec 2012 13:21:37 +0100 Received: by mail-wi0-f176.google.com with SMTP id hm6so8209805wib.3 for ; Fri, 28 Dec 2012 04:21:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type; bh=BS4wVrPJ2EBONxJc8g0L+v0HxlIrMQzI3vH9VB8hIsI=; b=GDeTh9nTOAMjIX7HWYZ0R8hmxKDH8ejtNaC74jo0iGCExmiZ0TuWacMAYXqqqTOfMy mE3mkVPjEVXGQa9ebTtnqjMP8vULLi2ZsJXgX40wpzDlRPzVYP0mOzFIHN9m5SnQ2kIN qpye2D0HsqIvSnI8fYpwYke25nM2tb46szKHTyhULr/lVDcpDPKLlUqM90W5kEYZMvgl HVzmr0yw9N80j6PjGnLbDN17l/oVChE5bWVIIG8kypMvw5h+8GeV10xH6zYQF/sOrFY1 jKg5eu5kyVFYyVbZW1q/vLe77aD5KsRs5L5+M9Ts4wF5aVOoVcF9eVkzp6ydKDteWv3k 3jxQ== MIME-Version: 1.0 Received: by 10.180.99.72 with SMTP id eo8mr45148431wib.34.1356697296878; Fri, 28 Dec 2012 04:21:36 -0800 (PST) Sender: philippe.wang.lists@gmail.com Received: by 10.216.16.82 with HTTP; Fri, 28 Dec 2012 04:21:36 -0800 (PST) In-Reply-To: <1356687451.79354.YahooMailNeo@web163402.mail.gq1.yahoo.com> References: <50D59147.3000201@ssi.gouv.fr> <1356687451.79354.YahooMailNeo@web163402.mail.gq1.yahoo.com> Date: Fri, 28 Dec 2012 13:21:36 +0100 X-Google-Sender-Auth: QMIzWAEV3B7WBB9xsMtUQNeUtqE Message-ID: From: Philippe Wang To: Arkady Andrukonis Cc: "caml-list@inria.fr" Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [Caml-list] Function returning recursive lists > let rec ls = [1; 2; 3;] :: ls ;; > it creates 40 items, > the first 38 are [1; 2; 3;] and the 39 is > [1; 2; ...]; and the last [...]. Actually, no, it does *not* create 40 items at all: the printer make no difference between circular data and big data. If one creates a list with 1000 elements, only the first X elements are displayed by "ocaml top-level interactive loop". (X depends on the size of the printed data) If the 39th is "[1; 2; ...]", it's only because the printer has reached the limit at "2" and won't go further to "see" that there's only a "3" remaining in that list. (Reminder: computers are particularly dumb, they only do (exactly) what we tell them to do.) let rec ls = [1; 2; 3;] :: ls ;; allocates [1; 2; 3;] and then a circular block (b) containing two elements: 1. a pointer to that list ([1; 2; 3;]) and 2. a pointer to itself (b). Try this: Array.to_list (Array.make 1000 42);; And maybe try this: List.length (Array.to_list (Array.make 1000 42));; Cheers, Philippe Wang On Fri, Dec 28, 2012 at 10:37 AM, Arkady Andrukonis wrote: > Hi, > > You cannot have a circular recursive definition > let rec ls = [1; 2; 3; ls; ] ;; > but you can have a "circular" list: > let rec ls = [1; 2; 3;] :: ls ;; > it creates 40 items, > the first 38 are [1; 2; 3;] and the 39 is > [1; 2; ...]; and the last [...]. > We cannot say it is a true 'circular' list, because > we don't return from the last element to the > first element. At any rate this will result > in an expression that is nested too deep and > we won't be able to use it. The ellipsis [...] has > the force of 'any' but it returns the same element > as before, a list of lists. An example of a not > very useful circular list in the literature > shows a continuous loop > let rec process = 1 :: 2 :: 3 :: 4 :: 5 :: process;; > while true do > let process :: process = process in > printf "Handling process %d\n" process; > Unix.sleep 2; > done ;; > ________________________________ > From: Peter Frey > To: Eric Jaeger (ANSSI) > Cc: caml-list@inria.fr > Sent: Thursday, December 27, 2012 8:41 PM > Subject: Re: [Caml-list] Function returning recursive lists > > On Sat, 2012-12-22 at 11:53 +0100, Eric Jaeger (ANSSI) wrote: >> On 21/12/2012 20:55, Peter Frey wrote: >> > It sometimes helps to read read the various libraries. >> > For example, this thing is a variation of Batteries.BatList.Append: >> > >> > module Cycle = struct >> > type 'a mut_list = { hd: 'a; mutable tl: 'a list } >> > external inj : 'a mut_list -> 'a list = "%identity" >> > external jni : 'a list -> 'a mut_list = "%identity" >> As far as I know, the use of "%identity" is a trick which is similar to >> Obj, telling the compiler to do nothing. You would not be allowed to do >> that with standard, typed OCaml identity. In this sense, it is not the >> sort of solution I'm looking for. >> >> Regards, Eric > > For what it's worth: Obj.ml, contains the line: > ... > external magic : 'a -> 'b = "%identity" > ... > That type allows anything, including 'unifying' any two types. > (The compiler does not do nothing: it assigns the argument of type 'a to > be the result which is of type 'b and is perfectly willing to produce > code that instantly causes a segmentation fault) > > inj and its inverse jni seem to have a type at least a bit more friendly > since they control the usage of the individual fields. > As long as you trust Ocaml lists to always have the layout above, this > seems a lot saver to me than type 'a -> 'b. > > You wanted, in effect, something like: > # let rec l = [1;2;3;l];; > Error: This expression has type int list > but an expression was expected of type int > > The type 'a list is built into the system; it is not recursive and if > there was a way to force it to be so (without hacks), the type system > would not be sound. > > You know the following, of course: > > # type 'a aRec = {mutable hd: 'a; mutable tl:'a aRec};; > type 'a aRec = { mutable hd : 'a; mutable tl : 'a aRec; } > > # let rec a = {hd=1; tl=a};; > val a : int aRec = > {hd = 1; > tl = > {hd = 1; > tl = > {hd = 1; > tl = > {hd = 1; > tl = > > The problem with docycle is not its coding style but that it produces in > fact a cyclic list, which is not very useful: Almost all functions, such > as List.rev are undefined. > > > Peter > > > > > > -- > Caml-list mailing list. 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 > > -- Philippe Wang mail@philippewang.info