Browse thread
[Caml-list] Breaking out of iterative loops
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2002-05-02 (06:52) |
From: | John Prevost <visigoth@c...> |
Subject: | Re: [Caml-list] Breaking out of iterative loops |
>>>>> "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