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 (++) []