階乗
昼間、Eulerの問題を解いていて気になったのでちょっとGHCiで調べてみた
Prelude> :t foldr foldr :: (a -> b -> b) -> b -> [a] -> b Prelude> foldr (*) 1 [1..0] 1 Prelude> foldr (*) 1 [0..1] 0 Prelude> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a Prelude> foldl (*) 1 [1..0] 1 Prelude> foldl (*) 1 [0..1] 0
なぜだ!!!
foldlでもfoldrでも、[1..0]を渡すと1が返ってくるのか.....
でも、
foldr (*) 1 [1,0]
とか
foldr (*) 1 [10000,9999..0]
とすると、予想どおり0が返ってきた!!
しかし、
foldr (*) 1 [10000..0]
とかしても、やっぱり1が帰ってくる。
不思議だ。
うーん
[,]と[..]の違いですね
foldrの定義をHaskellwikiから探してみたら、こんな風にある
foldr f z [] = z foldr f z (x:xs) = x `f` foldr f z xs
つまり?単純に[1,0]
を渡すと、
1 * foldr (*) 1 0 →1 * 0 * foldr (*) 1 [] →1 * 0 * 1 →0
ですね。これは。関数の問題ではなさそう
GHCiで、今度はリストの確認。
Prelude> [1..9] [1,2,3,4,5,6,7,8,9] Prelude> [1..0] [] Prelude> [10000..0] []
となった!!
ということは、上のようなリストはすなわち空リスト。
つまりリストが内部で予測してくれるのは値がインクリメントしていく場合だけで、それ以外の場合は空リストになるようです。
[10000,9999..0]
の場合は、次の項を与えてリストの様子を明示しているから空リストにならず、思う通りの動作をする。
だから、0の階乗は一般的なnの階乗同様、
foldr (*) 1 [1..n]
で得られたんですね。