※ 引述《ilway25 (Nick)》之铭言：
: ※ 引述《subtropical (风大雨大)》之铭言：
: : 几个问题请教大家
: : 1.所谓pure和impure的差别？
: : 我的理解是：
: : pure: Output跟input直接相关 可预测
: : impure: Output会受到环境的影响 不可预测
: : 但还是觉得不清不楚的...
: : 2.有关exponential
: : expt :: Integer -> Integer -> Integer
: : expt x 0 = 1
: : expt x n = x * expt x (n-1)
: : 这个方法好像需要用到很多空间？
: : (原因是因为乘法循环的关系)
: : 乘法是 n*(n-1)*(n-2)*..*1 -> n-1次吗??
: : 书上有提到一位Dirk提出用even跟odd算expt的方法，怎么用haskell表示呢？
: 我也是 Haskell 新手，若有错还麻烦指正
: 1. 可以看看这个
: http://stackoverflow.com/questions/4382223/pure-functional-language-haskell
这边提到用 side-effect 来区分，其实不大有效，主要原因是
要严格定义 side-effect 有实务上的麻烦，这是依照抽象化的层次而定，
因为 CPU 内的 program counter (或 instruction pointer）会改变，
必须讲清楚是语言内可见的范围，但语言定义的 state 是什么又是另一件事情了。
pure function 就是他跟数学上说的函数是一样的，
给定同样的输入，输出必然一样。跟可不可预测无关。
impure function 则是给定同样的输入，至少存在两个不一样的结果。
所以并不是 C/C++ 的程式没有 pure function, 而是所有的 Haskell
function 都是 pure function。(这点其实尚有争论)
: 2. exponentiation 是密码学中很重要的一环，因此有许多技巧可以来实作
: http://en.wikipedia.org/wiki/Exponentiation_by_squaring
: 用even和odd的方法应该是上面文中的第一个:
: 直接照抄实作可能如下
: expt :: Integer -> Integer -> Integer
: expt x 1 = x
: expt x n
: | even n = expt (x * x) (div n 2)
: | odd n = x * expt (x * x) (div n 2)
: 也可以偷看 Haskell 自己的 (^) 怎么实作
: http://www.haskell.org/onlinereport/standard-prelude.html
: 你写的 expt 的空间部份：
: expt x n = x * (x * (x * ... * (x * 1)))
: 所以 haskell 会展开很多项，直到能算 x * 1 = x，再往上算一层 x * (x * 1)
: 一直到最后一层
其实 Haskell 不会展开成 x* (x * ... * (x * 1))) 才开始算，
实际上根据 lazy evaluation 应该是
x * expt x n -> x * x * expt x n
-> x^2 * expt x (n -1)
-> x^2 * x * expt x (n-2) -> ... -> x^n
但空间上还是 O(n), 因为每个 expt x n 都会被记录下来直到某个上界为止，
超过上界的话就真的是 O(1) 了。
至于其他的实作方式则主要是减少时间复杂度，而不是处理空间复杂度。
根据记忆写的，有错的话请麻烦订正。