※ 引述《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