module HaskellBasics where

favouriteNumber :: Integer   -- Type signature. If omitted, the most general
                             -- type is inferred.
favouriteNumber = 4

isMultipleOf3 :: Integer -> Bool  -- Function type, "domain -> codomain"
isMultipleOf3 i = mod i 3 == 0

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

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

-- if-then-else version.
slowFactorial2 :: Integer -> Integer
slowFactorial2 n = if n == 0
                   then 1
                   else n * slowFactorial2 (n - 1)

-- Slow Fibonacci (yawn) to show you can have more pattern matching.
-- "This Fibonacci joke is as bad as the last two you heard combined."
-- https://twitter.com/sigfpe/status/776420034419658752
slowFib :: Integer -> Integer
slowFib 0 = 0
slowFib 1 = 1
slowFib n = slowFib (n-1) + slowFib (n-2)

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

-- Using guards.
slowFib3 :: Integer -> Integer
slowFib3 n | n == 0    = 0
           | n == 1    = 1
           | otherwise = slowFib3 n1 + slowFib3 n2
  -- This "where" is part of the whole "slowFib3 n ...".
  where
    n1 = n - 1
    n2 = n - 2


append :: [Integer] -> [Integer] -> [Integer]
-- WTP: append xs ys = concatenation of xs and ys
--                   = list of elements from xs followed by elements from ys
-- Strategy: induction on xs

-- Base case: xs is empty, answer is ys
append [] ys = ys

-- Induction step: Suppose xs has the form x:xt (and xt is shorter than xs).
-- E.g., xs = [1,3,5,8] = 1:3:5:8:[]
-- so x = 1, xt = 3:5:8:[]
--
-- Induction hypothesis: append xt ys = concatenation of xt and ys
--   E.g., append (3:5:8:[]) (4:1:6:[]) = 3:5:8:4:1:6:[]
-- WTP: append (x:xt) ys = concatenation of x:xt and ys
--   E.g., append (1:3:5:8:[]) (4:1:6:[]) = 1 : 3:5:8:4:1:6:[]
append (x:xt) ys = x : append xt ys


rev :: [Integer] -> [Integer]
rev xs = revhelper xs []

-- WTP: ∀xs, acc: revhelper xs acc = concatenation of xs reversed and acc
-- (I make explicit "∀xs, acc" because it is helpful later.)
-- Example: revhelper (4:1:6:[]) (2:5:[]) = 6:1:4:2:5:[]
-- Use induction on xs.

-- Base case: xs is empty, answer is acc.
revhelper [] acc = acc

-- Induction step: Suppose xs has the form x:xt (and xt is shorter than xs).
-- Induction hypothesis:
--   ∀acc: revhelper xt acc = concatenation of xt reversed and acc
-- Useful to note: The I.H. holds for any acc you want, not just the "original" acc.
-- WTP:
--   ∀acc: revhelper (x:xt) acc = concatenation of (x:xt) reversed and acc
-- Eureka:
--   concatenation of (x:xt) reversed and acc
-- = concatenation of xt reversed and (x : acc)
-- = revhelper xt (x : acc)
revhelper (x:xt) acc = revhelper xt (x : acc)