{-  Exploring Languages with Interprters and Functional Programming
    Chapter 14: Infix Opertations and List Examples
    Copyright (C) 2018, H. Conrad Cunningham

1234567890123456789012345678901234567890123456789012345678901234567890

2018-07-11: Revised for 2018 textbook Chapter 14

-}

module ListProgExamples
  ( +++. !!!, rev, reverse', f, g, splitAt', zip', unzip',
    isort, insert, isort', insert' )
where

infixr 5 +++  -- append really ++
		
(+++) :: [a] -> [a] -> [a]
[] +++ xs     = xs           -- nil left operand 
(x:xs) +++ ys = x:(xs +++ ys) -- non-nil left operand 
  
infixl 9 !!!  -- list selection really !!

(!!!) :: [a] -> Int -> a
xs     !!! n | n < 0 = error "!!! negative index"
[]     !!! _         = error "!!! index too large"
(x:_)  !!! 0         = x
(_:xs) !!! n         = xs !!! (n-1)

rev :: [a] -> [a]
rev []     = []            -- nil argument
rev (x:xs) = rev xs ++ [x] -- non-nil argument

reverse' :: [a] -> [a]`
reverse' xs = rev xs []
              where rev []     ys = ys
                    rev (x:xs) ys = rev xs (x:ys)

splitAt' :: Int -> [a] -> ([a],[a]) 
splitAt' n xs =  (take' n xs, drop' n xs) 

zip' :: [a] -> [b] -> [(a,b)]
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys -- zip.1
zip' _      _      = []                 -- zip.1

unzip' :: [(a,b)] -> ([a],[b])
unzip' []         = ([],[])
unzip' ((x,y):ps) = (x:xs, y:ys)
                    where (xs,ys) = unzip' ps

-- Integer insertion sort
isort :: [Int] -> [Int]
isort []     = []
isort (x:xs) = insert x (isort xs)  

insert :: Int -> [Int] -> [Int]
insert x []     = [x]
insert x xs@(y:ys)  
    | x <= y    = (x:xs)  
    | otherwise = y : (insert x ys)  

-- Generic insertion sort
isort' :: Ord a => [a] -> [a]
isort' []     = []
isort' (x:xs) = insert' x (isort' xs)

insert' :: Ord a => a -> [a] -> [a]
insert' x []    = [x]
insert' x xs@(y:ys)
    | x <= y    = (x:xs)
    | otherwise = y : (insert' x ys)