module HaskellBasics where

diffSq :: Integer -> Integer -> Integer
diffSq x y = (x - y) * (x + y)

diffSqV3a, diffSqV3b :: Integer -> Integer -> Integer

diffSqV3a x y =
    let minus = x - y
        plus = x + y
    in minus * plus

diffSqV3b x y = minus * plus
  where
    minus = x - y
    plus = x + y

slowFactorial :: Integer -> Integer
slowFactorial 0 = 1
slowFactorial n = n * slowFactorial (n - 1)

-- Slow Fibonacci (yawn) to show you can have more patterns.
slowFib :: Integer -> Integer
slowFib 0 = 0
slowFib 1 = 1
slowFib n = slowFib (n-1) + slowFib (n-2)

-- Long form---using a "case-of" expression:
slowFib2 :: Integer -> Integer
slowFib2 x = case x of
    0 -> 0
    1 -> 1
    n -> slowFib2 n1 + slowFib2 n2
        where
          n1 = n - 1
          n2 = n - 2
        -- The other example of "where".  This one is part of "n -> ...".


insert :: Integer -> [Integer] -> [Integer]

-- Structural induction on xs.

-- Base case: xs is empty. Answer is [e] aka e:[]
insert e [] = [e]  -- e : []

-- Induction step: Suppose xs has the form x:xt (and xt is shorter than xs).
-- E.g., xs = [1,3,5,8], x = 1, xt = [3,5,8].
-- Induction hypothesis: insert e xt = put e into the right place in xt.
insert e xs@(x:xt)
    -- xs@(x:xt) is an "as-pattern", "xs as (x:xt)",
    -- so xs refers to the whole list, and it also matches x:xt
    --
    -- If e <= x, then e should be put before x, in fact all of xs, and be done.
    -- E.g., insert 1 (10 : xt) = 1 : (10 : xt)

    | e <= x = e : xs

    -- Otherwise, the answer should go like:
    -- x, followed by whatever is putting e into the right place in xt.
    -- i.e.,
    -- x, followed by insert e xt (because IH)
    -- E.g., insert 25 (10 : xt) = 10 : (insert 25 xt)

    | otherwise = x : insert e xt

insertionSort :: [Integer] -> [Integer]
insertionSort [] = []
insertionSort (x:xt) = insert x (insertionSort xt)

insertionSortAcc :: [Integer] -> [Integer]
insertionSortAcc xs = go xs []
  where
    -- Specification for go (when you prove go correct by induction):
    -- for all xs, for all acc:
    --   Assume acc is in sorted order (precondition).
    --   go xs acc = add elements of xs to acc but in sorted order
    go (x:xt) acc = let acc2 = insert x acc
                    in go xt acc2
    go [] acc = acc