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 12 : Higher-Order Functions
  
  module Chap12_higher_order_functions where
  
  import Chap05_lists_and_comprehensions (squares, odds, isPrime, sumSqOdds)
  
  import Chap10_lists_and_recursion (oddsRec) -- also sum, product, and, which are in the Prelude
  
  import Chap11_more_fun_with_recursion (prodFromTo) -- also enumFromTo, which is in the Prelude
  
  import Data.Char (ord, isDigit)
  
  -- Patterns of computation
  
  enumFromTo' = enumPattern (:) []
  prodFromTo' = enumPattern (*) 1
  
  enumPattern :: (Int -> t -> t) -> t -> Int -> Int -> t
  enumPattern f e m n | m > n  = e
                      | m <= n = f m  (enumPattern f e (m+1) n)
  
  -- Map
  
  ords :: [Char] -> [Int]
  ords xs = [ ord x | x <- xs ]
  
  l1 = ords "cat"
  
  -- 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 (map)
  
  -- map :: (a -> b) -> [a] -> [b]
  -- map f xs = [ f x | x <- xs ]
  
  squares' :: [Int] -> [Int]
  squares' = map sqr
               where sqr x = x*x
  
  ords' :: [Char] -> [Int]
  ords' = map ord
  
  squaresRec :: [Int] -> [Int]
  squaresRec []     = []
  squaresRec (x:xs) = x*x : squaresRec xs
  
  ordsRec :: [Char] -> [Int]
  ordsRec []     = []
  ordsRec (x:xs) = ord x : ordsRec xs
  
  mapRec :: (a -> b) -> [a] -> [b]
  mapRec f []     = []
  mapRec f (x:xs) = f x : mapRec f xs
  
  squaresRec' :: [Int] -> [Int]
  squaresRec' = mapRec sqr
                  where sqr x = x*x
  
  -- Filter
  
  digits :: [Char] -> [Char]
  digits xs = [ x | x <- xs, isDigit x ]
  
  digitsRec :: [Char] -> [Char]
  digitsRec []                 = []
  digitsRec (x:xs) | isDigit x = x : digitsRec xs
                   | otherwise = digitsRec xs
  
  -- 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 (filter)
  
  -- filter :: (a -> Bool) -> [a] -> [a]
  -- filter p xs = [ x | x <- xs, p x ]
  
  filterRec :: (a -> Bool) -> [a] -> [a]
  filterRec p []                 = []
  filterRec p (x:xs) | p x       = x : filterRec p xs
                     | otherwise = filterRec p xs
  
  odds' :: [Int] -> [Int]
  odds' = filter odd
  
  digits' :: [Char] -> [Char]
  digits' = filter isDigit
  
  -- Fold
  
  -- 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 (concat)
  
  -- concat :: [[a]] -> [a]
  -- concat []       = []
  -- concat (xs:xss) = xs ++ concat xss
  
  l2 = concat [[1,2,3],[4,5]]
  
  l3 = concat ["con","cat","en","ate"]
  
  -- 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 (foldr)
  
  -- foldr :: (a -> a -> a) -> a -> [a] -> a
  -- foldr f v []     = v
  -- foldr f v (x:xs) = f x (foldr f v xs)
  
  foldr' :: (a -> a -> a) -> a -> [a] -> a
  foldr' f v []     = v
  foldr' f v (x:xs) = x `f` (foldr' f v xs)
  
  sum' :: [Int] -> Int
  sum' = foldr (+) 0
  
  product' :: [Int] -> Int
  product' = foldr (*) 1
  
  and' :: [Bool] -> Bool
  and' = foldr (&&) True
  
  concat' :: [[a]] -> [a]
  concat' = foldr (++) []
  
  -- foldr and foldl
  
  sum'' :: [Int] -> Int
  sum'' = foldl (+) 0
  
  product'' :: [Int] -> Int
  product'' = foldl (*) 1
  
  and'' :: [Bool] -> Bool
  and'' = foldl (&&) True
  
  concat'' :: [[a]] -> [a]
  concat'' = foldl (++) []
  
  cumulativeDivide :: Int -> [Int] ->Int
  cumulativeDivide i = foldl div i
  
  (<:) :: [a] -> a -> [a]
  xs <: x = x : xs
  
  reverse' :: [a] -> [a]
  reverse' = foldl (<:) []
  
  -- 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 (foldr1, maximum)
  
  -- foldr1 :: (a -> a -> a) -> [a] -> a
  -- foldr1 f []     = error "empty list"
  -- foldr1 f [x]    = x
  -- foldr1 f (x:xs) = x `f` (foldr1 f xs)
  
  -- maximum :: [Int] -> Int
  -- maximum = foldr1 max
  
  -- Combining map, filter and foldr/foldl
  
  dblPrimes :: [Int] -> [Int]
  dblPrimes ns = [ 2*n | n <- ns, isPrime n ]
  
  dblPrimes' :: [Int] -> [Int]
  dblPrimes' ns = map dbl (filter isPrime ns)
                    where dbl x = 2*x
  
  sumSqOdds' :: [Int] -> Int
  sumSqOdds' ns = foldr (+) 0 (map sqr (filter odd ns))
                    where sqr x = x*x
  
  -- Curried types and partial application
  
  increment :: Int -> Int
  increment = (+) 1
  
  isPositive :: Int -> Bool
  isPositive = (<=) 0
  
  pow2 :: Int -> Int
  pow2 = (^) 2
  
  pow2' = (2 ^)
  isVowel = (`elem` "aeiouAEIOU")
  squares'' = map (^ 2)
  