------------------------------------------------------------------------------
-- 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 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