From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id IAA27757; Thu, 2 May 2002 08:52:04 +0200 (MET DST)
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id IAA27752 for caml-list@pauillac.inria.fr; Thu, 2 May 2002 08:52:03 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id EAA25867 for <caml-list@pauillac.inria.fr>; Thu, 2 May 2002 04:12:53 +0200 (MET DST)
Received: from laurelin.dementia.org ([208.167.88.73])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g422CpX00569
	for <caml-list@inria.fr>; Thu, 2 May 2002 04:12:51 +0200 (MET DST)
Received: (from jprevost@localhost)
	by laurelin.dementia.org (8.11.6/8.11.6) id g422I8n67170;
	Wed, 1 May 2002 22:18:08 -0400 (EDT)
	(envelope-from visigoth@cs.cmu.edu)
X-Authentication-Warning: laurelin.dementia.org: jprevost set sender to visigoth@cs.cmu.edu using -f
To: OCaml Mailing list <caml-list@inria.fr>
Subject: Re: [Caml-list] Breaking out of iterative loops
References: <20020430202706.GA6791@vincent>
	<200204302331.32905.johan.baltie@wanadoo.fr>
	<3CD08EE3.9010202@ozemail.com.au>
From: John Prevost <visigoth@cs.cmu.edu>
Date: 01 May 2002 22:18:07 -0400
In-Reply-To: <3CD08EE3.9010202@ozemail.com.au>
Message-ID: <863cxbmgww.fsf@laurelin.dementia.org>
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

>>>>> "js" == John Max Skaller <skaller@ozemail.com.au> writes:

    js> the particular example that bugs me the most is this one:

    js> List.fold_left (&&) true (List.map2 pred a b)

    js> What is the input data were infinite?  Hmmm .. in an eager
    js> language, the usual functional decomposition is useless.

    js> CPS is looking better every day :-)

Another way to handle this is to use a datastructure that's meant to
work in this situation, rather than lists.  (To be honest, I somewhat
dislike the ability to define recursive datastructures in O'Caml for
this reason.)

module Stream =
  struct

    type 'a t = unit -> 'a cell
     and 'a cell = Nil | Cons of 'a * 'a t

    let decons s = s ()

    let cons h t = fun () -> Cons (h, t)

    let rec append a b = fun () ->
      match decons a with
        | Nil -> decons b
        | Cons (h, t) -> Cons (h, append t b)

    let rec map f l = fun () ->
      match decons l with
        | Nil -> Nil
        | Cons (h, t) -> Cons (f h, map f t)

    (* ... etc ... *)

  end

A smarter implementation (I just threw this off the top of my head)
would include remembering already accessed values and the like (lazy
evaluation).  With such a data structure, designed for infinities,
processing infinite values is easier.

The drawback to allowing:

let rec ones = 1 :: ones

and such expressions is that when looking at the definition of, for
example, 'a list and length, one would expect it to be guaranteed that
length terminates.  Since you can't prevent recursive use of
constructors, well, you can no longer guarantee that.

John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners