結城浩のHaskell日記 RSSフィード

2006-06-04

iterate関数 iterate関数 - 結城浩のHaskell日記 を含むブックマーク

iterate :: (a -> a) -> a -> [a]

iterate関数は「次に進む」関数と初期値をもらって無限リストを作ります。

これは簡単。

iterate' :: (a -> a) -> a -> [a]
iterate' f x = x : iterate' f (f x)

実行結果です。

*Main> take 10 $ iterate' (+1) 0
[0,1,2,3,4,5,6,7,8,9]
*Main> take 5 $ iterate' (++"OK") ""
["","OK","OKOK","OKOKOK","OKOKOKOK"]

関数合成を累積的にやってみると、こうなります。

iterate' :: (a -> a) -> a -> [a]
iterate' f x = iter f id x
  where
    iter f g x = g x : iter f (f.g) x

iterateで冪乗 iterateで冪乗 - 結城浩のHaskell日記 を含むブックマーク

コメント欄で教えていただきました。冪乗。

powers n = iterate (*n) 1

実行結果です。

*Main> take 10 $ powers 2
[1,2,4,8,16,32,64,128,256,512]
*Main> take 10 $ powers 10
[1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000]

関数の部分適用 (*n) を iterateで繰り返す…なるほど。ありがとうございます。

takatohtakatoh2006/06/04 11:54高階関数版 filter'。こうなんでどうでしょう。
filter' f xs = foldr (\m n -> if f m then m:n else n) [] xs

hanatanihanatani2006/06/04 13:24mapMaybe だとリストが縮みます。
filter' f = mapMaybe (\x-> if f x then Just x else Nothing)

hyukihyuki2006/06/04 14:43テスト書き込み。

..2006/06/05 02:45意図して map を使わないようにしているのですか?

hyukihyuki2006/06/05 07:01ええと、どのエントリへのコメントでしょう(mapを使わない件)。
特にmapを使わない意図はありません。

nobsunnobsun2006/06/05 07:59このreverse計算の手間はリストの長さnに対してO(n^2)になってるような。。。

hyukihyuki2006/06/05 08:31え、あ、うーん?そ、そうですか?(いまいちよくわかっていない)

..2006/06/06 01:43processLines = map ("> "++) とかです。
再帰で書く練習、高階関数で書く練習と段階をわけているのかと穿った見方をしてしまいました。すみません。