错误error 和例外Exceptions

错误error 和例外Exceptions

错误error
这是一个error 功能的例子

nth :: Int -> [a] -> a
nth n [] = error "Insufficient items in list"
nth 0 (x:xs) = x
nth n (x:xs) = nth (n-1) xs
1
2
3
4

不是很严重的错误
• 有时虽然您希望能够从错误中恢复，但不是只是轰炸程序
• Maybe 类型是执行此操作的一种方式。它被定义为：

data Maybe a = Nothing | Just a
			deriving (Eq,Ord,Read,Show)
1
2

• 因此，使用 Maybe 类型，我们可以：

nth’ :: Int -> [a] -> Maybe a
nth’ n [] = Nothing
nth’ 0 (x:xs) = Just x
nth’ n (x:xs) = nth’ (n-1) xs
1
2
3
4

现在，如果我们愿意，我们可以从错误中恢复……如果我们什么都没有(Nothing)就return；如果我们有 Just 的东西(Just a)，我们可以使用某物
• 我们没有关于出了什么问题的信息…… Haskell
还提供了一个 Either 类型，它携带关于两者的信息即成功和失败，例如：

safeDiv :: Double -> Double -> Either String Double
safeDiv x 0 = Left "Division by zero"
safeDiv x y = Right (x / y)
1
2
3

“右”部分是正确答案，“左”部分是错误的
回答

例外Exceptions
• Haskell 也有异常（和异常处理）机制
• 当我们谈到 monad 时，我们会看看这些

“倒计时是一个流行的测验程序，一直在运行
自 1982 年以来的英国电视，包括我们的数字游戏
应称为倒计时问题。问题的本质是如下：
给定一个数字序列和一个目标数字，尝试构造一个
表达式，其值为目标，通过组合来自的一个或多个数字使用加法、减法、乘法、除法和插入语。”
例子
• 顺序：1、3、7、10、25、50
• 目标：765
• 可能的解决方案：(1+50)*(25-10)
• 此示例实际上有 780 种不同的解决方案。
• 如果我将目标更改为 831（但保持相同的序列），则没有单一的解决方案。

规则
• 所有数字，包括中间结果，都必须是正自然数（1,2,3，…）。
• 每个源编号最多只能使用一次构造表达式。
• 我们从电视上采用的其他规则中提炼出务实的原因。

基础Foundations

data Op = Add | Sub | Mul | Div
instance Show Op where
	show Add = "+"
	show Sub = "-"
	show Mul = "*"
	show Div = "/"
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	

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

表达式Expressions

data Expr = Val Int | App Op Expr Expr
instance Show Expr where
	show (Val n) = show n
	show (App o l r)
		= brak l ++ show o ++ brak r
			where
			brak (Val n) = show n
			brak e
			= "(" ++ show e ++ ")"
eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r)
	= [apply o x y | x <- eval l
					, y <- eval r
					, valid o x y]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

生成可能的组合

subs :: [a] -> [[a]]
subs [] = [[]]
subs (x:xs)
	= yss ++ map (x:) yss
		where yss = subs xs
		
interleave :: a -> [a] -> [[a]]
interleave x [] = [[x]]
interleave x (y:ys)
	= (x:y:ys)
		: map (y:) (interleave x ys)

perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs)
	= concat (map (interleave x)
		(perms xs))
		
choices :: [a] -> [[a]]
choices
	= concat . map perms . subs

split :: [a] -> [([a],[a])]
split [] = []
split [_] = []
split (x:xs)
	= ([x],xs)
		: [(x:ls, rs)
			| (ls, rs) <- split xs]

values :: Expr -> [Int]
values (Val n) = [n]
values (App _ l r)
	= values l ++ values r
	
solution :: Expr -> [Int] -> Int -> Bool
solution e ns n
	= elem (values e) (choices ns) 
		&& eval e == [n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

subs 是得到[a]的所有组成成分,包含[]
interleave是在不同地方插入a但是不会重复
perms 是将所有[a]的元素重新排列组合,同样不会重复
concat (map (interleave x) (perms xs)) 的顺序是
1.map (interleave x) (perms xs)
2. contact
可是map (interleave x) (perms xs) 需要判断这其中的先后顺序吗?
split 是当例子里面有n个(n>=2)元素的时候仅仅把例子分成两部分,并且前面的list从1逐渐增加一直增加到(n-1)个元素

现在来自这些组合的表达式

exprs :: [Int] -> [Expr]
exprs [] = []
exprs [n] = [Val n]
exprs ns
	= [e | (ls,rs) <- split ns
	, l <- exprs ls
	, r <- exprs rs
	, e <- combine l r]
	
combine :: Expr -> Expr -> [Expr]
combine l r
	= [App o l r
		| o <- [Add,Sub,Mul,Div]]
1
2
3
4
5
6
7
8
9
10
11
12
13

浪费:
• 许多被考虑的表达式通常是无效的——无法评估。
• 对于我们的示例，在 3300 万个可能中只有大约 500 万个表达式是有效的。
• 将生成与评估相结合将允许更早地拒绝无效的表达。

type Result = (Expr,Int)
results :: [Int] -> [Result]
results [] = []
results [n]
	= [(Val n,n) | n > 0]
results ns
	= [res | (ls,rs) <- split ns
		, lx <- results ls
		, ry <- results rs
		, res <- combine' lx ry]

combine’ :: Result -> Result -> [Result]
combine' (l,x) (r, y)
	= [(App o l r, apply o x y)
		| o <- ops, valid o x y]
		
solutions’:: [Int] -> Int -> [Expr]
solutions' ns n
	= [e | ns’ <- choices ns
		, (e,m) <- results ns, m == n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

我们不必尝试所有可能的有效表达式。
本质上，我们只需要在我们的有效功能就足够了：

valid :: Op -> Int -> Int -> Bool
valid Add x y = x <= y
valid Sub x y = x > y
valid Mul x y = x <= y && x /= 1 && y /= 1
valid Div x y = x `mod` y == 0 && y /= 1
1
2
3
4
5