Re: [Caml-list] Queens examples

["Laurent Chéno" <laurent.cheno@noos.fr>]

(* please excuse my poor english *)

Le dimanche 26 août 2001, à 01:33, Gerd Stolpmann a écrit :

> For example, look at the definition of concmap:
>
> let rec concmap f = function
>   | [] -> []
>   | h :: t -> f h (concmap f t);;
>
> The point is that the recursive call (concmap f t) occurs within an 
> expression,
> and the current execution environment must be saved on the stack before 
> the
> self-invocation such that it is still available when the containing 
> expression
> (f h (concmap f t)) is being evaluated. This is what all programming 
> languages
> do when recursive definitions are executed.
>
> You can avoid that only by changing the algorithm, i.e. avoid concmap 
> (and
> perhaps filter_append). The simplest way is to make some parts of the 
> program
> imperative, because managing the stack effectively can be _very_ 
> difficult for
> purely functional programming.

You can avoid the stack problem by writing (still functionnaly) :

let concmap f l =
	let rec aux result = function
		| [] -> result
		| h :: t -> aux (f h result) t
	in aux [] (List.rev l) ;;

Of course, List.rev has been written with terminal recursion, like this :

let reverse l =
	let rec aux result = function
		| [] -> result
		| h :: t -> aux (h :: result) t
	in aux [] l ;;

(compare the two functions... !)

Best regards,

Laurent
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr