- Erik Meijer (for the whole interview go here)
That's high praise. I was lucky enough to come across a copy of said book, titled Introduction to Functional Programming, sneaking time during the last few weekends to read about a third of it. Of what I've read so far, let me say I agree with Erik and not without some sadness. It is a beautiful book, but that's one of its flaws. In fact, the same could be said of functional programming in general. Let me explain what I mean with an example taken from the book.
(Note, I've translated the above example to Haskell for ease of readability)
When I first read the code snippet I said "what in the world is that doing?", so if you thought the same thing you're not alone. Let me break the parts down, and we'll see how the machinery works.
"nondec xs"
Note: this would be "let nondec xs" if you're using GHCi. Here we define a new function called "nondec" that will test a list, here called 'xs', to see if it's in non-decreasing order.
"and [...]"
'and' is a function which will take a list of boolean values, apply a boolean 'and' to all the elements, and return the result.
"[ ... | ... ]"
This is a list comprehension. With it we'll create a list made from values defined by the left and right sides of the vertical bar.
"[ x <= y | ... ]"
Here the list comprehension says that we'll be using the 'x' and 'y' defined on the right side of the vertical bar in the following way: we're applying a less-than/equal comparison. The result of this will be boolean values that will make up the list we mentioned earlier (which we'll apply 'and' to).
Now let's look at the right hand side of the vertical bar, which in this case is easier to read from back to front.
"(tail xs)"
The argument to our function, if you recall, was 'xs'. Here we apply the 'tail' function to it, which returns everything but the first element of the list. For example: if we evaluated tail [1, 2, 3], we would get the list [2, 3] as the result. Why we would want to do so will soon become apparent.
"zip xs (tail xs)"
The 'zip' function takes two lists, walks down both of them, and creates pairs of the elements at corresponding indices. For example: zip [1, 2, 3] [4, 5, 6] would make the new list [(1, 4), (2, 5), (3, 6)]. To answer why we're zipping a list with itself, let's look a little closer at what the above is doing. Let's say 'xs' is equal to [1, 2, 3, 4].
zip [1, 2, 3, 4] (tail [1, 2, 3, 4])
After tail is evaluated*, we have the following:
zip [1, 2, 3, 4] [2, 3, 4]
The 'zip' function can only zip elements up to the length of the shortest list, which gives us:
[(1, 2), (2, 3), (3, 4)] -- notice that the final 4 from the first list goes unused.
Can you feel it starting to come together? Now each element in the list has been paired with the next element in the list. All that's left is to extract each pair and compare the elements, which is exactly what we do.
"[x <= y | (x, y) <- zip ...]"
The '<-' here says that the (x, y) pair will be drawn from the zip we just created, one at a time. Each one will then go through the x <= y comparison and be turned into a boolean for our list.
Let's recap: to see if a list is in non-decreasing order we take the elements of the list and pair it with itself, but slide the list over by an element so we create pairs of elements with the immediately following neighbor. We then apply the comparison to each pair and generate a boolean, which we 'and' together to get the final boolean answer.
The example problems in the book have you proud of your growing ability to read and even create samples like the above. Which, I put forward, is both a blessing and a curse.
To explain let me give another example. In high school, I studied classical Greek for fun (if you're reading this blog you're probably also a geek, so I know I'm in safe company). Greek is a language of strange characters as well as strange grammar and pronunciation rules. I relished making flash cards for myself and learning things like which tone marker meant to prepend an 'h' sound to the front of a word. I've long forgotten much of what I learned due in large part to not having other people around who had the patience to learn new characters, words and grammars.
The parallel between Greek and Haskell is striking. Instead of talking about diphthongs and diacritical marks (like the 'h' sound), Haskellers will speak about list comprehensions, monads, evaluation strictness and thunks, and so on. While programmers who learned C++ could go back in time and read Pascal or forward and read Java or C#, they will likely not be able to pick up Haskell source and easily understand what's going on. For those who appreciate the aesthetic, the above example is a beautifully crafted** algorithm to a common problem. But if programmers must learn Greek to speak your language of beautiful solutions, how many will go that extra mile? For the brave few who do, will they find themselves having visions on the island of Patmos, struggling to reintegrate with the outside world?
* - I realize this explanation assumes eager evaluation. My apologies. I did so for clarity of the example.
** - Bonus factoid to programmers more used to languages like Java or C++. Would you believe me if I told you the code above was actually fairly efficient, too? Because of Haskell's non-strict (or lazy) evaluation, the 'and' function will only continue to check values in the list if they are true, and each element of that list is only created when it's needed.
That's high praise. I was lucky enough to come across a copy of said book, titled Introduction to Functional Programming, sneaking time during the last few weekends to read about a third of it. Of what I've read so far, let me say I agree with Erik and not without some sadness. It is a beautiful book, but that's one of its flaws. In fact, the same could be said of functional programming in general. Let me explain what I mean with an example taken from the book.
Non-decreasing sequences
Suppose we want to define a function nondec which determines whether a sequence [Xl , . . . , xn] is in non-decreasing order...
...This condition can be expressed as a list comprehension in the following way:
nondec xs = and [x <= y | (x, y) <- zip xs (tail xs)]
(Note, I've translated the above example to Haskell for ease of readability)
When I first read the code snippet I said "what in the world is that doing?", so if you thought the same thing you're not alone. Let me break the parts down, and we'll see how the machinery works.
"nondec xs"
Note: this would be "let nondec xs" if you're using GHCi. Here we define a new function called "nondec" that will test a list, here called 'xs', to see if it's in non-decreasing order.
"and [...]"
'and' is a function which will take a list of boolean values, apply a boolean 'and' to all the elements, and return the result.
"[ ... | ... ]"
This is a list comprehension. With it we'll create a list made from values defined by the left and right sides of the vertical bar.
"[ x <= y | ... ]"
Here the list comprehension says that we'll be using the 'x' and 'y' defined on the right side of the vertical bar in the following way: we're applying a less-than/equal comparison. The result of this will be boolean values that will make up the list we mentioned earlier (which we'll apply 'and' to).
Now let's look at the right hand side of the vertical bar, which in this case is easier to read from back to front.
"(tail xs)"
The argument to our function, if you recall, was 'xs'. Here we apply the 'tail' function to it, which returns everything but the first element of the list. For example: if we evaluated tail [1, 2, 3], we would get the list [2, 3] as the result. Why we would want to do so will soon become apparent.
"zip xs (tail xs)"
The 'zip' function takes two lists, walks down both of them, and creates pairs of the elements at corresponding indices. For example: zip [1, 2, 3] [4, 5, 6] would make the new list [(1, 4), (2, 5), (3, 6)]. To answer why we're zipping a list with itself, let's look a little closer at what the above is doing. Let's say 'xs' is equal to [1, 2, 3, 4].
zip [1, 2, 3, 4] (tail [1, 2, 3, 4])
After tail is evaluated*, we have the following:
zip [1, 2, 3, 4] [2, 3, 4]
The 'zip' function can only zip elements up to the length of the shortest list, which gives us:
[(1, 2), (2, 3), (3, 4)] -- notice that the final 4 from the first list goes unused.
Can you feel it starting to come together? Now each element in the list has been paired with the next element in the list. All that's left is to extract each pair and compare the elements, which is exactly what we do.
"[x <= y | (x, y) <- zip ...]"
The '<-' here says that the (x, y) pair will be drawn from the zip we just created, one at a time. Each one will then go through the x <= y comparison and be turned into a boolean for our list.
Let's recap: to see if a list is in non-decreasing order we take the elements of the list and pair it with itself, but slide the list over by an element so we create pairs of elements with the immediately following neighbor. We then apply the comparison to each pair and generate a boolean, which we 'and' together to get the final boolean answer.
The example problems in the book have you proud of your growing ability to read and even create samples like the above. Which, I put forward, is both a blessing and a curse.
To explain let me give another example. In high school, I studied classical Greek for fun (if you're reading this blog you're probably also a geek, so I know I'm in safe company). Greek is a language of strange characters as well as strange grammar and pronunciation rules. I relished making flash cards for myself and learning things like which tone marker meant to prepend an 'h' sound to the front of a word. I've long forgotten much of what I learned due in large part to not having other people around who had the patience to learn new characters, words and grammars.
The parallel between Greek and Haskell is striking. Instead of talking about diphthongs and diacritical marks (like the 'h' sound), Haskellers will speak about list comprehensions, monads, evaluation strictness and thunks, and so on. While programmers who learned C++ could go back in time and read Pascal or forward and read Java or C#, they will likely not be able to pick up Haskell source and easily understand what's going on. For those who appreciate the aesthetic, the above example is a beautifully crafted** algorithm to a common problem. But if programmers must learn Greek to speak your language of beautiful solutions, how many will go that extra mile? For the brave few who do, will they find themselves having visions on the island of Patmos, struggling to reintegrate with the outside world?
* - I realize this explanation assumes eager evaluation. My apologies. I did so for clarity of the example.
** - Bonus factoid to programmers more used to languages like Java or C++. Would you believe me if I told you the code above was actually fairly efficient, too? Because of Haskell's non-strict (or lazy) evaluation, the 'and' function will only continue to check values in the list if they are true, and each element of that list is only created when it's needed.
