Nicer way to write folding? (list reversal?)

[and...@acooke.org]

Hi,

In the code below, foldr2 is clearly uglier than the rest. Is there a
nicer way (without destructive reversal - yuck - of the list
argument)? Also, are these things built-in (can't find them)? Is
recursion any faster than it used to be (I've not been following
Python development so am wondering if anything in 2 (or 2.2) would
help; foldr2 and fold2 are expected to be faster than foldl and foldr,
although I've not done any timing).

Thanks,
Andrew

# foldr: f(x1, f(x2, ... f(xn-1, f(xn, c))...))

# foldl: f(xn, f(xn-1, ... f(x2, f(x1, c))...))

def foldr(action, start, list):
if not list: return start
else: return action(list[0], foldr(action, start, list[1:]))

def foldl(action, start, list):
if not list: return start
else: return foldl(action, action(list[0], start), list[1:])

def foldr2(action, start, list):
for i in range(len(list), 0, -1): start = action(list[i-1], start)
return start

def foldl2(action, start, list):
for x in list: start = action(x, start)
return start

print foldr(operator.add, "x", ["a", "b", "c"])
print foldl(operator.add, "x", ["a", "b", "c"])
print foldr2(operator.add, "x", ["a", "b", "c"])
print foldl2(operator.add, "x", ["a", "b", "c"])

abcx
cbax
abcx
cbax

--
http://www.acooke.org

[Jason Orendorff]

> In the code below, foldr2 is clearly uglier than the rest. Is there a
> nicer way (without destructive reversal - yuck - of the list
> argument)? Also, are these things built-in (can't find them)?

foldr() is built-in. It's called reduce().

>>> from operator import add
>>> nums = [1, 2, 3, 4, 5]
>>> reduce(add, nums, 0)
15

## Jason Orendorff http://www.jorendorff.com/

[and...@acooke.org]

[crossposting to comp.lang.functional in case someone there knows
whether there's a convention, but followup still to comp.lang.python]

Thanks, I didn't know that. It seems to be

f(f(...f(f(c, xn), xn-1) ..., x2), x1)

rather than

f(x1, f(x2, ... f(xn-1, f(xn, c))...))

(ie the arguments to f are reversed). Is there any consensus across
languages about which way round the arguments should be in foldr?

In ML, it's the second argument to the function that takes the output
of earlier results:

- foldr;
val it = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Cheers,
Andrew

--
http://www.acooke.org

[Michael Hudson]

and...@acooke.org writes:

> Hi,
>
> In the code below, foldr2 is clearly uglier than the rest. Is there a
> nicer way (without destructive reversal - yuck - of the list
> argument)?

No. It's not that bad is it?

> Also, are these things built-in (can't find them)?

Well, there's reduce, but it's almost always a bad idea.

> Is recursion any faster than it used to be

Nope.

> (I've not been following Python development so am wondering if
> anything in 2 (or 2.2) would help;

Oh, if you're migrating from 1.5.2 it might be a touch quicker.
Nothing really siginificant though.

> foldr2 and fold2 are expected to be faster than foldl and
> foldr, although I've not done any timing).

I'd be amazed if they weren't.

Now for some content <wink>: why are you writing these functions?
It's not really a sensible way to program in Python.

Cheers,
M.

[and...@acooke.org]

Michael Hudson <m...@python.net> wrote:
[...]

> Now for some content <wink>: why are you writing these functions?
> It's not really a sensible way to program in Python.

There's two answers:

Superficial: I was manipulating paths - ended up writing an
explodePath function that calls os.path.split again and again and then
wanted to reassemble the result after processing. Realised I needed
to fold os.path.join and started wondering about folds.

Slightly deeper: I use Python only for odds n sods, but am learning ML
with a particular (larger) task in mind. Realised that playing with
this would hammer home the difference between the two folds and was
also curious about whether 2/2.2 was any more functional than 1.5. I
know that Python wasn't (and apparently still isn't) intended to be
used "functionally".

Actually, Python is quite nice for playing around learning things like
this (especially now in 2.2 that scope seems to work like you'd
expect). It's fun being able to swap between imperative and
declarative code and compare them. Actually, after writing up to the
end of the last sentence I just rewrote that pathExplode function that
I mentioned above so that it's recursive - see what you're making me
do with your silly questions! :-)

Andrew

--
http://www.acooke.org