ocaml-lib-devel

[Ocaml-lib-devel] Proposal: List.map_reduce

[<sp...@sc...>]

Hi all,

I found myself working with lists containing polymorphic variants, and 
I've found the following simple function very useful for improving the 
readability of my code (examples are in revised syntax since I've 
forgotten the "old" syntax):

    value map_reduce op zero map_f list =
       (List.fold_left op zero (List.filter_map map_f list));

This may of course be defined slightly more efficiently as

   value map_reduce op zero map_f list =
         (List.fold_left
            (fun acc av ->
               (match map_f av with
                  [ Some x -> op acc x
                  | None -> acc ]))
            zero
            list);

which avoids the creation of a temporary list.

Here's an example of usage: Let's say I have a polymorphic variant

	type t = [= `A of int | `B of bool | `C of int ]

and I have a list containing values of type t, say

         lst = [ `A 5 ; `A 2 ; `B false ; `B true ; `C 3 ]

and I want to extract and combine the values of the different variant 
values in different ways. Using both fold_left and filter_map this looks 
like

   let a_total = List.fold_left (\+) 0
  	(List.filter_map (fun [ `A x -> Some x | _ -> None ]) lst);
   let c_max = List.fold_left max 0
	(List.filter_map (fun [ `A x -> Some x | _ -> None ]) lst);
   let b = List.fold_left (\||) False
         (List.filter_map (fun [ `B x -> Some x | _ -> None ]) lst);

With map_reduce this becomes

   let a_total =
	map_reduce (\+) 0 (fun [ `A x -> Some x | _ -> None ]) lst;
   let c_max =
	map_reduce max 0 (fun [ `A x -> Some x | _ -> None ]) lst;
   let b =
	map_reduce (\||) False (fun [ `B x -> Some x | _ -> None ]) lst;

which I think is more readable since it removes noise (the extra 
parantheses and the "superfluous" call to a second function). If you 
want to get rid of the temporary list creations the version without 
map_reduce of course gets much, much uglier.

Do you think this should be added to ExtLib.ExtList, or is it too 
"specialized"?

-- 
Bardur Arantsson
<bar...@TH...>

There is no truth, only facts to be manipulated.
                                S.E. Corff, NSA Collection Manager

Re: [Ocaml-lib-devel] Proposal: List.map_reduce

[Jonathan R. <jon...@gm...>]

> Do you think this should be added to ExtLib.ExtList, or is it too
> "specialized"?

I don't think so. fold_reduce is a more general case of map_reduce.

Jonathan

Re: [Ocaml-lib-devel] Proposal: List.map_reduce

[<sp...@sc...>]

Jonathan Roewen wrote:
>> Do you think this should be added to ExtLib.ExtList, or is it too
>> "specialized"?
> 
> I don't think so. fold_reduce is a more general case of map_reduce.
> 

fold_reduce? Do you mean fold? If not, then what does the fold_reduce 
you're thinking of look like?

Anyway, I'm well aware that the reduce is a just special case of fold 
(where you assume that the folded function is "fully associative" by not 
specifying a fold "direction"). That's not the point, though.

The point is that combining the map with a reduce you get lighter syntax 
all the _usage sites_ where you can use the idiom and that it is 
slightly better efficiency-wise for huge lists. There is also precedent 
for this kind of thing -- see ExtList.filter_map.

Cheers,

-- 
Bardur Arantsson
<bar...@TH...>

Absolutely no one can sex a lobster without cutting it open.
                                       rusty @ http://kuro5hin.org

Re: [Ocaml-lib-devel] Proposal: List.map_reduce

[Jonathan R. <jon...@gm...>]

> fold_reduce? Do you mean fold? If not, then what does the fold_reduce
> you're thinking of look like?

Oops, sorry. fold is reduce :-) And I meant no, I don't think it's too
specialised.

I'm not sure about the name, as it's a fold that filters & maps
elements in a single step.

And in terms of readability and thinking about it some more, I don't
see why something like the following aren't suitable:

let a_total = List.fold_left (fun acc -> function `A x -> acc + x | _
-> acc) 0 list;;
let c_max = List.fold_left (fun acc -> function `C x -> max acc x | _
-> acc) min_int list;;
let b = List.fold_left (fun acc -> function `B x -> acc || x | _ ->
acc) false list;;

They all convey exactly what they're trying to achieve. Perhaps there
are more complicated cases in real life programming, but imo, I think
they're a little nicer, and probably more efficient than your
implementation.

> There is also precedent
> for this kind of thing -- see ExtList.filter_map.

I think this is different, as the naive approach of filtering, then
mapping can be considerably slower than combining the two.

Jonathan

Re: [Ocaml-lib-devel] Proposal: List.map_reduce

[<sp...@sc...>]

Jonathan Roewen wrote:
>> fold_reduce? Do you mean fold? If not, then what does the fold_reduce
>> you're thinking of look like?
> 
> Oops, sorry. fold is reduce :-) And I meant no, I don't think it's too
> specialised.
> 

Ah, ok.

> I'm not sure about the name, as it's a fold that filters & maps
> elements in a single step.

Google seems to like the name ;)

    http://labs.google.com/papers/mapreduce.html

Well, alright, it's not _exactly_ the same thing...

> 
> And in terms of readability and thinking about it some more, I don't
> see why something like the following aren't suitable:
> 
> let a_total = List.fold_left (fun acc -> function `A x -> acc + x | _
> -> acc) 0 list;;
> let c_max = List.fold_left (fun acc -> function `C x -> max acc x | _
> -> acc) min_int list;;
> let b = List.fold_left (fun acc -> function `B x -> acc || x | _ ->
> acc) false list;;
> 
> They all convey exactly what they're trying to achieve. Perhaps there

To me this seems like "overspecifying the solution" since fold_left 
_must_ by definition work in a particular way, and you're also 
(implicitly) specifying the associativity of the operator, you have an 
explicit accumulator adding noise, etc. I wanted the "map_reduce" name 
to convey that I don't _care_ how the solution is arrived at, I just 
want the solution ;)

In particular, when reading the code above the reader may think that it 
is crucial that the operations happen in exactly the right order when it 
actually doesn't. (Of course, I'm generalizing to complex operators and 
mapping functions since pretty much everyone knows the properties of || 
and max)

> are more complicated cases in real life programming, but imo, I think
> they're a little nicer, and probably more efficient than your
> implementation.
> 
>> There is also precedent
>> for this kind of thing -- see ExtList.filter_map.
> 
> I think this is different, as the naive approach of filtering, then
> mapping can be considerably slower than combining the two.

That's true.

-- 
Bardur Arantsson
<bar...@TH...>

- Women... can't live with 'em... can't shoot 'em.
                                  Al Bundy / Married With Children

Re: [Ocaml-lib-devel] Proposal: List.map_reduce

[Florian H. <ha...@bi...>]

B=E1r=F0ur =C1rantsson wrote:
> Google seems to like the name ;)

You might also want to look at this:

http://lambda-the-ultimate.org/node/1669

Yours, Florian