**Haskell**(Intro to Functional Programming FP101x @ edX.org with Erik Meijer

**DONE EXERCISES 7/9, DONE LAB**

**Ex 1 - DUE 26th Oct**

**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),**

**DONE**

**JAM 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 LECTURES**

**,**

**DONE JAM (QUICKCHECK),**

**DONE 3/4**

**, Ex 10 (The Countdown Problem) - DUE 10th Dec**

**DONE PART 1 & 2 LECTURES**

**,**

**DONE JAM**

**,**

**DONE 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.**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**

- Statements
- Immutable State
- Imperatively update Statements (i.e. using a loop)
- Computation Method: Variable Assignment
**Expressions style**(i.e. Haskell, Java 8 Streams)

- 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

- Function (tail) with argument List removes 1st elem from list

- Function (nth elem) with argument List returns specified elem
- Indexing as it linearly traverses the list across its length (not a constant time operation)

- Function (take first n elem) with argument List returns first n elems

- Function (drop first n elem) with argument List drops first n elems

- Function (length) with argument List returns amount of indexes (time linear in length of list)

- Function (sum, product, append, reverse, init) with argument List returns common sense outputs

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**

**meaning:**add Function takes Tuple comprising of two integers and returns an Integer result)

**Equivalent**is*add (x, y) = x + y***Example 2**

**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 Convention:**In 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

**a**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:

**meaning:**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 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 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)**:**

True && True = True

True && False = False

False && True = False

False && False = False

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

_ && _ = False

**Preferred**version (most Efficient)

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)

**Note #4:**Patterns Matching should**Not Repeat Variables**(variables inside Pattern Matching must be unique)**Example**(causes Error)

**Lists**(when Defining Functions)**Constant Lists**- Create non-empty list by adding elements to the start of the list with
**cons**(:)**operator**

**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 (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 (_: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)

**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]

where

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

**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)**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**( + )**, or Left**(**x**+ )**or Right**( +**y**)****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**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**(List Comprehension Notation)****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****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:**

**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):**

**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****:**

**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 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****:**

**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 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]**CONTINUED**

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

CONTINUED**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

**meaning:**zip has Type, List of 'a', to List of 'b', to List of pairs of a, b)

**Example 1****:**

[('a',1),('b',2),('c',3)]

pairs xs = zip xs (tail xs) (

> pairs [1,2,3,4]

sorted xs =

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

> sorted [1,2,3,4]

positions x xs =

[i | (x', i) <- zip xs [0..n], x == x']

where n = length xs {

> positions 0 [1,0,0,1,0,1,1,0]

**Example 2****:**

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 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****:**

**=>**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:**5 {

**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 xs =

length [x | x <- xs, isLower x]{

> lowers "Haskell"

factorial 4

= product [1..4]

= product [1..4]

= product [1,2,3,4]

= 1*2*3*4

{

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

(

filter p xs = [x | x <- xs, p x]

6

6

length :: [a] -> Int

length [] = 0 (case where empty list)

one = \s z -> s z {

two = \s z -> s (s z) {

= \s z -> (s . s) z {

= \s -> s . s {

2 x 3 = 2 + 2 + 2 = 6

two = \s -> s . s {

three = \f -> f . f . f {

six = \s -> (s . s) . (s . s) . (s . s) {

**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**{**I**f 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 :: Int -> Int

factorial n = product [1..n] {

factorial n = product [1..n] {

**meaning:**take the List of values between 1 to 'n' and multiply them together }**Execution**

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

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) {

-- Execution

factorial 3

= 3 * factorial 2

= 3 * (2 * factorial 1)

= 3 * (2 * (1 * factorial 0))

= 3 * (2 * (1 * 1))

= 3 * (2 * 1)

= 3 * 2 {

product :: [Int] -> Int

product [] = 1 (case where empty list, product maps an empty list to 1, where 1 is the

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

length :: [a] -> Int

length [] = 0 (case where empty list)

**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 {

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

reverse :: [a] -> [a]

reverse [] = []

**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] (

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]

**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 }

[4,5]

-- 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 }

[4,5]

**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

where

smaller = [a | a <- xs, a <= x]

larger = [b | b <- xs, b > x] (

qsort [] = [] (case of empty list, it is already sorted)

qsort (x:xs) =

qsort smaller ++ [x] ++ qsort larger

where

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)

**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)

**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])

**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 }

[1,2]

-- Execution

init [1,2,3]

= { applying init }

1 : init [2,3]

= { applying init }

1 : 2 : init [3]

= { applying init }

1 : 2 : []

= { list notation }

[1,2]

**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

-- 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:****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.**Embedded Domain-Specific Languages**(Collections of Higher-Order Functions) may be defined, for which associated APIs may be created and exposed**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]

[2,4,6,8]

map f xs :: [f x | x <- xs]

**{ 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) }[2,4,6,8]

**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

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]

[2,4,6,8,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
to traverse one List and return another List, then if we perform another**Fusion Dfn:**Given two Functions, with one of them using foldr**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 H****igher-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 v 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

product = foldr (*) 1

or = foldr (||) False

and = foldr (&&) True

**Example #3****foldr**Implementation of Sum:

-- Execution

sum [1,2,3]

foldr (+) 0 (1:(2:(3:[])))

1+(2+(3+0)) 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 0 }**{ note:**structure of List is maintained, as__foldr is homomorphic over Lists__, it simply replaces the Constructors by another Function}6

**Example #4****foldr**Implementation of Product:

-- Execution

product [1,2,3]

foldr (*) 1 (1:(2:(3:[])))

1*(2*(3*1))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 1 }6

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

length :: [a] -> Int

length [] = 0 (case where empty list)

length (_:xs) = 1 + length xs {

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

**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]

1+(1+(1+0))

3

length = foldr (Î»_ n -> 1+n) 0

reverse [] = []

reverse = foldr (Î»x xs -> xs ++ [x]) []

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 }1+(1+(1+0))

3

length = foldr (Î»_ n -> 1+n) 0

**{ meaning:**based on the above, length may be defined in terms of**this way }****foldr****Example #6 Recall Definition of Reverse Function**(Previously Shown**):**

reverse [] = []

reverse (x:xs) = reverse xs ++ [x] {

reverse [1,2,3]

(([] ++ [3]) ++ [2]) ++ [1]

[3,2,1]

**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]

[3,2,1]

reverse = foldr (Î»x xs -> xs ++ [x]) []

**{ meaning:**based on the above, length may be defined in terms of

**this way }**

**foldr****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. a 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 {

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) ->

c2i x =

-- Implementation

c2i two = (\s z -> s (s z)) (+1) 0 {

= (+1) ((+1) 0) {

= (+1) 1 = 2 {

{

c2i two = (\s z -> s (s z)) ('*':) "" {

= ('*':) ('*':"") {

= '*':"x" = "

**a**-> ac2i 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 Representation**, to 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 #2****:**Instantiate Church Numerals to other Things like Strings (other than Integers)

type Church = (a -> a) ->

c2i x = x ('*':) "" **a -> a**{

**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)****0**) {**Note:**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.**[...]**)**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:**mechanism allows for Pattern Matching in Haskell**case****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" }

**[('a',"bc")]**

**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 }

**[('a',"bc")]**

**More Complex Parsers****Note #1:**Use of the**Choice****+++**operator (aka "**OR ELSE")****Example #1: '**Combine**p +++ q**' Parser 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**Parse**' Parser 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)****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"**`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"**`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

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**

**{ 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) }

-- LIST COMPREHENSION NOTATION (EQUIVALENT)

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 }
^
+-------+ 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))

**-- REMOVE DUMMY CONSTRUCTOR "S" IN APPLICATION FUNCTION**

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

apply (S f) x = f x

**-- ST DEFINED AS A MONADIC TYPE**

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 []

else

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

**Example #3:**Sequence Two Monadic Expressions (discarding result Value produced by the First)

**{ 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)

**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:**may be used with**sat****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**

**else**

**failure**

**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(similar to applying a**Zero**or More times**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 ofDigits from a given String (i.e. similar to parsing an actual language) by combining multiple different parser Functions previously defined**One**or More

**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

__Digits) }__

**One**or More**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 }

**[("1234","")]**

**> 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) }

**GHCi Testing by Loading Sample Parse.lhs File.**Note that**.lhs**is Literate Programming also here on markdown application, which comes in handy if you want to explain more than you write code, and where the syntax > is called bird-tracks / Bird's feet in honor of Richard Bird

**-- 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"

[('A',"")]

*Parsing> parse (pA +++ pB) "A"

[('A',"")]

*Parsing> parse (pA +++ pB) "B"

[('B',"")]

*Parsing> parse (pA +++ pB) "AB"

[('A',"B")]

*Parsing> parse (pA +++ pB) "BAB"

[('B',"AB")]

**-- Test out the example parser**char 'a' +++ return 'b'

*Parsing> let test = char 'a' +++ return 'b'

*Parsing> parse test "yourTestStringHere"

[('b',"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"`

`[('1',"23")]`

**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,**I/O Monad****Beginner-I/O**(stuff done so far)**:****Batch Programs:**

**Batch Program ] ->**Outputs (i.e. print on REPL loop of GHC Interpreter)

**Normal I/O**(stuff we want to do)**:****Imperative Program:**

**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**{**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**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 s**and 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**

**}**

**else**

**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**

**}**

**else**

**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!"**

**else**

**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

**x**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"**

**"-as--ll"**

versus**Compare >>**Symbol(**>>=**Symbol*thx raphexion)*(Reference Material (*thx root_42)*)**{ meaning:**concatenates Monads**>>**Symbol__without__piping through the result of the previous step, whilstdoes pipe the previous step results through, see example below }**>>=**Symbol

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

Just 7

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

Just 45

versussequence_**Compare**(**sequence***thx SherMM, Gregl & headinthebox)*

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

1

2

3

4

5

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

[True,True,True]

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**

-- 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**

-- 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)

**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 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)

**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

**Rectangle**take 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)

**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**Nat**contains the following infinite Sequence of Values

**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**) }

...

..

and

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:

**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

**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))**

**5**

**(Node (Leaf 6) 7 (Leaf 9))**

Recursive Functions on Structure of Binary Trees**Algorithm #1 -**- 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***(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**

**l**

**(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 m**(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

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**

**Problem**

-- given numbers

**1 3 7 10 25 50**

**+ - * ÷**

**Rules**

**1,2,3..**

**Goal**

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

**Solution**

-- 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!

**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

data Op = Add | Sub | Mul | Div

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 :: 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 -> Boolvalid :: 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

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

**n**is greater than 0 }

**val (Val n) = [n | n > 0]**

**{ meaning:**if given an Expression that is the application

**App**of an Operator

**o**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

**o**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 }

**[[],[1],[2],[1,2],[2,1]]**

**{ 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

**e**, and 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

**e**must Evaluate to the Target number

**n**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 }

**[([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4])]**

**{ 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

**n**}

**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****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).

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

**prop_reverse()->**

**?FORALL(L,list(int()),**

**equals(reverse(reverse(L)),L)).**

**eqc:quickcheck(reverse:prop_reverse()).**

....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 }

**prop_wrong()->**

**?FORALL(L,list(int()),**

**equals(reverse(L),L)).**

-- Test giving the False Property to QuickCheck

**eqc:quickcheck(reverse:prop_wrong()).**

**{ 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.

[-1,-3]

[-3,-1] /= [-1,-3]

Shrinking xxx.x..xx(3 times)

[0,1]

[1,0] /= [1,0]

false

**Example #1 - Simple Key Value Store**

**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 K is a member of the List of Keys S in the Model of the Key Value Store State }

**lookup_args(_) ->**

**[key()].**

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

**eq(Res/=false,**

**lists:member(K,S)).**

%% 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(_) ->**

**[key(),val()].**

**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(_) ->**

**[key()].**

**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),**

**begin**

**kv:start(),**

**Result = run_commands(?MODULE,Cmds),**

**kv:stop(),**

**check_commands(?MODULE, Cmds, Result)**

**end).**

-- 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}

true

**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: r**e-run the same test to see same failures }

**eqc:check(kv:prop_kv_verbose()).**

**{ meaning: r**un 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 }

**delete(8)**

(0,a)

/ \

(10,e)

/ \

(9,e)

/ \

(6,e)

/ \

**{ 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

**RR**h, 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) ->**

**leaf;**

**delete(K,{node,L,KN,VN,R}) ->**

**if K<KN ->**

**{node,delete(K,L),KN,VN,R};**

**K==KN ->**

**merge(L,R);**

**K>KN ->**

**{node,L,KN,VN,delete(K,R)}**

**end.**

**merge(leaf,R) ->**

**{ meaning:**case of Empty Leaf }

**R;**

**merge(L,leaf) ->**

**{ meaning:**case of Empty Leaf }

**L;**

**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)

-- substitute Definition for 'square', and (7) for n and then substitute RHS

**square (7)**-- substitute Definition for 'square', and (7) for n and then substitute RHS

**7 * 7**

-- then evaluate it

**49**

**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) **Innermost Reduction -**Innermost Expression (Redex) that can be reduced is always reduced**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) }=

**1****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**

=

49

**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**

**? 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 }

[1,1,1,1,1]

**? take 5 [1..]**

**{ meaning:**

**Infinite List**of 1's is the same as

**ones**}

(

**CONTROL)**

**(DATA)**

[1,1,1,1,1]

**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)- Write down the List 2,3,4...
- Mark first Value 'p' in the List as Prime
- Delete (Filter out) all multiples of 'p' from the List (as they are not Primes)
- 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)

**p**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 }

[2,3,5,7,11,...

**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

**> take 7 primes**

**{ meaning:**constrained to Finite, lazily only doing enough work to meet constraint }

**[2,3,5,7,11,13,17]**

-- select primes less than 15

**> takeWhile (<15) primes**

[2,3,5,7,11,13]

**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 \,

,

|_| Morphism |_| |_| **A**--------------> ,**B**-----------> ,**C**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

,

Functor **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**

Functor

________________ F ________________

/ | \,,

**FC A**|

**n Natural**

**FC B**

\_________________

**|,,**__Transformation__/''**G**

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

**Commutating Diagram**

f : A --> B

Ff

**F A**------------>

**F B**

| \ |

n B | \ | n B

| \ |

| \ |

**G A**------------>

**G B**

Gf

**F B**

**F A**

**F B**

**F A**

n B . Ff = Gf . n A

**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: http://eclipsefp.sf.net/updates
- 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**- SublimeHaskell
- Help
- Cabal Bug Discussion - The package 'text' requires Cabal library version ... but no suitable version is installed"
- Uninstall Cabal Package
- Dependencies between Buildwrapper, GHC, and Cabal (Q5)
- Haskell-Docs
- GHC-Mod
**PENDING IntelliJ IDEA Community Edition**(Thanks to Ashley Towns!!)- Download & Install
- Install Haskell with GHC for Mac OSX (self-contained installer)
- Install Haskforce for IntelliJ (do not use brew install)
- Help

**NICE FPComplete**(Browser-based Haskell IDE with GitHub Integration)**Haskell Compiler (Standard)****GHC**(Glasgow Haskell Compiler)**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**

**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**{ 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**(Haskell)****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)**https://www.haskell.org/tutorial/goodies.html. Note the statement*"Notice that expressions and types have a consistent syntax. If t*at this link https://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-650004.1.2. Hence:_{i}is the type of expression or pattern e_{i}, then the expressions (\ e_{1}-> e_{2}), [e_{1}], and (e_{1},e_{2}) have the types (t_{1}-> t_{2}), [t_{1}], and (t_{1},t_{2}), respectively."**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)

('b',4,True,5,False)

**-- 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**))**
('b',4,True,5,False)

**-- 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****(+) 1 1****Division**(rounded down to nearest Integer)**3****2**output is**1****Multi-line Block Expressions (GHC)**

:{

1

+2

:}

**Type Checking**(of Expressions)

**Characters****:t 'a'**

**Decimal**(Unicode**:t '\97'**(returns Char, equiv. to 'a')

**Hexadecimal**(Unicode)**:t '\x61'**

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 aType Variable(lowercase letters) of 'a' and can take different values, supporting the IntegralType 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****: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).(returns "abc")**1 : 2 : 3 : []**(returns [1,2,3]), 'a' : 'b' : 'c' : [] **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**1**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")**

**outputs**

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

**Pairs and Projection Functions****Example:**

**fst (1, "Hello")****outputs**

**1**

**snd (1, "Hello")****outputs**

**"Hello"**

**:t fst****outputs**

**fst :: (a, b)**

**Errors (Static Errors) & Exceptions (Dynamic Errors)****Exceptions**occur during program execution

**Examples**- Append two Lists in a List
returns[1,2,3] : [4,5] : []**[[1,2,3],[4,5]]** - Check if List is Empty or its First element is Empty
returns Trueif null[[],[1,2]] || null(head[[],[1,2]]) then True else False - Check and return True if List has only one element
**if length['a'] == 1 then True else False**returns True -
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!)
- Prelude> :t [1,2..4][1,2..4] :: (Num t, Enum t) => [t]

Prelude> enumFromThenTo 3 10 100[3,10,17,24,31,38,45,52,59,66,73,80,87,94] **Exit (GHC)**

:quit(orCTRL+D)

**GHCi File**( .ghci )- DONE READ GHCi Wiki of Customisation Tips & Tricks
- Shell Scripts to Load Commands from other File Paths
- Hoogle Integration (External CLTs)
- HLint Integration
- Extensions to GHCi (i.e. GHC on Acid)

**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**

**Events**

- ATTENDED (thanks to and on behalf of
**Oomph**) YOW! Australia Developer Conference 2014 - BRISBANE, 8 - 9 Dec 2014 - Yowsers! the speaker line-up looks amazing!

**Books**

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

**Links**

- Mozilla Firefox Developer Edition
- John Carmack on Inlined Code and Functional Programming in C++ (the first link is gold)
- Haskell Platform Website
**Haskell Language Specification**- DONE Chapter 2 - Lexical Structure
- DONE Chapter 3 - Expressions
- SKIM READ Chapter 4 - Declarations and Bindings
- Hoogle (Haskell API Library Search Engine
- HLint (Haskell code improvement Tool)
- Cabal User Guide & Package Installation Guide
- Some Random Animations
- Haskell Links
- WIWINWLH
- Learn You a Haskell
- Haskell Wiki problems and solutions
- Someone elses Blog describing approach to List questions in Programming in Haskell book and here for Recursive functions and here for Functional Parsers
- Haskell Cheatsheet
- Graham Huttons Uni Websites
- Crossword
- Haskellcast
- Haskellcast Sourecode
- Haskell from Scratch
- Text Recognition (since all the code in the multiple choice answers is in PNG image format, it's not selectable to copy and paste, so to save having to type them all out, consider one of these options to potentially save you time)
- PicaText (Allows copying text embedded in image on edX)
*Thx zydox.* - Adobe Acrobat Pro XI (Picatext may be a viable option but it's $3.99, but if you've already got Adobe Acrobat XI Pro like me (it comes as part of Adobe Creative Cloud), which has OCR Text Recognition too. I just tested it successfully using Acrobat. I'm using a 15" screen size. I simply change the zoom level in my browser to 120% (to get a high quality screenshot which is necessary), switch to Adobe Acrobat XI Pro (without any document open already so the browser is visible) and go to the menu (File > Create > PDF From Selection Capture), then simply drag to select all the answers associated with the question in the browser. This automatically generates a PDF file and opens it in Acrobat, then go to (View > Tools > Text Recognition) or use the side-panel buttons, click "In This File", then edit the Settings if necessary (to minimise downsampling), then click "OK" (this causes it to add an invisible layer of searchable text on top of the text image, allowing you to then select, copy, and paste the code into GHCi). Lastly select the text, copy and paste it into your favourite editor, fix up any conversion errors and indentation (at least 95% of was converted correctly for me), and then paste into GHCi
- Evolution of Haskell Programmers LoL!!
- Monad Laws
- WikiBooks Haskell
- Haskell QuickCheck
- Foundations of Programming Object-Oriented Design
- TODO Real World Haskell Book
- TODO Graphical User Interfaces in Haskell
- QuickCheck CI (free for open source)
- Creating a New Haskell Program and Library Packaging Another Example
- Introduction to QuickCheck and Another Example
**Travis CI****Getting Started Guide**- Login to Public Repos or
**Login to Private Repos** - Activate GitHub Webhook (flip switch for certain repos)
- Create .travis.yml with Language Settings and Test with Travis Lint
- Git push .travis.yml to GitHub to trigger Travis worker (of chosen Language)
- Yesod Scaffolding
- TechBlog Realestate.com.au

## No comments:

## Post a Comment