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