Re: [問題] Haskell新手一些問題

[xcycl (XOO)]

※ 引述《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
推 ilway25:我覺得 lazy evaluation 不會知道結合律耶，但我不確定
→ ilway25:我的認知是 如果第一個x是0，後面就不會再展開了
→ Favonia:我想 impure 不代表一定存在兩個不一樣的結果
→ xcycl:impure 是定義問題..不用 side effect 的話
→ xcycl:非 pure 根據定義就是存在不同的結果
→ xcycl:至於第二個是我的疏忽，不管是 inductive
→ xcycl:的整數或是 Int 都不會這樣算
→ xcycl:但若是 Int 的話，第一個是零還是會繼續展開
→ xcycl:因為 * 是 primative operation 直接用底層的乘法運算定義的
→ xcycl:http://ppt.cc/GtnC 可以看到 (*) :: Int -> Int -> Int
→ ilway25:所以是只有像 True || (...) 才會不算了嗎
→ xcycl:看機器的 or 跟 * 怎麼作，從語言層面上是這樣實作是一回事
→ xcycl:晚點整理一下好了.. Haskell 有作 short circuit
→ xcycl:evaluation
推 SansWord:話說用tail recursion 會不會比較省空間？