Help save net neutrality! Learn more.

## ocaml-lib-devel

 [Ocaml-lib-devel] Proposal: List.map_reduce From: - 2006-08-29 19:36:57 ```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 There is no truth, only facts to be manipulated. S.E. Corff, NSA Collection Manager ```
 Re: [Ocaml-lib-devel] Proposal: List.map_reduce From: Jonathan Roewen - 2006-08-29 21:20:39 ```> 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 From: - 2006-08-30 05:10:28 ```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 Absolutely no one can sex a lobster without cutting it open. rusty @ http://kuro5hin.org ```
 Re: [Ocaml-lib-devel] Proposal: List.map_reduce From: Jonathan Roewen - 2006-08-30 10:39:13 ```> 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 From: - 2006-08-30 16:10:47 ```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 - Women... can't live with 'em... can't shoot 'em. Al Bundy / Married With Children ```
 Re: [Ocaml-lib-devel] Proposal: List.map_reduce From: Florian Hars - 2006-08-31 13:16:59 ```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 ```