Haskell: The Craft of Functional Programming
	Simon Thompson
	(c) Addison-Wesley, 1999.

	Chapter 9

Generalization: patterns of computation
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>	module Chapter9 where

>	import Prelude hiding (map,filter,zipWith,foldr1,foldr,concat,and)
>	import Pictures hiding (flipV,sideBySide)
>	import qualified Chapter7 

Higher-order functions: functions as arguments
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Mapping a function along a list.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>	map,map' :: (a -> b) -> [a] -> [b]

>	map' f xs = [ f x | x <- xs ]				-- (map.0)

>	map f []     = []					-- (map.1)
>	map f (x:xs) = f x : map f xs				-- (map.2)

Examples using map.

Double all the elements of a list ...

>	doubleAll :: [Int] -> [Int]

>	doubleAll xs = map double xs	       
>		       where	
>		       double x = 2*x
 
... convert characters to their numeric codes ...

>	convertChrs :: [Char] -> [Int]
>	convertChrs xs = map ord xs

... flip a Picture in a vertical mirror.

>	flipV :: Picture -> Picture
>	flipV xs = map reverse xs


Modelling properties as functions
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Is an integer even?

>	isEven :: Int -> Bool
>	isEven n = (n `mod` 2 == 0)

Is a list sorted?

>	isSorted :: [Int] -> Bool
>	isSorted xs = (xs == iSort xs)


Filtering -- the filter function
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>	filter :: (a -> Bool) -> [a] -> [a]

>	filter p [] = []				-- (filter.1)
>	filter p (x:xs)
>	  | p x         = x : filter p xs		-- (filter.2)
>	  | otherwise   =     filter p xs		-- (filter.3)

A list comprehension also serves to define \texttt{filter},

>	filter' p xs = [ x | x <- xs , p x ]		-- (filter.0)


Combining zip and map -- the zipWith function
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

>	zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

>	zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
>	zipWith f  _      _     = []

>	sideBySide :: Picture -> Picture -> Picture
>	sideBySide pic1 pic2 = zipWith (++) pic1 pic2


Folding and primitive recursion
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Folding an operation into a non-empty list

>	foldr1 :: (a -> a -> a) -> [a] -> a

>	foldr1 f [x]    = x				-- (foldr1.1)
>	foldr1 f (x:xs) = f x (foldr1 f xs)		-- (foldr1.2)

Examples using foldr1

>	foldEx1 = foldr1 (+) [3,98,1]
>	foldEx2 = foldr1 (||) [False,True,False]
>	foldEx3 = foldr1 (++) ["Freak ", "Out" , "", "!"] 
>	foldEx4 = foldr1 min [6]
>	foldEx5 = foldr1 (*) [1 .. 6]

Folding into an arbitrary list: using a starting value on the empty list.

>	foldr f s []     = s				-- (foldr.1)
>	foldr f s (x:xs) = f x (foldr f s xs)		-- (foldr.2)

Concatenating a list using foldr.

>	concat :: [[a]] -> [a]
>	concat xs = foldr (++) [] xs

Conjoining a list of Bool using foldr.

>	and :: [Bool] -> Bool
>	and bs = foldr (&&) True bs

Can define foldr1 using foldr:
	foldr1 f (x:xs) = foldr f x xs			-- (foldr1.0)


Folding in general -- foldr again
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The type of foldr is more general than you would initially expect...

>	foldr :: (a -> b -> b) -> b -> [a] -> b

>	rev :: [a] -> [a]
>	rev xs = foldr snoc [] xs

>	snoc :: a -> [a] -> [a]
>	snoc x xs = xs ++ [x]

Sorting a list using foldr

>	iSort :: [Int] -> [Int]
>	iSort xs = foldr Chapter7.ins [] xs

From the exercises: a mystery function ...

>	mystery xs = foldr (++) [] (map sing xs)
>	sing x     = [x]


Generalizing: splitting up lists
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Getting the first word from the front of a String ...

>	getWord :: String -> String
>	getWord []    = [] 					-- (getWord.1)
>	getWord (x:xs) 
>	  | elem x Chapter7.whitespace  = []			-- (getWord.2)
>	  | otherwise           	= x : getWord xs 	-- (getWord.3)

... which generalizes to a function which gets items from the front of a list
until an item has the required property.

>	getUntil :: (a -> Bool) -> [a] -> [a]
>	getUntil p []    = [] 
>	getUntil p (x:xs) 
>	  | p x         = []
>	  | otherwise   = x : getUntil p xs

The original getWord function defined from getUntil

	getWord xs 
	  = getUntil p xs
	    where 
	    p x = elem x whitespace