[Caml-list] List.fold_left vs. Hashtbl.fold

[Caml-list] List.fold_left vs. Hashtbl.fold

[William Smith]

That seems like an easy mnemonic--left means the base case argument is on the left and right means that the base case is on the right.   This is both for the parameters to fold_left/right and the parameters of its <fun> argument.  And then, if there is not _right/_left distinction available for a container, it defaults to being equivalent to _right.

Before I saw other people's explanations, I was thinking about how the parameter order fold_left is more useful for currying.

If you want to create an operator, fold_left makes it a lot easier to curry in its base case and then apply the operator to different lists that the operator is processing last.

If I wanted to do that with fold_right or the other container's folds, I would have to write a wrapper to swap the arguments--which isn't really a big deal, but it's a way that fold_left is more useful that no one mentioned.

Bill

> On Wed, Nov 28, 2012 at 6:25 PM, Gabriel Scherer
> <gabriel.scherer@gmail.com>  wrote:

> That's for the type. Regarding the implementation, fold_left applies
> the argument function starting from "the left" (the beginning) of the
> list first, while fold_right begins "on the right" (at the end): for
> some infix operator (++) :
>   fold_left (++) init [x; y; z]     is  ((init ++ x) ++ y) ++ z
>   fold_right (++) [x; y; z] init   is (x ++ (y ++ (z ++ init)))
> (The evaluation "begins" in the innermost nested parentheses)

On Wed, Nov 28, 2012 at 5:40 AM, William Smith<bills@wwayneb.com>  wrote:

> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
> parameter being the initial value... just the opposite of List.fold_left.

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Gabriel Scherer]

> Before I saw other people's explanations, I was thinking about how the
> parameter order fold_left is more useful for currying.

This is a correct observation. It is the reason why, in Haskell, both
foldl and foldr request the initial accumulator before the list. I
personally think it is a mistake because you break the nice property
that you're lifting a function-on-an-argument (either ('elem -> 'acc
-> 'acc) or ('acc -> 'elem -> 'acc)) to a function-on-the-list with
the exact same typing structure.

Designing for currying is a fragile thing to do in the general case
(you can be wrong on which argument happens to be the more often
delayed) and creates tensions with other surface API design choice
(such as putting the function argument last for syntactic
convenience). My personal opinion is that currying is overrated and we
should think about language design without currying, and with a nice
short syntax for partial application (inspired by Scala's admittedly
dubious (foo _ bar) syntax for (fun x -> foo x bar)). Labels also
provide a solution for this that is usable in OCaml APIs today (but I
think for the Language of the Future we could forget labels and use a
flexible notion of records to provide similar naming and
order-irrelevance) -- just remember to avoid optional arguments that
have other downsides.

On Fri, Nov 30, 2012 at 4:06 AM, William Smith <bills@emu-bark.com> wrote:
> That seems like an easy mnemonic--left means the base case argument is on
> the left and right means that the base case is on the right.   This is both
> for the parameters to fold_left/right and the parameters of its <fun>
> argument.  And then, if there is not _right/_left distinction available for
> a container, it defaults to being equivalent to _right.
>
> Before I saw other people's explanations, I was thinking about how the
> parameter order fold_left is more useful for currying.
>
> If you want to create an operator, fold_left makes it a lot easier to curry
> in its base case and then apply the operator to different lists that the
> operator is processing last.
>
> If I wanted to do that with fold_right or the other container's folds, I
> would have to write a wrapper to swap the arguments--which isn't really a
> big deal, but it's a way that fold_left is more useful that no one
> mentioned.
>
> Bill
>
>> On Wed, Nov 28, 2012 at 6:25 PM, Gabriel Scherer
>> <gabriel.scherer@gmail.com>  wrote:
>
>
>> That's for the type. Regarding the implementation, fold_left applies
>> the argument function starting from "the left" (the beginning) of the
>> list first, while fold_right begins "on the right" (at the end): for
>> some infix operator (++) :
>>   fold_left (++) init [x; y; z]     is  ((init ++ x) ++ y) ++ z
>>   fold_right (++) [x; y; z] init   is (x ++ (y ++ (z ++ init)))
>> (The evaluation "begins" in the innermost nested parentheses)
>
>
> On Wed, Nov 28, 2012 at 5:40 AM, William Smith<bills@wwayneb.com>  wrote:
>
>> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
>> parameter being the initial value... just the opposite of List.fold_left.
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Stefano Zacchiroli]

On Fri, Nov 30, 2012 at 10:53:21AM +0100, Gabriel Scherer wrote:
> My personal opinion is that currying is overrated

Very much agreed!

> and we should think about language design without currying, and with a
> nice short syntax for partial application (inspired by Scala's
> admittedly dubious (foo _ bar) syntax for (fun x -> foo x bar)).

... but I'm curious about this "dubious" point. Is it something that has
already been discussed in the context of OCaml and I've missed the
relevant discussion? Or is it something there are results available
elsewhere? Either way, pointers on that would be very much appreciated!

And thanks for your efforts in fueling language design discussion on
this list!, I really appreciate it and the resulting discussions.

Cheers.
-- 
Stefano Zacchiroli  . . . . . . .  zack@upsilon.cc . . . . o . . . o . o
Maître de conférences . . . . . http://upsilon.cc/zack . . . o . . . o o
Debian Project Leader . . . . . . @zack on identi.ca . . o o o . . . o .
« the first rule of tautology club is the first rule of tautology club »

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Gabriel Scherer]

> ... but I'm curious about this "dubious" point. Is it something that has
> already been discussed in the context of OCaml and I've missed the
> relevant discussion? Or is it something there are results available
> elsewhere? Either way, pointers on that would be very much appreciated!

My personal issue with Scala syntax is that the scope of the anonymous
function is entirely implicit: if you write (li.map(_ + 1)) it will
desugar into (li.map (x => x + 1)) (apparently to the first
parenthesis level), but (if (_) foo else bar) desugars to (fun x => if
x foo bar), and ((_ : Int) + 1) to (fun x => (x : Int) + 1); there is
no explicit enclosing boundary, the scope is the "smallest expression
that contains the underscore" for some notion of "containing" that I
don't find particularly intuitive on the examples above.

I think implicit scopes are a "dubious" idea and would really want an
explicit construction to mark the scope of these doubly anonymous
functions. The problem is that you have to find a really light syntax,
as the value of this construction is precisely its concision. In my
young years I used to think that Camlp4 syntax extensions could be
beneficial, and I wrote an extension for this purpose (  :
http://bluestorm.info/camlp4/pa_holes.ml.html  ). It allows to write
for example (\ \2 \1) for the swap function: (\ ... ) delimits the
abstraction scope and variable are written \n (_ would be another
compromise: less expressive on the ordering, but shorter).

Another upside of these syntax is that they give light thunking for
free: proponents of lazy evaluation like the fact that some control
construct can be defined as simple functions under a lazy stragy,
while writing
  if b (fun () -> e1) (fun () -> e2)
is too painful to be viable in ML. Well,
  if b (\ e1) (\ e2)
(using the convenition that there is always at least one parameter) is better.

> And thanks for your efforts in fueling language design discussion on
> this list!, I really appreciate it and the resulting discussions.

It's a double-edged sword: it's easy to get lost in mundane details or
ultimately void debates about "the next programming language" on a
list that is really about OCaml users. I wasn't sure already that
discussion of Scala's implicit function syntax was in-topic, but well.
I'll try to keep my side of the discussion not too long.

Daniel Bünzli wrote:
> I have the *impression* that currying is essential when you want to devise dsls and combinators that integrate naturally in the host language. But I may be wrong.

I don't know. "function application is just space" is indeed a
convenient syntax to emulate other syntaxes (for example embed a
concatenative language through cunning continuation-passing-style),
but that doesn't need to go away with non-currified functions, which
is about applying all arguments, not necessarily forcing a tupled
syntax. Only partial application would be less convenient (but you can
still explicitly define functions-that-return-functions). That would
certainly need more experimentation.

On Fri, Nov 30, 2012 at 11:06 AM, Stefano Zacchiroli <zack@upsilon.cc> wrote:
> On Fri, Nov 30, 2012 at 10:53:21AM +0100, Gabriel Scherer wrote:
>> My personal opinion is that currying is overrated
>
> Very much agreed!
>
>> and we should think about language design without currying, and with a
>> nice short syntax for partial application (inspired by Scala's
>> admittedly dubious (foo _ bar) syntax for (fun x -> foo x bar)).
>
> ... but I'm curious about this "dubious" point. Is it something that has
> already been discussed in the context of OCaml and I've missed the
> relevant discussion? Or is it something there are results available
> elsewhere? Either way, pointers on that would be very much appreciated!
>
> And thanks for your efforts in fueling language design discussion on
> this list!, I really appreciate it and the resulting discussions.
>
> Cheers.
> --
> Stefano Zacchiroli  . . . . . . .  zack@upsilon.cc . . . . o . . . o . o
> Maître de conférences . . . . . http://upsilon.cc/zack . . . o . . . o o
> Debian Project Leader . . . . . . @zack on identi.ca . . o o o . . . o .
> « the first rule of tautology club is the first rule of tautology club »
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Daniel Bünzli]

Le vendredi, 30 novembre 2012 à 17:00, Gabriel Scherer a écrit :
> I don't know. "function application is just space" is indeed a
> convenient syntax to emulate other syntaxes (for example embed a
> concatenative language through cunning continuation-passing-style),

My concern is not really about the syntax.

> but that doesn't need to go away with non-currified functions, which
> is about applying all arguments, not necessarily forcing a tupled
> syntax.

That's the point, currying allows you to build a function incrementally with things happening between each applied argument.  

This is for example very useful to meta-program other languages from OCaml (using the abstraction mechanisms and variable binders of OCaml itself). It may not be very clear (the whole program is not here, if you are interested I can mail you the whole example), but with the combinators given at the end of this message, I'm able to gradually construct a program representing a function in another language, with an arbitrary number of arguments, compile it, and then get it as regular OCaml function (Program.as_fun) that uses OCaml gound types and that can be passed around completely hiding that the function may actually not be executed by OCaml at all.

Currying gives you glue, I'm not sure you could do these kind of things without it. If you can't then currying is not overrated to me. See also http://mlton.org/Fold

Best,

Daniel

type 'a exp (* expressions constructed with combinators *)

module Program : sig
  type 'a t  
  type ('a, 'b, 'c) stage (* b is the type of the constructed function *)

  (* Note. The types enforces that only caml functions from 'a exp(s) to
   'a exp will be accepted for compilation into a program. *)

  val retb : ('a exp -> 'b) -> ('a exp -> 'b, bool , [`Bool ]) stage
  val reti : ('a exp -> 'b) -> ('a exp -> 'b, int , [`Int ]) stage
  val retf : ('a exp -> 'b) -> ('a exp -> 'b, float, [`Float]) stage

  val argb : (bool_e -> 'a, 'b, 'c) stage -> ('a, bool -> 'b, 'c) stage  
  val argi : (int_e -> 'a, 'b, 'c) stage -> ('a, int -> 'b, 'c) stage
  val argf : (float_e -> 'a, 'b, 'c) stage -> ('a, float -> 'b, 'c) stage

  val compile : ('a exp, 'b, 'a) stage -> 'b t
  val as_fun : 'a t -> 'a
  val source : 'a t -> string
end

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Daniel Bünzli]

Le vendredi, 30 novembre 2012 à 10:53, Gabriel Scherer a écrit :
> My personal opinion is that currying is overrated and we
> should think about language design without currying, and with a nice
> short syntax for partial application

I'm not so sure about that. It is true that when I miss currying in other language it's often because I want partial application, however I have the *impression* that currying is essential when you want to devise dsls and combinators that integrate naturally in the host language. But I may be wrong.

Daniel

[Caml-list] List.fold_left vs. Hashtbl.fold

[William Smith]

List.fold_left expects the List as the 3rd parameter with the second 
parameter being the initial value.

Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd 
parameter being the initial value... just the opposite of List.fold_left.

Is there a reason for this difference?   I'm having trouble remembering 
which goes which way.   If it's not a historical accident, I'd like to 
have a understanding of why they are different to help me know which is 
which.

Thanks,

Bill

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Lukasz Stafiniak]

I have this problem too. Look _very closely_ at List.fold_left and
List.fold_right. Hashtbl.fold should pretend to be like
List.fold_left, because it is not supposed to preserve the structure
of the underlying data structure in its computation, and it should be
tail-recursive.

On Wed, Nov 28, 2012 at 5:40 AM, William Smith <bills@wwayneb.com> wrote:
> List.fold_left expects the List as the 3rd parameter with the second
> parameter being the initial value.
>
> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
> parameter being the initial value... just the opposite of List.fold_left.
>
> Is there a reason for this difference?   I'm having trouble remembering
> which goes which way.   If it's not a historical accident, I'd like to have
> a understanding of why they are different to help me know which is which.
>
> Thanks,
>
> Bill

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Malcolm Matalka]

[-- Attachment #1: Type: text/plain, Size: 1297 bytes --]

Jane St Core uses labeled arguments to avoid this issue, worth considering
if you can.
On Nov 28, 2012 5:18 PM, "Lukasz Stafiniak" <lukstafi@gmail.com> wrote:

> I have this problem too. Look _very closely_ at List.fold_left and
> List.fold_right. Hashtbl.fold should pretend to be like
> List.fold_left, because it is not supposed to preserve the structure
> of the underlying data structure in its computation, and it should be
> tail-recursive.
>
> On Wed, Nov 28, 2012 at 5:40 AM, William Smith <bills@wwayneb.com> wrote:
> > List.fold_left expects the List as the 3rd parameter with the second
> > parameter being the initial value.
> >
> > Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
> > parameter being the initial value... just the opposite of List.fold_left.
> >
> > Is there a reason for this difference?   I'm having trouble remembering
> > which goes which way.   If it's not a historical accident, I'd like to
> have
> > a understanding of why they are different to help me know which is which.
> >
> > Thanks,
> >
> > Bill
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 1922 bytes --]

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[David House]

This is a perfect example of why we wrote the core library:

  https://bitbucket.org/yminsky/ocaml-core/wiki/Home

In core, most of the iteration functions take their closure argument
as a labelled ~f. So you can say List.fold_left my_list ~f:my_func, or
List.fold_left ~f:my_func my_list.

This tiny syntactic cost allows you lay out code much more logically:
sometime you have a big long list, so you don't want the name of the
function lost somewhere, way down the page. Sometimes it's the other
way round, and you have a bit lambda that you're folding with, but you
don't want the name of the list to be some anonymous bit of text a
very long way away from the word "fold".

On Wed, Nov 28, 2012 at 4:40 AM, William Smith <bills@wwayneb.com> wrote:
> List.fold_left expects the List as the 3rd parameter with the second
> parameter being the initial value.
>
> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
> parameter being the initial value... just the opposite of List.fold_left.
>
> Is there a reason for this difference?   I'm having trouble remembering
> which goes which way.   If it's not a historical accident, I'd like to have
> a understanding of why they are different to help me know which is which.
>
> Thanks,
>
> Bill
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Francois Berenger]

On 11/29/2012 01:21 AM, David House wrote:
> This is a perfect example of why we wrote the core library:
>
>    https://bitbucket.org/yminsky/ocaml-core/wiki/Home
>
> In core, most of the iteration functions take their closure argument
> as a labelled ~f. So you can say List.fold_left my_list ~f:my_func, or
> List.fold_left ~f:my_func my_list.

For those who only need labels, there are:

Module MoreLabels.Hashtbl
http://caml.inria.fr/pub/docs/manual-ocaml/libref/MoreLabels.Hashtbl.html

and

Module ListLabels
http://caml.inria.fr/pub/docs/manual-ocaml/libref/ListLabels.html

> This tiny syntactic cost allows you lay out code much more logically:
> sometime you have a big long list, so you don't want the name of the
> function lost somewhere, way down the page. Sometimes it's the other
> way round, and you have a bit lambda that you're folding with, but you
> don't want the name of the list to be some anonymous bit of text a
> very long way away from the word "fold".
>
> On Wed, Nov 28, 2012 at 4:40 AM, William Smith <bills@wwayneb.com> wrote:
>> List.fold_left expects the List as the 3rd parameter with the second
>> parameter being the initial value.
>>
>> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
>> parameter being the initial value... just the opposite of List.fold_left.
>>
>> Is there a reason for this difference?   I'm having trouble remembering
>> which goes which way.   If it's not a historical accident, I'd like to have
>> a understanding of why they are different to help me know which is which.
>>
>> Thanks,
>>
>> Bill
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Oliver Bandel]

[-- Attachment #1: Type: text/plain, Size: 1995 bytes --]

As both functions are working different, I,think from some reasoing about it, it might become logical ....

http://www.cs.cornell.edu/courses/cs3110/2011sp/recitations/rec05.htm

Even there is explained how which functionsmlooks like if implemented,
the reason is not obvious.
I think there might be a logical explanation for this,
but to be honest I also have no handy rule of thumb for it.

But both functions look different in the application of the non-tail argument,
so I think this is  the reason for it (if not by accident;-))

If you find an easy way to remember it from the above mentioned doc, please let me know.
athe üroblem there in the doc is, that the program structure is cluttered by type annotations.

But maybe writng down how an application would look like,
applying the function by hand, would offer the mysteries.

I just was to lazy for this until now, and just accepted the order.
So I also need to look up the order in the manual.

But from the different non-tail part of the functions I would think, it is possible to find a reason.
After you find it, you maybe dont want to have a unified API ;-)

Ciao,
   Oliver


Am 28.11.2012 um 05:40 schrieb William Smith <bills@wwayneb.com>:

> List.fold_left expects the List as the 3rd parameter with the second parameter being the initial value.
> 
> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd parameter being the initial value... just the opposite of List.fold_left.
> 
> Is there a reason for this difference?   I'm having trouble remembering which goes which way.   If it's not a historical accident, I'd like to have a understanding of why they are different to help me know which is which.
> 
> Thanks,
> 
> Bill
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 9761 bytes --]

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Adrien]

Well, MoreLabels.Hashtbl has
  val  fold  : f:(key:'a -> data:'b -> 'c -> 'c) -> ('a, 'b) t -> init:'c -> 'c

-- 
Adrien Nader

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Virgile Prevosto]

2012/11/28 Adrien <camaradetux@gmail.com>:
> Well, MoreLabels.Hashtbl has
>   val  fold  : f:(key:'a -> data:'b -> 'c -> 'c) -> ('a, 'b) t -> init:'c -> 'c
>

Fair enough, but there's no label (say acc) to the last argument of f
(nor for the table itself), so you can't really permute the current
element and the accumulator in the argument list.

-- 
E tutto per oggi, a la prossima volta
Virgile

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Jacques Garrigue]

On 2012/11/29, at 1:41, Virgile Prevosto <virgile.prevosto@m4x.org> wrote:

> 2012/11/28 Adrien <camaradetux@gmail.com>:
>> Well, MoreLabels.Hashtbl has
>>  val  fold  : f:(key:'a -> data:'b -> 'c -> 'c) -> ('a, 'b) t -> init:'c -> 'c
>> 
> 
> Fair enough, but there's no label (say acc) to the last argument of f
> (nor for the table itself), so you can't really permute the current
> element and the accumulator in the argument list.

Not true for fold itself: no label is equivalent to the empty label,
so if you write "fold t" you are partially applying to the table.
On the other hand, changing parameter order is not allowed
in functions passed as argument. So reordering of arguments to
f is not automatic. But at least it ensures that you do not get it wrong.

Also a good reason to use labels in fold is when both remaining arguments
have the same type:

  List.fold_left (fun l x -> if List.mem x l then l else x::l)

since the accumulator and the input list have the same type, I'm always
afraid of getting them wrong (ending up doing nothing).

	Jacques Garrigue

[Caml-list] List.fold_left vs. Hashtbl.fold

[Gabriel Scherer]

(Sorry for duplicate send.)

There are two exported way to fold over lists:
  fold_left : ('acc -> 'e -> 'acc) -> ('acc -> 'e list -> 'acc)
  fold_right : ('e -> 'acc -> 'acc) -> ('e list -> 'acc -> 'acc)

The _left and _right suffixes indicate whether the "accumulator"
argument (the partial result of what has been folded so far) is passed
as the left or the right parameter of the function argument: ('acc ->
'e -> 'acc) for left, ('e -> 'acc -> 'acc) for right. The return type
of fold then lifts this argument type from processing an element to
processing the whole list: the initial 'acc value for is passed "on
the left" for fold_left (before the list argument), "on the right" for
fold_right (after the list argument).

That's for the type. Regarding the implementation, fold_left applies
the argument function starting from "the left" (the beginning) of the
list first, while fold_right begins "on the right" (at the end): for
some infix operator (++) :
  fold_left (++) init [x; y; z]     is  ((init ++ x) ++ y) ++ z
  fold_right (++) [x; y; z] init   is (x ++ (y ++ (z ++ init)))
(The evaluation "begins" in the innermost nested parentheses)

Those two iterations techniques are available for linear data
structures (those that essentially look like lists). For more general
algebraic datatypes there is a canonical "folding" method, that
happens to coincide with fold_right on lists. The reason why
fold_right is "canonical" is that it turns the list
  x :: (y :: (z :: []))
into
  (x ++ (y ++ (z ++ init)))
replacing each constructor with a passed-in operator.

This means that fold_left may not exist for arbitrary data structure
(think of binary trees), while fold_right is rather universal. Other
folding functions in the standard library (in Set and Map in
particular, but in Hashtbl as well) have therefore taken inspiration
from the fold_right structure, rather than fold_left.

On Wed, Nov 28, 2012 at 5:40 AM, William Smith <bills@wwayneb.com> wrote:
>
> Hashtbl.fold expects the Hasthbl as the second parameter with the 3rd
> parameter being the initial value... just the opposite of List.fold_left.

Re: [Caml-list] List.fold_left vs. Hashtbl.fold

[Lukasz Stafiniak]

On Wed, Nov 28, 2012 at 6:25 PM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
>
> This means that fold_left may not exist for arbitrary data structure
> (think of binary trees), while fold_right is rather universal. Other
> folding functions in the standard library (in Set and Map in
> particular, but in Hashtbl as well) have therefore taken inspiration
> from the fold_right structure, rather than fold_left.

This is right, you get my "upvote". But Set and Map do not intend to
expose the structure of the underlying data structure to the folding
computation. The folds of Set and Map traverse the elements in a
sequential order. They could be a deforested variant of List.fold_left
composed with Set.elements.