読者です 読者をやめる 読者になる 読者になる

IT練習ノート

IT関連で調べたこと(実際は嵌ったこと)を書いています。

関数をn回適用する

Haskell
foldr (.) id (replicate n f)

を理解したい。

stackoverflow.com

*Main> :t foldr (.)

の型を考える。

*Main> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

置き換えておく。

foldr :: (x -> y -> y) -> y -> [x] -> y
*Main> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

(1) b -> c を x

(2) a -> b を y

(3) a -> c を y

と対応させる。

2番目と3番目をみるとbとcは同じになる。

また、

(1) は b->b となる。

(2),(3)は a->b となる。

これをx,yにあてはめると、

( (b->b) -> (a->b) -> (a->b) ) -> (a->b) -> [b->b] -> a -> b

となり、foldr (.)

foldr (.) :: (a -> b) -> [b -> b] -> a -> b

となる。

*Main> :t id
id :: a -> a

を適用すると、aとbは同じになるので、

*Main> :t foldr (.) id 
foldr (.) id :: [b -> b] -> b -> b
*Main> 

これの第1引数は関数のリストをとり、(それらをつなげた、一つの)関数を返す。 この第1引数につながるように、関数のリストをつくるが、それはreplicateがつかえる。

*Main> :t replicate
replicate :: Int -> a -> [a]
*Main> 
*Main> let repeatFunN n f = foldr (.) id (replicate n f)
*Main> :t repeatFunN
repeatFunN :: Int -> (b -> b) -> b -> b
*Main> repeatFunN 5 (\x -> x * 2) 1
32
*Main> 

というか、面倒なことを考えずに、直感的に、通常使う場合の関数版だと思えば良い。

要素 内容 通常使う場合の例
foldr
(.) 関数をつなげるもの (\x -> \y -> x + y )
id 関数の単位元(?!)のようなもの 0
(replicate n f) 関数のリスト [1,2,3,4]