Query re: duction and precedence.

In general, is

[op] (p1,p2,p3,p4...)

expected to return the same result as

p1 op p2 op p3 op p4...

including precedence considerations?

That is, should

[**](2,3,4)

return 2^(3^4)=2^81, or (2^3)^4 = 4096?

--
Mark J. Reed <markjreed@mail.com>

On Sat, Mar 29, 2008 at 10:18:53PM -0400, Mark J. Reed wrote:
: In general, is
:
: [op] (p1,p2,p3,p4...)
:
: expected to return the same result as
:
: p1 op p2 op p3 op p4...
:
: including precedence considerations?
:
: That is, should
:
: [**](2,3,4)
:
: return 2^(3^4)=2^81, or (2^3)^4 = 4096?

Yes, in fact the section on Reduction Operators uses exponentiation
obliquely in one of its examples of something that should work
right-to-left.  Admittedly it's not clearly stated there...

But the basic idea is always that the reduction form should produce
the same result as if you'd written it out with interspersed infixes.
It's a linguistic construct, not a functional programming construct.
It's not intended to be in the same league as foldl and foldr, and
is only just slightly beyond a macro insofar as it can intersperse
however many operators it needs to for an arbitrarily sized list.
It's not making any attempt to deal with anonymous first-class
functions though.  Call a real function for that. :)

Larry

You anticipated me. So, is there a core method for
foldl/foldr/inject/reduce, or do you have to roll your own as in p5?



On 3/29/08, Larry Wall <larry@wall.org> wrote:
> On Sat, Mar 29, 2008 at 10:18:53PM -0400, Mark J. Reed wrote:
> : In general, is
> :
> : [op] (p1,p2,p3,p4...)
> :
> : expected to return the same result as
> :
> : p1 op p2 op p3 op p4...
> :
> : including precedence considerations?
> :
> : That is, should
> :
> : [**](2,3,4)
> :
> : return 2^(3^4)=2^81, or (2^3)^4 = 4096?
>
> Yes, in fact the section on Reduction Operators uses exponentiation
> obliquely in one of its examples of something that should work
> right-to-left.  Admittedly it's not clearly stated there...
>
> But the basic idea is always that the reduction form should produce
> the same result as if you'd written it out with interspersed infixes.
> It's a linguistic construct, not a functional programming construct.
> It's not intended to be in the same league as foldl and foldr, and
> is only just slightly beyond a macro insofar as it can intersperse
> however many operators it needs to for an arbitrarily sized list.
> It's not making any attempt to deal with anonymous first-class
> functions though.  Call a real function for that. :)
>
> Larry
>

--
Sent from Gmail for mobile | mobile.google.com

Mark J. Reed <markjreed@mail.com>

Mark J. Reed wrote:
> You anticipated me. So, is there a core method for
> foldl/foldr/inject/reduce, or do you have to roll your own as in p5?
>
> On 3/29/08, Larry Wall <larry@wall.org> wrote: 

I think it would be powerful while not too difficult for Perl 6's "reduce"
to be able to do everything you'd get in functional programming, at least
some of the time.

Generally speaking, as long as the base operator is associative, then

[op] *$seq_or_array_etc

... should auto-parallelize with a deterministic result; or as long as the
base operator is both associative and commutative, then

[op] *$set_or_bag_or_seq_or_array_etc

... should also auto-parallelize with a deterministic result.

And then you get all the functional programming goodies.  The first example
works for string catenation, but the second doesn't; the second does work
for  sum|product|and|or|xor|union|intersectio
n though.

Some base operators have an identity value in case the input collection is
empty, as is the case with the above operators, but others only work with a
non-empty input, such as mean|median|mode.

For other operators, non-assoc etc, the work will probably all have to be
linear.  Eg difference|quotient|exponentiation.

Something I'm wondering, though, realistically how often would one actually
be reducing on an operator that is not associative?  What practical use is
there for [-] (3,4,5) for example?

Are you just supporting that with all operators for parsing rule simplicity
as per a macro?  I can understand that reasoning, but otherwise ...

I would think it makes sense to restrict the use of the reduction
meta-operator to just work over operators that are at least associative.

-- Darren Duncan

I'm a believer in generalizing where possible, modulo the principles
of KISS and YAGNI. The latter essentially means "at least make it
general enough that you can extend it later without major retooling if
it turns out YNIAA.".  It's pretty surprising what can turn out to be
useful, so I've never been swayed by arguments from "what is it good
for?"...



On 3/30/08, Darren Duncan <darren@darrenduncan.net> wrote:
> Mark J. Reed wrote: 
>
> I think it would be powerful while not too difficult for Perl 6's "reduce"
> to be able to do everything you'd get in functional programming, at least
> some of the time.
>
> Generally speaking, as long as the base operator is associative, then
>
>    [op] *$seq_or_array_etc
>
> ... should auto-parallelize with a deterministic result; or as long as the
> base operator is both associative and commutative, then
>
>    [op] *$set_or_bag_or_seq_or_array_etc
>
> ... should also auto-parallelize with a deterministic result.
>
> And then you get all the functional programming goodies.  The first exampl
e
> works for string catenation, but the second doesn't; the second does work
> for  sum|product|and|or|xor|union|intersectio
n though.
>
> Some base operators have an identity value in case the input collection is
> empty, as is the case with the above operators, but others only work with 
a
> non-empty input, such as mean|median|mode.
>
> For other operators, non-assoc etc, the work will probably all have to be
> linear.  Eg difference|quotient|exponentiation.
>
> Something I'm wondering, though, realistically how often would one actuall
y
> be reducing on an operator that is not associative?  What practical use is
> there for [-] (3,4,5) for example?
>
> Are you just supporting that with all operators for parsing rule simplicit
y
> as per a macro?  I can understand that reasoning, but otherwise ...
>
> I would think it makes sense to restrict the use of the reduction
> meta-operator to just work over operators that are at least associative.
>
> -- Darren Duncan
>

--
Sent from Gmail for mobile | mobile.google.com

Mark J. Reed <markjreed@mail.com>

Mark J. Reed wrote:
> I'm a believer in generalizing where possible, modulo the principles
> of KISS and YAGNI. The latter essentially means "at least make it
> general enough that you can extend it later without major retooling if
> it turns out YNIAA.".  It's pretty surprising what can turn out to be
> useful, so I've never been swayed by arguments from "what is it good
> for?"... 

The reduce meta-operator over - in APL gives alternating sum, similarly
alternating quotient for /, which only works if you right associate
things.

[-] 1,2,3,4,5,6 => 1-2+3-4+5-6 # pseudo-apl

[/] 1,2,3,4,5,6 => (1*3*5)/(2*4*6) #pseudo-apl

note that would break the perl 6 simple rule that [-] 1,2,3 => 1-2-3,
but gives something much more useful.  There currently is no easy way to
do alternating sum/quotient in perl6.

--
mark@biggar.org
mark.a.biggar@comcast.net

On Sun, Mar 30, 2008 at 08:21:39AM -0700, Mark A. Biggar wrote:
> The reduce meta-operator over - in APL gives alternating sum, similarly
> alternating quotient for /, which only works if you right associate
> things.
>
> [-] 1,2,3,4,5,6 => 1-2+3-4+5-6 # pseudo-apl
>
> [/] 1,2,3,4,5,6 => (1*3*5)/(2*4*6) #pseudo-apl
>
> note that would break the perl 6 simple rule that [-] 1,2,3 => 1-2-3,
> but gives something much more useful.  There currently is no easy way to
> do alternating sum/quotient in perl6.

How about...?

# alternating sum of elements in @list
$altsum = [+] ({ $^a - $^b } for @list);

Pm

On Sun, Mar 30, 2008 at 12:56 PM, Mark J. Reed <markjreed@mail.com> wrote:
> I'm a believer in generalizing where possible, modulo the principles
>  of KISS and YAGNI. The latter essentially means "at least make it
>  general enough that you can extend it later without major retooling if
>  it turns out YNIAA.".  It's pretty surprising what can turn out to be
>  useful, so I've never been swayed by arguments from "what is it good
>  for?"...

Amen.  Incidentally, you'll find that that is the most common response
when a programmer is introduced to a language feature he has not seen
before.

Tell a C programmer about objects, "okay, that's , but what is it good f
or".

Tell a C++ programmer about closures, "hmm, that just seems like it
would lead to bad design".

Tell a scheme programmer about laziness, "weird, I can't see how I
would ever use that".

Luke

HaloO,

Darren Duncan wrote:
> For other operators, non-assoc etc, the work will probably all have to
> be linear.  Eg difference|quotient|exponentiation.

That's why I would rename the left and right operator associativity
to left and right sequentiality. Note that there's a fundamental
difference between difference and quotient on the one hand and
exponentiation on the other. The former are defined as inverses
of associative operations. The right inverse of exponentiation is
logarithm which is not available as an operator for good reasons.
In other words exponentiation as a binary operator is a bit dubious.
Well, or we should spec 8 log 2 == 3 and bewail the fact that // is
already taken for much more useful things.


> Something I'm wondering, though, realistically how often would one
> actually be reducing on an operator that is not associative?  What
> practical use is there for [-] (3,4,5) for example?

I see it as a convenient notation for 3 - ([+] 4,5) just as $x - $y
means $x + -$y. Practical example is [-] $money, @bills which stresses
the payment of the bills whereas in $money - [+]@bills the summing-up
of the bills visually outweighs the subtraction. Perl 6 might actually
develop the idiom that [-]@array implies a special role of @array[0].


Regards, TSa.
--

The Angel of Geometry and the Devil of Algebra fight for the soul
of any mathematical being.   -- Attributed to Hermann Weyl

The inevitable question - why not support Polish Notation or Reverse
Polish ? Well known to be easier to use, since it involves no
ambiguities in regard to association, is notationally clearer (not
needing parentheses). Seems to make it easier to analyze what one might
want to mean by

[op] (p1 p2 p3 ... )

E.g.,=20

Convention 1

[op] (p1 p2 p3 ... ) =3Dby definition=3D p1 p2 op  p3 op ... pN op

Convention 2
=20
[op] (p1 p2 p3 ... ) =3Dby definition=3D p1 p2 p3 ... pN op op op =
...
op

One could support both conventions (with notational differences) ...

Example

[^] (2 3 4) =3Ddefn 1=3D 2 3 ^ 4 ^ , i.e., (2^3)^4

[^] (2 3 4) =3D defn 2=3D 2 3 4 ^^ , i.e., (2^(3^4))

Etc.

-
Hugh Miller
e-mail:	hdmi@chevrontexaco.com


-----Original Message-----
From: Darren Duncan [mailto:darren@darrenduncan.net]=20
Sent: Sunday, March 30, 2008 2:00 AM
To: p6l
Subject: Re: Query re: duction and precedence.

Mark J. Reed wrote:
> You anticipated me. So, is there a core method for=20
> foldl/foldr/inject/reduce, or do you have to roll your own as in p5?
>=20
> On 3/29/08, Larry Wall <larry@wall.org> wrote: 
 

I think it would be powerful while not too difficult for Perl 6's
"reduce"=20
to be able to do everything you'd get in functional programming, at
least some of the time.

Generally speaking, as long as the base operator is associative, then

[op] *$seq_or_array_etc

... should auto-parallelize with a deterministic result; or as long as
the base operator is both associative and commutative, then

[op] *$set_or_bag_or_seq_or_array_etc

... should also auto-parallelize with a deterministic result.

And then you get all the functional programming goodies.  The first
example works for string catenation, but the second doesn't; the second
does work for  sum|product|and|or|xor|union|intersectio
n though.

Some base operators have an identity value in case the input collection
is empty, as is the case with the above operators, but others only work
with a non-empty input, such as mean|median|mode.

For other operators, non-assoc etc, the work will probably all have to
be linear.  Eg difference|quotient|exponentiation.

Something I'm wondering, though, realistically how often would one
actually be reducing on an operator that is not associative?  What
practical use is there for [-] (3,4,5) for example?

Are you just supporting that with all operators for parsing rule
simplicity as per a macro?  I can understand that reasoning, but
otherwise ...

I would think it makes sense to restrict the use of the reduction
meta-operator to just work over operators that are at least associative.

-- Darren Duncan