What is a solid example of something that can be done with list comprehensions that is tricky with high order functions?

Question

I've heard from many Pythonists that they prefer list comprehensions because they can do everything you can do using high order functions such as filter and reduce, and more. So this question address them: what is a solid example of something you can do with them, that is tricky to do with HOFs?

Answer 1

The answer is that there is no such example. Everything you can do with list comprehensions has a mechanical translation to higher-order functions. In fact, this is how Haskell implements list comprehensions: it desugars them to higher-order functions.

Given a list comprehension like this:

[(x, y) | x <- [1..3], y <- [4..6]]

Haskell desugars it to:

concatMap (\x -> concatMap (\y -> [(x, y)]) [4..6]) [1..3]

Similarly, if you put in predicates like:

[(x, y) | x <- [1..3], y <- [4..6], x + y /= 5]

... then that desugars to:

concatMap (\x -> concatMap (\y -> if (x + y) == 5 then [(x, y)] else []) [4..6]) [1..3]

In fact, this desugaring is part of the Haskell specification, which you can find here.

Answer 2

As has been said, everything you can do with list comprehensions can be desugared into higher-order functions, but a large part of the problem with doing this in Python is that Python lacks support for the kind of point-free programming you can use with filter, map, and friends in Haskell. Here's a somewhat contrived example, but I think you'll get the idea.

Let's take this Python code:

[(x,y) for x,y in zip(xrange(20), xrange(20, 0, -1)) if x % 2 == 0 and y % 2 == 0]

All it does is print this out:

[(0, 20), (2, 18), (4, 16), (6, 14), (8, 12), (10, 10), (12, 8), (14, 6), (16, 4), (18, 2)]

Here's the equivalent version with filter:

filter(lambda ns : ns[0] % 2 == 0 and ns[1] % 2 == 0, zip(xrange(20), xrange(20, 0, -1)))

I hope you'll agree with me that it's a lot uglier. There isn't really much you can do to make it less ugly without defining a separate function.

But let's look at the equivalent version in Haskell:

[(x,y) | (x,y) <- zip [0..20] [20,19..0], x `mod` 2 == 0 && y `mod` 2 == 0]

Okay, pretty much as good as the Python list comprehension version. What about the equivalent filter version?

import Data.Function
let f = (&&) `on` (==0) . (`mod` 2)
filter (uncurry f) $ zip [0..20] [20,19..0]

Okay, we had to do an import, but the code is (imo) a lot clearer once you understand what it does, although some people might still prefer f to be pointed, or even a lambda with filter. In my opinion the point-free version is more concise and conceptually clear. But the main point I want to make is that it is not really going to be this clear in Python because of the inability to partially apply functions without bringing in a separate library, and the lack of a composition operator, so in Python it is a good idea to prefer list comprehensions over map/filter, but in Haskell it can go either way depending on the specific problem.

Answer 3

In Haskell, list comprehensions are 'syntactic sugar' for conditionals and functions (or can trivially be translated into do notation and then desugared monadically). Here's the 'official' guide to translating them: http://www.haskell.org/onlinereport/haskell2010/haskellch3.html#x8-420003.11

Hence, since list comprehensions can be translated mechanically and straightforwardly into equivalent code using simply higher order functions, there is by definition nothing you can do with them that is difficult to do without them.

Answer 4

The others are correct; list comprehensions do not provide any better manipulation of sequences, per se, compared to functions like map, reduce, filter, etc. They did not really address your question as to why Python programmers trump list comprehensions over higher order functions, though.

The reason Python advocates it and Python programmers use them is because according to Guido, the language creator, list comprehensions (and set comprehensions and dict compressions and generator expressions) are easier to read and to write than functional expressions. Python's philosophy is that readability trumps all.

Guido dislikes functional programming constructs in general, and was wary about adding lambda syntax. It is just a matter of style and taste, not expressiveness or power. His opinions shape Python and how it is written.

For more details, here is a proposal by Guido to remove lambda, map, filter, and reduce from Python 3 and up. It was not implemented (except for the removal of reduce, which is no longer a builtin function) , but he lays out his reasonings here: http://www.artima.com/weblogs/viewpost.jsp?thread=98196

He sums it up as follows, though:

filter(P, S) is almost always written clearer as [x for x in S if P(x)], and this has the huge advantage that the most common usages involve predicates that are comparisons, e.g. x==42, and defining a lambda for that just requires much more effort for the reader (plus the lambda is slower than the list comprehension).

Answer 5

compare

    [[x*x, x*x+x ..] | x <- [2..]]

and

    map (\x-> map (*x) $ enumFrom x) $ enumFrom 2

The first is obviously more readable. You asked "tricky", not "impossible". And with filter, there's nothing to indicate whether we're filtering in, or out the elements that pass, or fail, the given test. With LCs it is visually manifest.

So whenever there's an LC formulation, it is preferred IMO, just for the readability of it. Haskell's LC syntax is especially succinct and clear, clearer than Python's IMO (less noise). Shame not to use it. :)

Answer 6

I very rarely use list comprehensions for exactly the reasons in this question. However, there is one case where I've found them to be the only concise syntax: when a refutable pattern is to the left of the <-. Example:

data Foo = Bar Int | Baz String

getBazs :: [Foo] -> [String]
getBazs xs = [x | Baz x <- xs]

To write that without a list comprehension, you'd have to do something a lot longer like this:

data Foo = Bar Int | Baz String

getBazs :: [Foo] -> [String]
getBazs = foldr go []
          where go (Baz x) acc = x:acc
                go _       acc =   acc

But unlike the list comprehension, that isn't a "good producer", so its output list won't be able to fuse with anything. To fix that, you'd have to either add the rewrite rules by hand, or switch to importing a different function that is a good producer:

import Data.Maybe

data Foo = Bar Int | Baz String

getBazs :: [Foo] -> [String]
getBazs = mapMaybe go
          where go (Baz x) = Just x
                go _       = Nothing

End result is it's a lot more to think about, and a lot more code, than the basic list comprehension, for the same result.