-- 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 10 : Lists and Recursion

module Chap10_lists_and_recursion where

import Chap05_lists_and_comprehensions (squares)

import Test.QuickCheck (quickCheck)

-- Recursive function definitions

squaresRec :: [Int] -> [Int]
squaresRec []     = []
squaresRec (x:xs) = x*x : squaresRec xs

squaresCond :: [Int] -> [Int]
squaresCond ws =
  if null ws then []
  else x*x : squaresCond xs
    where x  = head ws
          xs = tail ws

squares_prop :: [Int] -> Bool
squares_prop ns =
    squares ns == squaresRec ns && squares ns == squaresCond ns

qc1 = quickCheck squares_prop

-- More recursive function definitions

oddsRec :: [Int] -> [Int]
oddsRec []                 = []
oddsRec (x:xs) | odd x     = x : oddsRec xs
               | otherwise = oddsRec xs

-- 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 (sum, product, and, or)

-- sum :: [Int] -> Int
-- sum []     = 0
-- sum (x:xs) = x + sum xs

-- product :: [Int] -> Int
-- product []     = 1
-- product (x:xs) = x * product xs

-- and :: [Bool] -> Bool
-- and []     = True
-- and (x:xs) = x && and xs

-- or :: [Bool] -> Bool
-- or []     = False
-- or (b:bs) = b || or bs

sumSqOddsRec :: [Int] -> Int
sumSqOddsRec []                 = 0
sumSqOddsRec (x:xs) | odd x     = x*x + sumSqOddsRec xs
                    | otherwise = sumSqOddsRec xs

-- Sorting a list

-- parameter list is in ascending order; same for result list
insert :: Int -> [Int] -> [Int]
insert m []                 = [m]
insert m (n:ns) | m <= n    = m:n:ns
                | otherwise = n : insert m ns

insertionSort :: [Int] -> [Int]
insertionSort []     = []
insertionSort (n:ns) = insert n (insertionSort ns)

l1 = insertionSort [4,8,2,1,7,17,2,3]

quicksort :: [Int] -> [Int]
quicksort []     = []
quicksort (m:ns) = quicksort less ++ [m] ++ quicksort more
                     where less = [ n | n <- ns, n < m ]
                           more = [ n | n <- ns, n >= m ]

l2 = quicksort [4,8,2,1,7,17,2,3]

sort_prop :: [Int] -> Bool
sort_prop ns = insertionSort ns == quicksort ns

qc2 = quickCheck sort_prop

-- parameter list is in ascending order; same for result list
insert' :: Ord a => a -> [a] -> [a]
insert' m []                 = [m]
insert' m (n:ns) | m <= n    = m:n:ns
                 | otherwise = n : insert' m ns

insertionSort' :: Ord a => [a] -> [a]
insertionSort' []     = []
insertionSort' (n:ns) = insert' n (insertionSort' ns)

quicksort' :: Ord a => [a] -> [a]
quicksort' []     = []
quicksort' (m:ns) = quicksort' less ++ [m] ++ quicksort' more
                      where less = [ n | n <- ns, n < m ]
                            more = [ n | n <- ns, n >= m ]

l3 = insertionSort' ["elephant","zebra","gnu","buffalo","impala"]

l4 = quicksort' ["hippopotamus","giraffe","hippo","lion","leopard"]

-- Exercise 6

insertionSort'' :: Ord a => [a] -> [a]
insertionSort'' []     = []
insertionSort'' (n:ns) = insertionSort'' (insert' n ns)