黄毅对《编程的本质》的笔记(6)
- 书名: 编程的本质
- 作者: Alexander Stepanov/Paul McJones
- 副标题: 英文版
- 页数: 262
- 出版社: 机械工业出版社
- 出版年: 2010
-
1.7 Concepts
template<typename Op> requires(BinaryOperation(Op)) Domain(Op) square(const Domain(Op)& x, Op op) { return op(x, x); }用haskell翻译过来，信息量一个不少：square :: a -> (a -> a -> b) -> b square a f = f a a
-
2.1 transform
power_unary 函数直接的翻译会是这样：
power :: a -> Int -> (a -> a) -> a power x n f = loop n x where loop 0 x = x loop n x = loop (n-1) (f x)而haskell标准库有更优雅的方案：iterate :: (a -> a) -> a -> [a] iterate f x = x : iterate f (f x)
iterate 生成一个无穷列表，其中的元素就是不断将 f 函数叠加的结果。从这个无穷列表中取第 n 个元素就是我们的 power 函数了。power x n f = (iterate f x) !! (n-1)
-
2.2 Orbits
使用上面介绍的 iterate 函数，这一节的 distance 函数也就一行代码的事，在叠加 f 函数的列表中查找 y 的存在：
distance :: a -> a -> (a -> a) -> Maybe Int distance x y f = y `elemIndex` (iterate f x)
这里甚至比原c++代码更优越的地方是使用 Maybe ，表达了可能存在的查找不到的情况。当然在这里查找不到就代表无限循环，实际意义不大。 -
2.3. Collision.
首先用类型来表达书中的两个概念：
type Transformation a = a -> a type Predicate a = a -> Bool
然后是实现：collision_point :: a -> Transformation a -> Predicate a -> Maybe a collision_point x f p = find (uncurry (==)) $ zip slow fast where slow = takeWhile p $ iterate f x fast = step 2 (tail slow)takeWhile p，表达当 p 不再满足时，循环终止。 step 函数用来在列表中跳过一些值，达到 slow 每迭代一次 fast 迭代两次的效果。这个没有现成的，需要自己写一个通用函数：step :: Int -> [a] -> [a] step _ [] = [] step n l = head l1 : step n l2 where (l1, l2) = splitAt n l
继续...terminating :: a -> Transformation a -> Predicate a -> Bool terminating x f p = isJust $ collision_point x f p
collision_point Maybe 类型的返回值表达可能的失败情况，isJust 将它转换成 Bool 值，成功为True，失败为False。 多解释几句，由于 Haskell 惰性按需求值的特点，时间复杂性是差不多的。 甚至这个实现比原书的更为高效，原书代码 slow 和 fast 两条路径会对 f 做重复的调用，每次循环对 f 调用3次，其中有一次是多余的；在Haskell的实现中， fast 路径共享了 slow 路径的迭代过程，节省了1/3的调用。 如果修改原 c++ 代码，共享这 1/3 的调用的话，代码就要变得丑陋很多了。 可以看出惰性函数式语言使用无穷列表来代替循环的模式，还是有不少优势的，代码更容易理解（这个可能见仁见智，想听听大家的意见），更具有复用性（对f的迭代过程 iterate，迭代的终止条件 takeWhile p，slow fast两条路径的循环都是分离的，模块化的），甚至不容易出现多余的计算。 -
Chapter 3. Asso
这本书最有意思的地方倒不是这些算法的实现，而是作者认真地去确定算法的概念，接口，需要满足的数学属性，前置条件后置条件这些东西，并用c++伪代码表达出来，虽然不是非常严格。应该算是所谓的面向契约编程了。 而这些正是Haskell类型系统最擅长的，书中大部分使用c++伪代码表达的契约很容易使用 Haskell 真实的代码表达出来。 表达二元操作符的接口
type BinaryOperation = a -> a -> a
操作符必须满足结合律:associative op = \a b c -> ((a `op` b) `op` c) == (a `op` (b `op` c))
可以使用QuickCheck验证该属性:> import Test.QuickCheck > quickCheck $ associative (+) +++OK, passed 100 tests.
继续...power :: BinaryOperation a -> a -> Int -> a power op a n = (iterate (a `op`) a) !! n
定理 3.1(power op a n) `op` (power op a m) == (power op a (n+m))
定理 3.2(power op (power op a n) m) == (power op a (n*m))
同样我们可以QuickCheck 对这些定理进行暴力验证。 甚至可以使用数学归纳法证明他们！这一点可以参考 The Haskell School of Expression 中关于证明函数式程序的章节。 3.2. Computing Powers ================== 上面的 power 有点小问题，修正如下：power1 op a n = (iterate (a `op`) a) !! (n-1)
如果 op 操作符满足结合律，我们可以得到更高效的 power 实现：power2 op a n | n <= 1 = a | otherwise = case n `mod` 2 of 0 -> power2 op aa (n `div` 2) _ -> (power2 op aa (n `div` 2)) `op` a where aa = a `op` a同样我们使用 QuickCheck 暴力验证这两个实现的等价性：> quickCheck $ \a b -> power1 (+) a b == power2 (+) a b *** Failed! Exception: 'Prelude.(!!): negative index' (after 1 test and 1 shrink)
很遗憾测试失败，失败信息说得很清楚，(!!) 遇到负数索引报错了，再次修改power1的实现，处理n为负数的情况：power1 op a n | n < 1 = a | otherwise = (iterate (a `op`) a) !! (n-1)重新测试：> quickCheck $ \a b -> power1 (+) a b == power2 (+) a b +++OK, passed 100 tests.
-
第1页
阅读后记之前看完本书对其与haskell typeclass类似的编程风格大为惊喜。今天才了解到，这个概念其实曾是一个c++0x正式的proposal( http://en.wikipedia.org/wiki/Concepts_(C%2B%2B) )，看完这个proposal再看本书代码就容易理解了，可惜被拒了。不过就算被接受，c++模板也还是很难用啊。。。
15人推荐