计算机代考程序代写 compiler Haskell PROGRAMMING IN HASKELL – cscodehelp代写

PROGRAMMING IN HASKELL
Chapter 9 – The Countdown Problem
0

What Is Countdown?
❚ A popular quiz programme on British television that has been running since 1982.
❚ Based upon an original French version called ” et “.
❚ Includes a numbers game that we shall refer to as the countdown problem.
1

Example
Using the numbers
1 3 7 10 25 50
and the arithmetic operators
+-*÷
construct an expression whose value is
765
2

Rules
❚ All the numbers, including intermediate results, must be positive naturals (1,2,3,…).
❚ Each of the source numbers can be used at most once when constructing the expression.
❚ We abstract from other rules that are adopted on television for pragmatic reasons.
3

For our example, one possible solution is (25-10) * (50+1) = 765
Notes:
❚ There are 780 solutions for this example.
❚ Changing the target number to 831 gives an example that has no solutions.
4

Evaluating Expressions
Operators:
data Op = Add | Sub | Mul | Div
Apply an operator:
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
5

Decide if the result of applying an operator to two positive natural numbers is another such:
valid::Op → Int → Int → Bool valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x `mod` y == 0
Expressions:
data Expr = Val Int | App Op
6

Return the overall value of an expression, provided that it is a positive natural number:
eval :: Expr → [Int]
eval(Valn) =[n|n>0] eval(Appolr)=[applyoxy|x ← evall
,y ← evalr , valid o x y]
Either succeeds and returns a singleton list, or fails and returns the empty list.
7

Formalising The Problem
Return a list of all possible ways of choosing zero or more elements from a list:
choices :: [a] → [[a]] For example:
> choices [1,2]
[[],[1],[2],[1,2],[2,1]]
8

Return a list of all the values in an expression:
values :: Expr → [Int]
values (Val n) = [n]
values (App _ l r) = values l ++ values r
Decide if an expression is a solution for a given list of source numbers and a target number:
solution :: Expr → [Int] → Int → Bool solution e ns n = elem (values e) (choices ns)
&& eval e == [n]
9

Brute Force Solution
Return a list of all possible ways of splitting a list into two non-empty parts:
split :: [a] → [([a],[a])] For example:
> split [1,2,3,4]
[([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4])]
10

Return a list of all possible expressions whose values are precisely a given list of numbers:
exprs :: [Int] → [Expr]
exprs [] = []
exprs [n] = [Val n]
exprs ns = [e | (ls,rs) ← split ns
, l , r ,e
← exprs ls
← exprs rs
← combinelr]
The key function in this lecture.
11

Combine two expressions using each operator:
combine :: Expr → Expr → [Expr] combine l r =
[App o l r | o ← [Add,Sub,Mul,Div]]
Return a list of all possible expressions that solve an instance of the countdown problem:
solutions :: [Int] → Int → [Expr] solutions ns n = [e | ns’ ← choices ns
, e ← exprs ns’ , eval e == [n]]
12

How Fast Is It?
System: Compiler: Example: One solution: All solutions:
2.8GHz Core 2 Duo, 4GB RAM GHC version 7.10.2
solutions [1,3,7,10,25,50] 765
0.108 seconds 12.224 seconds
13

Can We Do Better?
❚ Many of the expressions that are considered will typically be invalid – fail to evaluate.
❚ For our example, only around 5 million of the 33 million possible expressions are valid.
❚ Combining generation with evaluation would allow earlier rejection of invalid expressions.
14

Fusing Two Functions
Valid expressions and their values:
type Result = (Expr,Int)
We seek to define a function that fuses together the generation and evaluation of expressions:
results :: [Int] → [Result] results ns = [(e,n) | e ← exprs ns
,n ← evale]
15

This behaviour is achieved by defining
results [] = []
results [n] = [(Val n,n) | n > 0]
results ns =
[res | (ls,rs) ← split ns
, lx , ry , res
← results ls
← results rs
← combine’ lx ry]
where
combine’ :: Result → Result → [Result]
16

Combining results:
combine’ (l,x) (r,y) =
[(App o l r, apply o x y)
| o ← [Add,Sub,Mul,Div] , valid o x y]
New function that solves countdown problems:
solutions’ :: [Int] → Int → [Expr] solutions’ ns n =
[e | ns’ ← choices ns , (e,m) ← results ns’ , m == n]
17

How Fast Is It Now?
Example: One solution: All solutions:
solutions’ [1,3,7,10,25,50] 765
0.014 seconds 1.312 seconds
Around 10 times faster in
both cases.
18

Can We Do Better?
❚ Many expressions will be essentially the same using simple arithmetic properties, such as:
x*y = y*x
x*1=x
❚ Exploiting such properties would considerably reduce the search and solution spaces.
19

Exploiting Properties
Strengthening the valid predicate to take account of commutativity and identity properties:
valid::Op → Int → Int → Bool validAddxy =
validSubxy =x>y validMulxy =
validDivxy =x`mod`y==0
x≤y True
x ≤ y True
&& x ≠ 1
&& y ≠ 1
&& y ≠ 1
20

How Fast Is It Now?
Example: Valid: Solutions:
solutions” [1,3,7,10,25,50] 765
250,000 expressions 49 expressions
Around 20 times less.
Around 16 times less.
21

One solution:
0.007 seconds
Around 2 times faster.
All solutions:
0.119 seconds
Around 11 times faster.
More generally, our program usually returns all solutions in a fraction of a second, and is around 100 times faster that the original version.
22