※ 引述《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) 了。
至於其他的實作方式則主要是減少時間複雜度，而不是處理空間複雜度。
根據記憶寫的，有錯的話請麻煩訂正。