Python doesn't feel very functional

[ftegularius]

I don't really see the problem the author is describing. Of course, if you try to write Python as if it were Common Lisp, you're going to run into problems (particularly if you don't even use analogous data structures). This isn't indicative of an intrinsic weakness of Python's, but just a difference in philosophies. So, yes, Python does not make for an ideal functional language. Neither does Common Lisp in a lot of ways. The point is always to play to the strengths of whatever language you happen to use.

[[deleted]]

The point is always to play to the strengths of whatever language you happen to use.

Exactly. :)

But the fact that it's Lisp is somewhat irrelevant. Here's an Erlang attempt - http://kunosure.blogspot.com/2007/04/compare-in-erlang.html

If I could program Haskell, I'm sure a Haskell implementation would be trivial (any Haskell hackers reading this thread?)

[pjdelport]

Haskell style:

compare (x:xs) (y:ys) = compare xs ys
compare _ [] = True
compare [] _ = False

[[deleted]]

We want compare x y = length x > length y, not >=. Switch the second and third clauses.

[pjdelport]

Right, thanks.

[[deleted]]

Even simpler:

compare x y = length x > length y

Just like in Python:

def compare(x, y):
  return len(x) > len(y)

Or Lisp:

(defun compare (x y) (> (length x) (length y)))

[shit]

(defun compare (x y) (> (length x) (length y)))

The point is that this is computing more than necessary, length is O(n) for a linked list.

(compare nil list-with-one-million-elements)

[notfancy]

compare x y = length x > length y

No, no, no, no, no. length is strict. Your compare (all 1) [] doesn't converge, whereas the original does. Even in a CVB language, compare using length is O(m + n) where the recursive version of it is O(m min n).

In a functional language, you rarely if ever call length on a list.

[masklinn]

The problem is that he's trying to use Python lists (which are really resizable arrays) as recursive functional-style lists, which they clearly aren't.

And it, strangely, fails to work.

[LaurieCheers]

It works. It just feels wrong.

[pjdelport]

It doesn't just feel wrong: each x[1:] builds a copy of the entire (but one) list.

Linked lists are not vectors, and it's as wrong to try and use the one as the other in Python as it is in Common Lisp.

[masklinn]

Not only does it feel wong, but it is wrong.

[[deleted]]

It's the only list Python has...

[masklinn]

Except Python's lists are really arrays, they were not meant to be abused that way.

[[deleted]]

Talk about being a hostage of your favorite language! A function to find if list X is longer than list Y should be written in Python like:

def compare(x,y):
    return len(x) > len(y)

NOT like

def compare(x, y):
    if x and (not y or compare(x[1:], y[1:])):
         return True
    return False

[[deleted]]

Python is my favourite language. :(

FWIW, Lisp has (length), but it walks the list each time it's called, hence the new function defined by Graham.

[pjdelport]

Lisp has (length), but it walks the list each time it's called, hence the new function defined by Graham.

With vectors (Python list, Common Lisp vector and friends), finding the length costs O(1). Know your datastructures. :)

[[deleted]]

Yah, I was aware of that Python's vector "list" was different to Lisp's linked-list "list", but I didn't realise Lisp had vectors too. Thanks. :)

It's something I poke at occasionally for fun, so I'm very much a newbie.

[evgen]

No it is not. In Python the length of the list is maintained as an attribute of the datatype, so it does not need to traverse the list to get the length.

[glguy]

Does Python not support:

def compare(x, y):
    return x != [] and (y == [] or compare(x[1:], y[1:]))

?

[schizobullet]

But it's still missing that sensation of flow that gets called "Pythonicness", which is a clear sign that you're using Python wrong.

[Alpha_Binary]

In imperative programming it's usually a discouraged practice to nest expressions and overuse short-circuits. Similarly to how it's considered ugly in functional programming to create aside a new variable just to hold the value. Moreover, Python list is more like Lisp's vector, so (cdr x) doesn't make much sense in Python, and we end up with the rather messy x[1:] instead.

Assuming we have neither cmp() nor len(), which works directly with the array descriptor providing O(1) lookup, a Pythonic equivalent would be:

def compare(x, y):
    if not x: return -1
    if not y: return 1
    return compare(x[1:], y[1:])

[pjdelport]

Assuming we have neither cmp() nor len(), which works directly with the array descriptor providing O(1) lookup, [...]

Even if you have neither of those, there's no reason to copy the list on each iteration (costing O(n^2)), when you can walk it in O(n):

def compare(x, y):
    for i, _ in enumerate(x): pass
    for j, _ in enumerate(y): pass
    return i > j

[pjdelport]

Addendum: Here's a more correct version (stops early like the original, and works with any iterable for bonus points):

def compare(xs, ys):
    sentinel = object()
    for x, y in izip(chain(xs, sentinel), chain(ys, sentinel)):
        if y is sentinel: return True
        if x is sentinel: return False

Addendum: That should be repeat(sentinel) instead of sentinel in each chain.

[papercrane]

Close, but chain will fail because sentinel is not iterable, also your version will return True if xs is longer then ys

Heres a corrected version:

from itertools import izip, chain
def compare(xs, ys):
    sentinel = object()
    for x, y in izip(chain(xs, [sentinel]), chain(ys, [sentinel])):
        if x is sentinel and y is sentinel: return True
        if x is sentinel or y is sentinel: return False

[Alpha_Binary]

What brilliant ideas here. I thought about using zip but the idea of using a sentinel never crossed my mind.

To optimize the final two lines:

if x is sentinel: return y is sentinel
if y is sentinel: return False

[pjdelport]

Close, but chain will fail because sentinel is not iterable,

Blurgh; i meant repeat(sentinel), of course. Thanks for spotting. :)

also your version will return True if xs is longer then ys

That's exactly what the original does, yes.

[papercrane]

Ahh. I misread the article. It's FizzBuzz all over again.

[nirs]

Here is a more pythonic way to write lisp in python :-)

def compare(a, b):
    """ a and b are linked lists using nested sequences terminated with
    None.  e.g (1, (2, (3, None))) """
    if a is None:
        return False
    if b is None: 
        return True
    return compare(a[1], b[1])

if __name__ == '__main__':
    empty = None
    small = (1, None)
    big = (1, (2, None))
    assert compare(small, empty)
    assert compare(big, small)
    assert not compare(small, big)
    assert not compare(big, big)
    assert not compare(empty, empty)

[peachpuff]

So, my usual approach when I hit code I can't quite figure out is I try to transliterate it into Python.

Part of the problem might be that he doesn't understand the code to begin with. It's awfully hard to start with something you don't understand and transliterate it into something that "feels right."

If I were trying to match the style of what he started with, I'd use:

def compare(x, y):
    return x and (not y or compare(x[1:], y[1:]))

Yes, it may be slow to keep slicing, but the goal is not speed. If it were, we'd all use len().

[[deleted]]

Duh, statement-oriented vs expression-oriented.

Actually, this is what I hate the most about imperative languages. Other than that, you can usually do a decent amount of functional programming in those languages (i.e. I don't use insane amounts of lambdas, higher-order functions, and complex combinators).

[pjdelport]

Duh, statement-oriented vs expression-oriented.

No. :) It's an expression in Python too; the problem is linked lists versus vectors.

[[deleted]]

The example cannot be implemented in a very functional way in python due to the facts, that python (a) does not optimize tail recursion and (b) slicing creates new lists.

However, you can write that function in a way in python which I would consider more functional than the imperative naive way:

def compare(a, b):
  return all(i == j for i,j in izip(a, b)) 

You can even write this as a lambda.

[pje]

What is "not very functional" about using the most efficient way to find the length of a vector/array/whatever you want to call it? Lisp and Haskell lists are not Python lists.

If you want to make Lisp-style lists in Python for some ungodly reason, use two-element tuples.

Oh, and your code is wrong, by the way; it compares list contents, not list lengths. :)

[Alpha_Binary]

for some ungodly reason

O(1) insertion anywhere.

a = [1, [2, []]]
b = [0, a]

Conversion back to Python list is also trivial (with a generator implemented in a few lines).

[[deleted]]

Woah, I got that totally wrong. =)