From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA02653 for caml-red; Thu, 26 Oct 2000 20:38:56 +0200 (MET DST)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA00666 for <caml-list@pauillac.inria.fr>; Thu, 26 Oct 2000 18:33:33 +0200 (MET DST)
Received: from mail.libertysurf.net (mail.libertysurf.net [213.36.80.91])
	by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id e9QGXXv03681
	for <caml-list@inria.fr>; Thu, 26 Oct 2000 18:33:33 +0200 (MET DST)
Received: from debian.castelnau.fr (213.36.70.219) by mail.libertysurf.net (5.1.053)
        id 39F5960D0003E840; Thu, 26 Oct 2000 18:32:55 +0200
Received: from hubert by debian.castelnau.fr with local (Exim 3.12 #1 (Debian))
	id 13opvF-0002y1-00; Thu, 26 Oct 2000 18:30:33 +0200
To: datta@math.berkeley.edu
Cc: caml-list@inria.fr
Subject: Re: Why Not Tail-Recursive?
References: <20001025235738.A7286@blue1.berkeley.edu>
From: hubert.fauque@wanadoo.fr
Date: 26 Oct 2000 18:30:33 +0200
In-Reply-To: Ruchira Datta's message of "Wed, 25 Oct 2000 23:57:38 -0700"
Message-ID: <87lmvbpnti.fsf@debian.castelnau.fr>
User-Agent: Gnus/5.0807 (Gnus v5.8.7) Emacs/20.7
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: weis@pauillac.inria.fr


your function deepen is not tail recursive because
the recursive call to itself is enclosed in a try..with
and the function could return by its last line
        with Done -> ()
in fact it can't return by that line if there is a recursive
call to deepen because the Done would have been catched by the
recursive deepen and the function could be considered to be
tail recursive, but the compiler doesn't know that.

a possible solution is to catch the Done in
find_subsets_of_total_weight so deepen becomes tail recursive
and there is no more a stack overflow:


let find_subsets_of_total_weight all_elts wgt_fn print_fn desired_wgt =
  let elts_sorted_by_wgt = sort_elts_by_wgt all_elts wgt_fn in
  let rec next_path ( elts_so_far, wgt_so_far, undecided_elts ) =
    match elts_so_far with
    | [] -> raise Done (* no paths left *)
    | ( elt, true ) :: other_elts ->
        let new_wgt = wgt_so_far -. wgt_fn elt in
        ( ( elt, false ) :: other_elts, new_wgt, undecided_elts )
    | ( elt, false ) :: other_elts ->
        next_path ( other_elts, wgt_so_far, elt :: undecided_elts )
  in
  let rec deepen ( elts_so_far, wgt_so_far, undecided_elts ) =
      match undecided_elts with
      | [] -> 
        let new_path = next_path ( elts_so_far, wgt_so_far, undecided_elts ) 
        in deepen new_path
      | elt :: elts ->
        let new_wgt = wgt_so_far +. wgt_fn elt in
        if new_wgt < desired_wgt then
          deepen ( ( ( elt, true ) :: elts_so_far ), new_wgt, elts )
        else if new_wgt = desired_wgt then
          let _ = print_fn ( ( elt, true ) :: elts_so_far ) in
          deepen ( ( ( elt, false ) :: elts_so_far ), wgt_so_far, elts )
        else (* new_wgt > desired_wgt *)
          let new_path = next_path ( elts_so_far, wgt_so_far, undecided_elts ) 
          in deepen new_path
  in
  try (
    deepen ( [], 0., elts_sorted_by_wgt )
   ) with Done -> ()




additionnaly in the last function the 
        close_out cout
should be outside the
     with Stack_overflow



Hubert Fauque