content: -- D. Sannella. M Fourman, H. Peng and P. Wadler
  -- Introduction to Computation: Haskell, Logic and Automata
  -- Undergraduate Topics in Computer Science, Springer (2021)
  -- ISBN 978-3-030-76907
  
  -- Chapter 11 : More Fun with Recursion
  
  module Chap11_more_fun_with_recursion where
  
  import Chap05_lists_and_comprehensions (isPrime)
  
  -- Counting
  
  -- The following function definition is commented out because it is already in the Prelude.
  -- You can hide that definition to allow it to be re-defined by putting the following at the top of this module:
  -- import Prelude hiding (enumFromTo)
  
  -- enumFromTo :: Int -> Int -> [Int]
  -- enumFromTo m n | m > n  = []
  --                | m <= n = m : enumFromTo (m+1) n
  
  prodFromTo :: Int -> Int -> Int
  prodFromTo m n | m > n  = 1
                 | m <= n = m * prodFromTo (m+1) n
  
  factorial :: Int -> Int
  factorial n = prodFromTo 1 n
  
  -- Infinite lists and lazy evaluation
  
  -- The following function definitions are commented out because they are already in the Prelude.
  -- You can hide those definitions to allow them to be re-defined by putting the following at the top of this module:
  -- import Prelude hiding (enumFrom, head, tail)
  
  -- enumFrom :: Int -> [Int]
  -- enumFrom m = m : enumFrom (m+1)
  
  -- head :: [a] -> a
  -- head []      = error "empty list"
  -- head (x : _) = x
  
  -- tail :: [a] -> [a]
  -- tail []       = error "empty list"
  -- tail (_ : xs) = xs
  
  primes :: [Int]
  primes = [ p | p <- [2..], isPrime p ]
  
  upto :: Int -> [Int] -> [Int]
  upto bound []                 = []
  upto bound (x:xs) | x > bound = []
                    | otherwise = x : upto bound xs
  
  l1 = upto 30 primes
  
  -- Zip and search
  
  -- The following function definition is commented out because it is already in the Prelude.
  -- You can hide that definition to allow it to be re-defined by putting the following at the top of this module:
  -- import Prelude hiding (zip)
  
  -- zip :: [a] -> [b] -> [(a,b)]
  -- zip [] ys         = []
  -- zip xs []         = []
  -- zip (x:xs) (y:ys) = (x,y) : zip xs ys
  
  l2 = zip [0..] "word"
  
  l3 = zip "word" (tail "word")
  
  countDoubled :: String -> Int
  countDoubled [] = 0
  countDoubled xs = length [ x | (x,y) <- zip xs (tail xs), x==y ]
  
  search :: String -> Char -> [Int]
  search xs y = [ i | (i,x) <- zip [0..] xs, x==y ]
  
  searchRec :: String -> Char -> [Int]
  searchRec xs y = srch xs y 0
    where
      -- i is the index of the start of the substring
      srch :: String -> Char -> Int -> [Int]
      srch [] y i     = []
      srch (x:xs) y i
        | x == y    = i : srch xs y (i+1)
        | otherwise = srch xs y (i+1)
  
  search' :: Eq a => [a] -> a -> [Int]
  search' xs y = [ i | (i,x) <- zip [0..] xs, x==y ]
  
  -- Select, take and drop
  
  -- The following function definitions are commented out because they are already in the Prelude.
  -- You can hide those definitions to allow them to be re-defined by putting the following at the top of this module:
  -- import Prelude hiding ((!!), take, drop)
  
  -- (!!) :: [a] -> Int -> a
  -- (x:xs) !! 0 = x
  -- [] !! i     = error "index too large"
  -- (x:xs) !! i = xs !! (i-1)
  
  -- take :: Int -> [a] -> [a]
  -- take 0 xs     = []
  -- take i []     = []
  -- take i (x:xs) = x : take (i-1) xs
  
  -- drop :: Int -> [a] -> [a]
  -- drop 0 xs     = xs
  -- drop i []     = []
  -- drop i (x:xs) = drop (i-1) xs
  
  -- Natural numbers
  
  plus :: Int -> Int -> Int
  plus m 0 = m
  plus m n = (plus m (n-1)) + 1
  
  times :: Int -> Int -> Int
  times m 0 = 0
  times m n = plus (times m (n-1)) m
  
  power :: Int -> Int -> Int
  power m 0 = 1
  power m n = times (power m (n-1)) m
  
  -- Recursion and induction
  
  -- The following function definition is commented out because it is already in the Prelude.
  -- You can hide that definition to allow it to be re-defined by putting the following at the top of this module:
  -- import Prelude hiding ((++))
  
  -- (++) :: [a] -> [a] -> [a]
  -- [] ++ ys     = ys
  -- (x:xs) ++ ys = x : (xs ++ ys)
  
  -- Exercise 7
  
  plus' :: Int -> Int -> Int
  plus' m 0 = m
  plus' m n = plus' (m+1) (n-1)
  
  -- The following function definition is commented out because it is already in the Prelude.
  -- You can hide that definition to allow it to be re-defined by putting the following at the top of this module:
  -- import Prelude hiding (reverse)
  
  -- reverse :: [a] -> [a]
  -- reverse []     = []
  -- reverse (x:xs) = reverse xs ++ [x]
  