[Discuss mapping and filtering over lists. Bryan O'Sullivan **20070723064829] { hunk ./en/Makefile 15 - $(wildcard ../examples/ch[0-9][0-9]/*/*.hs) + $(wildcard ../examples/ch[0-9][0-9]/*/*.hs) \ + $(wildcard ../examples/ch04/*.c) \ + $(wildcard ../examples/ch04/*.cpp) hunk ./en/ch04-fp.xml 6 - FIXME + + How to think about loops + + Unlike traditional languages, Haskell has neither a + for loop nor a while loop. If we've + got a lot of data to process, what do we use instead? There are + several possible answers to this question, so let's build up a + toolbox of answers. + + + Transforming every piece of input + + Consider the C function square, which + squares every element in an array. + + &map.c:square; + + This contains a straightforward and common kind of loop, + one that does exactly the same thing to every element of its + input array. How might we write this loop in Haskell? + + &Map.hs:square; + + Our square function consists of two + pattern matching equations. The first + deconstructs the beginning of a non-empty list, + to get its head and tail. It squares the first element, then + puts that on the front of a new list, which is constructed by + calling square on the remainder of the + empty list. The second equations ensures that + square halts when it reaches the end of + the input list. + + The effect of square is to construct + a new list that's the same length as its input list, with + every element in the input list substituted with its square in + the output list. + + Here's another such C loop, one that ensures that every + letter in a string is converted to uppercase. + + &map.c:uppercase; + + Let's look at a Haskell equivalent. + + &Map.hs:upperCase; + + Here, we're importing the toUpper + function from the standard Data.Char module, + which contains lots of useful functions for working with + Char data. + + Our upperCase function follows a + similar pattern to our earlier square + function. It terminates with an empty list when the input + list is empty; and when the input isn't empty, it calls + toUpper on the first element, then + constructs a new list cell from that and the result of calling + itself on the rest of the input list. + + These examples follow a common pattern for writing + recursive functions over lists in Haskell. The base + case handles the situation where our input list + is empty. The recursive case deals with + a non-empty list; it does something with the head of the list, + and calls itself recursively on the tail. + + + + Mapping over a list + + The square and + upperCase functions that we just defined + produce new lists that are the same lengths as their input + lists, and do only one piece of work per element. This is + such a common pattern that Haskell's prelude defines a + function, map, to make it easier. + map takes a function, and applies it to + every element of a list, returning a new list constructed from + the results of these applications. + + Here are our square and + upperCase functions rewritten to use + map. + + &Map.hs:map2; + + This is our first time seeing a function that takes + another function as its argument. We can learn a lot about + what map does by simply inspecting its + type. + + &ch04.map.ghci:type; + + The signature tells us that map takes + two arguments. The first is a function that takes a value of + one type, a, and returns a + value of another type, b. This + is the only unfamiliar piece of notation in the type; notice + the parentheses that surround the signature of the function + argument so we (and Haskell) won't misread it. + + Since map takes a function as + argument, we refer to it as a + higher-order function. (In spite of the + name, there's nothing mysterious about higher-order + functions; it's just a term for functions that take other + functions as arguments, or return functions.) + + Since map abstracts out the pattern + common to our square and + upperCase functions so that we can reuse + it with less boilerplate, we can look at what those functions + have in common and figure out how to implement it + ourselves. + + &Map.hs:myMap; + + We try out our myMap function to give + outselves some assurance that it behaves similarly to the + standard map. + + &ch04.map.ghci:inuse; + + This business of seeing that we're repeating an idiom, + then abstracting it so we can reuse (and write less!) code, is + a common aspect of Haskell programming. + + + + Selecting pieces of input + + Another common operation on a sequence of data is to comb + through it for elements that satisfy some criterion. Here's + an example in C++ of a function that walks a linked list of + numbers and returns those that are odd. + + &filter.cpp:oddList; + + Our Haskell equivalent has a recursive case that's a bit + more complex than our earlier functions: it only puts a number + in the list it returns if the number is odd. Using a guard + expresses this nicely. + + &Filter.hs:oddList; + + Let's see that in action. + + &ch04.filter.ghci:oddList; + + Once again, this idiom is so common that Haskell's prelude + defines a function, filter, which removes + the need for boilerplate code to recurse over the list. + + &ch04.filter.ghci:filter; + + The filter function takes a predicate + (a function that tests an argument and returns a + Bool) and applies it to every element in its + input list, returning a list of only those for which the + predicate evaluates to True. + + addfile ./examples/ch04/Filter.hs hunk ./examples/ch04/Filter.hs 1 +{-- snippet oddList --} +oddList :: [Int] -> [Int] + +oddList (x:xs) | odd x = x : oddList xs + | otherwise = oddList xs +oddList _ = [] +{-- /snippet oddList --} addfile ./examples/ch04/Map.hs hunk ./examples/ch04/Map.hs 1 +{-- snippet upperCase --} +import Data.Char (toUpper) + +upperCase :: String -> String + +upperCase (x:xs) = toUpper x : upperCase xs +upperCase [] = [] +{-- /snippet upperCase --} + +{-- snippet square --} +square :: [Double] -> [Double] + +square (x:xs) = x**2 : square xs +square [] = [] +{-- /snippet square --} + +{-- snippet map2 --} +square2 xs = map squareOne xs + where squareOne x = x ** 2 + +upperCase2 xs = map toUpper xs +{-- /snippet map2 --} + +{-- snippet myMap --} +myMap :: (a -> b) -> [a] -> [b] + +myMap f (x:xs) = f x : myMap f xs +myMap _ [] = [] +{-- /snippet myMap --} addfile ./examples/ch04/ch04.filter.ghci hunk ./examples/ch04/ch04.filter.ghci 1 +:load Filter.hs + +--# oddList +oddList [1,1,2,3,5,8,13,21,34] + +--# filter +:type filter +filter odd [3,1,4,1,5,9,2,6,5] addfile ./examples/ch04/ch04.map.ghci hunk ./examples/ch04/ch04.map.ghci 1 +:load Map.hs + +--# type +:type map + +--# inuse +map toLower "SHOUTING" +myMap toUpper "whispering" +map negate [1,2,3] addfile ./examples/ch04/filter.cpp hunk ./examples/ch04/filter.cpp 1 +/** snippet oddList */ +#include + +using namespace std; + +list oddList(const list& in) +{ + list out; + + for (list::const_iterator i = in.begin(); i != in.end(); ++i) { + if ((*i % 2) == 1) + out.push_back(*i); + } + + return out; +} +/** /snippet oddList */ addfile ./examples/ch04/map.c hunk ./examples/ch04/map.c 1 +/** snippet uppercase */ +#include + +char *uppercase(char *out, const char *in) +{ + char *out = strdup(in); + + if (out != NULL) { + for (size_t i = 0; out[i] != '\0'; i++) { + out[i] = toupper(out[i]); + } + } + + return out; +} +/** /snippet uppercase */ + +/** snippet square */ +void square(double *out, const double *in, size_t length) +{ + for (size_t i = 0; i < length; i++) { + out[i] = in[i] * in[i]; + } +} +/** /snippet square */ }