※ 引述《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) 了。 至於其他的实作方式则主要是减少时间复杂度，而不是处理空间复杂度。 根据记忆写的，有错的话请麻烦订正。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 80.195.203.67