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 "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
prev sibling next sibling parent "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
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 "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 "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 =?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
prev sibling next sibling parent =?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
prev sibling next sibling parent "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
prev sibling next sibling parent =?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
prev sibling next sibling parent "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
prev sibling next sibling parent =?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
prev sibling next sibling parent "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
prev sibling next sibling 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 next sibling parent =?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
prev sibling 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 next 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 "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
prev sibling next sibling parent "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
prev sibling next sibling 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
next sibling parent 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
prev sibling 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 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 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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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 next sibling parent =?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
prev sibling 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 "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
prev sibling next sibling parent "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
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 next sibling parent =?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
prev sibling next 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 next sibling parent "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
prev sibling 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 next sibling parent =?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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling 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 next sibling parent "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
prev sibling next sibling parent "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
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.

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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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