Saturday, February 20, 2010

What in the world is a "List Comprehension"?

Sometimes I'll read something about a programming language I don't know and I'll be a little curious about some term I'm not familiar with. The writer will rave on and on about how great this language is because it supports this thing, yet I don't understand what it can do for me. Until recently, this is how it had been for me with "List Comprehensions".

Well, I found an excellent explanation of List Comprehensions in Erlang. Here's my thumbnail explanation:

"A List Comprehension is a way to apply some function to every member of a list."

Now, for an example. Here's an example, straight from the Erlang shell:

1> AList = [1,2,3,4].
[1,2,3,4]
2> ListDoubled = [ X * 2 || X <- AList ].
[2,4,6,8]

Let's look at this, line by line.

1> AList = [1,2,3,4].
This is me typing in the List I want to start with. Obviously, it contains 1,2,3, and 4.

[1,2,3,4]
This is the Erlang shell, responding with the right hand side after binding the list to the variable AList.

2> ListDoubled = [ X * 2 || X <- AList ].
This is the List Comprehension. It reads something like this: "A variable named ListDoubled should be bound to a new list made from applying the function "some variable times 2" to every item in an existing list, which is called "AList".

[2,4,6,8]
This is the result of my List Comprehension. As it should be, every member of the first list was doubled.

So that's it! A List Comprehension is just a very compact way to apply some function (and some filters, it turns out) to a list. The result is another list.

For more on List Comprehensions, I'd refer you to the excellent book "Programming Erlang" by Joe Armstrong. It's very readable, and makes learning new concepts easy.

Happy Coding!

Rick

5 comments:

Anonymous said...

Programming in Scala (nice Book!)
explains it quite blunt "for" me.
while "loops"
for "comprehension"
so a loop does something ( side effect) and return nothing
But the for comprehension in scala return something.

So a comprehension is a control structure which fits in the functional paradigm. -> avoid side effects but offer great transformation abilites by using Datastructures with apropriate Interfaces (Monads?!, etc..)
I think also that it may be wrong to simply call this a "List" comprehension. Because as i see this you can use this control structures not only with List's but ALL Datastructures implementing the required Interfaces (map, FlatMap etc...)
But i think you wrote this post as a personal insight for you, i hope you don't stop here because thats just a nice starting point how functional programming works and why its really nice :)

Anonymous said...

ah i forgot check out this "for" example:
http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-2.html

hth same as above ;)

Tony Morris said...

It's actually a bit more than that.

A list comprehension (in most languages) is actually a bind through the list monad. This isn't as scary as it sounds. What you have shown is a bind at the first level (also known as "map"). There is a zeroeth level (often called return or unit) and levels above one. This is also often called "lifting".

If we were to write the type signature for map it would look something like this: List x -> (x -> y) -> List y which would take a List of x an apply the given function to each element to yield a List of y.

A List comprehension allows this but it also allows List x -> List y -> (x -> y -> z) -> List z which is lifted to the next level. This goes on indefinitely.

Hope this helps.

Thomas Foxx said...

To put it in less programming-specific terms: The term "comprehension" comes from set theory--it basically means a set defined by a description of its elements, rather than enumeration of its every element. In most cases it's just shorthand, but it can actually be used to create sets that can't be described by enumeration. For example, "all real numbers" is a concise, precise definition of an infinite set.
Syntax aside, you can basically think of a list comprehension as creating a list by describing what's in it. And if you use parentheses instead of square brackets, you can create a generator expression--which, by the virtue of lazy evaluation, can actually be infinite.

Anonymous said...

buy viagra

viagra online

generic viagra