人気ブログランキング | 話題のタグを見る

foldr で length をプログラムする

foldr の本質は再帰関数だ。foldr の計算を展開してみると、

foldr (*) 1 [1..5] = (1*(2*(3*(4*(5*1))))) = 120

だが、これは次の再帰関数の計算と同じものだ。

foo [] = 1
foo (x:xs) = x * foo xs

foo [1..5] = (1*(2*(3*(4*(5*(1)))))) = 120

つまり、foldr は一種の無名再帰関数として使うことができる。そこで、length 関数を foldr でプログラムしてみた。

Prelude> foldr (\x y -> 1+y) 0 [1..5]
5

foldr の計算を展開すると、これは次のような計算をしていることがわかる。

foldr (\x y -> 1+y) 0 [1..5] = (1+(1+(1+(1+(1+0))))) = 5

同じような発想でリストの2乗和の計算もできる。

Prelude> foldr (\x y -> x*x + y) 0 [1..5]
55

この場合、次のような計算が行われていることになる。

foldr (\x y -> x*x + y) 0 [1..5] = (1+(4+(9+(16+(25+0))))) = 55

これは次のような普通の発想の計算でも確認できる。

Prelude> sum $ map (\x -> x*x) [1..5]
55

二項演算子 + を : に変えると、リストの各要素を2乗することもできる。

Prelude> foldr (\x y -> x*x : y) [] [1..5]
[1,4,9,16,25]

foldr の計算が再帰関数の計算と同じことがわかれば、foldr が不可解な関数どころか無名再帰関数を記述できる使い勝手のいい道具であることがわかる。

おまけで、reverse を foldl でプログラムすると次のようになる。

Prelude> foldl (flip (:)) [] [1..5]
[5,4,3,2,1]

(flip (:)) [] 1 = 1:[] = [1] であることを考えて、flip (:) を * で表すことにすると、

foldl * [] [1..5] = ((((([] * 1)*2)*3)*4)*5) = (((([1]*2)*3)*4)*5) = (((([2,1])*3)*4)*5) = ... = ([4,3,2,1]*5) = [5,4,3,2,1]

となることを確かめることができる。

by tnomura9 | 2018-10-24 05:26 | Haskell | Comments(0)
<< foldr と再帰関数 入れ子になった for 文 >>