= { 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
-- original Expression
e1 >>= λv1 ->
...
en >>= λvn ->
return (f v1 ... vn)
-- rewritten Expression using the "DO" Notation form
do v1 <- e1
...
vn <- en
return (f v1 ... vn)
- The Countdown Problem
- Transformation Development Dfn: Pattern of starting with simple and inefficient correct solution (using brute force), and then finishing by Refactoring the solution to make it more Efficient and optimised (similar to Extreme Programming). "Think like a fundamentalist but code like a Hacker" (FP101) by starting with fundamental code that is correct, and then hack on to make it more efficient
- Example: Haskell Prototyping { use Haskell code as a Prototype, then implement the same algorithm in another language }
- Countdown Problem Dfn: A numbers game that is based on a TV quiz program, similar to idiomatic developments like Haskell sudoku solver, and papers by Richard Birch.
Problem
-- given numbers
1 3 7 10 25 50
-- given arithmetic operators
+ - * ÷
Rules
All numbers must be positive natural no's (including intermediate results) i.e. 1,2,3..
Each number can be used only once when constructing expression
Goal
-- goal is to construct expression with Target Number result value of 765
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!
Search space (for this example with Target Number of 765) has 780 solutions
Search space (for another Target Number of 831) has no solutions
- Example #2: Evaluating Expressions (Bottom-Up Solution)
- Step #1 Create a Function that is a Symbolic Representation of the Expression that performs Symbolic Processing of Expressions
-- define Operators as an Algebraic Data Type
data Op = Add | Sub | Mul | Div
-- defined Evaluation Function that takes two numbers and applies the operator to an Expression
apply :: Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x `div` y
- Step #2 Encode the Rules of the Game
- Rule #1 - All operators must be applied to positive numbers
-- determine if a positive natural number results from applying an operator to two positive natural numbers (i.e. check if valid application of the operator)
valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True -- already know output of two pos given no's is a pos no
valid Sub x y = x > y -- avoid negative intermediate results that are disallowed
valid Mul _ _ = True
valid Div x y = x `mod` y == 0 -- check divisible to ensure we get a natural number
- define the Data Type of Expressions (one application that takes the operators)
data Expr = Val Int | App Op Expr Expr
- Step #3 Evaluate the Expression by either returning a Singleton List containing the resulting value, or return Empty List when Expression inside is not valid (similar to that used for Functional Parsers). It is much more convenient to use Lists than using the Maybe Type (as you can use List Comprehension)
{ meaning: defined Recursively over Expressions }
val :: Expr -> [Int]
{ meaning: if given a value n, it succeeds if the value 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 is the result of Evaluating the Expression to check if it satisfies the constraints of the game) Int )
-- valid Expressions and their Values
type Result = (Expr,Int)
-- define Function that Fuses together the Generation and Evaluation of Expressions
results :: [Int] -> [Result]
results ns = [(e,n) | e <- exprs ns { meaning: Generation of Expressions }
, n <- eval e] { meaning: Evaluation of Expressions }
-- define Function that combines the Generation and Evaluation behaviour
results [] = [] { meaning: result of Empty List is an Empty List }
results [n] = [(Val n,n)| n > 0] { meaning: Generating the combination of Expressions and their Values for a Singleton List by including a Test comprising of the Generation of an Expression Val n, whilst knowing its Value n but where it's only valid if the Value is n > 0 }
results ns = { meaning: same approach as previously described, with results called Recursively }
[res | (ls,rs) <- split ns
, lx <- results ls
, ry <- results rs
, res <- combine lx ry]
-- define Combine Function that Recursively checks that the Results are valid
combine' :: Result -> Result -> [Result]
-- same as the combine method, except combine' also checks if the results are valid
combine' (l,x) (r,y) = { meaning: carry a Pair of the Expression and its Value, to allow us to check if the result is valid whilst we're generating the Expressions }
[(App o l r, apply o x y)
| o <- [Add,Sub,Mul,Div]
, valid o x y]
-- new Function that solves the Countdown Problem
solutions' :: [Int] -> Int -> [Expr]
solutions' ns n =
[e | ns' <- choices ns { meaning: take the List of all the choices }
, (e,m) <- results ns' { meaning: calculate results given List of choices }
, m == n] { meaning: check if result is what we want }
--implementation of the Example with these alternative Functions takes about 0.04 sec to find the first solution and less than 4 sec to find all solutions (10 times faster)
solutions' [1,2,7,10,25,50] 765
- Further Improved Solution { whilst we have previously already improved the first solution by eliminating invalid expressions early, we can further improve performance by exploiting Symetries of Simple Arithmetic Properties based on the fact that many Expressions are essentially the same, and to further reduce the search and solution spaces. Eliminates evaluation of the Expressions below on the LHS, as they'll be considered the same as those on the RHS }
x * y = y * x { meaning: Multiplication is Commutative, so we do not need to check these two results separately }
x * 1 = x { meaning: 1 is the neutral element for Multiplication, may as well just use x instead of evaluating }
- Improve the Previous Definition Valid Expression (with Exploiting Properties)
- Strengthening the valid predicate to account for Commutativity and Identity Properties
valid :: Op -> Int -> Int -> Bool
valid Add x y = True { meaning: valid since adding two positives }
valid Add x y = x <= y { meaning: valid if x less than or eq y (force Bias Representation so the Commutative Expression Add y x is no longer valid) }
valid Sub x y = x > y { meaning: constraint to ensure always positive result }
valid Mul x y = True
valid Mul x y = x <= y && x != 1 && y != 1 { meaning: valid if x less than or eq y, and x != 1 (force Bias Representation so the Commutative Expression Mul y x is no longer valid, as with case where 1 is the Neutral Element of Multiplication i.e. x == 1 or y == 1) }
valid Div x y = x `mod` y == 0 && y != 1 { meaning: constraint to ensure within integer domain, and that when divide x by 1 this is the same as just x }
--implementation of the Example with these further improved alternative Functions gives about 20 times less valid Expressions
and about 16 times less valid solutions (since we've eliminated duplicate solutions). It finds one solution 2 times faster, and all the solutions about 7 times faster (about 0.5 sec).
solutions'' [1,2,7,10,25,50] 765
- Testing & Debugging with QuickCheck using Erlang (with John Hughes)
- Dfn: Random testing tool. "Don't Write Tests! Generate Them"
- Haskell QuickCheck
- Benefits:
- Allows wider variety of Tests than by hand (including those not thought of)
- Allows Tests at Higher Level against Specification of code (Properties, Models)
- Presents Minimal Failing Test Cases that are ready to Debug (so you don't have to try and simplify the failure yourself)
- Test code is 10x smaller than traditional test code and Scales
- Ordinary Unit Test { call a Function on sample data and match result against expected answer }
- QuickCheck Test
{ meaning: define a Property of a Function reverse(), that tests for all L, where L is a List of integers, by QuickCheck generating random Lists of integers as Test Data, and since we cannot predict the result of reverse() on an arbitrary List, we will instead test a Property of reverse, such that when we reverse an initial List twice, the result we get is equal to the initial List that we started with }
-- QuickCheck Function Definition of a True Property
prop_reverse()->
?FORALL(L,list(int()),
equals(reverse(reverse(L)),L)).
-- Test by running QuickCheck in shell, passing it the Property as an argument. Randomly generated tests are performed and success of each test indicated by a dot.
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
-- example of its capabilities
kv:start() ==> true
kv:insert(1,a) ==> ok
kv:insert(2,b) ==> ok
kv:lookup(1) ==> a
kv:lookup(2) ==> b
kv:delete(1) ==> ok
kv:lookup(1) ==> false
kv:stop() ==> ok
-- Function Definitions
{ meaning: Note that Key Value Store kv has Internal State, whereas the Function reverse() did not. The Internal State of kv needs to be Modelled in order to produce Sensible Tests. We will Generate Tests that are Sequences of Calls to an API, and use the Model of the State to define postconditions for each operation }
%% Generators
key() ->
nat(). { meaning: Generate a random natural number for key }
val() ->
oneof([a,b,c,d,e]). { meaning: Value one of randomly chosen atoms }
%% State Machine
initial_state() ->
[]. { meaning: we have Modelled the State of the kv as just a List of Keys that should be defined, and is initially an Empty List. Note: We do not need to Model the entire kv Store to produce useful Tests }
%% Lookup
{ meaning: for each operation we define a Generator, by specifying how to produce a List of Arguments for Lookup, by specifying, to pick a key(), and by specifying a postcondition that says when we lookup the Key K, then the result Res we get should be different from False, only if the Key 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: re-run the same test to see same failures }
eqc:check(kv:prop_kv_verbose()). { meaning: run an Instrumented version that gives more information. Note that internally, the KV Store is using an Ordered Binary Tree, and given that we have a verbose version of the Property that we can run the same test on, and which will display the Trees that are constructed at each Step. Using the graphical Tree result, we can visually see that we have the situation below for delete, where the 6 is to the Right of a 9, which Breaks the Ordered Invariant, as it should be to the Left, and is the reason it wasn't found }
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 RRh, and then Recursively merge merge(RL,LR)the Right Sub-Tree of the Left Node RL, and the the Left Sub-Tree of the Right Node LR R. Note that if it the code was erroneously merge(LR,RL), then a failure would occur in QuickCheck due to incorrect ordering }
-- codebase for delete function
delete(_,leaf) ->
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)
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
-- generate Finite Lists by taking elements from Infinite Lists
? take 5 ones { meaning: take defined as Induction over the Structure of the List, such that each time ones Pattern Matches on that List, it Evaluates just enough to get the next Value, so we nicely terminate }
[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
-- select first 6 primes
> 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 \,
, A --------------> , B -----------> , C
|_| Morphism |_| |_|
w w w
- Functor Rules:
- Functor applied to Object is a Generic Type
- Functor applied to Morphisms is the familiar Map Function
- Key 1:
- Category of Small Categories (SC) { Categories (CAT) as Objects }
- Morphism notion (aka Functors)
Category of Small Categories Diagram
Small Categories F G
, SC A ------------> , SC B ---------> , SC C
Functor
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
- PENDING IntelliJ IDEA Community Edition (Thanks to Ashley Towns!!)
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
