lang comparison: in-place algorithm for reversing a list in Perl, Python, Lisp

Evan Driscoll driscoll at cs.wisc.edu
Thu Mar 1 07:07:21 CET 2012


On 2/29/2012 23:05, Dan Stromberg wrote:
> 
> On Wed, Feb 29, 2012 at 8:07 PM, Xah Lee <xahlee at gmail.com
> <mailto:xahlee at gmail.com>> wrote:
> 
>     This page tells you what's “In-place algorithm”, using {python, perl,
>     emacs lisp} code to illustrate.
> 
> Aren't in-place reversals rather non-functional?

There is one place where they're reasonably idiomatic in Lispy
languages, at least by my understanding. That occurs when you are
writing a function that returns a list and there is a natural recursive
way to build up the answer -- but backwards. The idiom then is to build
up a temporary list up backwards, then call an in-place reversal
function. (NREVERSE in Common Lisp. I thought there was a reverse! in
Scheme, but apparently not.)

This doesn't break the external view of a pure function because the list
that's being reversed is a fresh, temporary list, which is why this
idiom would even fit in pretty well in Scheme.

Evan

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 552 bytes
Desc: OpenPGP digital signature
URL: <http://mail.python.org/pipermail/python-list/attachments/20120301/56997b67/attachment.sig>


More information about the Python-list mailing list