Re: [Ocaml-lib-devel] Idea with ExtList.fold_right

[Brian H. <bri...@ql...>]

On Mon, 16 Jun 2003, Nicolas Cannasse wrote:

> But even like this i'm not very satisfied...

Neither am I.

> 
> Actually , here's the problem : why do people need fold_right ? ( means :
> why don't they use fold_left ? )
> Answer : because most of the time they want to build a list in the same
> order as the input list.

Um, isn't that what List.map and Enum.map are for?  Any time you're 
building up another data structure, whatever the data structure, Enum is 
probably a better answer.

Basically, the problem with fold_right is the implicit assumption that 
lists can be traversed backwards.  They can't, and fold_right is the only 
routine that assumes that.  I'm treading dangerously close to saying "if 
you're using fold_right, you're screwing up.  One of List.map, Enum.map, 
or List.fold_left is what you really want to be using."

Minor nit: can we add a List.fold defined like:
let fold = fold_left
into extlib?  This has bit me more than once, forgetting that List doesn't 
have a fold, it has a fold_left and a fold_right.



> 
> Ok, so let's provide them a "list only" version of fold_right ( ExtList.fold
> ? ) that will do the job in a tail-rec way using internals set_cdr to
> construct the list in the user-wanted way. This of course does not cover all
> the cases, but should be enough to preserve speed where it is needed (btw
> enums should be even better for this kind of things ^^;) . The difference of
> this fold is that we are iterating from left_to_right but I don't think that
> a lot of users actually wants to do so.

Well, we already have List.map to convert a 'a list to a 'b list and keep 
the order the same.  We have List.rev to convert a 'a list to a 'a list in 
reverse order.  If we added a List.rev_map, which combined the two, I 
don't see what other possibilities are needed.  More complex stuff you do 
with Enums.

let rev_map f lst =
    let rec loop curr accum =
        match curr with
            | [] -> accum
            | h :: t -> loop t ( ( f h ) :: accum )
    in
    loop lst []

This has the advantages of being a) obvious, b) efficient, and c) simple.

Hmm.  While I'm thinking about it, maybe an Enum.rev as well.  This would 
have to create an intermediate list, but would look something like:

let rev e =
    let lst = ref [] in
    let rec loop () =
        lst := (e.next ()) :: (!lst);
        loop ()
    in
    try
        loop ()
    with
        No_more_elements -> List.enum (!lst)

Jumping back to fold_right, I now think we have three choices for extlib:

- Supply the non-tail recursive version, and go "that's what the function 
is defined like- don't use it on long lists.  In fact, probably don't use 
it at all."

- Supply the list reversing version, and go "works on all lists, but uses 
a bunch of heap space.  You probably don't want to use this."

- Don't supply it at all.  Declare it fundamentally broken.

Brian