www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - "fold": a replacement for "reduce"

reply "monarch_dodra" <monarchdodra gmail.com> writes:
I'm working on something called "fold". It is designed as nothing 
more than a replacement for "reduce", but where the seed comes 
*second* in terms of arguments. It allows this:

someLongUFCSChain().reduce(intoThis);

It might not look like this, but it is a *constant* source of 
nuisance. In particular, chains that start out like this:
someLongUFCSChain().reduce();
Need to be changed into this to add a seed:
reduce(someLongUFCSChain(), intoThis);

After a couple of tries to "swap" the arguments, it was observed 
that it simply couldn't be done wihthout silent run-time 
breakage. So that was not acceptable.

The solution: Re-introduce "reduce" under a new name: "fold".
Simple as that.

--------

I'm taking this naming-changing event as an opportunity to 
"cleanup" reduce too. One thing that gets on my nerves is that 
"range.reduce()" is not nothrow, because it throws an exception 
if the range is empty.

I think this is wrong. popping an empty range is an *Error*, and 
should be validated by the programmer. Because of this, it is 
currently not possible to use "reduce(range)" in nothrow context.

This however, even with a name change, it *is* change of 
behavior. Do you feel this is acceptable? Do you want this change 
at all? Or do you think an Exception is fine?
Mar 25 2014
next sibling parent reply "Graham Fawcett" <fawcett uwindsor.ca> writes:
On Tuesday, 25 March 2014 at 17:22:45 UTC, monarch_dodra wrote:

 I'm working on something called "fold". It is designed as 
 nothing more than a replacement for "reduce", but where the 
 seed comes *second* in terms of arguments. It allows this:

 someLongUFCSChain().reduce(intoThis);

 It might not look like this, but it is a *constant* source of 
 nuisance. In particular, chains that start out like this:
 someLongUFCSChain().reduce();
 Need to be changed into this to add a seed:
 reduce(someLongUFCSChain(), intoThis);

 After a couple of tries to "swap" the arguments, it was 
 observed that it simply couldn't be done wihthout silent 
 run-time breakage. So that was not acceptable.

 The solution: Re-introduce "reduce" under a new name: "fold".
 Simple as that.

 --------

 I'm taking this naming-changing event as an opportunity to 
 "cleanup" reduce too. One thing that gets on my nerves is that 
 "range.reduce()" is not nothrow, because it throws an exception 
 if the range is empty.

 I think this is wrong. popping an empty range is an *Error*, 
 and should be validated by the programmer. Because of this, it 
 is currently not possible to use "reduce(range)" in nothrow 
 context.

 This however, even with a name change, it *is* change of 
 behavior. Do you feel this is acceptable? Do you want this 
 change at all? Or do you think an Exception is fine?


My knee-jerk observation is that the documentation for 'fold' 
should indicate that it's a left fold, i.e., the sequence of 
operations associates to the left (in other words, it's 
sequence-iterative, not sequence-recursive). It's a small thing, 
but it might help Haskellers and Schemers to orient themselves.

http://srfi.schemers.org/srfi-1/srfi-1.html#fold
http://srfi.schemers.org/srfi-1/srfi-1.html#fold-right

Graham
Mar 25 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 25 March 2014 at 18:02:49 UTC, Graham Fawcett wrote:

 My knee-jerk observation is that the documentation for 'fold' 
 should indicate that it's a left fold, i.e., the sequence of 
 operations associates to the left (in other words, it's 
 sequence-iterative, not sequence-recursive). It's a small 
 thing, but it might help Haskellers and Schemers to orient 
 themselves.

 http://srfi.schemers.org/srfi-1/srfi-1.html#fold
 http://srfi.schemers.org/srfi-1/srfi-1.html#fold-right

 Graham


Will be noted.
Mar 25 2014
prev sibling next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Tuesday, 25 March 2014 at 17:22:45 UTC, monarch_dodra wrote:

 I'm working on something called "fold". It is designed as 
 nothing more than a replacement for "reduce", but where the 
 seed comes *second* in terms of arguments. It allows this:

 someLongUFCSChain().reduce(intoThis);

 It might not look like this, but it is a *constant* source of 
 nuisance. In particular, chains that start out like this:
 someLongUFCSChain().reduce();
 Need to be changed into this to add a seed:
 reduce(someLongUFCSChain(), intoThis);

 After a couple of tries to "swap" the arguments, it was 
 observed that it simply couldn't be done wihthout silent 
 run-time breakage. So that was not acceptable.

 The solution: Re-introduce "reduce" under a new name: "fold".
 Simple as that.

 --------

 I'm taking this naming-changing event as an opportunity to 
 "cleanup" reduce too. One thing that gets on my nerves is that 
 "range.reduce()" is not nothrow, because it throws an exception 
 if the range is empty.

 I think this is wrong. popping an empty range is an *Error*, 
 and should be validated by the programmer. Because of this, it 
 is currently not possible to use "reduce(range)" in nothrow 
 context.

 This however, even with a name change, it *is* change of 
 behavior. Do you feel this is acceptable? Do you want this 
 change at all? Or do you think an Exception is fine?


Sounds to me like the fact that it throws an Exception instead of 
an Error is a leftover from the earlier days of ranges, when it 
wasn't clear what one should do in the case of an empty range. I 
think it's well worth making fold nothrow, and it will simplify 
calling code in the case where the callee wrapped reduce in a 
try-catch block.
Mar 25 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 25 March 2014 at 18:21:25 UTC, Meta wrote:

 Sounds to me like the fact that it throws an Exception instead 
 of an Error is a leftover from the earlier days of ranges, when 
 it wasn't clear what one should do in the case of an empty 
 range. I think it's well worth making fold nothrow, and it will 
 simplify calling code in the case where the callee wrapped 
 reduce in a try-catch block.


Well, 1 thing I just thought of is that if you are operating on a 
"non-range iterable": Then it may not be possible to actually 
know if the iterable will loop more than once. So in this case, 
we'd have to keep the enforce for iterables...
Mar 25 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:


 I'm taking this naming-changing event as an opportunity to 
 "cleanup" reduce too. One thing that gets on my nerves is that 
 "range.reduce()" is not nothrow, because it throws an exception 
 if the range is empty.

 I think this is wrong. popping an empty range is an *Error*, 
 and should be validated by the programmer. Because of this, it 
 is currently not possible to use "reduce(range)" in nothrow 
 context.


This Haskell library shows one way Haskellers use to face similar 
problems:
http://hackage.haskell.org/package/safe-0.3.4/docs/Safe.html

Every function that could have similar problems is present in 
four forms, with the "Note", "Def", "May" and "Safe" suffixes.

An example with the standard Haskell function "tail", that is 
similar to dropOne of std.range (skips the first and returns the 
rest. The problem is when the input list is empty):

tailDef :: [a] -> [a] -> [a]
  tailDef [12] [] = [12]
  tailDef [12] [1,3,4] = [3,4]

tailMay :: [a] -> Maybe [a]
  tailMay [] = Nothing
  tailMay [1,3,4] = Just [3,4]

tailNote :: String -> [a] -> [a]
  tail "help me" [] = error "Pattern match failure, tail [], help 
me"
  tail "help me" [1,3,4] = [3,4]

tailSafe :: [a] -> [a]
  tailSafe [] = []
  tailSafe [1,3,4] = [3,4]

Bye,
bearophile
Mar 25 2014
prev sibling next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 25 March 2014 at 17:22:45 UTC, monarch_dodra wrote:

 I'm working on something called "fold". It is designed as 
 nothing more than a replacement for "reduce", but where the 
 seed comes *second* in terms of arguments. It allows this:

 someLongUFCSChain().reduce(intoThis);


Good! I've been greatly disturbed by this too.

Especially by the fact that reduce throws upon empty input 
because it currently has no way of deducing return value. This 
can be a greatly annoying "surprise" to new users.

 From algebra we learn the following relations:

Operator Unit
+,(-)    0
*,(/)    1
min      T.max
max      T.min
..

I guess typeof return value could be deduced according + and * at 
least.

Have you perhaps found a way to deduce it in the general case 
using the reduce function and ElementType of input range, 
something like

     typeof(binaryFun(E, E))

where

     alias E = ElementType!R,

I thought about adding an overload for reduce using template 
restriction that would solve the problem without adding a new 
function. But I guess that adding such an overload could cause 
just as much confusion to programmers who are used to the current 
syntax.
Mar 25 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
Correction:


 I guess typeof return value could be deduced according + and * 
 at least.


Return type is of course obvious, value is not...
Mar 25 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 25 March 2014 at 20:37:31 UTC, Nordlöw wrote:

 Correction:


 I guess typeof return value could be deduced according + and * 
 at least.


 Return type is of course obvious, value is not...


The return type is not actually obvious. You'd think:
alias S = typeof(fun(r.front, r.front));
S s;

Which is a good start. But then
is (S == typeof(fun(s, r.front))) ?

You have no guarantees that you'll have "stability" of the 
returned type.
More often than not, it *is* stable, but there are cases where it 
is not.

This is not a huge problem, because the consequence is simply 
that it fails to compile. We can simply catch it, and tell the 
user to provide an explicit seed, so as to help out the function.

But as you said, for the value, the is simply no correct initial 
value, unless you know the "identity" value of your operator. But 
even then, that value makes no sense is the range is empty.
Mar 25 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 You have no guarantees that you'll have "stability" of the 
 returned type.


What do you mean with "stability" of the return type?


 More often than not, it *is* stable, but there are cases where 
 it is not.


Could you gives examples of when it's stable and when it's not?
Mar 25 2014
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 25 March 2014 at 21:16:22 UTC, Nordlöw wrote:

 You have no guarantees that you'll have "stability" of the 
 returned type.


 What do you mean with "stability" of the return type?


 More often than not, it *is* stable, but there are cases where 
 it is not.


 Could you gives examples of when it's stable and when it's not?


Actually, not with a trivial use case.

I think I'm over-engineering.
Mar 25 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 Actually, not with a trivial use case.

 I think I'm over-engineering.


Do you have a sample implementation on Github I can test?

/Per
Mar 25 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 25 March 2014 at 21:27:45 UTC, Nordlöw wrote:

 Actually, not with a trivial use case.

 I think I'm over-engineering.


 Do you have a sample implementation on Github I can test?

 /Per


You can test my re-implementation of fold/reduce here if you want:
https://github.com/D-Programming-Language/phobos/pull/2033

It contains code that tests the "stability" thing I was talking 
about, but I think I'm going to remove it.
https://github.com/D-Programming-Language/phobos/pull/2033/files#diff-ff74a46362b5953e8c88120e2490f839R992

I think it's better to simply require that:
give: alias S = typeof(r.front, r.front);
isAssignable!(S, typeof(fun(S.init, r.front))
Mar 25 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 You can test my re-implementation of fold/reduce here if you 
 want:
 https://github.com/D-Programming-Language/phobos/pull/2033


Thx!
Mar 25 2014
prev sibling parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-25 21:16, "Nordlöw" wrote:

 You have no guarantees that you'll have "stability" of the returned type.


 What do you mean with "stability" of the return type?


 More often than not, it *is* stable, but there are cases where it is not.


 Could you gives examples of when it's stable and when it's not?


I'm not entirely certain if this is what monarch_dodra meant, but it's 
my understanding of the terms:


Stable:

     double[] arr = [1, 2, 3, 4];
     auto a = arr[0] * arr[1];
     auto b = a * arr[2];

a is of type double, b is of type double.

Unstable:
Consider a range of imaginary numbers, reduced with *.

     idouble[] arr = [1i, 2i, 3i, 4i];
     auto a = arr[0] * arr[1];
     auto b = a * arr[2];

a is of type double, b is of type idouble. When you consume the next 
element, the result would be double again, and it oscillates like that.

--
   Simen
Mar 26 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 26 March 2014 at 15:18:36 UTC, Simen Kjærås wrote:

 On 2014-03-25 21:16, "Nordlöw" wrote:

 You have no guarantees that you'll have "stability" of the 
 returned type.


 What do you mean with "stability" of the return type?


 More often than not, it *is* stable, but there are cases 
 where it is not.


 Could you gives examples of when it's stable and when it's not?


 I'm not entirely certain if this is what monarch_dodra meant, 
 but it's my understanding of the terms:
 ---
   Simen


That's what I meant. Good example!
Mar 26 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
 a is of type double, b is of type idouble. When you consume the 
 next element, the result would be double again, and it 
 oscillates like that.


I guess the return is CommonType!(double,idouble) in that case, 
right?

Is that so hard to figure out...Hmm, there seems to be a 
limitation in D's builtin handling of complex numbers.

import std.stdio, std.algorithm, std.traits;
void main(string args[])
{
     double re;
     idouble im;
     alias C = CommonType!(double, idouble);
     C c;
     writeln(typeof(re).stringof, ",", typeof(im).stringof, ",", 
C.stringof);
}

prints

double,idouble,double

This is *not* what we want.

We want to print something like

double,idouble,cdouble (or Complex!double!)

I guess that's why it's deprecated in favour of std.complex...
Mar 26 2014
prev sibling next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Tuesday, 25 March 2014 at 17:22:45 UTC, monarch_dodra wrote:

 I think this is wrong. popping an empty range is an *Error*, 
 and should be validated by the programmer. Because of this, it 
 is currently not possible to use "reduce(range)" in nothrow 
 context.


Popping an empty range is indeed an error, but that's not the 
issue here. The issue is whether or not it should check for 
empty, i.e. whether an empty input is valid. Other looping eager 
algorithms - like `sum` and indeed `copy` - do accept empty 
inputs.

I understand the issue of nothrow of course; I think it's likely 
that in most real-world use cases, reduce/fold will be used on 
guaranteed non-empty inputs, *but not always*, and I'd hate for 
release-build-only dangerous bugs to sneak into programs because 
of it.

Maybe we should have some kind of NonEmpty higher-order range 
type that algorithms can overload on, ala how std.container deals 
with Take? It could be initialized with `assumeNonEmpty(r)` 
and/or `checkNonEmpty(r)`.
Mar 26 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Thursday, 27 March 2014 at 02:08:04 UTC, Jakob Ovrum wrote:

 On Tuesday, 25 March 2014 at 17:22:45 UTC, monarch_dodra wrote:

 I think this is wrong. popping an empty range is an *Error*, 
 and should be validated by the programmer. Because of this, it 
 is currently not possible to use "reduce(range)" in nothrow 
 context.


 Popping an empty range is indeed an error, but that's not the 
 issue here. The issue is whether or not it should check for 
 empty, i.e. whether an empty input is valid. Other looping 
 eager algorithms - like `sum` and indeed `copy` - do accept 
 empty inputs.

 I understand the issue of nothrow of course; I think it's 
 likely that in most real-world use cases, reduce/fold will be 
 used on guaranteed non-empty inputs, *but not always*, and I'd 
 hate for release-build-only dangerous bugs to sneak into 
 programs because of it.

 Maybe we should have some kind of NonEmpty higher-order range 
 type that algorithms can overload on, ala how std.container 
 deals with Take? It could be initialized with 
 `assumeNonEmpty(r)` and/or `checkNonEmpty(r)`.


I'm not sure I understand this right, but are you or Monarch
proposing to disallow calling it with an empty range? I believe
this would be really bad, especially for generic code.
Folding/reducing an empty range should just return the seed
value, not be an error.
Mar 27 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 27 March 2014 at 10:42:56 UTC, Marc Schütz wrote:

 I'm not sure I understand this right, but are you or Monarch
 proposing to disallow calling it with an empty range? I believe
 this would be really bad, especially for generic code.
 Folding/reducing an empty range should just return the seed
 value, not be an error.


We are talking about the case when there *is* no seed. What 
should this do?

//----
int[] arr;
reduce!max(arr);
//----
Mar 27 2014
prev sibling next sibling parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-25 17:22, monarch_dodra wrote:


 I'm taking this naming-changing event as an opportunity to "cleanup"
 reduce too. One thing that gets on my nerves is that "range.reduce()" is
 not nothrow, because it throws an exception if the range is empty.

 I think this is wrong. popping an empty range is an *Error*, and should
 be validated by the programmer. Because of this, it is currently not
 possible to use "reduce(range)" in nothrow context.

 This however, even with a name change, it *is* change of behavior. Do
 you feel this is acceptable? Do you want this change at all? Or do you
 think an Exception is fine?


Your new fold (foldl? Should we have foldr as well?) should be nothrow. 
As for updating reduce, I'm slightly in favor of making it nothrow as 
well, but is this really necessary? The cases where it's already used 
will gain nothing from it, and new code would use fold instead. Or do I 
misunderstand?

Even with that argument though, I'd say make it nothrow. Like Meta said, 
it's probably remnants from elder times.

--
   Simen
Mar 27 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 27 March 2014 at 12:48:41 UTC, Simen Kjærås wrote:

 Your new fold (foldl? Should we have foldr as well?)


"fold" (from what I understood) is what you call "foldl". It was 
discussed to not introduce "foldr", as it's just 
"fold!(binaryReverseArgs!Fun)(range.retro);".

I'm not sure I was able to understand what the difference between 
"fold" and "foldl" is...
Mar 27 2014
next sibling parent reply "Brian Rogoff" <brogoff gmail.com> writes:
On Thursday, 27 March 2014 at 13:23:27 UTC, monarch_dodra wrote:

 On Thursday, 27 March 2014 at 12:48:41 UTC, Simen Kjærås wrote:

 Your new fold (foldl? Should we have foldr as well?)


 "fold" (from what I understood) is what you call "foldl". It 
 was discussed to not introduce "foldr", as it's just 
 "fold!(binaryReverseArgs!Fun)(range.retro);".

 I'm not sure I was able to understand what the difference 
 between "fold" and "foldl" is...


In functional languages,

fold_left(f, a, [b1, ..., bn]) is
f((... (f, (f, a, b1), b2) ...), bn)

as you can see, the innermost f call is on the leftmost sequence 
element, and

fold_right(f, [a1, ..., an], b) is
f(a1, (f a2 (... f(an, b) ...)))

That's how I think of them.
Mar 27 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 27 March 2014 at 14:41:19 UTC, Brian Rogoff wrote:

 On Thursday, 27 March 2014 at 13:23:27 UTC, monarch_dodra wrote:

 On Thursday, 27 March 2014 at 12:48:41 UTC, Simen Kjærås wrote:

 Your new fold (foldl? Should we have foldr as well?)


 "fold" (from what I understood) is what you call "foldl". It 
 was discussed to not introduce "foldr", as it's just 
 "fold!(binaryReverseArgs!Fun)(range.retro);".

 I'm not sure I was able to understand what the difference 
 between "fold" and "foldl" is...


 In functional languages,

 fold_left(f, a, [b1, ..., bn]) is
 f((... (f, (f, a, b1), b2) ...), bn)

 as you can see, the innermost f call is on the leftmost 
 sequence element, and

 fold_right(f, [a1, ..., an], b) is
 f(a1, (f a2 (... f(an, b) ...)))

 That's how I think of them.


Right, but what about "fold" vs "fold_left"? Is there a 
difference?
Mar 27 2014
next sibling parent "Brian Rogoff" <brogoff gmail.com> writes:
On Thursday, 27 March 2014 at 14:45:05 UTC, monarch_dodra wrote:

 On Thursday, 27 March 2014 at 14:41:19 UTC, Brian Rogoff wrote:

 On Thursday, 27 March 2014 at 13:23:27 UTC, monarch_dodra 
 wrote:

 On Thursday, 27 March 2014 at 12:48:41 UTC, Simen Kjærås 
 wrote:

 Your new fold (foldl? Should we have foldr as well?)


 "fold" (from what I understood) is what you call "foldl". It 
 was discussed to not introduce "foldr", as it's just 
 "fold!(binaryReverseArgs!Fun)(range.retro);".

 I'm not sure I was able to understand what the difference 
 between "fold" and "foldl" is...


 In functional languages,

 fold_left(f, a, [b1, ..., bn]) is
 f((... (f, (f, a, b1), b2) ...), bn)

 as you can see, the innermost f call is on the leftmost 
 sequence element, and

 fold_right(f, [a1, ..., an], b) is
 f(a1, (f a2 (... f(an, b) ...)))

 That's how I think of them.


 Right, but what about "fold" vs "fold_left"? Is there a 
 difference?


There's just fold_left and fold_right, or foldl and foldr if you 
prefer, though if f is associative they're both the same.
Mar 27 2014
prev sibling next sibling parent =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-27 14:45, monarch_dodra wrote:

 On Thursday, 27 March 2014 at 14:41:19 UTC, Brian Rogoff wrote:

 On Thursday, 27 March 2014 at 13:23:27 UTC, monarch_dodra wrote:

 On Thursday, 27 March 2014 at 12:48:41 UTC, Simen Kjærås wrote:

 Your new fold (foldl? Should we have foldr as well?)


 "fold" (from what I understood) is what you call "foldl". It was
 discussed to not introduce "foldr", as it's just
 "fold!(binaryReverseArgs!Fun)(range.retro);".

 I'm not sure I was able to understand what the difference between
 "fold" and "foldl" is...


 In functional languages,

 fold_left(f, a, [b1, ..., bn]) is
 f((... (f, (f, a, b1), b2) ...), bn)

 as you can see, the innermost f call is on the leftmost sequence
 element, and

 fold_right(f, [a1, ..., an], b) is
 f(a1, (f a2 (... f(an, b) ...)))

 That's how I think of them.


 Right, but what about "fold" vs "fold_left"? Is there a difference?


Different languages may have different standards, but I think fold is 
usually a left fold. So, no difference.

--
   Simen
Mar 27 2014
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2014 03:45 PM, monarch_dodra wrote:

 Right, but what about "fold" vs "fold_left"? Is there a difference?


'fold' is not descriptive enough. Ranges/lists have a very particular 
structure allowing 'foldl' to make sense. In general recursive data 
types (eg. think binary tree) allow only one fold (the recursive one). 
The instantiation for lists is 'foldr'.

I'd rather have this named 'foldl'. 'fold' is a more abstract name 
'foldr' rather than 'foldl'.
Mar 27 2014
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 27 March 2014 at 22:29:01 UTC, Timon Gehr wrote:

 On 03/27/2014 03:45 PM, monarch_dodra wrote:

 Right, but what about "fold" vs "fold_left"? Is there a 
 difference?


 'fold' is not descriptive enough. Ranges/lists have a very 
 particular structure allowing 'foldl' to make sense. In general 
 recursive data types (eg. think binary tree) allow only one 
 fold (the recursive one). The instantiation for lists is 
 'foldr'.

 I'd rather have this named 'foldl'. 'fold' is a more abstract 
 name 'foldr' rather than 'foldl'.


That makes sense.

Would it make sense to have also have a "fold" that does 
recursive reduction? EG:

fun(fun(a[0], a[1]), fun(a[2], a[3]))

That could seem useful to me.
Mar 28 2014
prev sibling parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 27 March 2014 at 13:23:27 UTC, monarch_dodra wrote:

 "fold" (from what I understood) is what you call "foldl". It 
 was discussed to not introduce "foldr", as it's just 
 "fold!(binaryReverseArgs!Fun)(range.retro);".


Rolls right off the tongue. We seriously need a better alias for 
binaryReverseArgs.
Mar 27 2014
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 27 March 2014 at 15:33:39 UTC, Meta wrote:

 On Thursday, 27 March 2014 at 13:23:27 UTC, monarch_dodra wrote:

 "fold" (from what I understood) is what you call "foldl". It 
 was discussed to not introduce "foldr", as it's just 
 "fold!(binaryReverseArgs!Fun)(range.retro);".


 Rolls right off the tongue. We seriously need a better alias 
 for binaryReverseArgs.


Arguably, we could just have a generic "reverseArgs". Not sure 
why it's restrained to "binary" to begin with.

In any case, I don't disagree, but the point is that "fold" is 
not special in that regard. If "foldr" was justified, then so 
would "filterr", "joinerr", "mapr" etc...
Mar 27 2014
prev sibling parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-27 15:33, Meta wrote:

 On Thursday, 27 March 2014 at 13:23:27 UTC, monarch_dodra wrote:

 "fold" (from what I understood) is what you call "foldl". It was
 discussed to not introduce "foldr", as it's just
 "fold!(binaryReverseArgs!Fun)(range.retro);".


 Rolls right off the tongue. We seriously need a better alias for
 binaryReverseArgs.


Is it even necessary to specifically have a binary version of that?
This seems to be a working generalization of binaryReverseArgs:

template reverseArgs(alias pred)
{
     import std.typetuple : Reverse;
     auto reverseArgs(Args...)(Args args)
         if (is(typeof(pred(Reverse!args))))
     {
         return pred(Reverse!args);
     }
}

unittest
{
     import std.functional;
     alias gt = reverseArgs!(binaryFun!("a < b"));
     assert(gt(2, 1) && !gt(1, 1));
     int x = 42;
     bool xyz(int a, int b) { return a * x < b / x; }
     auto foo = &xyz;
     foo(4, 5);
     alias zyx = reverseArgs!(foo);
     assert(zyx(5, 4) == foo(4, 5));

     int abc(int a, int b, int c) { return a * b + c; }
     alias cba = reverseArgs!abc;
     assert(abc(91, 17, 32) == cba(32, 17, 91));
}

On the same note, binaryFun and unaryFun seem to me unnecessary 
specializations of a more general 'fun' template. Philippe Sigaud has an 
implementation in his dranges called naryFun 
(https://github.com/PhilippeSigaud/dranges). That code has apparently 
not been touched for at least two years, so YMMV.

--
   Simen
Mar 27 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 27 March 2014 at 15:54:46 UTC, Simen Kjærås wrote:

 On 2014-03-27 15:33, Meta wrote:
 Is it even necessary to specifically have a binary version of 
 that?
 This seems to be a working generalization of binaryReverseArgs:


In binaryReverseArgs's defense, it was written before "Reverse!". 
But yes, it's just a question of time before binaryReverseArgs is 
replaced.

It's just a matter of having someone tackle the issue and submit 
a proposal *hint* ;)


 On the same note, binaryFun and unaryFun seem to me unnecessary 
 specializations of a more general 'fun' template. Philippe 
 Sigaud has an implementation in his dranges called naryFun 
 (https://github.com/PhilippeSigaud/dranges). That code has 
 apparently not been touched for at least two years, so YMMV.


Also yes, but the general feeling around here, is that "string 
functions" are a thing of the past, and should be replaced by 
"real" lambda functions.

As such, even if "naryFun" works, it promotes the use of 
something that is unpopular, and that some would like to see 
disappear.
Mar 27 2014
next sibling parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 27 March 2014 at 16:33:53 UTC, monarch_dodra wrote:

 Also yes, but the general feeling around here, is that "string 
 functions" are a thing of the past, and should be replaced by 
 "real" lambda functions.

 As such, even if "naryFun" works, it promotes the use of 
 something that is unpopular, and that some would like to see 
 disappear.


Don't forget this use case:

//Error
alias fun = (a) => a + 1;

//Ok
alias fun = unaryFun!(a => a + 1);

This is the main reason I think naryFun is a good idea.
Mar 27 2014
parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-27 16:35, Meta wrote:

 On Thursday, 27 March 2014 at 16:33:53 UTC, monarch_dodra wrote:

 Also yes, but the general feeling around here, is that "string
 functions" are a thing of the past, and should be replaced by "real"
 lambda functions.

 As such, even if "naryFun" works, it promotes the use of something
 that is unpopular, and that some would like to see disappear.


 Don't forget this use case:

 //Error
 alias fun = (a) => a + 1;

 //Ok
 alias fun = unaryFun!(a => a + 1);

 This is the main reason I think naryFun is a good idea.


That could very well be argued to be a bug, though.

--
   Simen
Mar 27 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 27 March 2014 at 16:42:31 UTC, Simen Kjærås wrote:

 That could very well be argued to be a bug, though.

 --
   Simen


What is the bug? Alias aliases symbols. A function literal is not 
a symbol, but a template instantiation is. Therefore, wrapping a 
function literal in a template instantiation allows it to be 
aliased. I don't think there's any bugger behaviour here.
Mar 27 2014
next sibling parent "Meta" <jared771 gmail.com> writes:
On Thursday, 27 March 2014 at 17:21:14 UTC, Meta wrote:

 On Thursday, 27 March 2014 at 16:42:31 UTC, Simen Kjærås wrote:

 That could very well be argued to be a bug, though.

 --
  Simen


 What is the bug? Alias aliases symbols. A function literal is 
 not a symbol, but a template instantiation is. Therefore, 
 wrapping a function literal in a template instantiation allows 
 it to be aliased. I don't think there's any bugger behaviour 
 here.


Whoops, I mean buggy.
Mar 27 2014
prev sibling parent reply =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-27 17:21, Meta wrote:

 On Thursday, 27 March 2014 at 16:42:31 UTC, Simen Kjærås wrote:

 That could very well be argued to be a bug, though.

 --
   Simen


 What is the bug? Alias aliases symbols. A function literal is not a
 symbol, but a template instantiation is. Therefore, wrapping a function
 literal in a template instantiation allows it to be aliased. I don't
 think there's any bugger behaviour here.


Ah, true. Call it an enhancement request, then. Wanting to alias a 
function literal like that is so common the language should support it.

--
   Simen
Mar 27 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 27 March 2014 at 17:30:58 UTC, Simen Kjærås wrote:

 Ah, true. Call it an enhancement request, then. Wanting to 
 alias a function literal like that is so common the language 
 should support it.

 --
   Simen


It's a bit unintuitive as to what works and what doesn't 
(although it makes sense for the most part).

//No good
alias fun = a => a + 1;
alias fun = (int a) => a + 1;
//Ok
alias fun = unaryFun!(a => a + 1);
alias fun = unaryFun!((int a) => a + 1);

//Doesn't work
enum fun = a => a + 1;
enum fun = unaryFun!(a => a + 1);
//Works
enum fun = (int a) => a + 1;
enum fun = unaryFun!((int a) => a + 1);


But the fun is just beginning. Now we can mix in template aliases 
and enums.

//Chokes
alias fun() = a => a + 1;
alias fun() = (a => a + 1);
alias fun() = (int a) => a + 1;
alias fun(T) = a => a + 1;
alias fun(T) = (a => a + 1);
alias fun(T) = (int a) => a + 1;

//Fine
alias fun() = unaryFun!(a => a + 1);

//Compiles but fails when fun is called
alias fun() = unaryFun!((int a) => a + 1);
fun(1); //undefined reference to 
`_D4f2924mainFZv8__T3funZ9__lambda2FNaNbNfiZi'

enum fun() = unaryFun!(a => a + 1);
fun(1); //cannot infer type from template template __lambda2

enum fun() = unaryFun!((int a) => a + 1);
fun(1); //cannot deduce function from argument types !()(int)

enum fun() = a => a + 1;
fun(1); //type void is inferred from initializer a => a + 1

enum fun() = (int a) => a + 1;
fun(1); //cannot deduce function from argument types !()(int)


So there you have it.
Mar 27 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2014 07:04 PM, Meta wrote:

 It's a bit unintuitive as to what works and what doesn't (although it
 makes sense for the most part).


It doesn't make sense at all. It is an arbitrary limitation. The rule is 
simple though: One can only alias things that syntactically look like 
they might be types. This is why the following triviality is way more 
useful than it should be:

alias Id(alias a)=a;

alias fun = Id!(a=>a); // ok!
Mar 27 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 27 March 2014 at 22:33:50 UTC, Timon Gehr wrote:

 It doesn't make sense at all. It is an arbitrary limitation. 
 The rule is simple though: One can only alias things that 
 syntactically look like they might be types. This is why the 
 following triviality is way more useful than it should be:

 alias Id(alias a)=a;

 alias fun = Id!(a=>a); // ok!


You can tell me that function literals look like types, but I 
won't believe you.
Mar 27 2014
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/28/2014 01:41 AM, Meta wrote:

 On Thursday, 27 March 2014 at 22:33:50 UTC, Timon Gehr wrote:

 It doesn't make sense at all. It is an arbitrary limitation. The rule
 is simple though: One can only alias things that syntactically look
 like they might be types. This is why the following triviality is way
 more useful than it should be:

 alias Id(alias a)=a;

 alias fun = Id!(a=>a); // ok!


 You can tell me that function literals look like types, but I won't
 believe you.


You mean because the literal is accepted as an alias argument? Alias 
template arguments are not actually the same thing as alias 
declarations. (Eg. the latter can accept built-in types like 'int', 
while the former will not, but otherwise allow arbitrary expressions.) I 
used to think this was a bug, but Walter stated that this is in fact by 
design. (I think this is a gratuitous design mistake.)

The expressions that are used in alias declarations are 'a' and 
'Id!(a=>a)'. Both of those can occur in a context where they denote types.
Mar 28 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Friday, 28 March 2014 at 22:39:24 UTC, Timon Gehr wrote:

 You mean because the literal is accepted as an alias argument? 
 Alias template arguments are not actually the same thing as 
 alias declarations. (Eg. the latter can accept built-in types 
 like 'int', while the former will not, but otherwise allow 
 arbitrary expressions.) I used to think this was a bug, but 
 Walter stated that this is in fact by design. (I think this is 
 a gratuitous design mistake.)

 The expressions that are used in alias declarations are 'a' and 
 'Id!(a=>a)'. Both of those can occur in a context where they 
 denote types.


I'm confused now. What exactly was it that you were saying didn't 
make sense?
Mar 28 2014
parent reply "Meta" <jared771 gmail.com> writes:
On Saturday, 29 March 2014 at 00:58:46 UTC, Meta wrote:

 I'm confused now. What exactly was it that you were saying 
 didn't make sense?


Ah, I see now. When I said "it's a bit unintuitive as to what 
works and what doesn't", I was talking about how unless you know 
exactly what can be assigned to an alias and enum, it seems 
unintuitive or even random as to what works, but there are 
actually sound logical underpinnings.
Mar 28 2014
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 03/29/2014 02:02 AM, Meta wrote:

 On Saturday, 29 March 2014 at 00:58:46 UTC, Meta wrote:

 I'm confused now. What exactly was it that you were saying didn't make
 sense?


 Ah, I see now. When I said "it's a bit unintuitive as to what works and
 what doesn't", I was talking about how unless you know exactly what can
 be assigned to an alias and enum, it seems unintuitive or even random as
 to what works, but there are actually sound logical underpinnings.


My point was: Yes, there are rules, but they are 
inadequate/unnecessarily restrictive.
Mar 29 2014
prev sibling parent =?UTF-8?B?U2ltZW4gS2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On 2014-03-27 16:33, monarch_dodra wrote:

 On Thursday, 27 March 2014 at 15:54:46 UTC, Simen Kjærås wrote:

 On 2014-03-27 15:33, Meta wrote:
 Is it even necessary to specifically have a binary version of that?
 This seems to be a working generalization of binaryReverseArgs:


 In binaryReverseArgs's defense, it was written before "Reverse!". But
 yes, it's just a question of time before binaryReverseArgs is replaced.

 It's just a matter of having someone tackle the issue and submit a
 proposal *hint* ;)


Done:
https://github.com/D-Programming-Language/phobos/pull/2054



 On the same note, binaryFun and unaryFun seem to me unnecessary
 specializations of a more general 'fun' template. Philippe Sigaud has
 an implementation in his dranges called naryFun
 (https://github.com/PhilippeSigaud/dranges). That code has apparently
 not been touched for at least two years, so YMMV.


 Also yes, but the general feeling around here, is that "string
 functions" are a thing of the past, and should be replaced by "real"
 lambda functions.

 As such, even if "naryFun" works, it promotes the use of something that
 is unpopular, and that some would like to see disappear.


True.

--
   Simen
Mar 27 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:


 I'm taking this naming-changing event as an opportunity to 
 "cleanup" reduce too.


This is possibly silly question, or perhaps fit just for D.learn. 
But I think it's sufficiently in topic in this thread.

You have a function foo1 like this:


import std.range, std.algorithm, std.array;

uint[] foo1(uint[][] X) {
     return X.reduce!((i, j) => zip(i, j)
                                .map!(kw => kw[0] | kw[1])
                                .array);
}

void main() {
     import std.stdio;
     uint[][] m1 = [[10, 20], [30, 40]];
     foo1(m1).writeln;
}


foo1 doesn't need to change its input so I'd like to use the 
signature:

int[] foo1(in int[][] X) {

But that can't work because reduce returns a const.

And you can't do this because it returns a wrong result:

uint[] foo2(in uint[][] X) {
     return reduce!((i, j) => zip(i, j)
                              .map!(kw => kw[0] | kw[1])
                              .array)
                   ((uint[]).init, X);
}



This seems OK, but can fold offer a better solution?:

uint[] foo3(in uint[][] X) {
     return reduce!((i, j) => zip(i, j)
                              .map!(kw => kw[0] | kw[1])
                              .array)
                   (X[0].dup, X[1 .. $]);
}

Bye,
bearophile
Mar 30 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Sunday, 30 March 2014 at 21:53:16 UTC, bearophile wrote:

 monarch_dodra:


 I'm taking this naming-changing event as an opportunity to 
 "cleanup" reduce too.


 This seems OK, but can fold offer a better solution?:

 Bye,
 bearophile


AFAIK, no: Your range's element type (E) is `const(uint)[]`, and 
given your predicate (let's just call it "pred"), `pred(e, e)` 
produces a `const(uint)[]`. There's not much that reduce or 
fold(l) could do about it at that point.

You'd have two (IMO cleaner) solutions.
1. tweak pred to return the right type (*):
uint[] foo1(uint[][] X)
{
     return X.reduce!((i, j) => zip(i, j)
         .map!(kw => uint(kw[0] | kw[1]))
         .array);
}
(*) This currently fails catastrophically with both single and 
multiple pred versions of reduce, due to suboptimal code.

I can get it to work for fold though.

2. provide a seed.
uint[] foo1(uint[][] X)
{
     return reduce!((i, j) => zip(i, j)
         .map!(kw => uint(kw[0] | kw[1]))
         .array)([uint(0), uint(0)], X);
}

In any case, thanks for reporting. I'll make certain this works.
Mar 31 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

Thank you for the answers.


 I can get it to work for fold though.


Good.



 2. provide a seed.
 uint[] foo1(uint[][] X)
 {
     return reduce!((i, j) => zip(i, j)
         .map!(kw => uint(kw[0] | kw[1]))
         .array)([uint(0), uint(0)], X);
 }



Unfortunately it doesn't work correctly (because the size of the 
rows is not always 2):



import std.range, std.algorithm, std.array;

// Original correct.
uint[] foo1(uint[][] X) {
     return X.reduce!((i, j) => zip(i, j)
                                .map!(kw => kw[0] | kw[1])
                                .array);
}

// OK
uint[] foo3(in uint[][] X) {
     return reduce!((i, j) => zip(i, j)
                              .map!(kw => kw[0] | kw[1])
                              .array)
                   (X[0].dup, X[1 .. $]);
}

// Modified, not good.
uint[] foo4(uint[][] X) {
     return reduce!((i, j) => zip(i, j)
                              .map!(kw => uint(kw[0] | kw[1]))
                              .array)
                   ([uint(0), uint(0)], X);
}

void main() {
     import std.stdio;
     uint[][] m1 = [[10, 20, 30], [40, 50, 60]];
     foo1(m1).writeln;
     uint[][] m3 = [[10, 20, 30], [40, 50, 60]];
     foo3(m3).writeln;
     uint[][] m4 = [[10, 20, 30], [40, 50, 60]];
     foo4(m4).writeln;
}


Output:

[42, 54, 62]
[42, 54, 62]
[42, 54]

Bye,
bearophile
Mar 31 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 31 March 2014 at 10:28:10 UTC, bearophile wrote:

 monarch_dodra:

 Thank you for the answers.


 I can get it to work for fold though.


 Good.


I've reconsidered my answer. It is *impossible* to get what you 
are asking for to work, without explicitly passing a seed.

This is because the seed is *initialized* to the range's front. 
Anything other than "const(uint)[]" would simply break the type 
system: If your range only has 1 element, then you'd be returning 
a mutable reference to const data.

So my vote goes to this solution.

//----
uint[] foo3(in uint[][] X)
{
     assert(!X.empty)
     auto seed = X.front.dup;
     X.popFront();
     return reduce!((i, j) => zip(i, j)
                              .map!(kw => kw[0] | kw[1])
                              .array)
                   (seed, X);
}
//----

I re-wrote it that way: It's a bit longer, but a bit more generic 
in terms of customizing your seed.
Mar 31 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:


 So my vote goes to this solution.

 //----
 uint[] foo3(in uint[][] X)
 {
     assert(!X.empty)
     auto seed = X.front.dup;
     X.popFront();
     return reduce!((i, j) => zip(i, j)
                              .map!(kw => kw[0] | kw[1])
                              .array)
                   (seed, X);
 }
 //----

 I re-wrote it that way: It's a bit longer, but a bit more 
 generic in terms of customizing your seed.


OK, thank you. So the price for that "in" is to use a dup :-) (Or 
use lower level code).

Bye,
bearophile
Mar 31 2014
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 31 March 2014 at 13:05:24 UTC, bearophile wrote:

 OK, thank you. So the price for that "in" is to use a dup :-) 
 (Or use lower level code).

 Bye,
 bearophile


I'd think so yes. But given you are calling "array" for every 
iteration, it doesn't look like a ludicrous overhead.

That said, if you were reduce *into* your actual seed (the dup'ed 
array) instead of duplicating it on every iteration, it should be 
better.

I think your code is simplified, but consider this:

//----
uint[] foo3(const(uint[])[] X)
{
     assert(!X.empty);
     auto seed = X.front.dup;
     X.popFront();
     return reduce!((i, j) => i[] |= j[])
                   (seed, X);
}
//----

This gives the same "logical" result, but reuses the seed 
contents on every iteration.

Then, the original dup looks less gratuitous: You are allocating 
your result.
Mar 31 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:


 uint[] foo3(const(uint[])[] X)
 {
     assert(!X.empty);
     auto seed = X.front.dup;
     X.popFront();
     return reduce!((i, j) => i[] |= j[])
                   (seed, X);
 }
 //----

 This gives the same "logical" result, but reuses the seed 
 contents on every iteration.


Nice, thank you :-)

And with a miniscule de-optimization it becomes very good:
https://d.puremagic.com/issues/show_bug.cgi?id=10523

Bye,
bearophile
Mar 31 2014