From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: weis Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA04759 for caml-redistribution; Wed, 13 Jan 1999 19:09:38 +0100 (MET) 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 TAA28745 for ; Wed, 13 Jan 1999 19:06:43 +0100 (MET) Received: from mcfs.whowhere.com (mcfs.whowhere.com [209.1.236.44]) by concorde.inria.fr (8.8.7/8.8.7) with SMTP id TAA13948 for ; Wed, 13 Jan 1999 19:06:41 +0100 (MET) Received: from Unknown/Local ([?.?.?.?]) by my-dejanews.com; Wed Jan 13 09:40:39 1999 To: caml-list@pauillac.inria.fr Date: Wed, 13 Jan 1999 17:40:39 -0000 From: "Marc Rouaix" Message-ID: Mime-Version: 1.0 X-Sent-Mail: off X-Mailer: MailCity Service Subject: Re: Map is not tail recursive X-Sender-Ip: 134.10.2.18 Organization: Deja News Mail (http://www.my-dejanews.com:80) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: weis It looks like this didn't get sent the first time. I made the suggestion of using a map function that maps chunks of the list at a time. Also, in a separate mail, I suggested using a map function that tested the length of the list and then chose what function to invoke, but I suppose that's a questionable strategy since finding the length of a list requires traversing it. Anyway... (* returns nth cons of a list, or [] if there is no such cons *) let rec nth_tail ls n = if n = 0 then ls else match ls with [] -> [] | x::xs -> nth_tail xs (n-1) (* jump_map n should compute the same function as List.map for any n>0. But jump_map n will use min(list_size, n+list_size/n) stack space whereas List.map uses list_size stack space. jump_map costs an extra list traversal compared to List.map. *) let rec jump_map jump fn lst = let rec do_a_chunk last stub chunk = if chunk == last then stub else (fn (List.hd chunk))::(do_a_chunk last stub (List.tl chunk)) in if lst == [] then [] else let last = nth_tail lst jump in do_a_chunk last (jump_map jump fn last) lst (* It may be a bad idea to use this because of the cost of List.length, but you get the idea. *) let general_map fn lst = let n = List.length lst in if n < 1000 then List.map fn lst else jump_map (truncate (sqrt (float n))) fn lst --- Marc -----== Sent via Deja News, The Discussion Network ==----- http://www.dejanews.com/ Easy access to 50,000+ discussion forums