Re: [Caml-list] Breaking out of iterative loops

[John Prevost <visigoth@cs.cmu.edu>]

>>>>> "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