[Sort names in auto-snippets.xml. Bryan O'Sullivan **20070824064519] { hunk ./en/Makefile 139 - cat $^ | sort >> $@ + cat $(sort $^) | sort >> $@ hunk ./en/ch04-fp.xml 32 - of the fundamentals of Haskell's standard libraries. + of the fundamentals of Haskell's standard libraries. We'll also + intermittently cover a few more language features along the + way. hunk ./en/ch04-fp.xml 47 - While lines looks useful, it's not - portable: it doesn't deal well with Windows line ending - conventions. + While lines looks useful, it relies on + us reading a file in text mode in order to work + (yes, we'll be talking about opening files soon); it doesn't + deal well with Windows line ending conventions. hunk ./en/ch04-fp.xml 54 - It only splits on newline characters, leaving carriage - returns dangling at the ends of lines. Ugh. + The function only splits on newline characters, leaving + carriage returns dangling at the ends of lines. Ugh. We can't + rely on opening a file in text mode to do the right thing on our + behalf. For example, if we're reading a Windows-generated text + file on a Linux or Unix box, we'll get trailing carriage returns + at the end of each line. hunk ./en/ch04-fp.xml 63 - Windows line ending conventions for us without us needing to - worry about them. Although Python conveniently provides a - splitlines string method, let's reimplement - it as a Python function, just to see what the code might look - like. + Windows line ending conventions for us, left us wanting + something similar in Haskell. Although Python conveniently + provides a built-in splitlines string + method, we'll rewrite it as a Python function, just to see what + a reasonable Python implementation might look like. hunk ./en/ch04-fp.xml 195 - &ch04.list.ghci:Data.List; + &ch04.list.ghci:Data.List; + + Because none of these functions is complex or takes more + than about three lines of Haskell to write, we'll be brief in + our descriptions of each. In fact, a quick and useful learning + exercise is to write a definition of each function after you've + read about it. hunk ./en/ch04-fp.xml 404 + The elem function indicates whether a + value is present in a list. It has a companion function, + notElem. + + &ch04.list.ghci:elem; + + For a more general search, filter + takes a predicate, and returns every element of the list on + which the predicate succeeds. + + &ch04.list.ghci:filter; + hunk ./en/ch04-fp.xml 440 + + + Working with several lists at once + + The zip function takes two lists and + zips them into a single list of pairs. The + resulting list is the same length as the shorter of the two + inputs. + + &ch04.list.ghci:zip; + + More useful is zipWith, which takes + two lists and applies a function to each pair of elements, + generating a list that is the same length as the shorter of + the two. + + &ch04.list.ghci:zipWith; + + Haskell's type system makes it an interesting challenge to + write functions that take variable numbers of arguments. So + if we want to zip three lists together, we call + zip3 or zipWith3, + and so on up to zip7 and + zipWith7. + + + + Special string-handling functions + + We've already encountered the standard + lines function in . It has a standard counterpart, + unlines, which joins a list of lines + together using newline characters, and adds another newline to + the end of the string. + + &ch04.list.ghci:unlines; + + The words function splits an input + string on any whitespace. Its counterpart, + unwords, uses a single space to join a + list of words. + + &ch04.list.ghci:words.unwords; + + hunk ./en/ch04-fp.xml 489 - + hunk ./en/ch04-fp.xml 493 - the standard partial list functions that never - fail. + the standard partial list functions, but make sure that + yours never fail. As a hint, you might want to consider + using the following types. hunk ./en/ch04-fp.xml 499 + + + + + + Write a function splitWith that + acts similarly to words, but takes + a predicate and a list of any type, and splits its input + list on every element for which the predicate returns + False. + + &ch04.exercises.hs:splitWith; + hunk ./en/ch04-fp.xml 1264 - Anonymous (Lambda) Functions - FIXME + Anonymous (lambda) functions + + In many of the function definitions we've seen so far, we've + written short helper functions. + + &Partial.hs:isInAny; + + Haskell lets us write completely anonymous functions, which + we can use to avoid the need to give names to our helper + functions. Anonymous functions are often called + lambda functions, in a nod to their heritage in + the lambda calculus. We introduce an anonymous function with a + backslash character, \. This is followed by the + function's arguments (which can include patterns), then an arrow + -> to introduce the function's body. + + Lambdas are most easily illustrated by example. Here's a + rewrite of isInAny using an anonymous + function. + + &Partial.hs:isInAny2; + + We've wrapped the lambda in parentheses here so that Haskell + can tell where the function body ends. + + Anonymous functions behave in every respect identically to + functions that have names, but Haskell places a few important on + how we can define them. Most importantly, whereas we can write + a normal function using multiple clauses containing different + patterns and guards, a lambda can only have a single clause in + its definition. + + The limitation to a single clause restricts how we can use + patterns in the definition of a lambda. We'll usually write a + normal function with several clauses to cover different pattern + matching possibilities. + + &Lambda.hs:safeHead; + + But as we can't write multiple clauses to define a lambda, + we have to be sure that any patterns we use will match. + + &Lambda.hs:unsafeHead; + + This definition of unsafeHead will + explode in our faces if we call it with a value on which pattern + matching fails. + + &lambda.ghci:unsafeHead; + + The definition typechecks, so it will compile, so the error + will occur at runtime. The moral of this story is to be careful + in how you use patterns when defining an anonymous function: + make sure your patterns can't fail! + + Another thing to notice about the + isInAny and isInAny2 + functions we showed above is that the first version, using a + helper function that has a name, is a little easier to read than + the version that plops an anonymous function into the middle. + The named helper function doesn't disrupt the + flow of the function in which it's used, and the + judiciously chosen name gives us a little bit of information + about what the function is expected to do. + + In contrast, when we run across a lambda in the middle of a + function body, we have to switch gears and read its definition + fairly carefully to understand what it does. To help with + readability and maintainability, then, we tend to avoid lambdas + in many situations where we could use them to trim a few + characters from a function definition. Very often, we'll use + a partially applied function instead, resulting in clearer and + more readable code than either a lambda or an explicit + function. Don't know what a partially applied function is yet? + Read on! hunk ./en/ch04-fp.xml 1342 - Curried functions and partial application - FIXME + Partial function application and currying + + In Haskell, a single piece of syntax doesn't often get + pressed into use for multiple tasks. So why does the + -> arrow get used for what looks like two + purposes in the type signature of a function? + + &ch04.list.ghci:dropWhile; + + It looks like the -> is separating the + arguments to dropWhile from each other, but + also that it separates the arguments from the return type. But + in fact -> has only one meaning: it + denotes a function that takes an argument of the type on the + left, and returns a value of the type on the right. + + The implication here is that in Haskell, all functions take + only one argument. While dropWhile + looks like a function that takes two + arguments, it only takes one. Here's a perfectly valid Haskell + expression. + + &ch04.list.ghci:dropWhile.isSpace; + + What type does it have, and what does it do? + + &ch04.list.ghci:dropWhile.isSpace.type; + + Well, that looks useful. The value + dropWhile isSpace is a function that strips leading + white space from a string. + + Every time we give an argument to a function, we can + chop an element off the front of its type + signature. Let's take zip3 as an example + to see what we mean; this is a function that zips three lists + into a list of three-tuples. + + &ch04.list.ghci:zip3; + + If we call zip3 with just one argument, + we get a function that accepts two arguments, where the first + argument is now fixed. No matter what + second or third arguments we pass, the first argument to this + new function will always be the fixed value we already + specified. + + &ch04.list.ghci:zip3foo; + + When we pass fewer arguments to a function than the function + can accept, we call this partial + application of the function: we're applying the + function to only some of its arguments. + + In the example above, we have a partially applied function, + zip3 "foo", and a new function, + zip3foo. We can see that the type + signatures of the two and their behaviour are identical. + + This applies just as well if we fix two arguments, giving us + a function of just one argument. + + &ch04.list.ghci:zip3foobar; + + Partial function application lets us avoid writing tiresome + throwaway functions. It's generally a lot better for this + purpose than the anonymous functions we introduced in . Looking back at the + isInAny function we defined there, here's + how we'd write it to use a partially applied function instead of + a named helper function or a lambda. + + &Partial.hs:isInAny3; + + Here, the expression isInfixOf needle is the + partially applied function. We're taking the function + isInfixOf, and fixing its + first argument to be the needle variable from + our parameter list. This gives us a partially applied function + that has exactly the same type and behaviour as the helper and + lambda in our earlier definitions. + + + Sections + + Haskell provides a handy notational shortcut to let us + write partially applied functions using infix operators. If + we enclose an operator in parentheses, we can supply its left + or right argument inside the parentheses to get a partially + applied function. This kind of partial application is called + a section. + + &partial.ghci:section; + + If we provide the left argument inside the section, then + calling the resulting function with one argument supplies the + operator's right argument. And vice versa. + + Recall that we can wrap a function name in backquotes to + use it as an infix operator. This lets us use sections with + functions. + + &partial.ghci:function; + + The above definition fixes elem's + second argument, giving us a function that checks to see + whether its argument is a lowercase letter. + + &partial.ghci:lower.letter; + + Using this as an argument to any, we + get a function that checks an entire string to see if it's all + lowercase. + + &partial.ghci:lower.string; + + + + + As-patterns and function composition + + Haskell's tails function, in the + Data.List module, generalises the + tail function we introduced earlier. It + successively applies tail to its input, + then calls itself on the result, until there's nothing + left. + + &suffix.ghci:tails; + + Each of these strings is a suffix of + the initial string, so tails produces a + list of all suffixes, plus an extra empty list at the + end. In fact, it always produces that extra empty list, even + when its input list is empty. + + &suffix.ghci:tails.empty; + + What if we want a function that behaves like + tails, but which only + returns suffixes? One possibility would be for us to write our + own version by hand. + + &SuffixTree.hs:suffixes; + + Let's try out that definition. + + &suffix.ghci:suffixes; + + + Where did that at-sign come from? + + You may have noticed the funny-looking pattern + xs@(_:xs') in our definition of + suffixes. This is called an + as-pattern, and it means bind the + variable xs to the expression in the + matched pattern (_:xs'). + + In this case, if the pattern after the @ + matches, xs will be bound to the entire + list that matched, and xs' to the rest of + the list (we used the wildcard _ pattern to + indicate that we're not interested in the value of the head of + the list). + + Let's look at a second definition of the + suffixes function, only this time without + using an as-pattern. + + &SuffixTree.hs:noisier; + + Here, the list that we've deconstructed in the pattern + match just gets put right back together in the body of the + function. The as-pattern makes the code more readable by + letting us avoid the need to repeat ourselves. + + + As-patterns are not just for readability + + Not only can as-patterns reduce the clutter in our code; + they can help it to execute more efficiently, too. Since we + don't have much of a mental model for thinking about + evaluation and efficiency yet, we'll return to this topic + later, in XXX. + + + + + Code reuse + + It seems a shame to introduce a new function, + suffixes, that does almost the same thing + as the existing tails function. Surely + we can do better? + + Remember the init function we + introduced in ? + + &SuffixTree.hs:suffixes2; + + The suffixes2 function behaves + identically to suffixes, but it's a + single line of code. + + &suffix.ghci:suffixes2; + + If we take a step back, we see the glimmer of a pattern + here: we're calling a function, then applying another function + to its result. Let's turn that pattern into a function + definition. + + &SuffixTree.hs:compose; + + We now have a function, compose, that + we can use to glue two other functions + together. + + &SuffixTree.hs:suffixes3; + + As Haskell's automatic currying lets us drop the + xs variable, we can make our definition + even shorter. + + &SuffixTree.hs:suffixes4; + + Fortunately, we don't need to write our own + compose function. Plugging functions + into each other like this is so common that Haskell's prelude + uses the (.) operator to denote function + composition. + + &SuffixTree.hs:suffixes5; + + The (.) operator isn't a special + piece of language syntax; it's just a normal operator. + + &suffix.ghci:types; + + We can create new functions at any time by writing chains + of composed functions, stitched together with + (.), so long (of course) as the result + type of the function on the right of each + (.) matches the type of parameter that + the function on the left can accept. + + &suffix.ghci:dotty; + + + + + + Working with data structures: the suffix tree + + A suffix tree is a useful and elegant data structure that + lets us deal efficiently with a fixed body of text or some other + kind of sequence. }