Haskell: The Craft of Functional Programming Simon Thompson (c) Addison-Wesley, 1999. Chapter 7 > module Chapter7 where Defining functions over lists ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ For pedagogical reasons, this chapter repeats many of the definitions in the standard Prelude. They are repeated in this file, and so the original definitions have to be hidden when the Prelude is imported: > import Prelude hiding (id,head,tail,null,sum,concat,(++),zip,take,getLine) > import Chapter5 hiding (mystery) -- for the digits function Pattern matching revisited ^^^^^^^^^^^^^^^^^^^^^^^^^^ An example function using guards ... > mystery :: Int -> Int -> Int > mystery x y > | x==0 = y > | otherwise = x ... or pattern matching > mystery' :: Int -> Int -> Int > mystery' 0 y = y > mystery' x _ = x To join two strings > joinStrings :: (String,String) -> String > joinStrings (st1,st2) = st1 ++ "\t" ++ st2 Lists and list patterns ^^^^^^^^^^^^^^^^^^^^^^^ From the Prelude ... > head :: [a] -> a > head (x:_) = x > tail :: [a] -> [a] > tail (_:xs) = xs > null :: [a] -> Bool > null [] = True > null (_:_) = False The case construction ^^^^^^^^^^^^^^^^^^^^^ Return the first digit in a string. > firstDigit :: String -> Char > firstDigit st > = case (digits st) of > [] -> '\0' > (x:_) -> x Primitive recursion over lists ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The sum of a list of Ints. > sum :: [Int] -> Int > sum [] = 0 > sum (x:xs) = x + sum xs Finding primitive recursive definitions ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Concatenating a list of lists. > concat :: [[a]] -> [a] > concat [] = [] > concat (x:xs) = x ++ concat xs Joining two lists > (++) :: [a] -> [a] -> [a] > [] ++ ys = ys > (x:xs) ++ ys = x:(xs++ys) To double every element of an integer list > doubleAll :: [Int] -> [Int] > doubleAll xs = [ 2*x | x<-xs ] > doubleAll' [] = [] > doubleAll' (x:xs) = 2*x : doubleAll' xs To select the even elements from an integer list. > selectEven :: [Int] -> [Int] > selectEven xs = [ x | x<-xs , isEven x ] > selectEven' [] = [] > selectEven' (x:xs) > | isEven x = x : selectEven' xs > | otherwise = selectEven' xs To sort a list of numbers into ascending order. > iSort :: [Int] -> [Int] > iSort [] = [] > iSort (x:xs) = ins x (iSort xs) To insert an element at the right place into a sorted list. > ins :: Int -> [Int] -> [Int] > ins x [] = [x] > ins x (y:ys) > | x <= y = x:(y:ys) > | otherwise = y : ins x ys General recursions over lists ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Zipping together two lists. > zip :: [a] -> [b] -> [(a,b)] > zip (x:xs) (y:ys) = (x,y) : zip xs ys > zip (x:xs) [] = [] > zip [] zs = [] Taking a given number of elements from a list. > take :: Int -> [a] -> [a] > take 0 _ = [] > take _ [] = [] > take n (x:xs) > | n>0 = x : take (n-1) xs > take _ _ = error "PreludeList.take: negative argument" Quicksort over lists. > qSort :: [Int] -> [Int] > qSort [] = [] > qSort (x:xs) > = qSort [ y | y<-xs , y<=x] ++ [x] ++ qSort [ y | y<-xs , y>x] Example: Text Processing ^^^^^^^^^^^^^^^^^^^^^^^^ The `whitespace' characters. > whitespace :: String > whitespace = ['\n','\t',' '] Get a word from the front of a string. > getWord :: String -> String > getWord [] = [] > getWord (x:xs) > | elem x whitespace = [] > | otherwise = x : getWord xs In a similar way, the first word of a string can be dropped. > dropWord :: String -> String > dropWord [] = [] > dropWord (x:xs) > | elem x whitespace = (x:xs) > | otherwise = dropWord xs To remove the whitespace character(s) from the front of a string. > dropSpace :: String -> String > dropSpace [] = [] > dropSpace (x:xs) > | elem x whitespace = dropSpace xs > | otherwise = (x:xs) A word is a string. > type Word = String Splitting a string into words. > splitWords :: String -> [Word] > splitWords st = split (dropSpace st) > split :: String -> [Word] > split [] = [] > split st > = (getWord st) : split (dropSpace (dropWord st)) Splitting into lines of length at most lineLen > lineLen :: Int > lineLen = 80 A line is a list of words. > type Line = [Word] Getting a line from a list of words. > getLine :: Int -> [Word] -> Line > getLine len [] = [] > getLine len (w:ws) > | length w <= len = w : restOfLine > | otherwise = [] > where > newlen = len - (length w + 1) > restOfLine = getLine newlen ws Dropping the first line from a list of words. > dropLine :: Int -> [Word] -> Line > dropLine = dropLine -- DUMMY DEFINITION Splitting into lines. > splitLines :: [Word] -> [Line] > splitLines [] = [] > splitLines ws > = getLine lineLen ws > : splitLines (dropLine lineLen ws) To fill a text string into lines, we write > fill :: String -> [Line] > fill = splitLines . splitWords