Re: [問題] Haskell新手一些問題
※ 引述《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
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)
一直到最後一層
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.107
→
12/08 13:03, , 1F
12/08 13:03, 1F
討論串 (同標題文章)
PLT 近期熱門文章
PTT數位生活區 即時熱門文章