Array.foldr (Array.reduce)


(KONTRA Gergely) #1

Hi!

I’ve noticed ruby has nice high level functions.
But I cannot find the reduce or foldr method.

I’ve discovered the inject method in the Ruby book.
It is very similar to one of the fold(l/r) methods in SML.

The def of foldr is:
where

  • denotes any kind of operator with 2 operands
    e is the (right) unit element

folr e + array = array1 + (array2 + … + (arrayn + e)…)

And foldl is the other way (if + is associative, then it gives the same
result)

If inject will be available, will foldl and foldr (=reduce) also?
Thanks in advance.

Gergo

±[Kontra, Gergely @ Budapest University of Technology and Economics]-+

    Email: kgergely@mcl.hu,  kgergely@turul.eet.bme.hu          |

URL: turul.eet.bme.hu/~kgergely Mobile: (+36 20) 356 9656 |
±------“Olyan langesz vagyok, hogy poroltoval kellene jarnom!”-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.net


(Ned Konz) #2

If I understand you, you could just do this:

used like:

foldr(e, array) { |partial,b| partial+b }

def foldr(e, array)
result = e
array.reverse_each { |elem| result = yield(result, elem) }
result
end

Same thing, but left associative

def foldl(e, array)
result = e
array.each { |elem| result = yield(result, elem) }
result
end

and you should provide it for Enumerables too:

module Enumerable
def foldr(e)
result = e
reverse_each { |elem| result = yield(result, elem) }
result
end

Same thing, but left associative

def foldl(e)
result = e
each { |elem| result = yield(result, elem) }
result
end
end

arr = [1,2,3,4,5]
p foldr(6, arr) { |a,b| a + b } => 21
p arr.foldr(6) { |a,b| a + b } => 21

···

On Thursday 06 June 2002 07:55 am, Kontra, Gergely wrote:

folr e + array = array1 + (array2 + … + (arrayn + e)…)

And foldl is the other way (if + is associative, then it gives the
same result)

If inject will be available, will foldl and foldr (=reduce) also?
Thanks in advance.


Ned Konz
http://bike-nomad.com
GPG key ID: BEEA7EFE


(Yukihiro Matsumoto) #3

Hi,

···

In message “Array.foldr (Array.reduce)” on 02/06/06, “Kontra, Gergely” kgergely@mlabdial.hit.bme.hu writes:

If inject will be available, will foldl and foldr (=reduce) also?

“inject” is available in 1.7. The point is the method name, for
example, Python has “reduce” which works like foldl (and no foldr).

						matz.

(Nobuyoshi Nakada) #4

Hi,

···

At Fri, 7 Jun 2002 00:13:33 +0900, Ned Konz wrote:

and you should provide it for Enumerables too:

module Enumerable
def foldr(e)
result = e
reverse_each { |elem| result = yield(result, elem) }
result
end

Enumerable doesn’t have reverse_each. Array#reverse_inject may
be possible.


Nobu Nakada


(Kyle Rawlins) #5

Just a note in the case that you want a really correct solution, AFAIK you
aren’t guaranteed the existance of ‘reverse_each’ in an Enumerable class, only
’each’. Most of them do have it though, but e.g. Range doesn’t seem to as of
1.6.7. I think this came up in a previous ruby-talk thread but I don’t have
the reference on me; the solution there (I think) was to check whether the
argument responds to that method, and then use it if it does; I can’t remember
what it did if it wasn’t there. It is entirely possible to convert the whole
thing to an array and reverse that if it can’t be reversed by itself, since
that is already part of Enumerable.

This is all quite unfortunate because it means that a really general foldr
won’t be particularly efficient in some cases (at least for really big lists),
but I suppose there’s not much to do about that. If whatever operation you are
folding over is transitive though it would always be better to use foldl, and
this seems like a somewhat silly thing to have to worry about in a high level
language. Maybe the practical difference would turn out to be small, though.

-kyle

···

On Fri, Jun 07, 2002 at 12:13:33AM +0900, Ned Konz wrote:

and you should provide it for Enumerables too:

module Enumerable
def foldr(e)
result = e
reverse_each { |elem| result = yield(result, elem) }
result
end


http://mas.cs.umass.edu/~rawlins

Delta Johnny Niner, You are cleared to land at 1 8 0 degrees.


(KONTRA Gergely) #6

If I understand you, you could just do this:

used like:

foldr(e, array) { |partial,b| partial+b }

def foldr(e, array)
result = e
array.reverse_each { |elem| result = yield(result, elem) }
result
end

Thanks for your solution.
Will these (and similarly general?) methods be in the next release, or
you try to keep ruby as compact as possible?

Gergo

±[Kontra, Gergely @ Budapest University of Technology and Economics]-+

    Email: kgergely@mcl.hu,  kgergely@turul.eet.bme.hu          |

URL: turul.eet.bme.hu/~kgergely Mobile: (+36 20) 356 9656 |
±------“Olyan langesz vagyok, hogy poroltoval kellene jarnom!”-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.net

···

On Thursday 06 June 2002 07:55 am, Kontra, Gergely wrote: