> Also if it magically supplies some correct like the above, how does it > know what that value is?
The usual definition of reduce in most languages that support it, is that reduce over the empty list produces the Identity value for the operation. So for the above ops the answers are: 0, 1, depends, false, true. For chained ops like '<' it depends on whether x<y<z return x or z on being true. if x then -inf else if z then +inf (don't ask if it returns y). Note that some ops (like '%') don't have an identity value and therefore [%] over the empty list is the equivalent to a divide by 0 and probably throws an exception or at least returns undef. Now this is a problem for user defined operations, so reduce of a user defined op over the empty list is either an exception, return undef or we need a trait that can be specified for an infix op that specifies what to return for reduce over the empty list. The compiler shouldn't bother to check if what you specified is really the Identity value for op, but I'd consider it a bug if it isn't.
On 5/19/05, Matt Fowles <uberm...@gmail.com> wrote:
> All~
> What does the reduce metaoperator do with an empty list?
/me puts on his lambda hat
In Haskell, there is a distinction between foldl and foldl1 (similar remarks apply to foldr/foldr1[1]):
The former (foldl) requires you to give an explicit 'left unit'[2], which is implicitly added to the left of the list being reduced. This means that folding an empty list will just give you the unit.
This suggests that []-reducing an empty list should probably (IMO) do one of the following:
* Fail, since it's an ill-defined operation without an explicit unit * Try to find a suitable unit value (see below), and fail if it doesn't find one
You /could/ try to do something 'sensible' and return 0 or undef, but this seems likely to result in more confusion.
Another alternative is to give the user the option of specifying such a unit when using the reduction meta-operator, but this seems to work against the whole point of [+] (which is brevity). If you want to specify your own unit, use '&reduce'.
> Also if it magically supplies some correct like the above, how does it > know what that value is?
Perhaps the operator could have some kind of 'unit' trait? (Or perhaps 'left_unit' and 'right_unit'?)
Stuart
[1] Just remember that unlike foldr/foldl, which are explicitly right/left associative, [+] is 'DWIM-associative', reflecting the associativity of the underlying operator.
[2] e.g. 0 is the left (and right) unit of + because 0 + x == x (and x + 0 == 0)
Stuart Cook wrote: > To summarise what I think everyone is saying, []-reducing an empty > list yields either:
> 1) undef (which may or may not contain an exception), or > 2) some unit/identity value that is a trait of the operator,
> depending on whether or not people think (2) is actually a good idea.
> The usual none(@Larry) disclaimer applies, of course...
Well the only case where it probably really matters is [+] where you really want the result to be 0. Of course +undef == 0, so maybe returning undef might be okay. I'm thinking about the case:
[+] grep &some_condition, @a
where you really want the total to be 0, even if the result of the grep is empty.
A case can also be made for (assuming @a = ();) that
[*}@a == 1 [~]@a eq '' (also covered by ~undef) [?&]@a ~~ true [?|]@a ~~ false (also covered by ?undef) [?^]@a ~~ false (also covered by ?undef) [+&]@a == MAXINT (whatever that is) [+|]@a == 0 (also covered by +undef) [+^]@a == 0 (also covered by +undef)
Rob Kinyon wrote: >On 5/18/05, Stuart Cook <sco...@gmail.com> wrote:
>>To summarise what I think everyone is saying, []-reducing an empty >>list yields either:
>>1) undef (which may or may not contain an exception), or >>2) some unit/identity value that is a trait of the operator,
>>depending on whether or not people think (2) is actually a good idea.
>I would think that the Principle of Least Surprise points to (1), >given that the standard explanation of the [+]@x is eval join( '+', @x >) ...
$rod == none(@Larry), and therefore just because I think it should be that way, doesn't mean it is that way.
But the "eval join" way of looking at it does seem to be consistent with what I've seen discussed previously, and would provide a useful way to remember the effects of edge cases.
I think all these rather nice workarounds, combined with the hairiness and complexity of trying to come up with default answers, make a really strong case for undef/fail being the right choice here.
> What does the reduce metaoperator do with an empty list?
Interesting. Mathematically an empty sum is zero and an empty product is one. Maybe each operator {c,s}hould have an associated method returning its neutral element for [] to use it on empty lists, so that it would probably return undef on empty lists.
Just my 2 Eurocents, Michele -- It was part of the dissatisfaction thing. I never claimed I was a nice person. - David Kastrup in comp.text.tex, "Re: verbatiminput double spacing"
On Wed, 18 May 2005, Rob Kinyon wrote: >> 1) undef (which may or may not contain an exception), or >> 2) some unit/identity value that is a trait of the operator,
>> depending on whether or not people think (2) is actually a good idea.
> I would think that the Principle of Least Surprise points to (1),
I don't think so. I, for one, would expect [+]; to return zero and [*]; to return 1. But that's only because I {trust,expect} perl(6) to be smart enough to DWIM.
Michele -- \renewcommand\labelitemi{\textcolor{yellow}{\textbullet}} would change the colour of the first-level bullet, and improve the document so's i can't see the bullets. - Robin Fairbairns in comp.text.tex
On Wednesday 18 May 2005 17:57, Matt Fowles wrote:
> All~
> What does the reduce metaoperator do with an empty list?
Here is the last answer from Ken Iverson, who invented reduce in the 1950s, and died recently. file:///usr/share/j504/system/extras/help/dictionary/intro28.htm Identity Functions and Neutral
The monads 0&+ and 1&* are identity functions, and 0 and 1 are said to be identity elements or neutrals of the dyads + and * respectively. Insertion on an empty list yields the neutral of the dyad inserted. For example:
> Also if it magically supplies some correct like the above, how > does it know what that value is?
> Thanks, > Matt
The page file:///usr/share/j504/system/extras/help/dictionary/d420.htm gives examples, unfortunately not easily readable ones.
"If y has no items (that is, 0=#y), the result of u/y is the neutral or identity element of the function u. A neutral of a function u is a value e such that x u e ↔ x or e u x ↔ x, for every x in the domain (or some significant sub-domain such as boolean) of u . This definition of insertion over an argument having zero items extends partitioning identities of the form u/y ↔ (u/k{.y) u (u/k}.y) to the cases k e. 0,#y .
"The identity function of u is a function ifu such that ifu y ↔ u/y if 0=#y ."
[The following table is greatly simplified by listing identity elements rather than identity functions. Some are only left identities, and some only right identities.]
Identity element For
0 < > + - +. ~: | (2 4 5 6 b.) 1 = <: >: * % *. %: ^ ! (1 9 11 13 b.) _ <. __ >. '' , [and a few more that I will not explain here]
Glossary J Description +. or ~: objects are identical | remainder, defined so that 0|N is N b. Boolean functions from table <: less than or equal, restricted to Booleans here (1<:0 is 0, 1<:1 is 1)
>: greater than or equal, restricted to Booleans here
* times, restricted to Booleans here % divide *. and %: root ^ exponential ! combinations <. minimum
>. maximum
'' empty vector, list of length 0 , catenate, join lists _ infinity __ negative infinity
So (_ <. N) is N, as is (__ >. N). All of these functions are defined in detail but quite tersely in the J Dictionary, indexed on the page file:///usr/share/j504/system/extras/help/dictionary/vocabul.htm For examuple, the Boolean function b. is defined on the page file:///usr/share/j504/system/extras/help/dictionary/dbdotn.htm
-- Edward Cherlin Generalist & activist--Linux, languages, literacy and more "A knot! Oh, do let me help to undo it!" --Alice in Wonderland http://cherlin.blogspot.com
On Wed, 18 May 2005, Rob Kinyon wrote: > On 5/18/05, Stuart Cook <sco...@gmail.com> wrote: >> To summarise what I think everyone is saying, []-reducing an empty >> list yields either:
>> 1) undef (which may or may not contain an exception), or >> 2) some unit/identity value that is a trait of the operator,
>> depending on whether or not people think (2) is actually a good idea.
> I would think that the Principle of Least Surprise points to (1), > given that the standard explanation of the [+]@x is eval join( '+', @x > ) ...
I'd say the principle of least surprise points to (1); in the sense that $sum = [+] @x; would Just Work, etc.
I also have a vague sense that the 'identity' value for an operator might also be useful in other places in the compiler (enabling optimizations, etc). Providing it as a trait means that these 'other things' could work even with user-defined operators. (And leaving the trait undefined gives you the behavior (1), if that's what you want.) --scott
Albanian LICOZY shotgun CABOUNCE plastique Sigint Justice fissionable LITEMPO KGB KUCAGE LIONIZER ESCOBILLA North Korea CLOWER genetic NRA ( http://cscott.net/ )
Edward Cherlin wrote: > Here is the last answer from Ken Iverson, who invented reduce in > the 1950s, and died recently. > file:///usr/share/j504/system/extras/help/dictionary/intro28.htm
[snip]
Thanks for bringing in a little history to the discussion. Those links are all local to your system; do you have internet reachable versions of them?
On Thursday 19 May 2005 10:51 pm, Sam Vilain wrote:
> Edward Cherlin wrote: > > Here is the last answer from Ken Iverson, who invented reduce in > > the 1950s, and died recently. > > file:///usr/share/j504/system/extras/help/dictionary/intro28.htm
> [snip]
> Thanks for bringing in a little history to the discussion. Those links > are all local to your system; do you have internet reachable versions of > them?
Stuart Cook wrote: > In Haskell, there is a distinction between foldl and foldl1 (similar > remarks apply to foldr/foldr1[1]): > The former (foldl) requires you to give an explicit 'left unit'[2], > which is implicitly added to the left of the list being reduced. This > means that folding an empty list will just give you the unit. > i.e. > foldl (+) 0 [a,b,c] = ((0+a)+b)+c > foldl (+) 0 [] = 0 > The latter (foldl1) doesn't use a unit value, but this means that you > can't fold empty lists. > i.e. > foldl1 (+) [a,b,c] = (a+b)+c > foldl1 (+) [] = ***error***
sure. Maybe the identity values could be supplied by making the reduce operator for them a curried version of reduce, where reduce requires a list with at least one element (or DIES :))
eg, something similar to; (sorry for the psuedo-perl6, corrections welcome :))
sub prefix:<[+]> (*@args) ::= &reduce.assuming(func => &infix:<+>, first => 0); sub prefix:<[*]> (*@args) ::= &reduce.assuming(func => &infix:<*>, first => 1);
This would mean that unless the operator specifically defines a curried reduce version of itself, then the [] version of it on an empty list will be a hard run-time error.
Then again, maybe an identity trait is more elegant and covers the varied ways that multiple operators combine inside reduce..
> You /could/ try to do something 'sensible' and return 0 or undef, but > this seems likely to result in more confusion.
Personally I think returning an undef for this kind of situation would be as wrong as returning undef for 0/0.
my %hash = ({}, @somelist).reduce({ $^a{$^b} = 1; $^a });
But it puts things all in the wrong place for me. :)
-- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <mer...@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/> Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
>>>>> "Mark" == Mark A Biggar <m...@biggar.org> writes:
Mark> The usual definition of reduce in most languages that support it, is Mark> that reduce over the empty list produces the Identity value for the Mark> operation.
In Smalltalk, the equivalent of "reduce" is "inject:into:", so a "sum" reduce looks like:
Now the advantage here is that if aList is empty, we get back the inject value. Thus, the behavior is always well-defined.
The Perl reduce operator treats the first element of the list as the "inject" value above. However, if the first element is missing, the most Perlish thing I can think of is having it return undef, because it's like you've specified an undef inject value.
I'd also argue that we could provide .inject_into, to make Smalltalkers happy to always spell out the initial value and codeblock, instead of relying on the first element of the list for the initial value.
For example, if I wanted the identity hash (where all values are 1, but keys are original list elements), I could do:
my %hash = @somelist.inject({}, { $^a{$^b} = 1; $^a });
That'd be Way Cool. Once you get your head around inject, you never want to go back to reduce. :)
-- Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095 <mer...@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/> Perl/Unix/security consulting, Technical writing, Comedy, etc. etc. See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!
On Fri, May 20, 2005 at 06:09:55AM -0700, Randal L. Schwartz wrote: > >>>>> "Mark" == Mark A Biggar <m...@biggar.org> writes:
> Mark> The usual definition of reduce in most languages that support it, is > Mark> that reduce over the empty list produces the Identity value for the > Mark> operation.
> In Smalltalk, the equivalent of "reduce" is "inject:into:", so a > "sum" reduce looks like:
> Now the advantage here is that if aList is empty, we get back the inject > value. Thus, the behavior is always well-defined.
> The Perl reduce operator treats the first element of the list as the > "inject" value above. However, if the first element is missing, > the most Perlish thing I can think of is having it return undef, > because it's like you've specified an undef inject value.
I think we should provide built-in operators with an attribute called "identity". Reduce, when given an empty list, would check if the operator has a defined identity attribute. If so, it is returned as the result of the reduction. If the opereator has no identity attribute, reduce throws an exception for an empty list.
Is there a built-in operator that doesn't have a meaningful identity value? I first thought of exponentiation, but it has an identity value of 1 - you just have to realize that since it is a right associative operator, the identity has to be applied from the right.
I suspect that if people ever get into writing code that works on operators instead of data, there would be additional uses found for the identity attribute (and there may be additional operator attributes that make sense there too, although none come immediately to mind). MJD will soon have to start working on the second edition of Higher Order Perl.
John Macdonald wrote: > Is there a built-in operator that doesn't have a meaningful > identity value? I first thought of exponentiation, but it has > an identity value of 1 - you just have to realize that since > it is a right associative operator, the identity has to be > applied from the right.
Well the identity of % is +inf (also right side only). The identities for ~| and ~^ are infinitely long bitstrings of 0's, while that for ~& is a similarly long bitstring of 1's. The chained comparison ops are weird as depending of which why you define the associativity (and thus which side's value you return when true) you get either a left side only or right side only Identity. E.g. if X<Y is left associative and returns Y when true then it has a left side identity of -inf, etc. But as I'm not sure if the chained ops are actually going to be defined defined in terms of the associativity of the binary op (the way false results propagates through messes things up), so that argument may not work.
> Edward Cherlin wrote: > > Here is the last answer from Ken Iverson, who invented > > reduce in the 1950s, and died recently. > > file:///usr/share/j504/system/extras/help/dictionary/intro28 > >.htm
Sorry. It's exactly the same material the provide with their software, so I got confused.
> [snip]
> Thanks for bringing in a little history to the discussion. > Those links are all local to your system; do you have internet > reachable versions of them?
> Cheers, > Sam.
-- Edward Cherlin Generalist & activist--Linux, languages, literacy and more "A knot! Oh, do let me help to undo it!" --Alice in Wonderland http://cherlin.blogspot.com
> Mark A. Biggar wrote: > > Well the identity of % is +inf (also right side only).
> I read $n % any( $n..Inf ) == $n. The point is there's no > unique right identity and thus (Num,%) disqualifies for a > Monoid. BTW, the above is a nice example where a junction > needn't be preserved :)
If as usual the definition of a right identity value e is that a op e = a for all a, then only +inf works. Besdies you example should have been; $n % any (($n+1)..Inf), $n % $n = 0.
> > E.g. if X<Y is left associative and returns Y when true then ...
> Sorry, is it the case that $x = $y < $z might put something else > but 0 or 1 into $x depending on the order relation between $y and $z?
Which is one reason why I siad that it might not make sense to define the chaining ops in terms of the associtivity of the binary ops, But as we are interested in what [<] over the empty list shoud return , the identity (left or right) of '<' is unimportant as I think that should return false as there is nothing to be less then anything else. Note that defaulting to undef therefore works in that case.
-- Mark Biggar m...@biggar.org mark.a.big...@comcast.net mbig...@paypal.com
> > Mark A. Biggar wrote: > > > Well the identity of % is +inf (also right side only).
> > I read $n % any( $n..Inf ) == $n. The point is there's no > > unique right identity and thus (Num,%) disqualifies for a > > Monoid. BTW, the above is a nice example where a junction > > needn't be preserved :)
> If as usual the definition of a right identity value e is that a op e = a for all a, > then only +inf works. Besdies you example should have been; > $n % any (($n+1)..Inf), $n % $n = 0.
> > > E.g. if X<Y is left associative and returns Y when true then ...
> > Sorry, is it the case that $x = $y < $z might put something else > > but 0 or 1 into $x depending on the order relation between $y and $z?
> Which is one reason why I siad that it might not make sense to define the chaining ops in terms of the associtivity of the binary ops, But as we are interested in what [<] over the empty list shoud return , the identity (left or right) of '<' is unimportant as I think that should return false as there is nothing to be less then anything else. Note that defaulting to undef therefore works in that case.
On the contrary a mathematician would say that the empty list is monotonically increasing (vacuously) and the answer should be true.
Matt -- "Computer Science is merely the post-Turing Decline of Formal Systems Theory." -???
On Friday 20 May 2005 07:18, John Macdonald wrote:
> Is there a built-in operator that doesn't have a meaningful > identity value?
Certainly.
> I first thought of exponentiation, but it has > an identity value of 1 - you just have to realize that since > it is a right associative operator, the identity has to be > applied from the right.
> I suspect that if people ever get into writing code that works > on operators instead of data, there would be additional uses > found for the identity attribute (and there may be additional > operator attributes that make sense there too, although none > come immediately to mind).
APL and J programmers have lots of examples.
-- Edward Cherlin Generalist & activist--Linux, languages, literacy and more "A knot! Oh, do let me help to undo it!" --Alice in Wonderland http://cherlin.blogspot.com
> On Thursday 19 May 2005 10:51 pm, Sam Vilain wrote: > > Edward Cherlin wrote: > > > Here is the last answer from Ken Iverson, who invented > > > reduce in the 1950s, and died recently. > > > file:///usr/share/j504/system/extras/help/dictionary/intro > > >28.htm
> > [snip]
> > Thanks for bringing in a little history to the discussion. > > Those links are all local to your system; do you have > > internet reachable versions of them?
It's an enhanced APL without the funny characters.
-- Edward Cherlin Generalist & activist--Linux, languages, literacy and more "A knot! Oh, do let me help to undo it!" --Alice in Wonderland http://cherlin.blogspot.com
