module S02 ( -- * Exercise 3 second, swap, pair, double, palindrome, twice, -- * Exercise 4 {-| Using the definition @ map f [] = [] map f (x:xs) = f x : map f xs @ The expression @map (+1) [1,2,3]@ can be evaluated as follows: @ map (+1) [1,2,3] = (1+1) : map (+1) [2,3] = (1+1) : (2+1) : map (+1) [3] = (1+1) : (2+1) : (3+1) : map (+1) [] = (1+1) : (2+1) : (3+1) : [] = [2,3,4] @ -} -- * Exercise 5 reverse, map, -- * Exercise 6 concat ) where import Prelude hiding (reverse, map, concat) import qualified Prelude (reverse, map, concat) {-| > second xs = head (tail xs) Since 'tail' is of type @[a] -> [a]@, @xs@ has to be of type @[a]@ and thus @tail xs@ is of type @[a]@. Combining this with the type of 'head' (which is @[a] -> a@), we obtain @a@ for @head (tail xs)@ and thus @[a] -> a@ for 'second'. -} second :: [a] -> a second xs = head (tail xs) {-| > swap (x,y) = (y,x) Since there are no restrictions on @x@ and @y@, the input of 'swap' is an arbitrary tuple of type @(a,b)@. Swapping the components then yields @(b,a)@ and thus @(a,b) -> (b,a)@ for 'swap'. -} swap :: (a,b) -> (b,a) swap (x,y) = (y,x) {-| > pair x y = (x,y) Since there are no restrictions on @x@ and @y@, the input of 'pair' are two arbitrary values of types @a@ and @b@. Constructing a pair out of those values, results in the type @(a, b)@ and thus @a -> b -> (a,b)@ for 'pair'. -} pair :: a -> b -> (a,b) pair x y = (x,y) {-| > double x = x*2 The operation @(*)@ is of type @Num a => a -> a -> a@, hence @x@, needs to be of some @Num@-type, resulting in @Num a => a -> a@ for 'double'. -} double :: Num a => a -> a double x = x*2 {-| > palindrome xs = Prelude.reverse xs == xs 'Prelude.reverse' is of type @[a] -> [a]@ and has no class constraints. On the contrary, @(==)@ is only applicable for types of the @Eq@ class. Putting this together results in @Eq a => [a] -> Bool@ for 'palindrome'. -} palindrome :: Eq a => [a] -> Bool palindrome xs = Prelude.reverse xs == xs {-| > twice f x = f (f x) Since @f@ is applied on the result of @f x@, the input as well as the output of @f@ need to be of the same type as @x@. There are no further restrictions. Hence the type of 'twice' is @(a -> a) -> a -> a@. -} twice :: (a -> a) -> a -> a twice f x = f (f x) {-| For 'reverse' we use the auxiliary function @snoc@ (\'cons\' spelled backwards), which adds an element at the end of a list. Then, using 'foldr', we obtain @ reverse = foldr snoc [] @ -} reverse :: [a] -> [a] reverse = foldr snoc [] where snoc x xs = xs ++ [x] {-| For 'map' we use \'function composition\' @(.)@ (where @(f . g) x = f (g x)@, reading \'first apply @g@ and then apply @f@ to the result\') together with the \'cons\' function @(:)@. Using 'foldr', we obtain @ map f = foldr ((:) . f) [] @ -} map :: (a -> b) -> [a] -> [b] map f = foldr ((:) . f) [] {-| One possible definition is @ concat [] = [] concat (x:xs) = x ++ concat xs @ Again, we could use 'foldr' to obtain the shorter definition @ concat = foldr (++) [] @ -} concat :: [[a]] -> [a] {- concat [] = [] concat (xs:xss) = xs ++ concat xss -} concat = foldr (++) []