[proposal] foldr1/foldl1

[Elifant]

Hello all.

I propose to add functions like Haskell's foldr1 and foldl1 to standard
library. They are very convenient
when result has the same type and element type has no "zero" value with
respect to the applied operation.

Example:
Within macro call I have a list of expressions (with type PExpr) "e1,
e2, ..., eN" and I need to get expression
"((e1 + e2) + ...) + eN". FoldLeft can't be used directly, since <[]>
can't be used as a starting value.
With FoldLeft: def sum = FoldLeft(exprs.Tail, exprs.Head, (el, er) => <[
$el + $er ]>)
With FoldLeft1: def sum = FoldLeft1(exprs, (el, er) => <[ $el + $er ]>)

Don't know whether these functions must have a different name or just be
an overload of FoldLeft and FoldRight.
Reference implementation:

def FoldLeft1 ['a'] (l: list['a], f: 'a * 'a -> 'a): 'a
FoldLeft(l.Tail, l.Head, f)

// This one may be implemented more efficiently, I think...
def FoldRight1 ['a'] (l: list['a], f: 'a * 'a -> 'a): 'a
def (rest, last) = DivideLast(l)
FoldRight(rest, last, f)

[Kamil Skalski]

Very nice functions indeed. It would be also nice to have a general
extension methods operating on IEnumerable [T] doing the same things,
so the functionality won't be limited to lists (which should have
their own specialized implementation as you provided).

Will you commit the changes or prepare a patch?

Post by Elifant
Hello all.
I propose to add functions like Haskell's foldr1 and foldl1 to standard
library. They are very convenient
when result has the same type and element type has no "zero" value with
respect to the applied operation.
Within macro call I have a list of expressions (with type PExpr) "e1,
e2, ..., eN" and I need to get expression
"((e1 + e2) + ...) + eN". FoldLeft can't be used directly, since <[]>
can't be used as a starting value.
With FoldLeft: def sum = FoldLeft(exprs.Tail, exprs.Head, (el, er) => <[
$el + $er ]>)
With FoldLeft1: def sum = FoldLeft1(exprs, (el, er) => <[ $el + $er ]>)
Don't know whether these functions must have a different name or just be
an overload of FoldLeft and FoldRight.
def FoldLeft1 ['a'] (l: list['a], f: 'a * 'a -> 'a): 'a
FoldLeft(l.Tail, l.Head, f)
// This one may be implemented more efficiently, I think...
def FoldRight1 ['a'] (l: list['a], f: 'a * 'a -> 'a): 'a
def (rest, last) = DivideLast(l)
FoldRight(rest, last, f)
_______________________________________________
https://nemerle.org/mailman/listinfo/devel-en

[Elifant]

Post by Kamil Skalski
Very nice functions indeed. It would be also nice to have a general
extension methods operating on IEnumerable [T] doing the same things,
so the functionality won't be limited to lists (which should have
their own specialized implementation as you provided).

So how to name it? FoldLeft1 or FoldLeft overload?

Post by Kamil Skalski
Will you commit the changes or prepare a patch?

I can commit. Is SVN public-writeable?

Post by Kamil Skalski

Post by Elifant
I propose to add functions like Haskell's foldr1 and foldl1 to standard
library. They are very convenient
when result has the same type and element type has no "zero" value with
respect to the applied operation.

[Kamil Skalski]

I think that FoldLeft and FoldRight are ok - the overloading
resolution will work fine for them, especially since they have
different number of parameters than existing ones.

Please send me a hash generated at
https://nemerle.org/svnaccount.php

Post by Elifant

Post by Kamil Skalski
Very nice functions indeed. It would be also nice to have a general
extension methods operating on IEnumerable [T] doing the same things,
so the functionality won't be limited to lists (which should have
their own specialized implementation as you provided).

So how to name it? FoldLeft1 or FoldLeft overload?

Post by Kamil Skalski
Will you commit the changes or prepare a patch?

I can commit. Is SVN public-writeable?

Post by Kamil Skalski

Post by Elifant
I propose to add functions like Haskell's foldr1 and foldl1 to standard
library. They are very convenient
when result has the same type and element type has no "zero" value with
respect to the applied operation.

_______________________________________________
https://nemerle.org/mailman/listinfo/devel-en

[Elifant]

Post by Elifant

Post by Kamil Skalski
Will you commit the changes or prepare a patch?

I can commit. Is SVN public-writeable?

Unfortunately, I am sticked to Mono 1.2.2.1, so I can't compile Nemerle
and check changes.
Thus I've attached patch, please verify and apply.

IEnumerable.FoldRight is implemented using temporary array (just because
existing FoldRight
does that) instead of recursion. Is it preferred way?


BTW, I was surprised by the argument order of callback function. I was
expecting that

[a, b, c, d].FoldLeft(@>>) produces (((a >> b) >> c) >> d), and
[a, b, c, d].FoldRight(@>>) produces (a >> (b >> (c >> d)))

but in fact I need to use [a, b, c, d].FoldLeft((elem, acc) => acc >> elem)

Haskell, for example, has following (convenient) signatures:
Prelude.foldl :: (a -> b -> a) -> a -> [b] -> a -- accumulator is on
the left
Prelude.foldr :: (a -> b -> b) -> b -> [a] -> b -- accumulator is on
the right

This change will break backward compatibility, but you did it several
times already,
so I hope you will want to make this change now, until it is too late.
To be clear, this change isn't included to the patch, this is just a
proposal.

Thanks for attention.

[Kamil Skalski]

+ while (not_end)
+ accum = convert(value, accum);
+ not_end = enumerator.MoveNext ();

Looks like you are missing the { }

It would be nice to have also a patch for tests in
nemerle/lib/tests/
or
nemerle/ncc/testsuite/positive/collections.n

Otherwise it looks ok, but I think the best approach is to have the
tests and then we can easily apply it to trunk and check if it
compiles fine and the tests are passing.

Post by Elifant
IEnumerable.FoldRight is implemented using temporary array (just because
existing FoldRight
does that) instead of recursion. Is it preferred way?

Yes, since we can avoid stack overflow and AFAIR allocation of a temp
array is not very costly. What I'm not sure about is how the
source.ToArray ();
performs. I guess it does another temporary allocations and given that
it should be possible to use the same method directly and not allocate
the array.

Post by Elifant
BTW, I was surprised by the argument order of callback function. I was
expecting that

I'm afraid it is too large breaking change, since for cases when acc
type is the same as value type user will not every know that something
changed and his program will start behaving unexpectedly.
Maybe create another function for that, howevery I don't like this too
much, we should stick to single parameters order in all fuctions and
AFAIR there are many functions with similar signature.

Post by Elifant
but in fact I need to use [a, b, c, d].FoldLeft((elem, acc) => acc >> elem)
Prelude.foldl :: (a -> b -> a) -> a -> [b] -> a -- accumulator is on
the left
Prelude.foldr :: (a -> b -> b) -> b -> [a] -> b -- accumulator is on
the right
This change will break backward compatibility, but you did it several
times already,
so I hope you will want to make this change now, until it is too late.
To be clear, this change isn't included to the patch, this is just a
proposal.
Thanks for attention.
_______________________________________________
https://nemerle.org/mailman/listinfo/devel-en

[Elifant]

Post by Kamil Skalski
+ while (not_end)
+ accum = convert(value, accum);
+ not_end = enumerator.MoveNext ();
Looks like you are missing the { }

Will fix.

Post by Kamil Skalski
It would be nice to have also a patch for tests in
nemerle/lib/tests/
or
nemerle/ncc/testsuite/positive/collections.n

Ok, I'll add them and will send new patch soon.

Post by Kamil Skalski
I'm afraid it is too large breaking change, since for cases when acc
type is the same as value type user will not every know that something
changed and his program will start behaving unexpectedly.

Ok, I understand.

[Michal Moskal]

Post by Elifant
IEnumerable.FoldRight is implemented using temporary array (just because
existing FoldRight
does that) instead of recursion. Is it preferred way?

Yes, because the IEnumerable can be large, and using recursion could
cause the stack to overflow.

Post by Elifant
BTW, I was surprised by the argument order of callback function. I was
expecting that
but in fact I need to use [a, b, c, d].FoldLeft((elem, acc) => acc >> elem)
Prelude.foldl :: (a -> b -> a) -> a -> [b] -> a -- accumulator is on
the left
Prelude.foldr :: (a -> b -> b) -> b -> [a] -> b -- accumulator is on
the right

There is a reason :-)

In Haskell you use: "foldl f ini lst" -- you pass initial accumulator
before the list, so also the callback takes the accumulator before the
element of the list. In Nemerle, OTOH you write: "lst.FoldLeft(ini,
f)", so the list goes before the accumulator in both function
invocation and the callback.

The callback goes last in Nemerle for two reasons: 1/ it is most
likely the longest expression in invocation, so you don't want any
stuff hanging around after it, and 2/ in Nemerle partial application
can be applied to any argument with the same ease, unlike in ML, so
you can write _.FoldLeft (0, f) and get a function.

Post by Elifant
This change will break backward compatibility, but you did it several
times already,
so I hope you will want to make this change now, until it is too late.

We've already changed that something like two years ago, for the
reasons described above.

[Elifant]

Post by Michal Moskal

Post by Elifant
BTW, I was surprised by the argument order of callback function.

In Haskell you use: "foldl f ini lst" -- you pass initial accumulator
before the list, so also the callback takes the accumulator before the
element of the list. In Nemerle, OTOH you write: "lst.FoldLeft(ini,
f)", so the list goes before the accumulator in both function
invocation and the callback.

Sorry, I don't understand this argument.

There is no relation to the absolute list-accumulator order. Even if
Haskell foldl has
signature like in Nemerle:
foldl :: [b] -> (a -> b -> a) -> a -> a
it is still more convenient than
foldl :: [b] -> (a -> a -> b) -> a -> a
because you can write "foldl [2, 3, 4] (>>)" 1 to get "(((1 >> 2) >> 3)

Post by Michal Moskal

Post by Elifant
4)

instead of "foldl [2, 3, 4] (flip (>>)) 1"

It is just more intuitive to have accumulator on the left when folding
from left to right, and
accumulator on the right when folding from right to left.

But I understand, that this is too breaking change, I just wanted to
know motivation.

[Sandro Magi]

I have implementations of map, filter and foldr for IEnumerable in my
FP# library:

http://fpsharp.svn.sourceforge.net/viewvc/fpsharp/trunk/FP.Fn/Fn.cs?view=markup

Perhaps they might be of use.

Sandro

Post by Kamil Skalski
Very nice functions indeed. It would be also nice to have a general
extension methods operating on IEnumerable [T] doing the same things,
so the functionality won't be limited to lists (which should have
their own specialized implementation as you provided).
Will you commit the changes or prepare a patch?

Post by Elifant
Hello all.
I propose to add functions like Haskell's foldr1 and foldl1 to standard
library. They are very convenient
when result has the same type and element type has no "zero" value with
respect to the applied operation.
Within macro call I have a list of expressions (with type PExpr) "e1,
e2, ..., eN" and I need to get expression
"((e1 + e2) + ...) + eN". FoldLeft can't be used directly, since <[]>
can't be used as a starting value.
With FoldLeft: def sum = FoldLeft(exprs.Tail, exprs.Head, (el, er) => <[
$el + $er ]>)
With FoldLeft1: def sum = FoldLeft1(exprs, (el, er) => <[ $el + $er ]>)
Don't know whether these functions must have a different name or just be
an overload of FoldLeft and FoldRight.
def FoldLeft1 ['a'] (l: list['a], f: 'a * 'a -> 'a): 'a
FoldLeft(l.Tail, l.Head, f)
// This one may be implemented more efficiently, I think...
def FoldRight1 ['a'] (l: list['a], f: 'a * 'a -> 'a): 'a
def (rest, last) = DivideLast(l)
FoldRight(rest, last, f)
_______________________________________________
https://nemerle.org/mailman/listinfo/devel-en