This is a continuation on part one, which was a very basic introduction to functional programming. In this portion I’m pointing out some aspects of Haskell which I find to be fairly kick-ass. 🙂
My apologies if 80-90% of this post is gibberish to you. I try to be clear, but I’m also trying not to spend a copious amount of time writing this post. Think of it as a rather detailed “best things about Haskell” list, rather than anything remotely like a tutorial, or something that otherwise gives you an actual decent understanding of Haskell as a language. The idea is to try to whet your appetite to investigate further.
Death to Parentheses
Well, the first thing that impressed me is going to be small hat to folks whose primary experience with functional programming is with languages other than Lisp or Scheme, or to folks who have no FP experience at all; but Lisp is notorious for its excessive use of parentheses. Every function call gets its own pair, and since invoking functions is a frequent occurrence in functional programming, you get quite a lot of them. Even better, when you’re done with all your nested function calls, you’re left to figure out how to place the dozen or so closing parentheses. Here’s an example of the crappy powers function from part one of this miniseries, in Lisp:
|
|
(defun powers (i v) (if (= i 8) () (cons v (powers (+ i 1) (* v 2))) ) ) |
For this example, it’s not too terrible; but it’s a simple function, and already we end up with five successive closing parentheses at the end. Imagine how more complex code might look! Still, you get used to it; and at least there’s never a question of what’s an argument of what.
The parens tend to bunch up when you nest function calls:
|
|
(reverse (mapcar '3* (filter 'oddp (number-sequence 1 10)))) |
The example above includes non-standard functions (3* and filter) whose definitions I have not provided (they’re trivial); it takes a list of numbers from 1 to 10, then filters the list so it’s just the odd numbers in that range (1 3 5 9), multiplies each element of the list by three, and then reverses the list (largest to smallest). You may note that it’s sometimes easier to read expressions like the above from right to left.
In Lisp there’s no way to avoid these parens in a series of nested function calls. In Haskell, you could also write something similar to the above…
|
|
reverse (map (3*) (filter odd [1..10])) |
However, Haskell provides a “dot” operator, which applies the function on the left to the output of the function on the right, so you can also write this snippet like:
|
|
(reverse . map (3*) . filter odd) [1..10] |
The outer set of parentheses are necessary in the above example, because the dot operator takes a function on either end; and the result of filter odd [1..10] (which binds more tightly than the dot operator; function applications always bind more tightly than operators) is not a function, it’s a list result. You might wonder how filter odd and map (3*) can be functions; they look more like the result of a function applied to an argument. And they are: one of Haskell’s great features is partial function application: you can pass one argument to a function that takes two, and the result is a function that takes the “second” argument. The (3*) is actually a partial application too: in the Lisp example, I would have had to define a function named 3* to make it work; but in the Haskell example (3*) is a partial application of the * operator.
I like to read the dot operator as “of”. So you can read (reverse . map (3*) . filter odd) as” reverse the order of mapping the multiply-by-three operation across the elements of the result of filtering for just the odd-numbered values of…”
We can even get rid of those outer parentheses, too, if we want:
|
|
reverse . map (3*) . filter odd $ [1..10] |
The dollar operator takes a function on the left and applies it to everything on the right as a single argument. It’s right-associative, so we actually could also write this expression as:
|
|
reverse $ map (3*) $ filter odd $ [1..10] |
The only set of parentheses we can’t get rid of is the ones in (3*), where they are used in the partial application of the * operator, called a section. Parentheses are part of the syntax required to designate a section. Of course, if we really wanted, to, we could just write a function that does the same thing, and name it mulThree or what have you.
Personally, I like this one best:
|
|
(reverse . map (3*) . filter odd) [1..10] |
Function Definitions and Pattern Matching
In part one of this overview, we presented this version of our powers function in Haskell:
|
|
powers i v | i >= 0 && i < 8 = v : powers (i+1) (v*2) | otherwise = [] |
The truth is, though, we don’t need both i and v. One value could be deduced from the other. I just kept both parameters because they’d been needed in C (they could each be deduced from the other in C as well, but at a performance penalty; there are other ways to write the example in C without using i; but the example was written for readability).
A common way to write function definitions in Haskell, is to first write a definition of the function for a concrete value, and then define the function for other values in terms of that first definition. For instance, we could’ve written powers like:
|
|
powers 0 = 1 : powers 1 powers 8 = [] powers n = 2 * head (powers (n-1)) : powers n+1 |
Note that this assumes no one ever calls powers 9; and also that powers now takes one argument instead of two (we dropped v).
This series of definitions means that
- “powers 0” is a list whose first element has the value 1, and whose remaining elements are defined by “powers 1”
- “powers 8” is the empty list.
- “powers n” for any other value n is a list whose first element is twice the value of the first element of “powers (n-1)”, and whose remaining values are defined by “powers (n+1)”.
This winds up giving us the same list result for powers 0 as we previously got for powers 0 1 in our original definition of the function.
Note that there’s just one function powers, but there are three definitions for that function. These definitions combine to provide the complete description of what powers means.
Pattern Matching
We’ve just made a slight use of a very powerful Haskell feature, pattern matching. In this case, we’re matching arguments to powers against various possibilities of 0, 1, or n (where n can be any value). But pattern matching can actually be performed against any sort of value or partial value.
For instance, if we wanted to write a very simplistic function to convert a string into 1337-speak, transforming
|
|
The quick brown fox jumped over the lazy dog |
to
|
|
Th3 quick br0wn f0x jump5 0v3r 7h3 14zy d0g. |
we could write it like:
|
|
leetize "" = "" leetize ('l':xs) = '1' : leetize xs leetize ('e':xs) = '3' : leetize xs leetize ('a':xs) = '4' : leetize xs leetize ('s':xs) = '5' : leetize xs leetize ('t':xs) = '7' : leetize xs leetize ('o':xs) = '0' : leetize xs leetize (x:xs) = x : leetize xs |
The above could have been written somewhat more tersely, but it’s a good demonstration of using pattern-matched function definitions. The (x:xs) patterns describe a list (: is the list-construction operator), whose first element is x and whose remaining elements are the (possibly empty) list xs. The first definition in this example simply says that applying leetize to an empty string will yield an empty string as the result. The following definition means that if the leetize function is applied to a string whose first character is the letter ell, then the result is the one digit, followed by the application of leetize to the remaining characters of the string. The final definition matches (x:xs), for any string beginning with an arbitrary character x that doesn’t match any of the previous patterns; it just leaves that character as-is, and continues to transform transformations on the remaining characters.
Roll your own operators
Another thing that I think is really cool in Haskell is the ability to invent or redefine your own operators. Languages like C++ let you override the definition of existing operators for new types, but Haskell lets you invent entirely new operators. Want to define a new operator *!? It’s as easy as writing
You can also use normal functions as if they were operators. This is common with functions like elem, where elem x mylist evaluates to True if x may be found as an element in mylist. While elem x mylist is fine, the meaning of x elem mylist seems just a little clearer.
For both operators and functions-applied-as-operators, you can specify associativity and precedence. (You can only define binary operators; all operators in Haskell are binary operators, except for unary -, as used in expressions such as -3.)
Lazy Evaluation
One of the things that many people find really cool about Haskell (not just me!), is that it follows a “lazy” or “non-strict” evaluation scheme. The value of an expression is only calculated when it is required. This has some rather interesting consequences.
One consequence is that Haskell allows you to define lists that don’t end. Among other things, this means I’ve been making our running powers example way more difficult than it needs to be. Instead of defining a function that takes some starting value and keeps doing calculations until it reaches a maximum, I can have it just keep calculating that result forever:
|
|
powers = 1 : map (*2) powers |
Note that this latest powers doesn’t need any arguments at all. It’s just bound to the set of all 2n, n≥0. That’s a list without a limit; but that doesn’t matter, so long as we never try to evalute the entire list. But if I ask Haskell to give me just the first eight elements of that list (with take 8 powers), it works just fine. Haskell performs the necessary calculations to bring me the first eight elements, and doesn’t continue trying to calculate any further elements.
Infinite-length lists are fun, but when you come down to it, they’re really just neat sugar. One area where Haskell’s lazy evaluation really comes in handy is in code like:
|
|
import Char (toUpper) main = do slurp <- getContents let upperCased = map toUpper slurp putStr upperCased |
This is a complete program to convert the standard input to all-uppercase, and print the results to the standard output. It binds the variable slurp to the full contents from standard input as a string, then binds the variable upperCased to a string which holds the result of mapping the toUpper function against each character in slurp. Finally, the string held in upperCased is printed to the standard output using putStr.
Similar code in Perl might look like:
|
|
undef $/; my $slurp = <STDIN>; my $upper_cased = uc $slurp; print $upper_cased; |
The difference is that the Perl example will happily try to take a 5GB file and shove it all into memory (or, much more likely, make the attempt and choke), whereas the Haskell version, which looks nearly identical, will process input a bit at a time—how much of a bit depends on the buffering scheme, which depends on the implementation—but the point is, it’s not going to try to slurp it all into memory. It’ll process data a bit at a time, converting it to uppercase, and spitting it out. It only grabs input when it’s ready to print out the next few characters. Then it looks at what it’s printing—upperCased, and sees that it’s supposed to hold the uppercasing of slurp. It then sees that slurp is supposed to be a string holding the content from standard input, so it goes ahead and reads the next bit from standard input, uppercases it like it’s supposed to… rinse, lather, repeat.
What’s neat about this is that it frees you from having to think about the details. Your code doesn’t need to “know” that it’s dealing with input piecemeal: as far as it’s concerned, it’s just transforming a string. Naturally, Perl is just as capable as Haskell at processing input a piece at a time; the difference is that the Perl code will be very aware that it’s doing things one bit at a time, while the Haskell code “thinks” it’s just working on the whole data.
Note, the Haskell example is for illustration. A much simpler program that does the same thing is:
|
|
import Char (toUpper) main = interact (map toUpper) |
Monads
You may have noticed that the original version of the uppercasing program looked somewhat procedural-ish. The do keyword introduces a block of code that is essentially procedural; but it never for a moment violates the rules of a pure functional language. The behavior of do is defined in terms of a series of function applications and nested name-bindings. The important thing is that Haskell preserves the principle of non-destructive, immutable data, and do doesn’t let you do anything you can’t do without it; it just looks much cleaner than its equivalent.
What’s cool about the do block, though, is that it actually provides a mechanism that many people refer to as overloading the semicolon. The do block is defined in terms of a couple of operators, >> and >>=, that the user can overload in the types phe creates. All types that can be used as the types of the expression-statements in a do block, and as a do block’s own type, belong to a class called Monad.
For instance, take the Maybe parameterized type (parameterized means it takes another type as a parameter; for instance, it can be a Maybe String or a Maybe Integer). This is a type provided by the Haskell standard library, that provides a way to represent a “null”-like value. For instance, an expression that returns a Maybe String can construct return values such as Just "hello" or Just "what is your name?"; it can also use the constructor Nothing, to represent no value (often used to indicate an error condition). For instance, Haskell provides a find function that takes two arguments: a predicate function, and a list. If it finds an element a that matches the predicate in the list, it will return Just a; if it doesn’t find anything, it returns Nothing. So, find (< 2) [1 5 3 9 8] will return Just 1; but find (> 10) [1 5 3 9 8] would return Nothing.
So, what happens if you need to use the result from several successive finds? Say, to find the customer ID corresponding to a name, and then use that to find a sales record? You could end up with successive, nested if expressions to check for Nothing before proceeding. Rough pseudo-Haskell:
|
|
getSalesRecord name = let custId = find (== name) customers record = find (== custId) salesRecords in if isJust custId then if isJust record then Just record else Nothing else Nothing |
(There are severe glitches in the above, but it was written for human readability, and not actual compilability.) Note that it’s safe to bind record as above, even though we haven’t yet checked isJust record, because it’s not actually evaluated until we use it, and we don’t use it until after we check.
Imagine if there were even more dependent lookups we needed to perform! The nested if expressions would quickly become unweildly. However, since the Maybe type is a Monad, we can write it with the do block, like this:
|
|
getSalesRecord name = do custId <- find (== name) customers record <- find (== custId) salesRecords return record |
The Maybe type overloads the meaning of the name bindings done with <- (actually, it overloads >>=, but <- is defined in terms of >>=). If the result of the right-hand side is a Just x (for any x), it binds custId to x (stripping off the Just) for the remaining statements. If either of the two <- statements result in a Nothing value, then the remaining statements are not processed, and the result of the entire do block is Nothing.
I was at first dismayed when I discovered that Haskell’s exception mechanisms are not as powerful as one might hope. However, as it turns out, it doesn’t actually pose a problem, because you can just use Maybe and do blocks, as in the example above. The first <- binding or statement that evalutes to Nothing will short-circuit the rest of the code, and eliminates the need to manually check for error-status results after each statement!
This “semicolon-overloading” mechanism is really very powerful. The do block provides a mechanism for compactly and abstractly representing a sequence-of-statements, where a statement is either a Monad-returning expression or a name-binding; but the monadic type gets to decide what “sequencing” these things actually means.
A great example of the power of Monads is that simple lists are also Monads. But with list types, the name-binding <- notation is overloaded so that x <- someList will result in x being set to each element of someList in turn, and then all the remaining statements that appear after the <- binding statement in the same do block will be evaluated in turn, for each x. The result of the do block will be the list of each of those results. As an example, here’s a simple permuation of two lists:
|
|
example = do word <- ["foo", "bar"] num <- [1, 2, 4] return (word, num) -- evaluates to: [("foo",1),("foo",2),("foo",4), -- ("bar",1),("bar",2),("bar",4)] |
As perhaps you’re beginning to see, Monads are an incredibly powerful feature of Haskell. In fact, Monads combined with Haskell’s lazy, evaluate-as-needed behavior is what enables Haskell to be capable of elegantly dealing with interactive with user input, without sacrificing its status as a pure functional programming language. Interactivity (such as might be found in a typical text-editor) is not possible in languages that are purely functional (immutable data), and use strict (non-lazy) evaluation, because such languages require that they have all the input at the beginning before processing can even begin.
String Literals
I haven’t seen this emphasized anywhere, and it’s a small thing, but one more aspect of Haskell that strikes me as particularly elegant is the ways in which Haskell deals with string literals.
One of the things I really like, is that Haskell’s string literals can include spans of whitespace that are ignored, when they are enclosed within backslashes; this whitespace can include newlines. So you can write something like:
|
|
main = putStr " _ _ _ _ _ _ _ \n\ \| | | | ___| | | ____ _ _ ______ _ __| | __| | |\n\ \| |_| |/ _ | | |/ _ | | | |/ / _ | '__| |/ _` | |\n\ \| _ | __/ | | (_) | | V / (_) | | | | (_| |_|\n\ \|_| |_|____|_|_|____( ) |_/|_/|____/|_| |_|___,_(_)\n\ \ |/ \n" |
The large “Hello, World!” will be printed flush-left, but we were able to align the literal rather nicely in the Haskell source. This sort of thing can be a little more difficult in some other languages.
Also, in addition to the usual C-style \r, \n, \b, etc, and hexadecimal and octal notations (which differ slightly from C’s), Haskell also provides a \^C notation (where '\^C' represents “Control-C”), and a \ESC notation (representing the escape character, using its ASCII acronym). Thus, the ASCII backspace character can be represented as any of '\b', '\BS', '\^H, '\o33', or '\x1B'. Every one of those representations can be useful in different circumstances, especially for a terminal enthusiast and GNU Screen co-maintainer such as myself.
Well, that pretty much sums it all up. This took a lot longer to write than I really wanted it to, so maybe I’m finished talking about Haskell for a while. In presenting all the things that really impress me about Haskell, I’m perhaps painting an unrealistically rosy picture of the language. I do believe that Haskell, and its current best implementations, have some significant shortcomings (but none that actually render Haskell impractical, as is sometimes suggested); if I get around to writing a “part 3”, I’ll probably dwell on those, to counter-balance the wondrous things I covered here. However, that one might be a while in coming, as I think I’ve spent quite enough time writing about Haskell for a limited audience, for now. 😉
