{-
    Opgaver på ugeseddel 8
-}
module Chapter19 where

-- strict (p. 427)
strict :: (a -> b) -> a -> b
strict f x = seq x (f x)
-- (dvs. evaluér x først og afleverer dernæst udtrykket f x)

-- -- foldr (p. 426)
-- foldr :: (a -> b -> b) -> b -> [a] -> b
-- foldr f st []     = st
-- foldr f st (x:xs) = f x (foldr f st xs)
--

-- foldl' (p. 428ø)
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f st []     = st
foldl' f st (x:xs) = strict (foldl' f) (f st x) xs


-- Opgave 19.20 p. 429

-- Tilføj i slutningen
append :: a -> [a] -> [a]
append x y = y ++ [x]

-- Tilføj i slutningen
append' :: [a] -> a -> [a]
append' x y = y : x

reverseR  xs = foldr  append  [] xs
reverseL' xs = foldl' append' [] xs

{- 
reverseR [1..4]
  = foldr append [] [1..4]
  = foldr append [] (1:[2..4])
  = append 1 (foldr append [] [2..4])
  = (foldr append [] [2..4]) ++ [1]
  = ((foldr append [] [3..4]) ++ [2]) ++ [1]
  = (((foldr append [] [4..4]) ++ [3]) ++ [2]) ++ [1]
  = ((((foldr append [] []) ++ [4]) ++ [3]) ++ [2]) ++ [1]
  = ((([] ++ [4]) ++ [3]) ++ [2]) ++ [1]

reverseL [1..4]
  = foldl' append' [] [1..4]
  = foldl' append' [] (1:[2..4])
  = strict (foldl' append') (append' [] 1) [2..4]
  = foldl' append' [1] [2..4]
  = strict (foldl' append') (append' [1] 2) [3..4]
  = foldl' append' [2,1] [3..4]
  = foldl' append' [3,2,1] [4..4]
  = foldl' append' [4,3,2,1] []
  = [4,3,2,1]
-}


-- Opgave 19.21 p. 429

iSortr  xs = foldr        ins  [] xs
iSortl' xs = foldl' (flip ins) [] xs

ins :: Int -> [Int] -> [Int]
ins x []    = [x]
ins x (y:ys)
  | x <= y      = x : (y:ys)
  | otherwise   = y : ins x ys

iSortr [1..4]
  = foldr i [] [1..4]
  = foldr i [] (1:[2..4])
  = i 1 (foldr i [] [2..4])
  = i 1 (i 2 (foldr i [] [3..4]))
  = i 1 (i 2 (i 3 (foldr i [] [4..4])))
  = i 1 (i 2 (i 3 (i 4 (foldr i [] []))))
  = i 1 (i 2 (i 3 (i 4 [])))
  = i 1 (i 2 (i 3 [4]))
  = i 1 (i 2 [3,4])
  = i 1 [2,3,4]
  = [1,2,3,4]

iSortl' [1..4]
  = foldl' fi [] [1..4]
  = foldl' fi [] (1:[2..4])
  = strict (foldl' fi) (fi [] 1) [2..4]
  = foldl' fi [1] [2..4]
  = foldl' fi [1,2] [3..4]
  = foldl' fi [1,2,3] [4..4]
  = foldl' fi [1,2,3,4] []
  = [1,2,3,4]


-- Opgave 19.23 p. 429