From: Kyle Rawlins <rawlins@...>
Date: 2002-06-07T01:03:27+09:00
Subject: Re: Array.foldr (Array.reduce)

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

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

-- 
http://mas.cs.umass.edu/~rawlins
--
Delta Johnny Niner, You are cleared to land at 1 8 0 degrees.