Nicer way to write folding? (list reversal?) 
Author Message
 Nicer way to write folding? (list reversal?)

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.*-*-*.com/



Mon, 21 Jun 2004 05:27:52 GMT  
 Nicer way to write folding? (list reversal?)

Quote:
> 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/



Mon, 21 Jun 2004 06:57:21 GMT  
 Nicer way to write folding? (list reversal?)
[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

Quote:

>> 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/

--
http://www.acooke.org


Mon, 21 Jun 2004 15:37:45 GMT  
 Nicer way to write folding? (list reversal?)

Quote:

> 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?

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

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

Quote:
>  Is recursion any faster than it used to be

Nope.

Quote:
> (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.

Quote:
> 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.



Mon, 21 Jun 2004 18:59:50 GMT  
 Nicer way to write folding? (list reversal?)
[...]

Quote:
> 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



Mon, 21 Jun 2004 20:22:23 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Nicer way to write folding? (list reversal?)

2. NICE and NICE Discussion List

3. How do I write byte reversal code?

4. Nice parser for C++ header language written in Scheme

5. List of objects sorted in multiple ways

6. Web Page Listing Ways People Use Ruby

7. The Official Naughty Or Nice List

8. list comprehensions *are* nice

9. Decimal division causing sign reversal

10. Newbie Q: String reversal

11. Reversal of date in text file

12. Reversal of date in text file

 

 
Powered by phpBB® Forum Software