Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Recursive lists
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Christophe Raffalli <christophe.raffalli@u...>
Subject: Re: [Caml-list] About Obj (was Recursive lists)
james woodyatt wrote:
> On 11 Oct 2004, at 06:38, Christophe Raffalli wrote:
> 
>> Jean-Christophe Filliatre wrote [quite sensibly]:
>>
>>>
>>> [...]
>>> This shouldn't be advised, and not even posted on this list.
>>
>>
>> And how do you write a tail recursive map doing only one structure 
>> traversal (which is important with the penalty for memory access) on 
>> immutable list without the Obj module ?
> 
> 
> By using a more appropriate data structure, e.g. a lazy list.  It's a 
> pay-me-now-or-pay-me-later sort of game you're playing here.
> 
> Rather than whack on the immutable list, maybe you should consider doing 
> this:
> 
>     type 'a mlist = N | C of 'a mcell
>     and 'a mcell = { mutable cdr: 'a; mutable car: 'a mlist }

This data structure uses 5 words and 2 indirection per cons cell 
(instead of 3 and 1 for standard list). So it will be slower on all 
operations. Moreover you may want immutable list with tail recursive and 
  one mono-traversal map and fold_right.




-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature
---------------------------------------------

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