Thursday, 16 October 2014

Functional Programming (Haskell)

Haskell (Intro to Functional Programming FP101x @ with Erik Meijer
DONE EXERCISES 19/21, DONE LAB Ex 2 (Types and Classes) - DUE 17th Nov   Tips: 
  • Type Testing in GHCi  i.e.     
let ... :t ['a','b','c']
  • Type Testing in Eclipse   i.e.   The type of the following function:  twice f x = f (f x)
twice :: (a -> a) -> a -> a -- Replace to find the right answer
twice f x = f (f x)

DONE EXERCISES 6/9 / DONE LAB 15/16 Ex 3 (Defining Functions) - DUE 17th Nov
DONE 15/16  Ex 4 (List Comprehensions)- DUE 26th Nov
DONE EXERCISES 10/10 LAB 25/28 (NFI) Ex 5 (Recursive Functions) - DUE 26th Nov
DONE LECTURES EXERCISES 25/32 (GUESSED NFI Q 17,  24 (GUESSED!), 30), DONEJAM SESSION (CHURCH NUMERALS) DONE LABS 100% 13/13 Ex 6 (Higher-Order Functions) - DUE 3rd Dec
DONE LECTURES EXERCISES 7/9 Ex 7 (Functional Parsers and Monads)  - DUE 7th Dec
DONE LECTURES, JAM (Kotlin Language), EXERCISES 9/12 (GUESSED NFI Q 4, 5, 8 (GUESSED!), 9), AND LABS 15/22 (GUESSED NFI Q 1,3,4,5,6,7), Ex 8 (Interactive Programs) - DUE 7th Dec
DONE LECTURES (READ CH10), DONE EXERCISES 10/14, Ex 9 (Declaring Types & Classes) - DUE 10th Dec
DONE PART 1,2,&3 LECTURESDONE JAM (QUICKCHECK), DONE 3/4, Ex 10 (The Countdown Problem) - DUE 10th Dec
DONE PART 1 & 2 LECTURESDONE JAMDONE 10/14, LAB... meh, nfi, Horus the saviour!!, Ex 11 (Lazy Evaluation) - DUE 15th Dec
DONE READING Meh, Ex 12 (Reasoning about Programs) - DUE 20th Dec
DONE HOMEWORK (GUESSED RIGHT AFTER 8 ATTEMPTS) NFI LAB 1/22 (NFI Q 1-8, 10-11, 13-22), Ex 13 (Rose Tree) - DUE 20th Dec
  • Software Crisis
    • Problem: Reduce Time & Cost and Increase Quality. 
    • Solution: Code Features at High Level of Abstraction so Clear and Concise using Functional Programming Techniques based on lambda calculus Concepts }
Haskell {
  • Dfn: Pure Functional Language style provides elegant Framework to program using maths functions. Composing Expressions (i.e. lambda expressions) returning values for immediate use in programs instead of just Statements style used in Imperative Language (with side effect of communicating values via global state)
  • Example #1 (Summing Integers)
    • Statements imperative style
int x = 0; for ( ... ) { x += 1 }
      • Statements
      • Immutable State
      • Imperatively update Statements (i.e. using a loop)
      • Computation Method: Variable Assignment
    • Expressions style (i.e. Haskell, Java 8 Streams)
sum [ ... ] 
      • No Statements
      • Compose program using Expressions
      • Computation Method: Function Application
  • CLI 
  • Basic Operations Expressions used to experiment 
    • Example #2 (Select first element from list)
      • Function (head) with argument List returns 1st element (elem). Note: Haskell starts indexing at 0
head [1,2,3] -- output: 1
      • Function (tail) with argument List removes 1st elem from list
tail [1,2,3] -- output: [2,3]
      • Function (nth elem) with argument List returns specified elem
      • Indexing as it linearly traverses the list across its length (not a constant time operation)
[1,3,2] !! 2 -- output: 2
      • Function (take first n elem) with argument List returns first n elems
take 2 [1,3,2] -- output: [1,3]
      • Function (drop first n elem) with argument List drops first n elems
drop 2 [1,3,2] -- output: [2]
      • Function (length) with argument List returns amount of indexes (time linear in length of list)
length [1,3,2] -- output: 3
      • Function (sum, product, append, reverse, init) with argument List returns common sense outputs
sum [1,3,2] -- output: 6
product [2,3,4] -- output: 24
[2,3,4] ++ [1,5] -- output: [2,3,4,1,5]
reverse [2,3,4] -- output: [4,3,2]
init [1,2,3] -- output: [1,2] 
  • Complex Operations (Higher Order Functions used instead of Indexing over Lists)
  • Function Application (FA) (Maths)
    • Parenthesis in maths (denotes applying Function Application with Args)  f(a,b)
    • Space in maths (applies multiplication) 2 7 -- output: 14
  • Function Application (FA) (Haskell) (lightweight)
    • Space (applies Function Application with Args) f a b
    • * (applies multiplication) 2*5 -- output: 10
    • Priority
      • Function Application binds higher priority than other Operators ('f' applied to 'a' plus 'b') f a + b -- means: f(a)+b rather than f(a+b)
    • Equivalents
      • f a b (Haskell)  is  f(a,b) (Maths)  (applies 'f' to 'a', and applies that result to 'b')
      • f (a b) (Haskell)  is  f(a(b)) (Maths)  
      • f x (a b) (Haskell)  is  f(x,a(b)) (Maths) 
      • f x * a b (Haskell)  is  f(x)a(b) (Maths) 
  • Function Composition (FC) (Haskell)
    • Equivalents
      • f composed a (Haskell FC)  is  f(a(b)) (Haskell FA) 
  • Function
    • Dfn: Mapping from Values of a Type to Values of another Type
  • Function Types
    • t1 -> t2 (Domain of Fn -> Range of Fn) is a Type of Fn that maps set of all Values of Type t1 and returns to Value in set of Type t2
      • Example
isDigit :: CHAR -> BOOL
    • Unrestricted Types for Domain & Range (for inputs and outputs like with Lists and Tuples)
      • Example 1
add :: (Int, Int) -> Int (meaning: add Function takes Tuple comprising of two integers and returns an Integer result)
        • Equivalent is add (x, y) = x + y
      • Example 2
zeroto :: Int -> [Int] (meaning: zeroto Function takes Integer and returns a List of Integers)
        • Equivalent is zeroto n = [0 .. n]
  • Curried Functions
    • Benefits: Optimised for Haskell (all Functions normally defined in Curried form unless Tupling explicitly required) and more flexible and convenient than Functions taking Tuple args (as can Partially Apply a Function
    • Example A
add` :: Int -> (Int -> Int) (meaning: add prime (`) is defined as a Function taking Integer and returning another Function, which takes yet another Integer and returns another Integer)
      • Equivalent usage form is add` :: Int -> Int -> Int
      • Equivalent is add` x y = x + y (meaning: add prime (`) is defined as a Function taking an Integer x, and returning a Function add` x, which takes an Integer y and returns a result of x + y)
    • Example B 
      • Function mult takes 3 OFF args (x, y, z) and multiplies them
mult :: Int -> (Int -> (Int -> Int))
      • Currying ConventionIn the Function Type the Function Arrows and Parenthesise bind from Left to Right
mult x y z = x * y * z (meaning: Curry Function mult takes Integer x and returns a Function mult x (where x is Arg#1), it then takes y (Arg#2) and returns Function mult x y, it then takes z (Arg#3) and returns Function mult x y z. Finally all Args are multiplied to return resultant Integer)
      • Equivalent usage form is (((mult x) y) z)
        • Currying Convention: In the Function Application, the Expression has Parenthesise that associate from Right to Left
    • Example C
take` 5 (Curried Function that Partially Applies "take` " to 5, by taking an input List of Integers and returns an output Function List of Integers that only takes the first 5 elements of the initial List). It Partially Applies the Curry Function " take` " to 5 to yield a Fn
    • Note #1: Arrows (i.e. ->) in Haskell are usually omitted as they are optional (causes confusion to beginners)
    • Note #2: add` (add prime) and add both produce the same overall result
    • Note #3: 
      • add - Function that takes multiple arguments (aka Tuple) at once 
      • add` (aka add prime) - Function (a Curried Function) that takes arguments one at a time. Curried by returning Nested Functions
  • Polymorphic Functions
    • Definition: Polymorphic functions have a Type that contains Type Variables (i.e. a, [a]) but are not defined on Concrete Types (i.e. Int, Bool)
    • Example A
length :: [a] -> Int { meaning: Polymorphic Function named 'length' that takes a List of values of Type 'a', and returns an Integer, for any Type of element 'a' in the List. In this example  is an implicitely declared Type Variable (starts with lowercase) and Int (is a Concrete Type (starts with uppercase) }
    • Example B
length [False, True] (returning output of 2) { meaning: Instantiate 'length' Function that takes a List of Booleans for its Type Variable. Note: It is not necessary to declare on what Type the Function 'length' will be Polymorphic, as we differentiate Namespace of Types (start with uppercase letter) and Type Variables (start with lowercase letter) }
    • Standard Prelude (aka Haskell SDK) contains Polymorphic Functions including:
fst :: (a,b) -> ameaning: takes Tuple and returns value (first element) of Type a }
head :: [a] -> a { meaning: takes List of 'a' (for any Type 'a') and returns 'a' }
take :: Int -> [a] -> [a] { meaning: takes Integer and returns a Function that takes a List, then takes the first n elements of the List and returns another List }
zip :: [a] -> [b] -> [(a,b)] { meaning: takes each element from two Lists and returns a List of of pairs (combines the elements into a Tuple) }
find :: (Eq a) => a -> [(a,b)] -> [b] meaning: Hoogle takes a value together with a list of pairs and matches on the first component of each pair and returns a list of the corresponding second components }
  • Overloaded Polymorphic Functions
    • Definition: Overloaded if its Type contains one or more Class Constraints that restrict the Types of allowable parameters/elements in the List
    • Constrained Type Variable
      • Definition: Instantiated only with Types that satisfy given Constraints
    • Example A
sum :: Num a => [a] -> a meaning: Function named 'sum' takes a List of values of Type 'a' and returns a value of Type 'a', but only where 'a' is a numeric Type from the Num Class. Note: The Object-Oriented equivalent would be only taking a List of values of Type 'a' that implement a Num Interface (aka specification for Num) }
      • Sample Values
sum [1.1, 1.2] (returns result successfully as 'a' is of Type Float)
sum ['a', 'b'] (returns Error as 'a' is Type Char, it is a non-numeric Type that is not from the Num Class)
  • Type Classes
    • Num (numeric Types)
(+) :: Num a => a -> a -> a  (meaning: the addition '+' Type takes a value of Type 'a', returns a Function that takes another value of Type 'a', and returns a value of Type 'a', but only for values of Type 'a' that are in the Num Class)
    • Eq (equality Types for comparison)
(==) :: Eq a => a -> a -> Bool
    • Ord (ordered Types for comparison)
(<) :: Ord a => a -> a -> Bool
  • Defining Functions
    • Nested Conditional Expressions 
      • Example #1:  Function defined immediately using a Conditional Expression
signum :: Int -> Int
signum n = if n < 0 then -1 else
              if n == 0 then 0 else 1
      • Note #1: 'Else' must always be used to avoid ambiguity in nested conditionals
    • Guarded Equations (preferred Haskell notation)
      • Purpose: Use Guarded Equations in Function Definitions that starts with a Conditional Expression. The Guarded Equation may be used as an alternative short-form that replaces the Conditional Expression (improved readability).
      • Example #2 (replacement for Example #1 with Guarded Equations):  
signum :: Int -> Int
signum n | n >= 0     = -1
         | n == 0     = 0
         | otherwise  = 1
      • meaning: The Function 'signum' of 'n', is -1 when n >= 0, 
        • is 0 when n == 0, or its 1 otherwise
      • Note #1: 'otherwise' is an alias for False
    • Pattern Matching
      • Benefit: Use Pattern Matching on Arguments directly in Function Definitions in Haskell to provide a clarity
      • Example #1 (define Truth Table mapping directly in Function Definition):  
(&&)          :: Bool -> Bool -> Bool
True && True = True
True && False = False
False && True = False
False && False = False

      • More Compact version (since all other cases are False:

True && True = True
_    && _    = False
        • Preferred version (most Efficient)
True  && b = b
False && _ = False
      • Note #1: '_' underscore is a wildcard placeholder used in Pattern Matching to match any value of an Argument (we do not care what its value is)
      • Note #2: Minimise the amount of evaluation necessary in function calls by using Example #2 (more Efficient as avoids evaluation of 2nd Arg if 1st Arg is False) instead of Example #1 (where Arguments on both sides of the && are evaluated)
      • Note #3: Order is Important in Patterns Matching (occurs Left to Right, Top to Bottom)
        • Example (always returns False)
_     && _    = False
True  && True = True
      • Note #4: Patterns Matching should Not Repeat Variables (variables inside Pattern Matching must be unique)
        • Example (causes Error)
b && b = b
_ && _ = False
    • Lists (when Defining Functions)
      • Constant Lists
        • Create non-empty list by adding elements to the start of the list with cons (:) operator 
[1,2,3,4]          meaning:  1:(2:(3:(4:[])))
      • Pattern Matching Lists (only matches on non-empty Lists)
        • Functions on Lists defined using x:xs patterns 
          • head maps non-empty List to its first element
head       :: [a] -> a
head (x:_) = x  (cons head-tail form) (meaning (of the Type): Head takes a List, where the Head of a List is the element Type of the List 'a', the Type is therefore List to 'a'
          • tail maps non-empty List to its remaining elements (after the first)
tail       :: [a] -> [a]
tail (_:xs) = xs  (meaning (of the Type): Tail takes a List, where the Tail of a List is a List, the Type is therefore List to List
        • Note #1: Head and Tail are not defined on Empty Lists so errors occur if type head [] in GHCi (as it is not of the form defined above), so the above are not Total Definitions
        • Note #2: x:xs List patterns must be Parenthesised, as Application has priority over cons (:)
    • Lambda Expressions
      • Dfn:  Unnamed Functions that are constructed concisely as an Expression of Function Type, where backslash ' \ ' is used to represent of λ (Lambda)
λx -> x + x (meaning: Function takes x, adds it to itself)
      • Purpose: 
        • Lambda Expressions allow coders to concisely express their intent Equivalently with better Readability and convey the actual meaning as follows using explicit Lambdas when defining Functions by Currying them, and when defining Functions that return Functions as results (in a sense the same as Currying).
        • Avoids having to come up with meaningful names when you just want to pass information directly. Only really bother Naming Functions when intend to use it repeatedly or for clarity
      • Example A:
add x y = x + y  (meaning: add is a Function that takes param x, returns a Function that takes a param y, then adds them together)

add = λx -> (λx -> x + y) (Lambda Expression meaning: add is a Function that takes param x, returns a Function that takes param y, then adds them together)
      • Note: Haskell is a Functional Programming language, which use Lambda Expressions similar to Lambda Calculus (based on Pure Functions), whilst in other languages they are represented as Closures (close over variables in outer scope) 
      • Example B:
const    :: a -> b -> a
const x _ = x (note: this doesn't make it explicit that you're Returning a Function)

const    :: a -> (b -> a) (meaning: const Function that given 'a', will return a Function that whatever 'b' is given will return 'a'. It uses parenthesise around the Type to make it clear that you're Returning a Function)

const x   = λ_ -> x  (Lambda Expression meaning: const 'x' returns a Function that will ignore whatever it is given and just return x )
      • Example C (Avoids inventing a Function name unnecessarily):
odds n = map f [0..n-1]
           f x = x*2 + 1 (meaning: no purpose in giving a Function a name 'f', which simply performs a mapping over a List  )

odds n = map (λx -> x*2 + 1) [0..n-1] (Lambda Expression (idiomatic Haskell) meaning: instead just pass a Lambda Expression to the map Function, which will be used to map the Function x*2 + 1 over the List

    • Sections
      • Dfn: Use an Infix Operator (i.e. used between two arguments) and use it as a Curried Function written before the two args using parenthesise  
      • Uses:
        • Construct useful Functions using Sections without inventing a name for it unnecessarily
(1+) (Successor Function)
(1/) (Reciprocation Function)
(*2) (Doubling Function)
(/2) (Halving Function) - (meaning: takes arg and halves it)
      • Example #1:  
1 + 2 = 3

(+) 1 2 = 3  (equivalent with Sections using the + operator as a Function)

      • Example #2 (Partially Applied):  
(1+) 2 = 3 (meaning: Function Section that expects a 2nd arg, and adds 1 to it. A Function that increments something as a Section)

(+2) 1 = 3  (meaning: Function Section that expects a Value to be inserted before the +, and then adds the 1 there)
      • Note:  If + is a Binary Operator then you can write it in parenthesis and use it as a Normal Function ( + ), or Left  ( + ) or Right  ( + Section it by Partially Applying it to an arg
    • List Comprehensions
      • Dfn: Mechanism in code to define Functions that manipulate Collections (similar to SQL queries)
      • History and Comparison
        • Imperitive Languages use mechanisms to iterate over Collections (for loops, while, do while, for each, continue, break)
        • Mathematicians (Set Comprehension Notation) use mechanisms to iterate over Collections (Set). Traditionally to deal with a Set in maths, duplicate elements are removed, and equality is required to be determined between Functions (overcoming the impossible Halting problem) 
{ x^2 | x E {1..5}}  (meaning: Set of 'x' squared where i values are taken from the Set of values between 1 and 5. The result here is {1,4,9,16,25})
        • Haskell (List Comprehension Notation)  uses a simplified mechanism than that used in maths to deal with constructing new Sets from old ones, applying theory from maths to instead deal with Lists with minimum constraint on the Collection Type (deals with Collections by decomposing a List recursively by grabbing the first element, similar to Java 8 Streams)
[x^2 | x <- [1..5]]  (meaning: List of 'x' squared numbers where the element 'x' is taken from the values between 1 and 5. The result here is {1,4,9,16,25})
      • Multiple Generators in List Comprehensions
        • Generator Dfn:  Expression stating how to generate values for 'x'
          • Example: x <- [1..5]  (see above)
        • Multiple Generators Dfn: Nested and composed by separating individual Generators with elements comprising of Constant Values by commas and recursively reusing the same structure. View it as a Nested Loop, where 'x' Inner loop, and 'y' Outer loop (Outer loop variable value when included in each output component will change the most frequently). Swapping the Order of the Inner and Outer Generators changes the elements of the Final List)
          • Example 1: 
[(x,y) | x <- [1,2,3], y <- [4,5]]  (meaning: take all pairs x and y, x drawn from [1,2,3], and y drawn from [4,5]), returning[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
          • Example 2 (Generator Ordering Swapped): 
[(x,y) | y <- [4,5], x <- [1,2,3]]  (meaning: take all pairs y and x, y drawn from [4,5], and x drawn from [1,2,3]), returning[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]
        • Dependant Generators Dfn: Nested and composed by separating individual Generators where Outer Generators may be Dependant on variables in the Inner Generators (that are introduced earlier). Similar to a loop, where the inner loop may be dependant on outer loop variables. 
          • Benefits: Concise code
          • Example 1: 
[(x,y) | x <- [1..3], y <- [y..3]]  (meaning: take all pairs x and y, x is drawn from [1..3], and y is drawn from [x..3), such that 'x' variable is In-Scope of Generators on its Outer side), returning: [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)] (3 OFF iterations)
          • Example 2 (Library Fn that Concatenates a List of Lists): 
concat     :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

concat [[1,2,3],[4,5],[6]] returns: [1,2,3,4,5,6]

  (meaning: Comprehension that gets every List, out of the List of Lists (doubly nested loop), and yields every element value of that List to return a flattened Single List of Type 'a', with same element Type as the original List)
        • Guards (Filters) in List Comprehensions
          • Guard Dfn:  Restricts the Values produced by Inner Generators (earlier ones). Guards are similar to SELECT WHERE in SQL, where the Guard is the WHERE part
          • Example 1: 
    [x | x <- [1..10], even x]  (meaning: x is drawn from numbers between [1..10] Collection with the even numbers filtered out and thrown away, as these Values do not hold true for the predicate) (result: [2,4,6,8,10] even numbers) 
          • Example 2: 
    factors :: Int -> [Int]
    factors n =

    [x | x <- [1..n], n `mod` x == 0]   (meaning: Function that takes a positive number and maps it by breaking it down into its List of factors, where the factors are derived by taking the number 'n', taking all numbers [1..n] and only retain where 'n' modulo 'x' is zero)

    > factors 15 returns: [1,3,5,15]


    prime :: Int -> Bool
    prime n = factors n == [1..n]  (meaning: Use the Factors Function to define a Predicate that checks whether a number is prime, if its factors are exactly the List [1..n])

    > prime 15 returns: False
    > prime 7  returns: True


    prime :: Int -> Int
    prime n = [x | x <- [2..n], prime x]  (meaning: check what the List is of all primes up to a given limit between [2..n])

    > prime 40 returns: [2,3,5,7,11,13,17,19,24,29,31,37]
        • Zip Function in List Comprehensions
          • Zip Dfn:  Combine two Lists into a Single List of pairs with their corresponding elements. It only continues until the length of one of the Lists being used is exhausted
    zip :: [a] -> [b] -> [(a,b)]  (meaning: zip has Type, List of 'a', to List of 'b', to List of pairs of a, b) 
          • Example 1: 
    > zip ['a','b','c'] [1,2,3,4]

          • Example 2: 
    pairs   :: [a] -> [(a,a)]
    pairs xs = zip xs (tail xs) (meaning: Function that takes the List [1,2,3,4], then takes the tail of the List [2,3,4], and then zips and returns a List of all pairs of adjacent elements from the List until one of the Lists becomes exhausted of elements, like a sliding window of pairs) 
    > pairs [1,2,3,4] returns: [(1,2),(2,3),(3,4)]

          • Example 3: 
    sorted   :: Ord a => [a] -> Bool
    sorted xs =     
           and [x <= y | (x,y) <- pairs xs] (meaning: Function that checks if List is Sorted by taking all adjacent Function pairs in List to give 'x' comma 'ys', then check that 1st value < 2nd value) 
    > sorted [1,2,3,4] returns: True
          • Note 1 (Lists vs Arrays): 
            • Lists do not have positions, access elements from Left to Right (i.e. grab the head, or the head of the tail, or the head of the tail of the tail, etc)
            • Arrays are indexed
          • Position of List Elements using a Zip Function: 
            • Function that returns the List of all Positions of a Value in a List
            • Example 3: 
    positions :: Eq a => a -> [a] -> [Int]
    positions x xs =
      [i | (x', i) <- zip xs [0..n], x == x']
      where n = length xs meaning: Using Zip Function, take List xs (i.e. infinite List starting at 0), take List [0..n] where n is length of the List. Zip the List with the Positions }
    > positions 0 [1,0,0,1,0,1,1,0] returns: [1,2,4,7] meaning: Pair every element with its Position, and then Filter out result with only the Values we are looking for (i.e. Position 0 only) }
        • String Comprehensions
          • Definition: Strings are sequences of Chars (simply a List), so all available operations on Lists such as Comprehensions, Map, Filter, Foldr, work over Strings.
              "abc" :: String  (meaning: ['a','b','b'] :: [Char]) 

    > length "abcde" returns: meaning: Use length Function over a List }
    > take 3 "abcde" returns: "abc" meaning: take first 3 Chars from a List }
    > zip "abc" [1,2,3,4] returns: [('a',1),('b',2),('c',3)] meaning: zip a String with a List, to get a List of pairs }
          • Note:  Literal Syntax for List  'a' : 'b' : 'c' : [] meaning: 'a' cons 'b' cons 'c' on the empty List, where  : is the List Constructor, which is Right Associative }
          • Example 1 (Count Qty of Lowercase Chars in a String): 
    lowers    :: String -> Int
    lowers xs =     
           length [x | x <- xs, isLower x]meaning: grabs all Chars 'x' in the String 'xs' (List), filter out lowercase ones, and compute the length }
    > lowers "Haskell" returns: 6
    • Recursive Functions
      • Stack Overflow 
        • Example If given a List of bananas that we want to eat, for each of the bananas where there exists a Next banana, we decide to add the current banana to a stack and begin eating the Next banana first before the current one. With multiple bananas we'd built multiple stacks. If there are a large number of bananas we'd experience a Stack Overflow }
      • Tail Call Elimination
        • Dfn: Concept in Haskell where Recursive Functions are used to safely define Control Structures (without causing a Stack Overflow with multiple stacks)
        • Example { Finishing each current banana before eating the Next banana, so you only need one stack }
      • (Non-Recursive) Function Definition
        • Example { Factorial maps any integer n to product of integers between 1 and n) }
    factorial    :: Int -> Int
    factorial n = product [1..n] meaning: take the List of values between 1 to 'n' and multiply them together }

    factorial 4
    = product [1..4]
    = product [1..4]
    = product [1,2,3,4]
    = 1*2*3*4
    meaning: unfold expressions Evaluated in process of steps, applying Functions to their Arguments }
      • Recursive Function Definition (defining the Function in terms of itself)
        • Usage and Alternatives (of Function Definition): Functions may be defined in terms of Recursion, defined in terms of Other Functions, or defined in terms of Themselves, or Abstract Recursion Pattern as Higher Order Function (that only performs the Recursion) and then simply plugin the amount of times and the 1.
        • Example 1 
          • Recursive Function over Numbers { we look at the Recursive Structure of Numbers and then define the Function according to that structure }
    factorial 0 = 1 (case where number is 0, where 1 is the Identity for multiplication i.e. 1*x = x = x*1)
    factorial n = n * factorial (n-1) (case where number is n, such that the recursion will be performed by taking factorial of 'n-1' * n) meaning: maps 0 to 1 and any other integer to the product of itself, and the factorial of its predecessor }

    -- Execution
    factorial 3
    = 3 * factorial 2
    = 3 * (2 * factorial 1)
    = 3 * (2 * (1 * factorial 0))
    = 3 * (2 * (1 * 1))
    = 3 * (2 * 1)
    = 3 * 2  meaning: stack appears, similar to the bananas example, as there is a factorial getting moved to the right (added to a stack) until all factorials have been is executed, followed by multiplication and popping off the stack }

        • Diverge { Note that in this Recursive Definition over Numbers will diverge for numbers less than 0 (i.e. factorial (-1) and not terminate because the Base Case is never reached, causing a Stack Overflow }
        • Induction { Mathematical technique to prove Properties of Functions using Recursion }
        • Example 2 
          • Recursive Function over Lists { we look at the Recursive Structure of Lists and then define the Function over that Recursive Structure }

    product        :: [Int] -> Int
    product []     = 1 (case where empty list, product maps an empty list to 1, where 1 is the Identity for multiplication i.e. 1*x = x = x*1)
    product (n:ns) = n * product ns (case where we have a list of n cons ns, such that the recursion will be performed by taking product of ns * n) meaning: take the product of a value n on any non-empty list ns, by taking the product of the rest of the list (the tail), and multiplying it by n (the head) }

    -- Execution

    product [2,3,4]
    = 2 * product [3,4] (i.e. 2 cons 3, 4)
    = 2 * (3 * product [4])
    = 2 * (3 * (4 * product []))
    = 2 * (3 * (4 * 1))
    = 24
      meaning: executing the product unfolds the definition of the Function, then pop the stack to get the result. Note that the Recursion is hidden in the product Function (of numbers 1 to n) }

        • Example 3
          • Recursive Function over Lists (defined by Induction on the Structure of the List, and follows the Recursive Structure of the List)

    length        :: [a] -> Int
    length []     = 0 (case where empty list)
    length (_:xs) = 1 + length xs meaning: if the list is non-empty then we do not care what the first element is, we simply compute the length of the rest of the list (i.e. the tail xs) and add 1 to it }

    -- Execution

    length [1,2,3]
    = 1 + length [2,3] 
    = 1 + (1 + length [3]) (unfold)
    = 1 + (1 + (1 + length [])) (unfold)
    = 1 + (1 + (1 + 0)) (unfold and add them up)
    = 3

        • Example 4
          • Recursive Function over Lists

    reverse        :: [a] -> [a]
    reverse []     = [] 
    reverse (x:xs) = reverse xs + [x] (meaning: non-empty list mapped to reverse of its tail appended to its head)

    -- Execution

    reverse [1,2,3]
    = reverse [2,3] ++ [1] (appending elements from Right to Left)
    = (reverse [3] ++ [2]) ++ [1] 
    = ((reverse [] ++ [3]) ++ [2]) ++ [1]
    = (([] ++ [3]) ++ [2]) ++ [1] (reverse the list)
    = [3,2,1] 

      • Recursive Functions with Multiple Arguments
        • Example 1  
          • Recursive Function over Lists (Zip takes every element from two lists, combines them into a pair)
    zip                 :: [a] -> [b] -> [(a,b)]
    zip []     _        = [] (stop the recursion when either of the two lists are exhausted, and simply return the empty list)
    zip _      []       = []
    zip (x:xs) (y:ys)   = (x,y) : zip xs ys  -- aka xs `zip ys (given two non-empty lists, take the head (i.e. x and y) of both and put into a pair (i.e. (x,y)), then recursively zip the rest until either of the two lists are exhausted)

        • Example 2 
          • Recursive Function over Lists (Drop takes an integer and a list, and returns a list. It's recursing over both the integer and the list)
    drop                :: Int -> [a] -> [a]
    drop 0 xs           = xs (drop zero elements from the list, and just return the empty list)
    drop _ []           = [] (drop whatever elements we want if we have the empty list, and just return the empty list)
    drop n (_:xs)       = drop (n-1) xs { otherwise, drop of n and whatever cons xs (here we recurse over the structure of the list, and recurse over the structure of the number) is drop of (n-1) and xs. Note: use (n-1) on the right hand side since n+k patterns are deprecated }

    -- Execution

    drop 3 [1,2,3,4,5]
    = { applying drop }
    drop 2 [2,3,4,5]
    = { applying drop }
    drop 1 [3,4,5]
    = { applying drop }
    drop 0 [4,5]
    = { applying drop }

        • Example 3
          • Recursive Function over Lists (Append)
    (++)                :: [a] -> [a] -> [a]
    []      ++ ys       = ys (append the empty list to another list, results in the other list)
    (x:xs)  ++ ys       = x : (xs ++ ys) (append a list x cons xs to a list ys, we first append xs to ys, and then cons x on top)
        • Note: n+k patterns in Haskell have been deprecated

        • Example 4  
          • Quicksort Algorithm (sorting list of integers recursively by decomposing the lists, then sorting those lists recursively, and finally combining the results together). Note that behind the scenes we are not actually creating new lists, instead we are mutating the data structure in-place to swap the elements
          • Specification and Rules of Quicksort - Empty list is already sorted, whilst Non-Empty lists are broken into two parts that we can recursively sort and then combine the results into a sorted list. We sort them by creating a 1st list by sorting the tail values (by checking which ones are <= to the head value), then creating a 2nd list by sorting the tail values (which are > the head value), and appending the resulting two lists on either side of the head value that is injected in the middle
          • Implementation of Quicksort (simple illustration of Quicksort translated using recursion)
    qsort               :: [Int] -> [Int]
    qsort []            = [] (case of empty list, it is already sorted)
    qsort (x:xs)        = 
      qsort smaller ++ [x] ++ qsort larger 
        smaller = [a | a <- xs, a <= x]
        larger  = [b | b <- xs, b > x] (meaning: case where want to sort list x cons xs, create 1st list with all elements <= x, using a List Comprehension, and create a 2nd list with all elements > x, , also using a List Comprehension, then sort both of the two lists and inject x in the middle of them)

    -- Execution (where abbreviate qsort as q)

          q [3,2,4,1,5]


    q [2,1] ++ [3] ++ q [4,5] (recursively sort the smaller and larger lists, and inject the head of the original list in the middle)   

          ↓                  ↓                 ↓  

          ↓            not shown    not shown

    q [1] ++ [2] ++ q [] (inject head in middle, split the remaining list which is just 1, where <= is just 1, and > is nil) 


         [1]    [2]    []
        • Example 5
          • Replicate (produce a list with 'n' identical elements)
    replicate :: Int -> a -> [a] { meaning: Function that takes an Integer (which is the 'n'), it then takes a value 'a', and it should return a List of 'n' copies of that value 'a') 

    (Hint: We will not recurse over 'a', but we need to build a List, so we need to define this recursively over the structure of this Integer, where there are two cases as usual, 1st case of n = 0, if replicate an element zero times we get the empty list, 2nd case is replicating the value 'n' times, we first replicate it (n-1) times, so we get a List of (n-1) * a, and then we cons 'a' on top)
        • Example 6
          • !! (select the nth element of a List)
    (!!) :: [a] -> Int -> a meaning: take a List (i.e. [a]) and a number (i.e. Int), and return the element in that List in that position. Note that in Haskell, Lists do not have constant time access, which becomes clear when we run this Function }

    (Hint: We could use existing Functions to achieve this, like  take or  drop but the Goal in this example is to try and define it using Recursion. Here we have two Recursive Functions (i.e. the List (i.e. [a], and the Integer (i.e. Int)), we will define this by recursing over both. For the 1st case, if we want the zero'ed element of the List (x cons xs) (the head) when given an Int ('n') value of 0, then it should give the element at index 0. For the case of an empty List, we should note that if we want to index the nth element of the empty list, it will give an error (so we'll use this as the 3rd case). So for the 2nd case that Int is NOT zero, and the List [a] is NOT empty, if Int is zero, we are done, whereas is List [a] is empty, and Int is NOT zero then we get an error. What we do then is if List [a] is 'x:xs', and Int is 'n', then we'll take the index ('a') of the tail of the List (which is index 'n-1'). Care required when dealing with base cases.)

        • Example 7
          • elem (decide if a given value 'a' is an element of a List [a])
    elem :: Eq a => a -> [a] -> Bool Note: The Type of 'a' must support Equality (we can only search for a value in the List, if the Types in the List support Equality), which is why we use the Constraint => to ensure 'a' is a member of the Type Class of 'Eq a' }

    (Hint: We could cheat and use existing Functions (without using recursion) to achieve this, like  filter or List Comprehension but Goal in this example is to try and define it using Recursion. The obvious candidate to perform the recursion is the List [a]. So, given an element 'a', in the empty list, the result is False (as the element is not in the list). Now, if we check for equality of given element 'a' in the given non-empty list x:xs until we find a match, then we need to check if the head of the List is equal to the element value that we are looking up, and if it is then we return True, otherwise, we just search for that element 'a' in the tail of the List recursively until the tail of the List is empty, which is when we'll have hit the base case and we are done)

        • Example 8
          • Recursive Function over Lists (Init similar to 'tail' but takes all the initial elements except for the last value at the end of the list)
    init                :: [a] -> [a]
    init []             = [] 
    init (x : xs)       = x : init xs

    -- Execution

    init [1,2,3]
    = { applying init }
    1 : init [2,3]
    = { applying init }
    1 : 2 : init [3]
    = { applying init }
    1 : 2 : []
    = { list notation }

        • Example 9
          • Recursive Function over Lists (and is a Function that decides if all the values in a List are True)
          • Note: use import Prelude hiding ( and ) and possibly even import Data.List hiding ( and ) to prevent ambiguity in evaluation
    and                 :: [Bool] -> Bool
    and []              = True
    and (b : bs)        = b && and xs

    -- Execution

      and :: [Bool] -> Bool
      and [] = True

      and (b : bs) = b && and bs

    -- OR 

      and [] = True
      and (b : bs)
        | b = and bs
        | otherwise = False

    -- OR 

      and [] = True
      and (b : bs)
        | b == False = False
        | otherwise = and bs

    -- OR 

      and [] = True
      and (b : bs) = and bs && b

    • Higher-Ordered Functions
      • Dfn: Functions that take Functions as Arg (i.e. indicated by explicit parentheses as Parentheses for Function Types Associate from Left to Right (a -> a)) and returns Function as result (on the Right the use of Parentheses is Optional). Note: In the example below, with Optional Parentheses applied the first line would read: twice :: (a -> a) -> (a -> a)
      • Benefits: 
        1. DRY Modular Code with Lazy Evaluation Encodes the concept of DRY into the programming language itself, as Higher-Order Functions overcome repetitive code by abstracting repetitive patterns (common programming idioms) into the higher-order functions, which take different arguments that cater for the differences between common uses of the common pattern. Lazy Evaluation of the arguments is important (evaluate only when they are actually being needed rather than in advance), otherwise they may be evaluated prematurely.
        2. Embedded Domain-Specific Languages (Collections of Higher-Order Functions) may be defined, for which associated APIs may be created and exposed
        3. Algebraic Properties of the Higher-Order Functions may be reused to perform reasoning about programs. The properties hold regardless of the Argument being passed in
      • Example #1: Higher-Ordered Function named 'twice'
    twice      :: (a -> a) -> a -> a (meaning: takes a Function (a -> a) and takes an argument of Type 'a' (i.e. 'x') (on LHS) and returns value of Type 'a' f x, which itself is the argument to the second Function (on RHS), which when applied returns a value of Type 'a')
    twice f x  = f (f x)             

      • Example #2: Higher-Ordered Function named 'map' takes a Function (1st Arg), and then takes a List (2nd Arg). It then applies the Function to all elements in the List. 
        • Type Signature of the Higher-Ordered Function 'map'
    map        :: (a -> b) -> [a] -> [b] (meaning: takes a Function of Type 'a' to Type 'b', and takes a List with values of Type 'a', and then applies the Function to transform every element in the input List to get an output List with values of Type 'b')
    > map (+1) [1,3,5,7] { meaning: map the Sectioned plus Function (which is implicitly defined as lambda x x+1) over the List (which simply adds 1 to every element in the List) } 

        • Define Higher-Order Function 'map' with List Comprehensions (Alternative Definition #1)

    map f xs    :: [f x | x <- xs] (meaning: map Function applies Function 'f' to every element in the List 'xs'. Iteratively take each element 'x' out of the List 'xs' and apply the Function 'f' to it in order to return the List)

        • Define Higher-Order Function 'map' using Recursion (Alternative Definition #2) (used for the Purpose of Proofs)
          • Note: Recursive Definition is Inductive over the Structure of the List, where here we either have an Empty List, or we have a List built using x:xs
          • Benefit: Prefer to use Recursive Definition as other Recursively Defined Higher-Order Functions share a common pattern, which we may abstract (i.e. we may then abstract the Higher-Ordered Function 'map' easily into a Super Higher-Ordered Function 'fold')
    map f []      = []  (meaning: 'map' of Empty List gives an Empty List)
    map f (x:xs)  = f x : map f xs (meaning: 'map' of the List x:xs involves recursively mapping the Function 'f' over the rest (Tail) of the List 'xs', and then we concatenate the Function 'f' of argument 'x' (Head) to the front)

      • Example #3: Higher-Ordered Function named 'filter' is a Library Function that selects every element from a List that satisfies the Predicate
        • Type Signature of the Higher-Ordered Function 'filter'
    filter :: (a -> Bool) -> [a] -> [a] { meaning: Function 'filter' takes a Predicate (a Function from 'a' to Bool (a -> Bool)), then takes a List and returns another List where all the elements that do not satisfy the Predicate have been removed }
    > filter even [1..10] 

        • Define Higher-Order Function 'filter' with List Comprehensions (Alternative Definition #1)

    filter p xs = [x | x <- xs, p x] (meaning: take every element 'x'  out of the List 'xs', and if the Function 'p' of argument 'x' returns True, then insert 'x' into the output List)
        • Define Higher-Order Function 'filter' using Recursion (Alternative Definition #2) (used for the Purpose of Proofs)
          • Benefit: Prefer to use Recursive Definition as other Recursively Defined Higher-Order Functions share a common pattern, which we may abstract (i.e. we may then abstract a combination of the Higher-Ordered Function 'map' and 'filter' easily into a Super Higher-Ordered Function 'foldr', which will define 'map', 'filter', and any other function over a list)
    filter p []     = []  (meaning: 'filter' of Empty List gives an Empty List)
    filter p (x:xs)
      | p x         = x : filter p xs
      | otherwise   = filter p xs
    (meaning: filter out all the values for which 'p' does not hold True across the List x:xs, which involves two cases: Firstly if Function 'p' of argument 'x' is True then we filter the rest of the List recursively, and then concatenate 'x' on top, or Otherwise, we just forget about 'x' and filter the rest of the List recursively)

    • Super Higher-Ordered Function 'foldr' (similar to Visitor Pattern)
      • Dfn: Function that captures the essence of recursion simply over the structure of a List, folding from the Right (it starts with empty List [] and folds from there onward)
      • Benefits: 
        • Properties of Functions defined using foldr may be proved using algebraic properties of foldr (i.e. fusion and banana split rule), for using the properties to calculate more efficient programs
        • Optimising programs is simpler using foldr instead of explicit recursion
      • Fusion Dfn: Given two Functions, with one of them using foldr to traverse one List and return another List, then if we perform another foldr on the result, we can fuse the results together (so the intermediate List is never constructed), therefore optimising a program with this higher-order pattern (WWTTFFF?)
      • Note: 'foldr' and 'foldl' captures a pattern that may be used to defines 'map', 'filter', and any other function over a list
      • Visitor Pattern Dfn: Visits a List and for every Constructor it applies a Function, and this Function is passed as a parameter to foldr
      • Example: Recursion over a List
    f []     = v  (meaning: maps empty List to value 'v')
    f (x:xs) = x ⨁   f xs (meaning: f applied to x cons xs, recursively calls f on xs, it maps non-empty List to Function Plus  , and applies Function Plus to to the head of the list 'x', and to the recursion call of the function f to its tail, it does this by taking the result of the recursive invocation and combines it with the value of the head on top, by using the Function Plus. Note that the function f traverses the List and replaces the empty List with 'v', and replaces occurrences of cons with plus. f is a homomorphism over the List, and respects the List structure)

      • Define (recursively) the Higher-Order Library Function foldr (fold right) (with a arguments f and v)
        • Simple Alternative: Alternatively think of foldr non-recursively in that it simply replaces cons (:) in a List by a given Function (i.e. instance of ⨁ ) that we represent as operator 'f', and replacing an Empty List by a given value (i.e. instance of 'v')
    foldr :: (a -> b -> b) -> b -> [a] -> b { meaning: takes 1st parameter as an operation (a -> b -> b) that replaces cons (:), take the 2nd parameter to replace the empty list with, and then we get a Function of a List of 'a' to b [a] -> b }
    foldr f v []     = v
    foldr f v (x:xs) = f x (foldr f v xs)  { meaning: recursive invocation of foldr of f and v parameters, and then call f on x, where f is used to represent Function Plus }
      • Example #1:
    sum []     = 0 { meaning: where instantiate v, replacing v = 0 }
    sum (x:xs) = x + sum xs  { meaning: where instantiate Plus Fn, replacing  = + } 

    product []     = 1 { meaning: replacing  v = 1 }
    product (x:xs) = x * product xs  { meaning: replacing  = * } 

    add []     = True { meaning: replacing v = True }
    add (x:xs) = x && and xs  { meaning: replacing   = && } 

      • Example #2 - Define recursive pattern (i.e. Sum, Product, Add) as Instances in terms of the Higher-Order Library Function foldr (fold right) (with a arguments v and )
    sum         = foldr (+) 0
    product     = foldr (*) 1
    or          = foldr (||) False
    and         = foldr (&&) True

      • Example #3 foldr Implementation of Sum:
    -- Execution

    sum [1,2,3]  { meaning: expands into below when executing }


    foldr (+) 0 [1,2,3] { meaning: where  [1,2,3] is Haskell shorthand for Lists and means 1 cons 2 cons 3 cons Empty List (1:(2:(3:[]))) } 
    foldr (+) 0 (1:(2:(3:[]))) { meaning: replace all occurrences of cons (:) with (+), and replace all occurrences of Empty List [] with } 
    1+(2+(3+0)) { note: structure of List is maintained, as foldr is homomorphic over Lists, it simply replaces the Constructors by another Function}

      • Example #4 foldr Implementation of Product:
    -- Execution

    product [1,2,3]  


    foldr (*) 1 [1,2,3] { meaning: where  product is defined as (*) 1 } 
    foldr (*) 1 (1:(2:(3:[]))) { meaning: replace all occurrences of cons (:) with (*), and replace all occurrences of Empty List [] with } 

      • Example #5 Recall Definition of Length Function (Previously Shown):

    length        :: [a] -> Int
    length []     = 0 (case where empty list)
    length (_:xs) = 1 + length xs meaning: if the list is non-empty then we do not care what the first element is (as we won't use it on the right side), we simply compute the length of the rest of the list (i.e. the tail xs) and add 1 to it }

    -- Execution

    length [1,2,3]
    = 1 + length [2,3] 
    = 1 + (1 + length [3]) (unfold)
    = 1 + (1 + (1 + length [])) (unfold)
    = 1 + (1 + (1 + 0)) (unfold and add them up)
    = 3

        • Length is an Instance of Higher-Order Library Function foldr 
          • Note: Replaces cons (:) with the Function that throws away the first argument 'x', and then adds 1 to the recursive invocation of foldr on the List 
      • Example #5 foldr Implementation of Length:
    -- Execution

    length [1,2,3]  


    length (1:(2:(3:[]))) { meaning: replaces cons (:) with λ_ n -> 1+n (the Function that throws away the first argument so it's not written, and then takes a second argument and adds 1 to it), and  [] with 0 } 

    length = foldr (λ_ n -> 1+n) 0 { meaning: based on the above, length may be defined in terms of foldr this way }

      • Example #6 Recall Definition of Reverse Function (Previously Shown):

    reverse []     = []
    reverse (x:xs) = reverse xs ++ [x] meaning: reverse of xs appended with the singleton List of x.  }

        • Reverse is an Instance of Higher-Order Library Function foldr
      • Example #6 foldr Implementation of Length:

    -- Execution

    reverse [1,2,3]


    reverse (1:(2:(3:[]))) { meaning: replaces cons (:) with λx xs -> xs ++ [x] (Function x xs that goes to xs cons x) and [ ] with [ ] } 
    (([] ++ [3]) ++ [2]) ++ [1]

    reverse = foldr (λx xs -> xs ++ [x]) [] { meaning: based on the above, length may be defined in terms of foldr this way }

      • Note: 
        • Append Function  (++) has a more compact definition in pointfree style  (++ ys) = foldr (:) ys { meaning: replaces cons (:) with (:) and [ ] with ys} 
      • Church Numerals
        • Dfn: Abstract over concrete representation of a number using Functions and Function Application
        • Type of Church Numeral 
    type Church = (a -> a) -> a -> a { meaning: Function that takes another Function (Successor Function) as its input argument, then takes another argument (the zero number), and returns the Church representation of the number. The Type tells us that they are Polymorphic (may instantiated the numerals to represent any concrete representation i.e. can be an Integer, String, etc) }

        • Note: Ideally a number n is defined as n applications of the Successor Function over the zero number a
        • Examples:
    -- Implementation 

    zero = \s z -> z meaning: Zero Representation is a Function that takes input parameters 's' and 'z', and returns only the zero number  }

    one = \s z -> s z meaning: One Representation is a Function that takes input parameters 's' and 'z', and returns the Successor Function applied only once  }

    two = \s z -> s (s z) meaning: Two Representation is a Function that takes input parameters 's' and 'z', and returns the Successor Function applied twice  }

        = \s z -> (s . s) z meaning: Two Representation refactored using the Composition Operator to achieve s . s  }

        = \s   -> s . s meaning: Two Representation refactored further using Eta Reduction from Lambda Calculus where we can remove the z argument }

        • Example #1: Instantiate Church Numerals (polymorphic) to Concrete Representation (Integer)
    type Church = (a -> a) -> a -> a 
    c2i x = x (+1) 0 meaning: Church to Int Function that takes an input argument that is a church representation of a number (a Function), to which a Successor Function will be applied, comprising a (+1) and 0

    -- Implementation
    c2i two = (\s z -> s (s z)) (+1) 0 meaning: First argument is the Two Representationto which we apply (+1) and 0 }
            = (+1) ((+1) 0) meaning: Substitute and apply (+1) to 0 for the first time }
            = (+1) 1 = 2 meaning: Apply (+1) to that which is enclosed, and get result  }

        • Example #2Instantiate Church Numerals to other Things like Strings (other than Integers)
    type Church = (a -> a) -> a -> a
    c2i x = x ('*':) ""  
      meaning: Successor Function appends to the Head of the String (a star) *, and the Zero Operator is the Empty String "". Noting that: -- "*****" = 5  }
    c2i two = (\s z -> s (s z)) ('*':) ""  meaning: Apply to the Two Representation, which we previously established has a value of 2 }
            = ('*':) ('*':"") meaning: (Start cons ) : ( Star cons : Empty String ) }
            = '*':"x" = "**meaning: evaluates to Two Representation }

        • Deriving Implementation of Addition (Define Operations over Concrete Representation)
    -- Given Two Definitions
    x' = c2i x meaning: x prime equals Church to Int (version is an Integer) of x, where x is a Church Numeral }
    y' = c2i y meaning: y prime equals Church to Int (version is an Integer) of y, where y is a Church Numeral }

    x' + y' = c2i x    + c2i y
            = x (+1) 0 + c2i y meaning: expand with our original definition of Church to Int. This applies to the Successor Function (+1) and the zero number 0 } 

            = x (+1) 0 + c2i y { Note: reflecting on same result, Focus on the structure on the Right Hand side }
            = x (+1) (c2i y) Note: Assuming c2i Function will take another parameter 'z' we can substitute the zero to a param defined by the User, and move the c2i Function inside and use it as a Base Number of the X Representation (so we can build X from an Integer Representation of Y itself, instead of from Zero }
            = x (+1) (y (+1) 0) { meaning: expand with same definition of c2i }
            = x (+1) (y (+1) 0Note: reflecting on same result, Focus on the structure on the Right Hand side, where we have Two Instances of the (+1) Function and one Zero number }
    -- Abstract the (+1) and 0 instances using Lambda Calculus (Beta Expansion) and create a Function from that
            = (\s z -> x s (y s z)) (+1) 0  meaning: (+1) and Successor are highlighted. We have expanded the Expression into a Function that is then applied to (+1) 0 }
            = (\s z -> x s (y s z)) (+1) 0  Note: reflecting on the same result, we will grab the Lambda component and give it a Name of "ADD" and parameterize it over x and y (the only free variables in this definition) } 
            = (add x y) (+1) 0  Note: ref
            = c2i (add x y { meaning: this is just a Representation of the Church to Integer body of the Function that was previously defined, so we simply Substitute and arrive at our original definition since c2i x = x (+1) 0 }

    -- Goal of Derivation
    x' + y' = c2i (add x y) meaning: Integer addition of x and y equals Church to Int of a Function 'add x y' that we will define over Church Numerals }

        • Definition of Addition (between Two Church Numerals)
    add x y = \s z -> x s (y s z) meaning: Function (which is a Church Numeral) that builds 'x' with the Successor Function, but starting from the Final Representation of 'y', which gives the Addition of 'x' and 'y' }

        • Deriving Implementation of Multiplication
          • Derivation with Integers
    -- Example
    2 x 3 = 2 + 2 + 2 = 6
          • Derivation with Functions
            • Functions cannot just be Added together, but they can be Composed together

    two   = \s -> s . s meaning: Two Representation }
    three = \f ->   f    .    f    .    f  meaning: Three Representation }
    six   = \s -> (s . s) . (s . s) . (s . s) meaning: Six Representation that Composes the definition of Two Representation (which is defined above) three times, by Substituting 's' for the definition of the Two Representation, and where the Six Representation is just the Composition of the Successor Function six times }

          • Definition of Multiplication (between Two Church Numerals)
    mult x y = \s z -> x (y s) z meaning: Function (which is a Church Numeral) that takes a Successor Function and a Zero number. We apply a Super Successor Function to 's', which will contain 'y' exemplars of the Successor Function }
             = \s z -> x . y meaning: Lambda Calculus simplifies to the Composition of 'x' and 'y' }

            • Note: Exponentiation used in the exercises

    • Functional Parsers & Monads (Parse Strings of Chars into Expressions)
      • Dfn: Parser is program that analyses Unstructured text to determine and extract the syntactic Structure from the text. Parser Type is a Monad
      • Monad Dfn: Monad is a mathematical structure. It is just a Type used for modelling different computations and has certain operations on its Type.
      • Usage: Pre-process Inputs i.e. 
        • GHCi parses Haskell programs
        • Unix parses Shell scripts
        • Explorer parses HTML
      • Parser Type: Parser is viewed as a Function in functional languages like Haskell
      • Example:                                     +
      • 2 * 4 + 4          { meaning:         /    \
                                                         *       4
                                                       /   \
                                                      2    3
    type Parser = String -> Tree  { meaning: Function takes String and returns Tree }

      • Important Notes:
        • Unused Input from the String that is not required may also be returned 
    type Parser = String -> (Tree,String) { meaning: Function takes a String and returns a Pair containing a Tree, plus the Remainder of the String }
        • List of Results (i.e. [...]) is used as a Generalisation for the Output that may be of any Type { other languages use Maybe Type (either Nothing or a Single Value), instead of a List (either 0, 1, or more values) }, since we may be able to parse the String input into a Tree in many ways or in no way at all
          • No Parse { Empty List }
          • Ambiguous { Multiple Pairs in List }
          • Non-Ambiguous Grammar { List with Single Element OR Empty List } 
    type Parser = String -> [(Tree,String)] { meaning: Function takes a String and returns a List of Pairs, each containing a Tree, plus the Remainder of the String (representing all possible ways we can Parse the String) }

    type Parser a = String -> [(a,String)] { meaning: For Simplicity, here we only consider Parsers that fail and return an Empty List of results, or succeed and return a Singleton List (i.e. only consider parsers that fail with an empty value or succeed with a single value). Parameterize the Type Parser over 'a', as we don't care whether a Tree is returned as 'a'. Final Type of Parser takes a String and returns List of Pairs of 'a' (value we want to extract from the String) plus the remainder of the String that we don't use. Note: We are not going to use the Maybe Type }

      • Simple Parsers
        • Example #1: 'Item' Parser Function that takes the input (Parse a Single Character by taking a String) and returns either an Empty List or a Singleton List comprising of a Pair of a Char and the Remainder of the String
        • Note #1: case mechanism allows for Pattern Matching in Haskell 
        • Note #2: Instead of using Pattern Matching on the LHS and defining 'item' using two clauses, we choose to use the syntactic construct of a Lambda Expression with a Case Expression that has the Pattern Matching
    item :: Parser Char
    item = λinp -> case inp of { meaning: Lambda Expression used with a Case Expression that has the Pattern Matching }
                    []     -> [] { meaning: Empty input String prevents us from extracting a Char from the String so return the Empty List }
                    (x:xs) -> [(x,xs)] { meaning:  Given a List of form x cons xs, then take the Pair of the first Char and the Remainder of the String to return a Singleton List of the result }

          • GHC Testing (verify that definition of 'item' Parser works as expected)
    % ghci Parsing
    > parse item "" { meaning: Try to parse Empty String }
    > parse item "abc" { meaning: Try to parse first value from String "abc" }
        • Example #2: 'Failure' Parser Function that always Fails for any input, and returns an Empty List
    failure :: Parser a
    failure = λinp -> [] { meaning: always returns an Empty List }

          • GHC Testing
    > parse failure "" { meaning: Try to parse Empty String }
        • Example #3: 'Succeeds/Return' Parser Function that always Succeeds, and returns the value 'v' without doing anything to the input before returning it
    return :: a -> Parser a { meaning: we need to give the Parser Function that always succeeds an input value, with which it can succeed }
    return v = λinp -> [(v,inp)] { meaning: the Parser that always succeeds takes a value 'v', it takes the input, but it doesn't do anything with the input before it gets returned, and it returns the value 'v' with the input unchanged in a Singleton List }
          • GHC Testing
    retu> parse (return 1) "abc" { meaning: Try the parser that always succeeds with the number 1 applied to the String "abc", which results in success by returning the value 1 and leaving the input unchanged }

      • More Complex Parsers
        • Note #1: Use of the Choice  +++ operator (aka "OR ELSE") 
        • Example #1: 'Combine p +++ qParser Function that takes Two Parsers and combines the results by 
          • 1) Trying the first Parser, and if it Succeeds we go and return the output OR otherwise if it Fails then we:
          • 2) Try the second Parser
    (+++) :: Parser a -> Parser a -> Parser a { meaning: First Parser -> Second Parser -> result }
    p +++ q = λinp -> case p inp of { meaning: defined by taking Two Parsers 'p' and 'q', then define a Parser Function that takes an input λinp d, and attempts to parse the input using the First Parser. If doing so fails then return the Empty List and then try the Second Parser on the input. Otherwise if the First Parser succeeds then it will succeed with a Singleton List of a Value 'v' and the Remainder 'out' of the input, and we just return that same value }
                       []        -> parse q inp
                       [(v,out)] -> [(v,out)] 
        • Example #2: 'String Parser ParseParser Function that takes One Parser and One String and applies that Parser to the String.
    parse :: Parser a -> String -> [(a,String)] { meaning: takes a Parser and a String, and applies the Parser to the String to result in a List of 'a' and String }
    parse p inp = p inp { meaning: simply applies the Parser to the input  }

          • GHC Testing (Mixture)
    > parse (item +++ return 'd') "abc" { meaning: Try to parse a 'item' and if that fails return 'd' (using the parser that always succeeds). We will apply this to "abc" }
    [('a',"bc")] { meaning: Since we can get the First Element of "abc" that will succeed we just get result [('a', "bc")]

    > parse (failure +++ return 'd') "abc" { meaning: Try the parse that always results in Failure (which will fail), and if it fails we try the parser that always Succeeds (which will succeed without consuming any input, but just returning 'd') }
    [('d',"bc")] { meaning: Since we can get the First Element of "abc" that will succeed we just get result [('a', "bc")]

      • Parsing Library
      • TODO Monadic Nature of Functional Parsers (Step-by-step guide to Building Functional Parsers with Monadic Approach)
      • TODO IO Monad (Monadic IO, Concurrency, Exceptions, Foreign Language Calls)
      • DONE Addendum on Monads (Programming with Effects) includes topics:
        • Pure Languages { Function as Mapping Args to Results, Lazy Evaluation benefit }
        • Impure Languages { Effects (Exceptions, Assignments), Efficient Shorter programs }
        • Monads { Approach to Integrating the Pure and Impure language camps, Abstract common Programming Patterns as a Definition }
        • Maybe Type { Safe version of code to Deal explicitly (i.e. with division by zero so program does not produce error) }
        • Monadic Fold { i.e. where a Case analysis is performed on the result of an Eval
        • Auxiliary Function { i.e. Apply ... Where }
        • Nested Tuples { complex code may be caused by use of nested `Seqn` 
        • "THEN" (>>=) (aka BIND) { Abstracting a pattern gives rise to new sequencing operator >>= that replaces Case Analysis with Pattern Matching by allowing the result of the first Arg to be made directly available for processing by the second Arg (second Arg is bound to result of the first Arg) instead of being paired up with the second result for processing later on (where the pattern is that of performing Case Analysis on value of Maybe Type, mapping Nothing to itself, and Just x to some result depending upon x). operator >>= integrates sequencing of values of type Maybe with the processing of their result values. (>>=) is equivalent to Apply with the order of its Args swapped.  (>>=) saves programmers from worrying about dealing with possible failures (i.e. returning Nothing) from any component expressions as it automatically handles them, as the overall expression only succeeds if all of the sequences succeed }
    -- example structure of Expression built using the >>= operator
    eval x >>= (\n ->
    eval y >>= (\m ->
    safediv n m)) { meaning: evaluate each expression x, y, etc in turn, and combine their result values n, m, etc, by applying the function f, where the >>= definition ensures the overall expression only succeeds if each component sequence succeeds, so the programmer doesn't have to worry about dealing with possible failures }
        • Haskell Special Sequencing "DO" 
          Notation for Expressions instead of using   (>>=) that may be used with any Type that forms a Monad (not just those of the Maybe Type), which is a concept from the mathematics Category Theory
    do n <- eval x
       m <- eval y
       safediv n m
        • Monads are simply a parameterised Type m together with Two Functions (of Types as follows) that must satisfy simple Properties of Monadic Law:
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b
    { meaning: where 
    • Type m is taken to by the parameterised Type Maybe
    • return is taken as the First Function Just :: a -> Maybe a
    • >>= is as defined (see link for details)
    • then the result is the Maybe Monad (see link for details) }
        • Monad Laws (Properties that apply to Functions return and >>= )
    -- Properties #1 & #2 (Link between return and >>=) (where the Second Arg to >>= involves a Modulo Binding Operation whereby 'return' is the left and right identity for >>=)

    return x >>= f =  f x (1) { meaning: if we return Value 'x' and feed it into Function 'f' it should give same result as simply applying 'f' to 'x' }
    mx >>= return  =  mx          (2) { meaning: if feed results of computation 'mx' into Function 'return' it should give same result as performing just 'mx' }

    -- Properties #3 (Link between >>= and itself) (where expresses with Modulo Binding Operation that >>= is associative)

      (mx >>= f) >>= g
    = (3)
      mx >>= (\x -> (f x >>= g))

          • Example: Utility of Monad Laws to Prove a Property of liftM Function (in that it distributes over the composition operator for Functions)
    -- Generalise distribution property of Map from Lists to an Arbitrary Monad 
    liftM (f . g)  =  liftM f . liftM g

    -- Verify above equation by rewriting definition of liftM using >>=
       liftM f mx  =  mx >>= \x -> return (f x)

    -- Distribution property can be verified as:
         (liftM f . liftM g) mx
       =    applying .
         liftM f (liftM g mx)
       =    applying the second liftM
         liftM f (mx >>= \x -> return (g x))
       =    applying liftM 
         (mx >>= \x -> return (g x)) >>= \y -> return (f y)
       =    equation (3)
         mx >>= (\z -> (return (g z) >>= \y -> return (f y)))
       =    equation (1)
         mx >>= (\z -> return (f (g z)))
       =    unapplying . 
         mx >>= (\z -> return ((f . g) z)))
       =    unapplying liftM
         liftM (f . g) mx
        • Maybe Monad Dfn { simple model of computations that can fail, where a value of Type Maybe 'a' is either Nothing (i.e. Failure), or the form Just 'x' for 'x' of Type 'a' (i.e. Success) }
        • Monads captured as a New Class Declaration where a Haskell Class is a collection of Types that support certain Overloaded functions, where each Type to be an instance of the Class they must support the operators of the specified types, and where Default definitions may already been included for each operator for ease of declaring instances of the class

    class Monad m where

          return :: a -> m a

          (>>=)  :: m a -> (a -> m b) -> m b
    { meaning: where Monad is a parameterised Type m that supports return and >>= Functions of the specified Types }
          • Example: Converting Maybe into a Monadic Type 
          • Note: because of this declaration, the "DO" 
            Notation may be used to Sequence Maybe values, and Haskell supports this notation with any Monadic Type)
    instance Monad Maybe where
       -- return      :: a -> Maybe a
       return x       = Just x
       -- (>>=)       :: Maybe a -> (a ->  Maybe b) -> Maybe b
       Nothing  >>= _ =  Nothing
       (Just x) >>= f =  f x
        • List Monads { Generalises the notation of Maybe Monads by permitting multiple results in case of Success, where value of [a] is either the empty list [] (i.e. Failure) or has non-empty list form [x1,x2,...,xn]
          for some 'x' of Type 'a' (i.e. Success). 
          • Example #1: Converting List into a Monadic Type
    instance Monad [] where { meaning: [] denotes List Type [a] without a parameter }
    -- return :: a -> [a] return x = [x]
    { meaning: return converts value 'x' into Success result containing that value 'x' } -- (>>=) :: [a] -> (a -> [b]) -> [b] { meaning: (>>=) sequences computations that may produce multiple results } xs >>= f = concat (map f xs) { meaning: xs >> f applies function f to each of the results in the List xs to give nested List of results, which is then concatenated to give single List of results }
          • Example #2: List Monad Function that returns all ways to Pair elements from Two Lists using the "DO" Notation (see link for details)
          • Note: "DO" Notation and List Comprehension Notation are both Short-hand Notation for repeated use of the "THEN" (>>=) operator for Lists
    -- "DO" NOTATION
    pairs     :: [a] -> [b] -> [(a,b)]
    pairs xs ys =  do x <- xs
                      y <- ys
                      return (x,y)
    { meaning: consider each possible value 'x' from the List 'xs' and each value 'y' from the List 'ys' and return the Pair (x,y) }

    pairs xs ys = [(x,y) | x <- xs, y <- ys]

        • State Monad { Functions that manipulate a kind of State that are represented with a Type whose internal details aren't important }
          • Note: ST can take Argument Values by means of exploiting Currying (i.e. an ST that takes a Char and returns an Integer has Type Char -> ST Int, which abbreviates Curried Function Type Char -> State -> (Int, State)

    type State = ... 

    type ST = State -> State { meaning:  State Transformer (ST) is most basic form of Function on Type 'State', takes current State as Arg and produces modified State as result, which reflects any Side Effects performed on the Function }

    type ST a = State -> (a, State) { meaning:  Generalised ST that both returns a result Value, and Updates the State (e.g. returning the current value of function that increments a counter) }

          • Example: Converting ST into a Monadic Type 
    instance Monad ST where
    -- return :: a -> ST a return x = \s -> (x,s) { meaning:  return converts a Value into a ST that simply returns that Value without modifying the State }
    -- (>>=) :: ST a -> (a -> ST b) -> ST b { meaning:  (>>=) sequences ST's } st >>= f = \s -> let (x,s') = st s in f x s' { meaning:  st >>= f applies First ST to initial State s and then applies the Function f to the resulting Value x to give a Second ST (f x), that is then applied to modified State s' to give final result. Note that in this definition the second Arg s is shunted to body of definition using a Lambda Abstraction \s (to clearly indicate that return is a Function taking Single Arg a and returning an ST a -> ST a }

    Depicted as (extract from

    ^ +-------+ x +-------+ | s | | -----> | | ---' -----> | st | | f | | | -----> | | -----> +-------+ s' +-------+

        • Data Mechanism { Used with "dummy" Constructor "S" to Redefine and make ST an Instance of the Class of Monadic Types, as in Haskell those Types defined using the "Type" Mechanism cannot be made into Instances of Classes }
        • Note: Avoid runtime overhead of manipulating the "dummy" Constructor "S" by defining ST using the Newtype Mechanism of Haskell instead of the Data Mechanism
          • Example: Binary Tree (see link)
    data ST a = S (State -> (a, State))


    apply        :: ST a -> State -> (a,State)

    apply (S f) x = f x


    instance Monad ST where

       -- return :: a -> ST a

       return x   = S (\s -> (x,s))

       -- (>>=)  :: ST a -> (a -> ST b) -> ST b

       st >>= f   = S (\s -> let (x,s') = apply st s in apply (f x) s')

        • IO Monad { Interactive Programs in Haskell are written with Type IO 'a' of "actions" that return a result of Type 'a', and may perform input/output }
          • Note: Primitives are provided for building Values of this Type including:

    return  :: a -> IO a

    (>>=)   :: IO a -> (a -> IO b) -> IO b { meaning:  (>>=) being used means the IO is Monadic, so the "DO" Notation may be used to write Interactive Programs }

    getChar :: IO Char

    putChar :: Char -> IO ()

          • Example: Action that Reads String of Chars from Keyboard Definition
    getLine :: IO String

    getLine =  do x <- getChar

                  if x == '\n' then

                     return []


                     do xs <- getLine

                        return (x:xs)

          • Note: IO Monad viewed as special case of State Monad where Internal State represents the "State of the World"
    type World = ...

    type IO a  = World -> (a,World) { meaning:  (>>=) bAction viewed as a Function taking Current State of World as Arg and producing a Value of Modified World as result and reflects any input/output performed }

        • Derivative Primitives { Abstracting the notion of a Monad provides the benefit of being able to Define some useful Functions that work in an Arbitrary Monad }
          • Example #1: Generalisation of "Map" Function on Lists 
    liftM :: Monad m => (a -> b) -> m a -> m b liftM f mx = do x <- mx return (f x)
          • Example #2: Generalisation of "Concat" Function on Lists 
    join :: Monad m => m (m a) -> m a join mmx = do mx <- mmx x <- mx return x
          • Example #3: Sequence Two Monadic Expressions (discarding result Value produced by the First)
    (>>) :: Monad m => m a -> m b -> m b { meaning:  (>>) operator is a normal Sequential Composition (written ; in most languages) } mx >> my = do _ <- mx y <- my return y
          • Example #4: Transform List of Monadic Expressions into a Single Expression (that returns a List of results by performing each Arg expression in sequence and collecting their results)
    sequence :: Monad m => [m a] -> m [a] sequence [] = return [] sequence (mx:mxs) = do x <- mx xs <- sequence mxs return (x:xs)

      • Sequencing of Parsers
        • Dfn: Combine a sequence of parsers as a single composite parser using the Do keyword, to sequentially compose them (i.e. First Parser is run, and then when it is Terminated, the Second Parser is run). 
        • Layout Rule: 
          • Parsers must begin in the same column of the text
          • Semi-colons and brackets are allowable
        • Note #1: Use of Monad here results in code that appears sequential
        • Note #2: Use of the Generator <- operator (aka "THEN") causes Intermediate Parsers to return their values to be returned and named. If we do not use this operator, the values returned are discarded
        • Note #3: Value returned by the last parser is the value returned by the sequence as a whole
        • Note #4: If any parser in a sequence of parsers fails, then the sequence as a whole fails and simply returns an Empty List
        • Monad Advantage: Use of do notation may be used with any Monadic Type (usage of 'do' notation is not restricted to the Parser Type)
        • Example #1: .Sequencing Three Parsers of 'items' (only return the First and the Third)
    p :: Parser (Char,Char)
    p = do x <- item { meaning: Try to parse a First 'item' (which is a Function previously defined) and give it the name 'x' }
           item { meaning: Try to parse a Second 'item' (but we don't care about this 'item' so we won't give it a name) }
           y <- item { meaning: Try to parse a Third 'item' and give it a name 'y' }
           return (x,y) { meaning: Return the Pair (x,y) after the above }

          • GHC Testing
    > parse p "abcdef" 
    [(('a','c'),"def")] { meaning: Correctly parses the First and Third 'items' given the quantity of a sequence of inputs that is at least the same quantity as the amount of inputs we define should be parsed }

    > parse p "ab" 
    [] { meaning: Given insufficient inputs (less inputs than there are parsers) or inputs that will fail when attempted to be parsed, this will cause one of the parsers to fail. If any parser in a sequence of parsers fails, then the sequence as a whole fails and simply returns an Empty List }

        • Derived Primitives
          • Example #1: 'Satisfies' Function parses a Char that Satisfies a Predicate (aka a 'conditional')
          • Note #1: Assumes that the Parser used here can perform Sequential Composition
          • Note #2: sat may be used with Predicates from the Haskell Standard Prelude to defined various other parsers (refer to Chapter 8 of Programming in Haskell textbook for details)
    sat :: (Char -> Bool) -> Parse Char  { meaning: 'sat' Function takes a Predicate from Char to Bool (Char -> Bool) and returns a Parser for Chars }
    sat p = do x <- item  { meaning: looking for a Char that Satisfies 'p', involves us doing the Parsing of any 'item', which will return 'x', now if 'p' holds True when we check the predicate 'p' against 'x', then we immediately return 'x' (using the parser named 'return' that we previously defined that always Succeeds), and we don't chase the input, otherwise if the predicate does not hold (i.e. False), then we fail (using the parser named 'failure' that we previously defined that always results in Failure) }
               if p x then
                 return x

          • Example #2: 'isDigit' Function parses a Digit and specific Chars
    digit :: Parser Char
    digit  = sat isDigit  { meaning: use both the previously defined Function 'sat' and the Function  'isDigit' together, to Try to parse a Char and check whether it is a digit, and if this is the case then it will immediately succeed with that digit, else in the case where it isn't then it will immediately fail 

    char :: Char -> Parser Char { meaning: parse a specific Char }
    char x = sat (x ==) { meaning: parse a specific Char 'x', we use Sectioning to create a Predicate, where (x ==) is a Function that expects a Char, and checks whether it is equal to 'x', and then we apply that result to sat  }

    Alternative: Since there is an 'x' on both sides of the equal side, it may also be written in Pointfree Style with Function Composition (Warning: in some cases this may cause the code to become unreadable)

          • Example #3: 'many' Function applies a parser Zero or More times (similar to applying a Regular Expression)
    many :: Parser a -> Parser [a] { meaning: takes a Parser of 'a' and returns a Parser of the List of a }
    many p = many1 p +++ return [] { meaning: defined Recursively whereby many p first tries to parse at least one 'p' with many1 p and if that fails it returns the Empty List [] which is the output of parsing it zero times (note importantly that it is not failing here, so we do not use 'failure) }

          • Example #4: 'many1' Function applies a parser One or More times
    many1 :: Parser a -> Parser [a]
    many1 p = do v <- p { meaning: Try to parse 'p' one or more times by first trying to parse 'p' once, and grabbing the value 'v' of the output }
                 vs <- many p { meaning: many1 is defined in terms of many so we have a very subtle Mutual Recursive Definition, so we can try to parse 'p' zero or more times, and we grab the value 'vs' of the output (which may be the Empty List if it can't parse at least one 'p') }
                 return (v:vs) { meaning:  return 'v' (one times) concatenated with 'vs' (many times) }

          • Example #5: 'string' Function that is defined Recursively and tries to parse a specific String of Chars (where we already know that a String is just a List of Chars). It simply checks if the String is the prefix of our input 
    string       :: String -> Parser String
    string []     = return [] { meaning: Base Case given an Empty List we just return the Empty List, which is the Empty String }
    string (x:xs) = do char x { meaning:  Recursive Case Try to parse the Char (x:xs) by first trying to parse the Char 'x', 
                       string xs { meaning: secondly we try to Recursively parse a String that represents the remainder of the List }
                       return (x:xs) { meaning:  just return the String }

          • Example #6: 'parser' Function is a parser that consumes a List of One or More Digits from a given String (i.e. similar to parsing an actual language) by combining multiple different parser Functions previously defined
    p :: Parser String
    p  = do char '[' { meaning: parse an open brace since we're parsing from the start of a List. Note that we do not use <- as we are not interested in these values }
            d  <- digit { meaning: Try to parse the first One Digit }
            ds <- many (do char ',' digit) { meaning: Try to parse More Digits (because we want a List of One or More Digits) }
            char ']' { meaning: parse an closing brace since we're parsing up to the end of a List }
            return (d:ds) { meaning: concatenate the One Digit 'd' with the More Digits 'ds' }

            • GHC Testing
    > parse p "[1,2,3,4]" { meaning: parse a given List as a String }
    > parse p "[1,2,3,4"  { meaning: parse an incorrect List as a String (i.e. missing closing square bracket) }
    []                    { meaning: get an Error (but in a real parser we would at least indicate the position in the list where the error occurred or try to correct the error so we may recover from errors) }

    -- Update the .lhs file changes I made are on GitHub here
    -- to implement the bind (>>=) method, as it is needed by
    -- the 'sat' method, which is in turn needed by 'char'
    -- (if you don't, you'll get *** Exception: Prelude.undefined
    -- Navigate to folder containing parsing.lhs file
    -- Run GHCi and Load
    ghci parsing.lhs
    -- Alternatively Load it with GHCi
    Prelude> :load Parsing
    -- Test out some examples
    *Parsing> :t item
    *Parsing> let pA = char 'A'
    *Parsing> let pB = char 'B'
    *Parsing> parse pA "B"
    *Parsing> parse pA "A"
    *Parsing> parse (pA +++ pB) "A"
    *Parsing> parse (pA +++ pB) "B"
    *Parsing> parse (pA +++ pB) "AB"
    *Parsing> parse (pA +++ pB) "BAB"
    -- Test out the example parser char 'a' +++ return 'b'
    *Parsing> let test = char 'a' +++ return 'b'

    *Parsing> parse test "yourTestStringHere"

    -- After making changes to the .lhs file, reload it before further tests
    *Parsing> :r
    *Parsing> parse int "-007"

            • GHCi Testing by Alternatively Implementing within Eclipse using .hs file
    -- Update the .hs file in Eclipse changes I made are on GitHub here
    -- to implement the bind (>>=) method
    -- then test that it works correctly with a sample input to see what it returns and without error
    *Parsing> parse (digit) "123"

    • Interactive Programs { 
      • Dfn: Importance for programs to be able to communicate with the outside world using I/O
      • Haskell I/O Evolution: Stream I/O, Continuation Based I/O, and I/O Monad
      • Beginner-I/O (stuff done so far):
        • Batch Programs: 
    Input (i.e. Int, String, Tuple, List) -> [ Batch Program ] -> Outputs (i.e. print on REPL loop of GHC Interpreter)

      • Normal I/O (stuff we want to do):
        • Imperative Program: 
    Input (i.e. Interact with Dependent Keyboard/Screen) -> [ Imperitive Program ] -> Outputs produced and Communicate with Screen (so can get New Inputs at same time)
      • Problem { Haskell programs are Pure Functions (i.e. No Side-Effects)
      • Mathematical Function { Function that gives same Output result when given same Argument (i.e. factorial n, takes n and always gives factorial n) }
      • Common Function in Imperative Programming { i.e. readLine is Not a Mathematical Function because it has Side-Effects as a result of something being there which is not apparent in the Type
        • 1st Run - readLine takes either no args or empty tuple, returns a String
        • 2nd Run - readLine takes same args but returns different String
      • I/O Monads { Solve the Side-Effects that are apparent in Interactive Programs (that interact with the outside world) by expressing in the Type of a Function if it has a Side-Effect (to distinguish Pure Expressions from Impure Actions that may involve Side-Effects), and we incorporate the right balance (its up to the developer) of these Side-Effects into Haskell Programs, as they are useful and make Interactive Programs easier to write. Developers should care about Purity whilst also deciding whether or not to use Side-Effects and to what extent to achieve the ideal balance
      • New Type { Assume we have a new Abstract Type IO a that are the Type of Actions of Type 'a' (we don't care how the IO Monad is defined as long as we have operations defined on them i.e. just like in OOP where we have Classes, and Methods on the Class, but in order to use the Class you don't have to know how the Class is Implemented, you just use the Methods). It denotes an Action that performs Side-Effects and returns a value of Type 'a' as a result. }
      • Statements VS Expressions { so far we have only used Expressions. Imperative Languages have Expressions and Statements, where Statements mostly Communicate via Side-Effects sand where I/O Monads introduce Statements to Haskell (the notation of Actions, which are also Expressions and can be Composed) }
      • Haskell Function that Returns 'void' { in Haskell this is a Function that returns Type IO of Unit }
      • Laziness in Imperative Languages { indicated by a Function that has a Type Unit Arrow something, as this means it's trying to simulate laziness }
          • Example #1: I/O Monad of Char
    IO Char { meaning: a type of Action that performs Side-Effects and returns a Char }
    IO ()   { meaning: IO of Unit (the most Imperative of Imperative Types) Type is a Function that only performs Side-Effects, which are Purely Side-Effecting Actions that returns the Empty Tuple (no real result value) (aka the Type 'void' in other Imperative Languages), and where () is the type of Tuple with no components }
          • Example #2: I/O Monad of getChar
    getChar :: IO Char { meaning: getChar is just something that has a Side-Effect and then returns a Char. It is a Primitive Action Operation on the IO Monad (from the Standard Library), that reads a Char from keyboard, echoes to screen, and returns Char as result value. If it were Strict then it would immediately return the Char, but it isn't, and because Haskell is Lazy it doesn't explicitly indicate that it's deferring evaluation (by use of a unit arrow) }

          • Example #3: I/O Monad of putChar  (this Action writes the Char 'c' to the screen (stdout) and returns no result value)
    putChar :: Char -> IO () { meaning:  takes Char and returns Void (i.e. with Side-Effects) but it doesn't return any useful value) }

          • Example #4: I/O Monad of return  (this Action immediately returns without doing anything)
    return :: a -> IO a { meaning:  takes Value and immediately returns Value (without Side-Effects}

      • Sequencing with I/O Monads (same syntactic structure as used previously with item Parsers)
        • Note: where the "DO" Notation (appears like imperative code) may be translated to a Bind function
    a :: IO (Char, Char) { meaning: define a Function 'a' is of Type I/O Monad and performs the Action of reading two Chars from stdout }
    a = do x <- getChar { meaning: Firstly reads a Char and return it labelled as 'x'
           getChar      { meaning: Secondly reads another a Char (ignores result)
           y <- getChar { meaning: Thirdly reads yet another Char and return it labelled as 'y', then finally returns a Pair of outputs }
           return (x,y)

      • Derived Primitives with I/O Monads
        • Example #1:
    getLine :: IO String { meaning: define a Function 'getLine' is of Type I/O Monad and performs the Action of reading a single String from stdout }
    getLine =  do x <- getChar { meaning: Firstly reads a Char (of Type I/O Char) and returns an output named 'x' (of Type Char)
    t <- I/O t { Note: the Arrow Symbol in the line above is similar to a Generator in List Comprehensions, whereby the Arrow Symbol is used to denote transformation to a different Type (i.e. from Type I/O t to Type t) }
                  if x == '\n' then
                     return [] { meaning: return Empty String if we just read a Char that was a 'New Line' Char \n }
                     do xs <- getLine { meaning: otherwise Recursively continue read the rest of the input (i.e. after the 'New Line' Char) }
                        return (x:xs) { meaning: and concatenate each subsequent remaining Chars that are read to the previous Char that was read immediately prior }

        • Example #2:
    putStr        :: String -> IO () { meaning: take String and write to stdout }
    putStr []     :: return () { meaning: case of Empty String, simply return Unit immediately }
    putStr (x:xs) = do putChar x { meaning: case of a Char 'x' followed by a remainder String 'xs', print the First Char 'x' to the screen
                       putStr xs { meaning: then Recursively print the Remaining String 'xs' to the screen (where 'xs' returns IO of Unit) }

        • Example #3: (combines putString and putChar and afterward prints a New Line to the screen)
    putStrLn      :: String -> IO ()
    putStrLn xs   = do putStr xs
                       putChar '\n'

        • Example #4: { define an Action that Prompts for String entry and displays its length }
          • Note: We mix and match imperative code or I/O code with all Functions defined previously (i.e. Functions over Lists i.e. a String)
    strlen        :: IO () { meaning: imperatively read a String from stdout }
    putStrLn xs   = do putStr "Enter a string: " { meaning: print String to stdout }
                       xs < getLine { meaning: read input entered by User }
                       putStr "The string has " { meaning: print another String to stdout }
                       putStr (show (length xs)) { meaning: use regular List Functions on the String. Note: This line is an Island of Purity (i.e. nice pure functions over Lists) within the Sea of Impurity (i.e. the rest of the code in this example), where the pattern observed is a snippet of Pure code is embedded in context of Impure code that glues the program together }
                       putStrLn " characters" { meaning: imperatively within the I/O Monad write it to stdout }

          • Implementation in GHCi
            • Note: Only the Side-Effects are evaluated. It does not return a useful Value, as it has Type IO of Unit

    > strlen

    Enter a string: abcde
    The string has 5 characters

      • Game (Hangman)!!!!!
        • Spec:
          • Player 1: Secretly enter a word
          • Player 2: Try to guess the word with sequence of guesses
          • Computer: Indicates which guessed letter is match in secret word
          • Game Ends: After finite qty guesses, or correct guess
        • Implementation (Top-down Approach to designing parts of game that are needed as we progress)
          • Note: Haskell has Mutable Variables that require a Special Monad or the I/O Monad by specifically allocating mutable variables (write and read access)
    hangman :: IO ()
    hangman  =
       do putStrLn "Think of a word: " { meaning: UI prompt to think of ques
          word <- sgetLine { meaning: secretly reads String and echo String with underscores
          putStrLn "Try to guess it:" { meaning: UI prompt to guess answer
          guess word

    sgetLine :: IO String { meaning: Function 'sgetLine' of Type I/O Monad performs Action of reading single String from stdout (same as getLine defined in earlier example }
    sgetLine  = do x <- getCh { meaning: Firstly reads a Char (of Type I/O Char) and returns an output named 'x' (of Type Char)
                   if x == '\n' then  { meaning: case of First New Line Char
                      do putChar x { meaning: echo the First Char 'x' to the screen
                         return [] { meaning: return Empty String if we just read a Char that was a 'New Line' Char \n }
                      do putChar '-' { meaning: echos every line of String as a dash }
                         xs <- sgetLine { meaning: Recursively secretly continue to read the rest of the input (i.e. after the 'New Line' Char) }
                         return (x:xs) { meaning: and concatenate each subsequent remaining Chars that are read to the previous Char that was read immediately prior }

    { meaning: the below example is typical Imperative code with multiple Statements. Side-Effects are apparent since we are Interacting with the environment, but without any Mutable Variables }
    import System.IO

    getCh :: IO Char  
    getCh  = do hSetEcho stdin False { meaning: turning stdin off, so reads Char without echo to screen }
                c <- getChar         { meaning: read Char, which is of Type IO of Char and we bind it to the Char. This Monad simply read value of computation and binds it to c (so c is an Immutable Variable) }
                hSetEcho stdin True  { meaning: turning stdin bacj on
                return c             { meaning: return Char

    { meaning: guess Function is the game loop that requests guesses, checks if correct guess until correct or finite attempts reached }
    guess    :: String -> IO ()
    guess word =                     { meaning: where word is the secret word
      do putStr "> "                 { meaning: prompt user for input
         xs <- getLine               { meaning: read the guess input from user
         if xs == word then          { meaning: check if correct guess (i.e. matches secret word)
           putStrLn "You got it!"
           do putStrLn (diff word xs) { meaning: otherwise compute and print to stdout the difference between secret word and user input guess
              guess word             { meaning: then perform tail recursion to guess the word again

    { meaning: diff is a Pure Function (previous Functions contained mostly Imperative code) }
    diff    :: String -> String -> String { meaning: takes Two Strings and returns a String describing their Difference }
    diff xs ys = { meaning: use a List Comprehension taking Two Strings xs and ys }
       [if elem x ys then x else '-' | x <- xs] { meaning: check if for each Char x in First String xs (i.e. | x <- xs), whether appears in Second String ys, and if so print the matching Char to stdout if it does (i.e. then x), otherwise just show an Underscore Char as the secret letter not revealed (i.e. else '_') }

          • GHCi Test

    > diff "haskell" "pascal"


        • Compare >> Symbol versus >>= Symbol (thx raphexion) (Reference Material (thx root_42))
          • { meaning: >> Symbol concatenates Monads without piping through the result of the previous step, whilst >>= Symbol does pipe the previous step results through, see example below }

    Prelude> Just 3 >>= (\x -> Just $ x + 1) >>= (\y -> Just $ y + 3)

    Just 7

    Prelude> Just 3 >> (Just 42) >>= (\y -> Just $ y + 3)

    Just 45

        • Compare sequence_ versus sequence  (thx SherMM, Gregl & headinthebox)

    Prelude> sequence_ (map print [1..5])

    Prelude> sequence [(>4), (<10), odd] 7

    Prelude> sequence_ [(>4), (<10), odd] 7

    Prelude> :t sequence_
    sequence_ :: Monad m => [m a] -> m () { meaning: sequence_ cares about Side-Effect but not the Result }

    Prelude> :t sequence
    sequence :: Monad m => [m a] -> m [a]

    Prelude> import Test.QuickCheck

    Prelude Test.QuickCheck> quickCheck ((\s -> (reverse.reverse) s == s) :: [Char] -> Bool)
    Loading package .........                  ... linking ... done.
    Loading package QuickCheck-2.6 ... linking ... done.

    +++ OK, passed 100 tests.

        • n + k Patterns (Enabling them)
          • .hs File
    -- insert this flag at top of .hs file to turn on n+k patterns

    {-# LANGUAGE NPlusKPatterns #-}

          • GHCi

    Prelude> :set -XNPlusKPatterns

    • Declaring Types & Classes { 
        • Outline: Mechanisms for declaring New Types and Types Classes in Haskell, and Instantiating Type Classes, rather than just continuing to use Existing ones (refer to Chapter 10.6 of Programming in Haskell, and Wiki Link) and Commonalities with OO languages
        • Note: Classes are Categories of Types. Class Instances are Types (not Values)
      • Type Alias Declarations
        • Dfn: Type Declarations define New Names (i.e. an Alias) for an Existing Type (making other Types easier to read and to more easily convey our intent of what we want to do)
        • Example #1
    -- where String is synonym for Type [Char]
    -- we use String to convey in Type declarations
    -- we use [Char] when coding and want to see them as List of Chars
    type String = [Char] 

    type Pos    = (Int,Int)

    origin      :: Pos
    origin      = (0,0) -- using Pairs to represent positions

    left        :: Pos -> Pos -- Note: or replace with Type Trans (see Example 3)
    left (x,y)  = (x-1,y)

        • Example #2 - Parametrized Type Alias
    -- define Type of Pairs (of Type a) as Pairs of Type a
    -- where Type of Pairs (of Values of Type a) are Pairs of Type a Values
    type Pair a = (a,a)

        • Example #2 (CONT'D) - Define Functions over Type 'Pair' (defined above)
    -- take Pair of Int, multiply the Pairs of Int and return an Int
    mult        :: Pair Int -> Int 
    mult (m,n)  = m*n 

    -- take a Single Value, copy it into Pair by taking x and returning a Tuple containing another copy of x
    copy        :: a -> Pair a
    copy x      = (x,x)

        • Example #3 - Nested Type Declarations
    -- define Pos as Pair of Int
    -- define another Type Synonym meaning Pos to Pos
    type Pos    :: (Int,Int)
    type Trans = Pos -> Pos { meaning: Transformation of a Position is a Function that takes one Position and returns another Position }

    Note: Type Declarations cannot be Recursive (as they are just Abbreviations). Recursive Types in Haskell must always go through a Nominal Type (which are defined through Data Declarations)
    type Tree = (Int,[Tree])

      • Data Declarations
        • Data Declarations are used to define Nominal Types (Algebraic Data Types) in Haskell (similar to Case Classes in Haskell)
    data Bool = False | True { meaning: define New Type named Bool (Abstract Base Class), having two Constructors (SubTypes whereby True and False are an Extension of Bool): True, and False (which are also Values, since they do not take Arguments) }

        • Note:
          • Cannot create Instances of Bool since it is Abstract Base Class
          • Can create Instances of False and True (of Type is Bool)
          • Haskell Functions and Type Variables start with Lowercase letter
          • Haskell Type and Constructor Names start with Uppercase letter

        • Example #1 - Algebraic Data Type

    -- three valued booleans 
    data Answer  = Yes | No | Unknown

    answers      :: [Answer]
    answers      = [Yes,No,Unknown] -- define List of answers

    -- generalisation of negation that flips the answers
    flip         :: Answer -> Answer
    flip Yes     = No
    flip No      = Yes
    flip Unknown = Unknown -- Unknown similar to NULL in SQL)

        • Example #2 - Algebraic Data Types (Haskell) (standard example used in OO for Inheritance Hierarchies)
    -- Constructors in this Data Declaration also have Parameters
    data Shape = Circle Float { meaning: Abstract Base Class is Shape }
               | Rect Float Float
    { meaning: SubTypes are Circle and Rectangle (do not have their own Types), and they implicitly define Constructors (Functions Circle and Rectangletake Float(s) and return Shape), so when you create a SubType using the Constructor you get a Shape }

    -- use Constructor to create particular Shape named 'square'
    -- taking a Value (for first coordinate) and create a Shape by duplicating the Value
    square     :: Float -> Shape
    square n   = Rect n n

    -- computer the Area of a Shape and return a Float
    -- where 'area' is defined on Shape
    area       :: Shape -> Float -- Shape has Values of form 'Circle r'
    -- cases of pattern matching (like dynamic/virtual dispatch)
    -- where Algebraic Data Types thought of as Object Hierarchies
    area (Circle r) = pi * r^2 -- r is a Float
    area (Rect x y) = x * y -- x and y are Floats
    { meaning: Circle and Rectangle may be viewed as Functions that construct Values of Type Shape
    i.e. in GHCi checking the Type of these Functions gives
    Circle  :: Float -> Shape
       Rect    :: Float -> Float -> Shape { meaning: Function takes two Floats and returns Shape }

        • Example #3 - "Maybe" Type (not preferred)
          • Dfn: Maybe is like a List. It's either Empty or has a Single Value. If you want to use it then simple Define a New Algebraic Data Type

    -- this Data Declaration has Parameters itself
    data Maybe a = Nothing | Just a { meaning: Maybe of a is either Nothing or Just a }

    -- define a lot of Functions
    safediv      :: Int -> Int -> Maybe Int
    safediv _ 0  = Nothing
    safediv m n  = Just (m `div` n)

    safehead     :: [a] -> Maybe a { meaning: Maybe takes a List, and take the Head (Singleton List), but if Empty List we return Nothing, otherwise take the Head and return Just }
    safehead []  = Nothing
    safehead xs  = Just (head xs)

      • Recursive Types (Simple)
        • Dfn: Declaring New Types in terms of themselves (Types can be Recursive). Recall that Recursive Types in Haskell must always go through a Nominal Type (which are defined through Data Declarations)

        • Example #1 - Natural Numbers of Integers (Recursive Type)
          • Note: Integers may be either Zero, or Successor of an Integer (using n-1 on right-hand size of equation since Haskell does not support n+k patterns anymore)
          • Note: Integers represented as Recursive Types shown below allows Recursive Functions to be written on the two cases (either Zero, Successor of a Natural Number)
    -- New Type named "Nat"
    data Nat = Zero | Succ Nat { meaning: Natural number is either Zero, or One more than Another Natural number }

    -- Constructors have Type Definitions:
    --   Zero :: Nat { meaning: Zero is a Function that takes no args and returns a Natural number }
    --   Succ :: Nat -> Nat { meaning: Succ is a Function that takes a Natural number and returns Another Natural number }
          • Note: Values of Recursive Type Nat is either Zero, or of the form Succ n where n :: Nat, such that Nat contains the following infinite Sequence of Values
    Zero                    { meaning: Base Case, where Zero represents 0 }
    Succ Zero               { meaning: where Succ represents Successor Function 1+ }
    Succ (Succ Zero)
    Succ (Succ (Succ Zero)) { meaning: An Instance of this Nat Recursive Type and map it to an Integer (turn every occurrence of the Succ Constructor into 1, and Zero into 0), which maintains the same Structure so the Value represents the Natural Number  1 + (1 + (1 + 0)) = 3  This is a Homomorphism from Nat to Integers, and we can define this with foldr over Natural Numbers (just like we previously defined foldr over Lists) }
    Undefined { meaning: Bottom }

        • Example #2 - Recursive Function that Converts Values (of Type Nat to Int)

    nat2int          :: Nat -> Int { meaning: Function from Nat to Int }
    nat2int Zero     = 0
    nat2int (Succ n) = 1 + nat2int n { meaning: Function nat2int of (n + 1) = 1 + nat2int of n

    int2nat          :: Int -> Nat
    int2nat 0        = Zero
    int2nat n        = Succ (int2nat (n-1))  { meaning: Alternative to n+k patterns (no longer available in Haskell), otherwise we could write int2nat n + 1 = Succ (int2nat n) }

          • Note: From here we can proove that these Functions are Inverses and that Nat is Isomorphic to Int

        • Example #3a - Addition of Two Natural Numbers (Ineffciently)
          • Brief: Given two Natural numbers, we can add them together by:
            • Converting them to Integers
            • Adding them
            • Converting the result back to Natural numbers

    add            :: Nat -> Nat -> Nat
    add m n        = int2nat (nat2int m + nat2int n)

        • Example #3b - Addition of Two Natural Numbers (Efficiently and elegantly using Recursion instead of having to Convert)
          • Brief: Define directly by Induction over the Natural numbers using Recursion
    add Zero     n = n { meaning: Adding Zero to n is the same as n }
    add (Succ m) n = Succ (add m n) { meaning: Adding m+1 to n is the same as +1 + (m+n) }

          • Implementation Example
    add (Succ (Succ Zero)) (Succ Zero) -- add Two to One
    = Succ (add (Succ Zero) (Succ Zero)) { meaning: Recursively push addition inside and take one of the Succs to the outside }
    = Succ (Succ (add Zero (Succ Zero)))
    = Succ (Succ (Succ Zero)) -- Three

          • Note: The Recursive Definition for Add corresponds to the Laws:
    0+n = n and (1+m)+n = 1+(m+n)

      • Recursive Types (More Interesting)
        • Arithmetic Expressions with Functional Parsers
          • Recall Functional Parsers building an Abstract Syntax Tree representing the Structure of a String as a Tree (before we learnt how to define New Types we simply computed the Value of the Expression as we Parsed it)
          • Example:                                        + 
                                    1 + 2 * 3          { meaning:         /    \
                                                                                    1       *
                                                                                           /   \
                                                                                         2    3
        • Arithmetic Expressions with Recursive Types
          • Define Algebraic Data Types of Expressions and Functions over the Expressions
        • Defining Expressions in Haskell
          • Define an Abstract Base Class
    data Expr = Val Int        { meaning: Simple Value SubType }
              | Add Expr Expr  { meaning: Addition (of Expressions) SubType }
              | Mul Expr Expr  { meaning: Multiplication (of Expressions) SubType }
    { meaning: Expr is an Abstract Base Class, has three Concrete SubTypes }

          • Implementation (of Expression)
    Add (Val 1) (Mul (Val 2) (Val 3))

        • Defining Recursive Functions over Expressions in Haskell
          • Pattern Matching over each Case with same Structure
    -- Count how many Values appear in the Expression
    size           :: Expr -> Int
    size (Val n)   = 1 -- if its a Value then its just 1 (replace the Constructor Val with the Constant Function 1)
    -- Recursively calculate the size of LHS and RHS and add or multiply
    size (Add x y) = size x + size y (replace the Constructor Add with (+) Symbol)
    size (Mul x y) = size x * size y (replace the Constructor Mul with (*) Symbol)

          • Note: In OOP you would make size into a Virtual Method of the Expression Superclass, and overwrite the Virtual Method in each of the Concrete SubTypes

    -- Evaluator/Interpreter for the Expressions
    -- takes an Expression and calculates the Integer value
    eval           :: Expr -> Int
    eval (Val n)   = n -- If you already have a Value you are done (if you have Constructor Val, simply replace it with the Identity)
    eval (Add x y) = eval x + eval y -- case of Addition, add them
    eval (Mul x y) = eval x * eval y -- case of Mult, mult them

    -- Constructors have Type Definitions:
    --   Val :: Int -> Expr 
    --   Add :: Expr -> Expr -> Expr 
    --   Mul :: Expr -> Expr -> Expr

          • Note: size and eval simply replace Val, Add and Mul by other Functions (i.e. replace Constructor Val with Constant Function 1, replace Constructor Add with (+) Symbol, etc)
          • Fold Function to replace Constructors by other Functions (when defining Functions on Expressions)
            • Alternative to Recursive Functions (instead of having to write the above 2 recursive functions, we can just do it once by defining a Foldr over Expressions)

    eval = fold id (+) (*) 
    { meaning: 
    • replace the Val Constructor by the Identity n
    • replace the Add Constructor by Plus (+)
    • replace the Mul Constructor by Times (*)

        • Binary Trees
          • Storing Data in a Two-Way Branching Structure (aka Binary Tree) with Values in Nodes and Leaves
          • Example:                                        5 
                                                           { meaning:         /    \
                                                                                    3       7
                                                                                   /  \     /  \
                                                                                 1   4   6   9
          • Recursive New Type Definition (to represent Binary Trees)
    data Tree = Leaf Int
              | Node Tree Int Tree
    { meaning: Tree is either a: Leaf with an Integer OR Node (with Two SubTrees) with an Integer } 
            • Implementation (of previous example)
    Node (Node (Leaf 1) 3 (Leaf 4))
         (Node (Leaf 6) 7 (Leaf 9))

          • Algorithm #1 - Recursive Functions on Structure of Binary Trees
            • Search to see if a given Integer occurs in the Binary Tree and return Boolean 
            • Problem: Worst case is when Integer does not occurs and Function traverses entire Binary Tree (use "Search Tree" to overcome).

    occurs                :: Int -> Tree -> Bool
    occurs m (Leaf n)     = m==n { meaning: Case 1:  If have a Leaf, then check if Leaf value matches what we're searching for and return Boolean }
    occurs m (Node l n r) = m==n { meaning: Case 2:  If have Node, then check if Node value matches what we're searching for and return Boolean OR whether the value occurs in the Left SubTree OR whether it appears in the Right SubTree} 
                            || occurs m l 
                            || occurs m r

          • Algorithm #2 - Recursive Functions on Structure of Trees
            • Flatten Function returns List of all Integers contained in a Tree
            • Note: The Tree is a "Search Tree" if when we Flatten it into a List it becomes an Ordered List [1,3,4,5,6,7,9]
    flatten               :: Tree -> [Int]
    flatten (Leaf n)      = [n]  { meaning: Case 1:  If a Leaf, return Singleton List }
    flatten (Node 1 n r)  = flatten l
                          ++ [n]
                          ++ flatten r
                                 { meaning: Case 2:  If a Tree with Left & Right SubTrees and a Node, then Flatten Left SubTree (Splice in that value), then Appending the Right SubTree }}

          • Algorithm #3 - Recursive Functions on "Search Trees" (More Efficient)
            • Only traverses down One Path of the Tree
            • Use of "Search Tree"s avoids worse case of having to search the entire Tree, by exploiting the fact that values in the Tree are located in a certain relation (defined by saying that when Flatten the Tree then the result is a Sorted List)

    occurs m (Leaf n)     = m==n { meaning: Case 1:  If have Search Tree check if it's a Leaf }
    occurs m (Node l n r) | m==n = True { meaning: Case 2:  If have Node and values match return True }
    -- Tree Structure known more so only traverse down one path of the Tree
                          | m<n  = occurs m l { meaning: If number being searched for is Less Than the current Node, then only need search in Left SubTree }
                          | m>n  = occurs m r { meaning: If number being searched for is Greater Than the current Node, then only need search in Right SubTree }

      • Additional Notes (Chapter 10.4 onward in recommended textbook)
        • Tautologies Dfn: Given a Functions that decides if the output of a simple logical Propositions is True (i.e. in the representation of some kind of language). The Proposition is known as a Tautology where the output is True
        • Example: Language of Propositions (see recommended textbook)
          • Truth Tables: Define the Meaning of Logical Operators (output Value for Combinations of Argument Values). Custom Truth Tables may be constructed to cater for all possible Propositions of a language, from which we can determine (after considering all possible Substitutions for the Variables it contains) if any of the Propositions are Tautologies (i.e. if the result is always True) 
          • Substitution: Declare a Substitution Type to perform the role of a Look-up Table (associating Variable Names to Logical Values) using the Assoc Type. Substitutions are generated by generating Lists of logical values of a given length
          • Recursive Definitions: Include Base Case and the Recursive Case { i.e. ___ (n + 1) = ...  OR  ___ (n) = ...... (n -1) (since n+k Patterns not supported anymore by Haskell) 
        • Example: Abstract Machine (see recommended textbook)
          • Dfn: Purpose is to have explicit power in Haskell by defining an Abstract Machine for Expressions with customised control and specify the Order of Evaluation of Control Information 
          • Data Mechanism: 
          • Control Stacks Type: Declared Type comprising a List of Operations to be performed by the Abstract Machine after Evaluation completed using  eval (Function defined to evaluate Expressions in the Context of the Control Stack). An additional Function exec is defined to Execute a Control Stack in the Context of an Integer Argument). The Abstract Machine uses two mutually recursive functions eval and  exec (as it has two States depending on whether it's being driven by the Structure of the Expression or the Control Stack)
          • Implementation (Warning: I made this one up)
    -- given
    value            :: Expr -> Int
    value e          = eval e []

    eval             :: Expr -> Const -> Int
    eval(Val n) c    = exec c n
    eval(Add x y) c  = eval x (EVAL y : c)

      value (Add(Val 2)(Val 3))
    =   { applying the definition of 'value' }
         eval (Add(Val 2) (Val 3)) []
    =   { applying the definition of 'eval' }
        { note that 'x' is (Val 2), 'y' is (Val 3), and 'c' is [] }
         eva(Val 2) [EVAL (Val 3)]
    =   { applying the definition of 'eval' }
      exec [EVAL (Val 3)] 2
    =   { applying the definition of 'exec' }
    ... { see Page 110 of text to complete this }

        • Clases and Instance Declarations (see recommended textbook 10.6)
          • Class Mechanism: Declares New Classes in Haskell
    class <insert Existing Class Name> <insert New Class Type> where
      <insert Type Signature>
       __,__  :: a -> a -> Bool
      <insert Cases>
          • Instances
            • Type Name is only an Instance of Class Name if it supports the same Operators of the specified Types (only non-Default Definitions need to be declared in the Instance of the Class) and only if the Type Name is declared using the Data Mechanism
    instance <insert Existing Class Name> <insert New Class Type Instance Name> where
      <insert Cases>

          • Class Extensions
            • Classes may be Extended to form New Classes 
            • Types that are Instances of the Extension Class must be an Instance of the Class that the Extension Class extends from

    class <insert Existing Class Name> <insert Existing Class Type> => <insert New Extension Class Name> <insert New Extension Class Type> where
      <insert Type Signature>
      <insert Cases>

          • Derived Instances: 
            • Dfn: New Types that are declared may be made Instances of various Built-In Classes. Deriving Mechanism is the facility Haskell uses to automatically make New Types into Instances of Built-In Classes (i.e. Eq, Ord, Show, Read), so that the Member Functions of the Deriving Built-In Classes may be used with Values of the New Type 
            • Note: Ordering of the Constructors of a Type is determined by their position (i.e. False | True results in the ordering False < True)
            • Note: In Constructors with Arguments we must ensure that the Types of the Arguments are also Instances of any Derived Class (these are known as Class Constraints on Parameters)
    data <insert Type> = <insert possible Constructors/Values>
                         deriving (<insert Built-In Classes comma separated) 

          • Monadic Types: 
            • Dfn: The notion of a Monad is due to Generalisation from specific cases of Parser and IO to an arbitrary Parameterised Type, captured in Haskell by Class Declaration:
    class Monad m where
      return :: a -> m a
      (>>=)  :: m a -> (a -> m b) -> m b

            • Note: Monad is a Parameterised Type (inferred from its use of Types for the two Functions), supporting both Functions return and >>= of the specified Types. 
            • Note: Use this Class Declaration to make Parsers and IO (Interactive Programs) into Instances of the Class of Monadic Types, by means of Two Member Functions

    instance Monad Parser where
      return v = ...
      p >>= f  = ...
    instance Monad IO where
      return v = ...
      f >>= g  = ...

            • Note: Given these Class Declarations and Instances we can use the "DO" Notation to Sequence the Parsers and IO (Interactive Programs). Haskell supports use of "DO" Notation with any Monadic Type, allowing rewriting the following Expression form
    -- original Expression
    e1 >>=
     λv1 ->

    en >>= λvn ->
    return (f v1 ... vn)

    -- rewritten Expression using the "DO" Notation form
    do v1 <- e1
          vn <- en
          return (f v1 ... vn)

    • The Countdown Problem
      • Transformation Development Dfn: Pattern of starting with simple and inefficient correct solution (using brute force), and then finishing by Refactoring the solution to make it more Efficient and optimised (similar to Extreme Programming). "Think like a fundamentalist but code like a Hacker" (FP101) by starting with fundamental code that is correct, and then hack on to make it more efficient
        • Example: Haskell Prototyping { use Haskell code as a Prototype, then implement the same algorithm in another language }
      • Countdown Problem Dfn: A numbers game that is based on a TV quiz program, similar to idiomatic developments like Haskell sudoku solver, and papers by Richard Birch.
        • Example #1: Informal Way
    -- given numbers
    1 3 7 10 25 50
    -- given arithmetic operators
    + - * ÷


  • All numbers must be positive natural no's (including intermediate results) i.e. 1,2,3..
  • Each number can be used only once when constructing expression

  • Goal
    -- goal is to construct expression with Target Number result value of 765

    -- leverage infinite patience of computer and restricting the search breadth to churn through a search space to find a solution quickly

    (25-10) * (50+1) = 765
       5    *   51   = 765
    -- note: intermediate results are positive numbers!

  • Search space (for this example with Target Number of 765) has 780 solutions
  • Search space (for another Target Number of 831) has no solutions 

        • Example #2: Evaluating Expressions (Bottom-Up Solution)
          • Step #1 Create a Function that is a Symbolic Representation of the Expression that performs Symbolic Processing of Expressions
    -- define Operators as an Algebraic Data Type
    data Op = Add | Sub | Mul | Div

    -- defined Evaluation Function that takes two numbers and applies the operator to an Expression
    apply         :: Op -> Int -> Int -> Int

    apply Add x y = x + y
    apply Sub x y = x - y
    apply Mul x y = x * y
    apply Div x y = x `div` y

          • Step #2 Encode the Rules of the Game
            • Rule #1 - All operators must be applied to positive numbers
    -- determine if a positive natural number results from applying an operator to two positive natural numbers (i.e. check if valid application of the operator)
    valid         :: Op -> Int -> Int -> Bool
    valid Add _ _ = True -- already know output of two pos given no's is a pos no
    valid Sub x y = x > y -- avoid negative intermediate results that are disallowed
    valid Mul _ _ = True
    valid Div x y = x `mod` y == 0 -- check divisible to ensure we get a natural number

    - define the Data Type of Expressions (one application that takes the operators)
    data Expr = Val Int | App Op Expr Expr

          • Step #3 Evaluate the Expression by either returning a Singleton List containing the resulting value, or return Empty List when Expression inside is not valid (similar to that used for Functional Parsers). It is much more convenient to use Lists than using the Maybe Type (as you can use List Comprehension)
    { meaning: defined Recursively over Expressions }
    val             :: Expr -> [Int] 
    { meaning: if given a value n, it succeeds if the value is greater than 0 }
    val (Val n)     = [n | n > 0]
    { meaning: if given an Expression that is the application App of an Operator and two sub-Expressions l r, then first Evaluate the LHS l, then Evaluate the RHS r, and lastly perform a Filter to check that the application of the Operator to these numbers x y is Valid, and if so we Evaluate by returning the application with apply o x y }
    val (App o l r) = [apply o x y | x <- eval l
                                   , y <- eval r
                                   , valid o x y]

        • Example #3: Formalised Problem (with Helper Functions that we either assume exist or we have to define ourselves)
    { meaning: Function that takes an Input List of values of Type 'a', and returns an Output List of Lists with all possible ways to choose zero or more Elements from the Input List }
    choices :: [a] -> [[a]]

    { meaning: if want to have all the choices of choosing zero or more Elements from the List [1,2] }
    > choices [1,2]
    { meaning: there is one way to choose the 0 elements from the List, there are two ways to choose 1 element from the List, etc } 

    { meaning: define a new Function that given an Expression returns a List of all the values at the Leaves }
    values           :: Expr -> [Int]
    { meaning: if have just a value then return a Singleton List }
    values (Val n)   = [n]
    { meaning: if have application of whatever Operator, then first take the values of the LHS sub-Expression, and combine them with the values of the RHS sub-Expression }
    values (App _ l r) = values l ++ values r

    { meaning: Function to decide if a given Expression is a solution for a given List of numbers by directly translating the rules of the Countdown Problem  to the Haskell Program }
    { meaning: given an Expression Expr, a List of Initial Numbers [Int], a Target Number Int, then check and confirm with a Boolean Bool response if the Expression is a solution to our problem }
    solution         :: Expr -> [Int] -> Int -> Bool

    { meaning: when we take all values values in that Expression eand take all the possible choices choices for the input numbers ns, then the elements elem in the List (values e) must be members of the List  (choices ns) }
    solution e ns n  = elem (values e) (choices ns) 
    { meaning: the Expression must Evaluate to the Target number we're searching for }
                       && eval e == [n]

        • Example #4: Brute Force Solution - Part 1 (one-to-one translation of the original problem that is a brute force way of enumerating all possible Expressions that are built out of the given numbers, in search of all possible solutions, and check if they satisfy the rules of the game)
    { meaning: Function that takes a List and returns a Pair of Lists inside another List, giving all possible ways you can split the given List into a Pair of Lists }
    split :: [a] -> [([a],[a])]

    { meaning: if we want to split the list [1,2,3,4], without taking the Empty List into account as splitting into [1,2,3,4] and [] does not make sense }
    > split [1,2,3,4]
    { meaning: these are the possible ways the List can be split }

    { meaning: define a Function that given a List of integers, will return a List of Expressions, where the values that are in the Expression are exactly those in the List of given numbers }
    exprs      :: [Int] -> [Expr]
    { meaning: given an Empty List of numbers then we cannot build any Expression }
    exprs []   = []
    { meaning: given a Singleton List then we can only build an Expression that contains its value }
    exprs [n]  = [Val n]
    { meaning: given a List of numbers, then we build all the Expressions by first Splitting the List, then Recursively using the LHS to create an Expression, the RHS to create an Expression, and then using the Function "combine" combine to combine the two Expressions.
    exprs ns   = [e | (ls,rs) <- split ns
                    , l       <- exprs ls
                    , r       <- exprs rs
                    , e       <- combine l r]

    { meaning: combine two Expressions using any of the Operators }
    combine     :: Expr -> Expr -> [Expr]
    combine l r =
       [App o l r | o <- [Add,Sub,Mul,Div]]

    { meaning: List Comprehension that takes all choices choices for the Input List ns, then perform brute force creation of all the Expressions e, and ensure the value we've searched for is equal to the required Target value }
    solutions   :: [Int] -> Int -> [Expr]
    solutions ns n = [e | ns' <- choices ns
                        , e <- exprs ns'
                        , eval e == [n]]

    --implementation of the Example on a slow laptop takes about 30 sec to find the first solution and 43 sec to find all solutions
    solutions [1,2,7,10,25,50] 765

          • Improved Solution instead of brute forcing all possible Expressions, causing many i.e. 20% or so to be invalid since they will fail to evaluate. We will have to filter these out later OR check that we are not generating any invalid expressions by combining aka Fusing the Generation Function with the Evaluation Function to allow earlier rejection of invalid expressions }

        • Example #4: Brute Force Solution - Part 2 (check if we can avoid invalid Expressions upfront to try and achieve a performance improvement of less invalid Expressions, by Fusing Two Functions and inspecting the Pairs (Expr,Int) of Expressions Expr  (Symbolic Representation is the result of Generating the Expression) and their Values (Numeric Representation is the result of Evaluating the Expression to check if it satisfies the constraints of the game) Int )

    -- valid Expressions and their Values
    type Result = (Expr,Int)

    -- define Function that Fuses together the Generation and Evaluation of Expressions
    results     :: [Int] -> [Result]
    results ns  = [(e,n) |  e <- exprs ns { meaning: Generation of Expressions }
                         ,  n <- eval e] { meaning: Evaluation of Expressions }

    -- define Function that combines the Generation and Evaluation behaviour
    results [] = [] { meaning: result of Empty List is an Empty List }
    results [n] = [(Val n,n)| n > 0] { meaning: Generating the combination of Expressions and their Values for a Singleton List by including a Test comprising of the Generation of an Expression Val n, whilst knowing its Value n  but where it's only valid if the Value is n > 0 }
    results ns = { meaning: same approach as previously described, with results called Recursively }
       [res | (ls,rs) <- split ns
            , lx      <- results ls
            , ry      <- results rs
            , res     <- combine lx ry]

    -- define Combine Function that Recursively checks that the Results are valid
    combine' :: Result -> Result -> [Result]

    -- same as the combine method, except combine' also checks if the results are valid
    combine' (l,x) (r,y) = { meaning: carry a Pair of the Expression and its Value, to allow us to check if the result is valid whilst we're generating the Expressions }
       [(App o l r, apply o x y)
          | o <- [Add,Sub,Mul,Div]
          , valid o x y]

    -- new Function that solves the Countdown Problem
    solutions'    :: [Int] -> Int -> [Expr]
    solutions' ns n =
       [e | ns'   <- choices ns  { meaning: take the List of all the choices }
          , (e,m) <- results ns' { meaning: calculate results given List of choices }
          , m == n]  { meaning: check if result is what we want }

    --implementation of the Example with these alternative Functions takes about 0.04 sec to find the first solution and less than 4 sec to find all solutions (10 times faster)
    solutions' [1,2,7,10,25,50] 765

    • Further Improved Solution whilst we have previously already improved the first solution by eliminating invalid expressions early, we can further improve performance by exploiting Symetries of Simple Arithmetic Properties based on the fact that many Expressions are essentially the same, and to further reduce the search and solution spaces. Eliminates evaluation of the Expressions below on the LHS, as they'll be considered the same as those on the RHS }
    x * y = y * x { meaning: Multiplication is Commutative, so we do not need to check these two results separately }
    x * 1 = x { meaning: 1 is the neutral element for Multiplication, may as well just use x instead of evaluating }

    • Improve the Previous Definition Valid Expression (with Exploiting Properties)
      • Strengthening the valid predicate to account for Commutativity and Identity Properties
    valid         :: Op -> Int -> Int -> Bool
    valid Add x y = True { meaning: valid since adding two positives }
    valid Add x y = x <= y { meaning: valid if x less than or eq y (force Bias Representation so the Commutative Expression Add y x is no longer valid}
    valid Sub x y = x > y { meaning: constraint to ensure always positive result }
    valid Mul x y = True 
    valid Mul x y = x <= y && x != 1 && y != 1 { meaning: valid if x less than or eq y, and x != 1 (force Bias Representation so the Commutative Expression Mul y x is no longer valid, as with case where 1 is the Neutral Element of Multiplication i.e. x == 1 or y == 1) }
    valid Div x y = x `mod` y == 0 && y != 1 { meaning: constraint to ensure within integer domain, and that when divide x by 1 this is the same as just x }

    --implementation of the Example with these further improved alternative Functions gives about 20 times less valid Expressions
    and about 16 times less valid solutions (since we've eliminated duplicate solutions). It finds one solution 2 times faster, and all the solutions about 7 times faster (about 0.5 sec).
    solutions'' [1,2,7,10,25,50] 765

    • Testing & Debugging with QuickCheck using Erlang (with John Hughes)
      • Dfn: Random testing tool. "Don't Write Tests! Generate Them"
      • Haskell QuickCheck
      • Benefits: 
        • Allows wider variety of Tests than by hand (including those not thought of)
        • Allows Tests at Higher Level against Specification of code (Properties, Models)
        • Presents Minimal Failing Test Cases that are ready to Debug (so you don't have to try and simplify the failure yourself)
        • Test code is 10x smaller than traditional test code and Scales
      • Ordinary Unit Test { call a Function on sample data and match result against expected answer }
      • QuickCheck Test 
    { meaning: define a Property of a Function reverse(), that tests for all L, where L is a List of integers, by QuickCheck generating random Lists of integers as Test Data, and since we cannot predict the result of reverse() on an arbitrary List, we will instead test a Property of reverse, such that when we reverse an initial List twice, the result we get is equal to the initial List that we started with }
    -- QuickCheck Function Definition of a True Property

    -- Test by running QuickCheck in shell, passing it the Property as an argument. Randomly generated tests are performed and success of each test indicated by a dot. 
    ....Passed after x tests.

    -- QuickCheck Function Definition of a False Property
    { meaning: case where forget to apply the reverse() Property twice reads that for any List, reversing the List returns the List itself. This is False }

    -- Test giving the False Property to QuickCheck 
    { note: QuickCheck will indicate which random tests failed. QuickCheck then attempts to simplify the test example that failed various times using a Shrinking Process until it reaches a minimal final Counter Example, noting that in order to Falsify the Property, we need at least 2 elements in the List and each element must be different }
    ....Failed after x tests.
    [-3,-1] /= [-1,-3]
    Shrinking xxx.x..xx(3 times)
    [1,0] /= [1,0]

      • Example #1 - Simple Key Value Store
    -- example of its capabilities
    kv:start() ==> true
    kv:insert(1,a) ==> ok
    kv:insert(2,b) ==> ok
    kv:lookup(1) ==> a
    kv:lookup(2) ==> b
    kv:delete(1) ==> ok
    kv:lookup(1) ==> false
    kv:stop() ==> ok

    -- Function Definitions
    { meaning: Note that Key Value Store kv has Internal State, whereas the Function reverse() did not. The Internal State of kv needs to be Modelled in order to produce Sensible Tests. We will Generate Tests that are Sequences of Calls to an API, and use the Model of the State to define postconditions for each operation } 

    %% Generators
    key() -> 
      nat(). { meaning: Generate a random natural number for key }

    val() ->
      oneof([a,b,c,d,e]). { meaning: Value one of randomly chosen atoms }

    %% State Machine
    initial_state() ->
      []. { meaning: we have Modelled the State of the kv as just a List of Keys that should be defined, and is initially an Empty List. Note: We do not need to Model the entire kv Store to produce useful Tests }

    %% Lookup
    { meaning: for each operation we define a Generator, by specifying how to produce a List of Arguments for Lookup, by specifying, to pick a key(), and by specifying a postcondition that says when we lookup the Key K, then the result Res we get should be different from False, only if the Key is a member of the List of Keys in the Model of the Key Value Store State }

    lookup_args(_) ->

    lookup_post(S,[K],Res) ->

    %% Insert
    { meaning: we Model the Insert with a State Transition Function insert_next that simply adds the Key [K, that we Insert in the Model State -> [K], by appending a List containing [K] to the previous List, whilst removing any previous occurrence of -- [K] from that State so each Key will appear at most once }

    insert_args(_) ->

    insert_next(S,_,[K,_V]) ->
      [K] ++ (S -- [K]). 

    %% Delete
    { meaning: we Model the Delete in a similar way, such that when we call Delete, the next Model State is derived by removing the Key that we Deleted from the Model State }

    delete_args(_) ->

    delete_next(S,_,[K]) ->
      S -- [K].

    %% Property
    { meaning: given the above Specifications, write a Property that uses the QuickCheck State Machine Library that says that for all sequences of Cmds that we generate using the above functions, then if we start the KV Store kv:start(), then Run the Commands run_commands, then stop the KV Store kv:stop(), then all the the postconditions will be True, there will be No Exceptions, and the Lookups will return a defined result exactly when they should }

    prop_kv() ->
      ?FORALL(Cmds, commands(?MODULE),
                Result = run_commands(?MODULE,Cmds),
                check_commands(?MODULE, Cmds, Result)

    -- QuickCheck Tests
    eqc:quickcheck(kv:prop_kv()). { meaning: QuickCheck Test giving it the KV Property to test, which will generate random sequences of calls and check that the postcondition is true for all of them }
    ... OK, passed 100 tests
    { meaning: we used each operation about 1/3 of the time }
    35.% {kv,delete,1} 
    32.9% {kv,insert,2}
    32.6% {kv,lookup,1}

    eqc:quickcheck(eqc:numtests(10000,kv:prop_kv())). { meaning: run more tests i.e. 10,000, if not satisfied with the results, and we may discover that some of the tests fail a postcondition, which after simplification using Shrinking, we may have some hope of Debugging }

    eqc:check(kv:prop_kv()). { meaning: re-run the same test to see same failures }

    eqc:check(kv:prop_kv_verbose()). { meaning: run an Instrumented version that gives more information. Note that internally, the KV Store is using an Ordered Binary Tree, and given that we have a verbose version of the Property that we can run the same test on, and which will display the Trees that are constructed at each Step. Using the graphical Tree result, we can visually see that we have the situation below for delete, where the 6 is to the Right of a 9, which Breaks the Ordered Invariant, as it should be to the Left, and is the reason it wasn't found }

       /   \
           /      \
        /    \ 
            /     \

    { note: in the Example above, we are deleting the Key 8, which comes from from the Root Value of a call to Insert, so the case called is K==KN d, which causes merging the Left and Right Sub-Trees, discarding the root node, using the merge Function on two non-empty Trees, so we run the case merge({node and we Pattern Match on the Left and Right Sub-Trees, and the Key and Value .LL,KL,VL,RL in each Node, and then build a New Tree using the Key and Value from the Left KL,VL and Right KR,VR Sub-Trees, putting the Sub-Tree from the very Left at the Left  LL and putting the Sub-Tree from the very Right at the Right  RRh, and then Recursively merge merge(RL,LR)the Right Sub-Tree of the Left Node RL, and the the Left Sub-Tree of the Right Node LR  R. Note that if it the code was erroneously merge(LR,RL), then a failure would occur in QuickCheck due to incorrect ordering }
    -- codebase for delete function
    delete(_,leaf) ->
    delete(K,{node,L,KN,VN,R}) ->
      if K<KN -> 
         K==KN ->
         K>KN ->

    merge(leaf,R) -> { meaning: case of Empty Leaf } 
    merge(L,leaf) -> { meaning: case of Empty Leaf } 
    merge({node,LL,KL,VL,RL},{node,LR,KR,VR,RR}) ->
      {node,LL,KL,VL,{node,merge(LR,RL),KR,VR,RR}}. { meaning: case of  merging two Non-Empty Leaf Sub-Trees } 

    • Lazy Evaluation
      • Dfn: Everything uses the Strategy of Lazy Evaluation in Haskell, as Haskell is a Lazy Functional Language, unless you make things Strict
      • Lazy Evaluation Strategy for Functional Programs (Haskell Expressions) is an Evaluation Technique that:
        • Avoids unnecessary evaluation (only evaluate when absolutely necessary)
        • Allows more Modularity in programs
        • Allows programming with Infinite Lists / Data Structures (as we're never doing more work than necessary)
        • Makes it easier to compose programs (never more work required than is necessary)
      • Example #1 - Evaluating Expressions
        • Note: Large Expressions are Evaluated / Reduced by successively applying definitions to evaluate its Sub-Expressions until no further Simplification is possible
    -- given Function Definition
    square n = n * n

    -- given Expression
    square(3 + 4)

        • Evaluation Strategy #1 (First Applying Definition of Square) (Innermost Reduction)
    square (3 + 4)
    -- evaluate (3 + 4)
    square (7)
    -- substitute Definition for 'square', and (7) for n 
    and then substitute RHS 
    7 * 7
    -- then evaluate it

        • Evaluation Strategy #2 (First Perform Arithmetic on Arguments) (Outermost Reduction)
          • This Reduction Sequence involves evaluating (3 + 4) twice (duplicated computation), that can by avoided by using Haskell
    square (3 + 4)
    -- substitute (3 + 4) for n and then substitute RHS
    (3 + 4) * (3 + 4)
    -- execute the first (3 + 4)
    7 * (3 + 4{ meaning: the work is being done twice here as the Sub-Expression 3 + 4 is duplicated when square is reduced, so it is Inefficient, which is proof that Outermost Reduction may require more steps than Innermost Reduction }
    -- execute the other (3 + 4)
    7 * 7
    -- then evaluate it
    49 { meaning: same result even though we applied square before doing addition }

          • If there were Side Effects in the code, then since the Evaluations performed if different order, the Side Effects might occur in different order and the result may be different, but since we are in the Pure world, the order doesn't matter, such that "given two different (but terminating) way of evaluating the same expression always give the same final result"
      • Reduction Strategies
        • At each Stage when Evaluating an Expression, there may be many choices of Sub-Expressions that we can Reduce (by applying a Definition)
        • Two Common Strategies
          • When deciding which Redex (reducible Sub-Expression) of all possible Expressions to choose (they are Systematic Strategies that allow us to reason about the Properties of the Expression)
            1. Innermost Reduction - Innermost Expression (Redex) that can be reduced is always reduced
            2. Outermost Reduction - Outermost Expression (Redex) is always reduced. 
          • Notes:
            • Outermost Reduction may give results when Innermost Reduction may fail to terminate
            • Given an Expression where any Reduction Sequence exists that terminates, then the Outermost Reduction also terminates with the same result (the Outermost Strategy is not a bad thing)
            • Outermost Reduction may require more steps than Innermost Reduction Innermost Reduction sometimes may not terminate
        • Example #1 - Two Reduction Strategies (Innermost Reduction)
    -- given Definition
    loop = tail loop { meaning: loop to take the tail of loop, where loop must have Type List, so it is just a List that chases its own tail }

    -- evaluate Expression using the Two Reduction Strategies
    fst (1, loop) { meaning: give us the first of the Pair (1, loop) and then we'll compare and contrast the Two Reduction Strategies }
    fst (1, loop { meaning: takes the Innermost Reducible Expression argument inside the Tuple, and reduces it, which diverges loop into tail loop, so there is no chance of taking the first fst value of the Pair  }
    fst (1, tail loop)
    fst (1, tail (tail loop))
    ...  { note: this Strategy does not terminate, as the Evaluation Order is too Strict }

        • Example #2 - Two Reduction Strategies (Outermost Reduction)

    -- given Definition
    fst (1, loop) { meaning: take the Outermost Reducible Expression, and gives result in one step (instead of never terminating like the Innermost Strategy) }


        • Sharing
          • Solution to the problem is by using Pointers to indicate Sharing of Expressions during Evaluation, so when we Substitute (3 + 4) into the Definition of 'square' we don't just copy the Expression (3 + 4), but we Share it, so we have Pointers to the Expression 

    square (3 + 4)

    (. * .)  (3 + 4)
    (. * .)     7


        • Lazy Evaluation (New Reduction Strategy)
          • Never requires more steps than Innermost Reduction
          • Expressions are only Evaluated as much as required to produce the final result. Note: It is note expanded eagerly to an Infinite List
          • Note: If this Lazy Evaluation was performed in a Strict Language then ones would be described as a law abiding Thunk, and by inserting a Unit Arrow somewhere to stop the Evaluation (since the Function Unit Arrow is already a Value }
    ones = 1 : ones { meaning: only defines ones as a Potentially Infinite List that is only Evaluated (and expanded on-demand) as much as required by the Context in which it is used }

    Lazy Evaluation = Outermost Reduction + Sharing

      • Infinite Lists
        • Advantages of Lazy Evaluation is ability to program with Infinite Lists of values
    ones :: [Int] { meaning: define a Recursive Value of List }
    ones = 1 : ones { meaning: define the Infinite List of ones as 1 : ones }

    ones = 1 : ones { meaning: unfolding the Recursion a few times }
         = 1 : 1 : ones
         = 1 : 1 : 1 : ones { meaning: ones  is the Infinite List of ones }

        • Example #1 - Evaluation of Expression head ones
          • Comparing and Contrasting Innermost Reduction and Lazy Evaluation 

    -- using Innermost Reduction
    head ones = head (1 : ones{ meaning: taking he Innermost Reducable Expression and unfolding it repeatedly }
              = head (1 : 1 : ones)
              = head (1 : 1 : 1 : ones)
              = ... { meaning: Evaluation does not terminate, and we never get to take the head of the List }

    -- using Lazy Evaluation (Outermost Reduction + Sharing)
    head ones = head (1 : ones{ meaning: Evaluation gives Result of 1 }
              = 1

    • Modular Programming
      • Lazy Evaluation makes code more Modular because it does just enough to make the next Step, and because it separates Control from Data
      • Data is only Evaluated as much as required by the Control part, using Lazy Evaluation

    -- generate Finite Lists by taking elements from Infinite Lists
    ? take 5 ones { meaning: take defined as Induction over the Structure of the List, such that each time ones Pattern Matches on that List, it Evaluates just enough to get the next Value, so we nicely terminate }
    ? take 5      [1..] { meaning: Infinite List of 1's is the same as ones }
        (CONTROL)     (DATA)

      • Example #1: Recipe for Generating Prime Numbers (Sieve of Eratosthenes Algorithm simplest version) using Lazy Evaluation  
        • Note: Previously used List Comprehensions (but this way is better)
        • Specification (procedure to generate Infinite List of Prime Numbers)
          1. Write down the List 2,3,4...
          2. Mark first Value 'p' in the List as Prime
          3. Delete (Filter out) all multiples of 'p' from the List (as they are not Primes)
          4. Return to Step 2 and make Next Value 'p'
        • Note: There are numerous variants to make this more Efficient (i.e. wheels, using all the properties of natural numbers, etc)
    primes :: [Int]
    primes = sieve [2..] { meaning: start with Infinite List of Natural No's starting at 2 }

    sieve :: [Int] -> [Int]
    { meaning: start with the first number (head)  of the List xs, consider it a Prime, return that number, throw out all multiples of p from xs xs, and then make Recursive Call to go back to Step 2 by calling sieve  and sieve out all the numbers from there }
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

    -- implementation
    > Primes
    { meaning: Infinite List of prime numbers }

        • Modular Dfn { achieved by freeing the generation of primes from the constraint of finiteness, such that different Boundary Conditions may be imposed in different situations. }
        • Note: Imperative languages without Lazy Evaluation require Fusion into one Function
    -- select first 6 primes
    > take 7 primes 
    { meaning: constrained to Finite, lazily only doing enough work to meet constraint }
    -- select primes less than 15
    > takeWhile (<15) primes

    Why Functional Programming Matters (John Hughes) - more examples of Modular approaches

    • Category Theory (aka Generalised Abstract Nonsense)
      • Mathematicians Approach to OOP and Design Patterns
      • Built from Objects and Morphisms (satisfying certain Laws)
        • Morphism Law (i.e. given Morphisms a -> b, and b -> c, then Morphism a -> c must exist)
                                                  g,f = f,g
            Object      /             f                            g    \,
                    ,    A   -------------->   ,   ----------->  , C
                    |_|       Morphism      |_|                     |_| 
                       w                              w                       w

      • Functor Rules:
        • Functor applied to Object is a Generic Type
        • Functor applied to Morphisms is the familiar Map Function
      • Key 1:
        • Category of Small Categories (SC) Categories (CAT) as Objects }
        • Morphism notion (aka Functors)
    Category of Small Categories Diagram

    Small Categories         F                           G          
                    ,  SC A   ------------>  , SC B   ---------> , SC C

                  F id A  =  id B
                  F (f . g)  =  (F f) . (F g)   meaning: Action on Morphism }

                 F A = B   meaning: Action on Objects }
      • Key 2:
        • Functor Category (FC) { Functors as Objects }
        • Morphisms (in FC) notion (aka Natural Transformations) (aka Generic Functions)
          • Natural Transformation Laws { proof that they are satisfied is demonstrated with a Commuting Diagram whereby it doesn't matter which direction you take (of two possible ways) to get from Top Right to Bottom Left }
    Natural Transformations Diagram

                           ________________ F ________________
                          /                                  |                                 \,, 
                     FC A                                |  n  Natural                 FC B  

                  n <A>  :   F<A>  -->  G<A>

    Commutating Diagram

                                 f : A --> B
                    F A   ------------>  F B 
                        |      \                       |
                        |           \                  |
                 B  |               \              |  B
                        |                   \          |
                        |                       \      |
                     G A   ------------>  G B 

         F B          F A         F B        F A
         B   .  Ff  =  Gf  .  

    Haskell (Beginning Haskell)
    • WORKS GOOD :) Haskell Eclipse IDE Installation (Mac) 
      • Download & Install latest Xcode CLI
      • Download & Install latest JDK in 64 Bit (i.e. Java SE Development Kit 8u25, which includes JVM from Oracle website, NOT the Java website). Reasoning
      • Download & Install latest Eclipse IDE for Eclipse Committers 4.4.1 (latest) Mac OS X 64 Bit (NOT 32 Bit), copy into Applications directory, and open from Launchpad. (Note: If you get an error stating that "Eclipse" can't be opened because the identity of the develoer cannot be confirmed, then open System Preferences > Security & Privacy, and click button "Open Anyway" where it says "Eclipse" was blocked ...)
      • Download & Install latest EclipseFP from within Eclipse IDE (Luna). Open Eclipse IDE.
        • Help Menu > Install New Software > Work with:
        • Click "Add..." > Enter a "Name" (i.e. EclipseFP) > Press OK
        • "Pending" appears and eventually "Functional Programming" loads. Click the adjacent Checkbox. Click "Next" (downloads FP: Haskell support for Eclipse). 
    • NOT WORKING CORRECTLY Sublime Text 2 with Haskell
    • PENDING IntelliJ IDEA Community Edition  (Thanks to Ashley Towns!!)
    • NICE FPComplete (Browser-based Haskell IDE with GitHub Integration)
    • Haskell Compiler (Standard)
      • GHC (Glasgow Haskell Compiler) { Haskell Implementation (Compiler & interactive REPL Interpreter) }
      • Standard Prelude of Library Functions (SDK for Haskell) (i.e. lists)
    • Haskell Compiler (Other)
    • Haskell Packaging & Build System Tool
      • Cabal (tailored for Haskell and Hackage)
    • Haskell Online Package Repository of Libraries
    • Haskell Tools
      • GHC Profiler (Detect Space & Time Leaks)
      • Hoogle & Haddock (Browser & Create Documentation)
      • UU Attribute Grammar System (Build DSLs)
    • Similar Languages
      • Agda ("Type-Oriented Programming" interactive environment)
      • Idris ("Dependent Typing" with stronger "Type Checking" than Haskell with invariants expressed)
      • Groovy
      • F#
      • Frege
    • Terminology
      • Programming Paradigm (Style) { Set of ideas and Concepts shared by different programming languages } 
      • Functional Programming (Haskell) { is one of the Programming Paradigms with focus on Functions as First-Class Citizens. }
    "Functional programming means using Higher Order Functions (whether they are Pure or not), whilst focusing on using Expressions (as opposed to Statements). It does not mean having to use Pattern Matching, nor does it imply that we cannot use Side-Effects"  (my version of Functional Programming Dfn according to Erik Meijer)

      • Functions as First-Class Citizens (Haskell) { where Functions may be treated and manipulated as any other data, which allows higher level of Abstraction (since details are Abstracted in a Function) and opportunities for more concise and Reusable code that explicitly indicates its intention (i.e. Functions may be passed as Arguments, Returned as results, or Assigned to variables) and allows Bugs to be detected quickly in its implementation. Haskell Functions like map provide a one-line equivalent of otherwise extensive code required to creating an Interface for Type Checking that is implemented through a Class in other languages like JavaScript }
      • Purity Concept (Haskell) { separating code with Side Effects from rest of app, as outcomes of Pure Functions only depend on their Parameters without interference in Execution. Easier for Testing. Evaluation of Pure Expressions is not dependent on their order of execution so different Execution Strategies may be adopted for code (default strategy is the Lazy Evaluation Model), and Haskell libraries take advantage of this with Parallel, Concurrent, and Scheduled execution }
      • Referential Transparency (Haskell) { Deterministic Expressions that require the same effects and output for a given set of inputs at a point in time, and allows developer and Compiler to Reason about the app behaviour and apply formal Verification techniques (i.e. Refactoring algorithms, Functional Correctness whereby each input produces the correct output to Specification, Common Subexpression Elimination (CSE) by the Compiler where optimisation achieved by replacing instances of identical Expressions with single variables, Parallelism, and Memoization (optimisation by storing and returning outcomes of expensive Function calls using Cache) ) }
      • Referential Opaqueness { opposite of Referential Transparency }
      • Side Effects (Haskell) { elements in global state that may Change between Executions of same Function and are Outside of Black Box of program Control (i.e. Input, Output, Network Comms, Randomness) }
      • Expressions { in Haskell, the Expressions are Pure as they cannot have Side Effects by default, and the developer is forced to separate the Expressions (Pure without Side Effects) from Impure aspects }
      • Lazy Evaluation Model (Haskell) { execution strategy where Expressions are not evaluated until they are needed, and after evaluation the result is either Saved or Discarded if not being used in any other running code. Benefits include Minimising Computation during Execution time. Drawbacks include that suspended Expressions pending evaluation must be Saved in Memory. }
      • Type System (Haskell) { Abstraction that Categories the Values that may appear during execution and Tags them with a Type to restrict the possible Set of Actions (Operations) that could be Applied to a Value }
      • Static Type Checking (Haskell) { Checking the Tags (Typechecking) at the moment of Compilation by the Compiler before being run at Execution (Validate the Typing of Apps in compliance with language Rules before generating target output code and being allowed to run) }
      • Dynamic Type Checking { Checking the Tags during Execution time (used in Loose Typing languages that allow implicit type conversions) } 
      • Non Typing Language { Try to compute regardless of whether dealing with different types }
      • Strong Type System (Haskell)  { higher quantity of Invariants caught at Compile time, instead of waiting for an Error to instead occur when app running. Example is dividing two Strings in GHC, which returns error indicating no instance of its Type Class "Fractional" (supports the use of "/" operator) for dividing two Strings, unless a declaration is added for this case}
    "string1" / "string2"
      • Type Collection / Grouping / Category of related Values with common properties }
      • Type Class { Grouping Sets of Types that support same operations }
      • Infix Syntax { Functions represented entirely by Symbols (i.e. ++) must be called Between Arguments (i.e. a ++ b) and only outside Args by using parenthesis (i.e. (++) a b )
      • Type-Oriented Programming { where Developer knows Type of Function being developed and Structure of the code and fills in holes with Expressions that fit in from surrounding environment }
      • Parametric Polymorphism { coding Functions on lists without caring about the Type of element contained in them. The fact that a Type like a List is Dependant on other Types }
      • Type Classes { Group different Types with a common Interface that allows Expressions for Abstract ideas (Functors, Monads) }
      • Syntactically Well Formed Expressions { have Type that may be auto calculated at compile time using Type Inference }
      • Type Soundness { when Type corresponds to the value of an expression when evaluated at runtime }
      • Type Errors { Apply Function to Arguments of wrong Type }
      • Type Expressions and Value Expressions { i.e. ('b',4) :: (Char,Integer) Note the statement "Notice that expressions and types have a consistent syntax. If ti is the type of expression or pattern ei, then the expressions (\ e1 -> e2)[e1], and (e1,e2) have the types (t1 -> t2)[t1], and (t1,t2), respectively." at this link Hence:
        • Type(a,f,b,g,c) is equivalent to  ((a,f,b,g,c)), and
        • Expression(a,f,b,g,c) is equivalent to  ((a,f,b,g,c))
        • Proof in GHCi:
    -- Test with random elements and only the outer parenthesise
    Prelude> ('b',4,True,5,False) :: (Char,Integer,Bool,Integer,Bool)
    -- Test different combinations of inner parenthesise to check the output doesn't result in an error when matching the expected type with the actual type
    -- The following (extra outer parenthesise) will compile without error
    Prelude> ('b',4,True,5,False) :: ((Char,Integer,Bool,Integer,Bool))
    -- Reflect upon the statement above from Chapter 4, which indicates a consistent syntax between Expressions and Types

    • Haskell GHC Examples
      • Autocomplete Input
        • Press TAB key (after typing some text)
      • Commands Available Listing (of the GHC Interpreter, but not Functions on any Library)
    a :: b (syntax) has semantic meaning: evaluating expression 'a' produces value of Type 'b' 
    :?  (extract of Console output below)
    Commands available from the prompt:

       <statement>                 evaluate/run <statement>
       :                           repeat last command
       :{\n ..lines.. \n:}\n       multiline command
       :add [*]<module> ...        add module(s) to the current target set
       :browse[!] [[*]<mod>]       display the names defined by module <mod>
                                   (!: more details; *: all top-level names)
       :cd <dir>                   change directory to <dir>
       :cmd <expr>                 run the commands returned by <expr>::IO String
       :complete <dom> [<rng>] <s> list completions for partial input string
       :ctags[!] [<file>]          create tags file for Vi (default: "tags")
                                   (!: use regex instead of line number)
       :def <cmd> <expr>           define command :<cmd> (later defined command has
                                   precedence, ::<cmd> is always a builtin command)
       :edit <file>                edit file
       :edit                       edit last module
       :etags [<file>]             create tags file for Emacs (default: "TAGS")
       :help, :?                   display this list of commands
       :info[!] [<name> ...]       display information about the given names
                                   (!: do not filter instances)
       :issafe [<mod>]             display safe haskell information of module <mod>
       :kind[!] <type>             show the kind of <type>
                                   (!: also print the normalised type)
       :load [*]<module> ...       load module(s) and their dependents
       :main [<arguments> ...]     run the main function with the given arguments
       :module [+/-] [*]<mod> ...  set the context for expression evaluation
       :quit                       exit GHCi
       :reload                     reload the current module set
       :run function [<arguments> ...] run the function with the given arguments
       :script <filename>          run the script <filename>
       :type <expr>                show the type of <expr>
       :undef <cmd>                undefine user-defined command :<cmd>
       :!<command>                 run the shell command <command>

     -- Commands for debugging:

       :abandon                    at a breakpoint, abandon current computation
       :back                       go back in the history (after :trace)
       :break [<mod>] <l> [<col>]  set a breakpoint at the specified location
       :break <name>               set a breakpoint on the specified function
       :continue                   resume after a breakpoint
       :delete <number>            delete the specified breakpoint
       :delete *                   delete all breakpoints
       :force <expr>               print <expr>, forcing unevaluated parts
       :forward                    go forward in the history (after :back)
       :history [<n>]              after :trace, show the execution history
       :list                       show the source code around current breakpoint
       :list <identifier>          show the source code for <identifier>
       :list [<module>] <line>     show the source code around line number <line>
       :print [<name> ...]         prints a value without forcing its computation
       :sprint [<name> ...]        simplifed version of :print
       :step                       single-step after stopping at a breakpoint
       :step <expr>                single-step into <expr>
       :steplocal                  single-step within the current top-level binding
       :stepmodule                 single-step restricted to the current module
       :trace                      trace after stopping at a breakpoint
       :trace <expr>               evaluate <expr> with tracing on (see :history)

     -- Commands for changing settings:

       :set <option> ...           set options
       :seti <option> ...          set options for interactive evaluation only
       :set args <arg> ...         set the arguments returned by System.getArgs
       :set prog <progname>        set the value returned by System.getProgName
       :set prompt <prompt>        set the prompt used in GHCi
       :set prompt2 <prompt>       set the continuation prompt used in GHCi
       :set editor <cmd>           set the command used for :edit
       :set stop [<n>] <cmd>       set the command to run when a breakpoint is hit
       :unset <option> ...         unset options

      Options for ':set' and ':unset':

        +m            allow multiline commands
        +r            revert top-level expressions after each evaluation
        +s            print timing/memory stats after each evaluation
        +t            print type after evaluation
        -<flags>      most GHC command line flags can also be set here
                             (eg. -v2, -XFlexibleInstances, etc.)
                        for GHCi-specific flags, see User's Guide,
                        Flag reference, Interactive-mode options

     -- Commands for displaying information:

       :show bindings              show the current bindings made at the prompt
       :show breaks                show the active breakpoints
       :show context               show the breakpoint context
       :show imports               show the current imports
       :show linker                show current linker state
       :show modules               show the currently loaded modules
       :show packages              show the currently active package flags
       :show paths                 show the currently active search paths
       :show language              show the currently active language flags
       :show <setting>             show value of <setting>, which is one of
                                      [args, prog, prompt, editor, stop]
       :showi language             show language flags for interactive evaluation
      • Numeric Addition
        • 1 + 1  prefix is equivalent to infix  (+) 1  1  
      • Division (rounded down to nearest Integer)
        • 3 `div`    output is  1

      • Multi-line Block Expressions (GHC)   
      • Type Checking (of Expressions)
        • Characters     :t 'a'   (returns Char)
          • Decimal (Unicode   :t '\97'  (returns Char, equiv. to 'a')
          • Hexadecimal (Unicode)   :t '\x61'   (returns Char, equiv. to 'a')
        • Load Module for Additional Functionality (instead of just Default)
        [t]  - Lists of 't' denotes Type of lists with elements of Type 't'
    import Data.Char 
     :t toUpper   (toUpper :: Char -> Char. It takes Type on left of '->' and returns Type on right of it)
     chr 97   (returns 'a') 
     :t chr  (chr :: Int -> Chr)  
    :t odd  (odd :: Integral a => a -> Bool)  (odd can be used for creating values of every Type, as it shows a Type Variable (lowercase letters) of 'a' and can take different values, supporting the Integral Type Class, which includes whole number division and operation)
    sin (-4) (NOT' 'sin -4') (parenthesis important for correct interpretation) 
        • Numbers     
          • Bounded (Fixed-precision) Integer Type  Int (Faster native, i.e. 32 or 64 bit) (+/- 536870911)
          • Unbounded (Arbitrary-precision) Integer Type Integer (Slower) (any value, no decimal, no overflow or underflow)
          • Rational Number Types  Ratio (type) syntax n % m
          • Floating-Point Types  Float (single precision) or Double
          • Conversion between Numeric Representations fromInteger or toInteger or fromRational (Floating-Point to Rational by dividing by ratio numerator by denominator fromRational (1 % 1 + 1 % 2) returns 1.5) or toRational (Rational to Floating-Point close to original value toRational (1 % 1 + 1 % 2) returns 3 % 2)
          • Load Module for Additional Functionality
     import Data.Ratio
        • Boolean
          • Short-Circuiting (Haskell uses Lazy Evaluation Model so always uses short-circuiting whereby it may stops if condition achieved after evaluating Left side of operator) && and  || e.g. 1 (True && False) || (False && not False) returns False e.g. 2 (2 == 2.1) || (2 < 2.1) || (2 > 2.1) returns False
          • List of Booleans (and and  or take a List of Booleans) e.g. or [True, False, and [False, True, True]] returns True
        • Strings    
          • Lists of Chars  :t "Hello" (returns "Hello" :: [Char], where [ x ] means type of all lists whose elements are all of Type 'x' )
        • Lists  (aka  xs ) (dfn: sequences of values of same Type) 
          • Type  :t [1,2,3] (returns [1,2,3] :: Num t => [t] )
          • Reverse Order (operates on any kind of List)  :t reverse (returns reverse :: [a] -> [a] ),   reverse [1,2,3] (returns [3,2,1] ,   reverse "abc" (returns "cba")
          • Concatenate Lists (operates on any kind of List)  :t (++) (returns (++) :: [a] -> [a] -> [a]), [1,2,3] ++ [4,5,6] (returns [1,2,3,4,5,6])
          • Restrictions (Haskell Lists are Homogenous and so can only handle elements of a Single Type). Mixing Types in Lists is erroneous and Forbidden: "abc" ++ [4,5,6] and [1,2,3,'a','b','c']
        • Linked List Operations
          • Cell Series (of 'cons' operators binding elements) that holds List Values, Next Cell Reference, End List Marker ('null' operator is empty list constructor). 1 : 2 : 3 : [] (returns [1,2,3]), 'a' : 'b' : 'c' : [] (returns "abc") 
          • Append (use : 'cons' operator)
          • Check for List Emptiness null [] (returns True)
          • Grab First Element head [1,2,3] (returns 1)
          • Grab List except First Element tail [1,2,3] (returns [2,3])
          • Error Prevention { check for List non-emptiness before applying Functions (head, tail, or Pattern Matching). Warning: Do not use Exceptions as they cause app to crash }
        • Nested Lists head[[]] returns [] o(since an empty List can be a member of a larger list)
        • Comparison == (equal), /= (not equal), >= (greater than or eq), <= (less than or eq), (greater than), (less than)    
        • If-Then-Else if True then 1 else 2 returns or if not (null ["hello", "hola"]) then (null []) else False returns True
          • Note: Entire Expression must have Same Type i.e. if True then "Goodbye" else "Hello"  Forbidden: if True then 1 else "Hello"
        • Tuples
          • Dfn: Sequence of Values of different Types. Fixed length but different Types may be combined. Tuple Types reflect each of the Types of its components
          • Example:

    :t (1, "Hello")

    (1, "Hello") :: Num t => (t, [Char])

        • Pairs and Projection Functions
          • Example:

    fst (1, "Hello")

    snd (1, "Hello")


    :t fst

    fst :: (a, b)

        • Errors (Static Errors) & Exceptions (Dynamic Errors)
          • Exceptions occur during program execution
      • Examples
        1. Append two Lists in a List
          [1,2,3] : [4,5] : []
          returns [[1,2,3],[4,5]]
        2. Check if List is Empty or its First element is Empty
          if null[[],[1,2]] || null(head[[],[1,2]]) then True else False
          returns True
        3. Check and return True if List has only one elementif length['a'] == 1 then True else False returns True
        4. Concatenate two Lists from different Lists (head["abc","de"]) ++ head(tail["wrong","de"]) returns "abcde" (note importantly that Tail returns an Array, whilst Head returns a String!)
        5. Prelude> :t [1,2..4]
          [1,2..4] :: (Num t, Enum t) => [t]

          Prelude> enumFromThenTo 3 10 100
      • Exit (GHC)
    :quit   (or CTRL+D)
    Sublime Text 2 Auto-Indentation (thanks to Alberto Forni)

    • Add the following code in  Preferences > Key Bindings - User
    "keys": ["super+shift+r"],
    "command": "reindent",
    "tab_size": 2,
    "translate_tabs_to_spaces": true
    • Use it by selecting unformatted code and pressing CMD + SHIFT + R



    • 10% COMPLETE Beginning Haskell - A Project-Based Approach
    • 20% COMPLETE Developing Web Applications with Haskell and Yesod
    • DONE Scripting InDesign with JavaScript



    No comments:

    Post a Comment