2006-06-04
■ makehtmlを作る(4) 
各行をチェックして、置換すべきものは置換する。とりあえずは >|| と ||< を <pre> と </pre>にしてみた。機械的にやっているので、処理としては嘘っこである。
…眠くなってきちゃった。くぅ。
-- makehtml.cs -- Version 0.04 -- 標準入力から得た文字列を、makehtmlを通して出力する。 main = do cs <- getContents putStr (makehtml cs) -- 与えられた文字列を行ごとのリストにし、 -- processLinesを通してから文字列に戻して返す。 makehtml :: String -> String makehtml cs = unlines $ processLines $ lines cs -- 各行をチェックして、置換すべきものは置換する。 processLines :: [String] -> [String] processLines [] = [] processLines (s:ss) | s == ">||" = "<pre>" : processLines ss | s == "||<" = "</pre>" : processLines ss | otherwise = s : processLines ss
■ makehtmlを作る(3) 
ちゃんと動いているのか不安になったので、各行の頭に "> "をつけてみた。
-- makehtml.cs -- Version 0.03 -- 標準入力から得た文字列を、makehtmlを通して出力する。 main = do cs <- getContents putStr (makehtml cs) -- 与えられた文字列を行ごとのリストにし、 -- processLinesを通してから文字列に戻して返す。 makehtml :: String -> String makehtml cs = unlines $ processLines $ lines cs -- 各行の頭に "> " をつける。 processLines :: [String] -> [String] processLines [] = [] processLines (s:ss) = ("> " ++ s) : processLines ss
追記:以下でもいいですね、というコメントをいただきました。そういえばそうですね。頭が高階になってない…(^_^; 感謝します。
processLines = map ("> "++)
■ makehtmlを作る(2) 
次に、文字列をそのまま返すんじゃなく、
- linesで行分解し
- processLinesで行単位の処理をし、
- そしてunlinesで文字列に戻す
とやってみた。
-- makehtml.cs -- Version 0.02 -- 標準入力から得た文字列を、makehtmlを通して出力する。 main = do cs <- getContents putStr (makehtml cs) -- 与えられた文字列を行ごとのリストにし、 -- processLinesを通してから文字列に戻して返す。 makehtml :: String -> String makehtml cs = unlines $ processLines $ lines cs -- 各行を素通しする。 processLines :: [String] -> [String] processLines ss = ss
■ makehtmlを作る(1) 
はてダラスプリッタの形式のファイル(はてなダイアリーライターの複数日を一つのファイルにまとめたもの)をHTMLに変換するツールmakehtmlを作ってみようと思います。少しずつ、ね。
とりあえず、標準入力のコピーからだな。
-- makehtml.cs -- Version 0.01 -- 標準入力から得た文字列を、makehtmlを通して出力する。 main = do cs <- getContents putStr (makehtml cs) -- 与えられた文字列をそのまま返す。 makehtml :: String -> String makehtml cs = cs
■ span関数 
span :: (a -> Bool) -> [a] -> ([a], [a])
span関数はbreak関数の逆で、リストの先頭から、指定した述語を満たす要素を集めたリストをfst、残りのリストをsndにするようなペアを返します。
break関数を使えば一発。
span' :: (a -> Bool) -> [a] -> ([a], [a]) span' f = break (not . f)
実行結果です。
*Main> span' even [] ([],[]) *Main> span' even [0] ([0],[]) *Main> span' even [1] ([],[1]) *Main> span' even [0,2,4,1,3,5,0,2,4] ([0,2,4],[1,3,5,0,2,4])
■ scanl関数 
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl関数は、(a -> b -> a)型の関数と、a型の初期値と、[b]型のリストが与えられて、累積的に計算をしていき[a]型のリストを得るというもの。
scanl'を自作しましょう。
scanl' :: (a -> b -> a) -> a -> [b] -> [a] scanl' f x [] = [x] scanl' f x (y:ys) = x : scanl' f (f x y) ys
実行結果です。
*Main> scanl' (+) 0 [] [0] *Main> scanl' (+) 0 [1] [0,1] *Main> scanl' (+) 0 [1,2] [0,1,3] *Main> scanl' (+) 0 [1..10] [0,1,3,6,10,15,21,28,36,45,55]
えっ、これを高階関数で? …うーん。
こっ、これでどうでしょうか。
scanl' :: (a -> b -> a) -> a -> [b] -> [a] scanl' f x xs = x : zipWith f self xs where self = scanl' f x xs
■ reverse関数 
reverse :: [a] -> [a]
reverse関数はリストの要素を逆転します。
reverse' :: [a] -> [a] reverse' [] = [] reverse' (x:xs) = (reverse' xs) ++ [x]
素直じゃない書き方をしてみます。
reverse' :: [a] -> [a] reverse' = \x -> if null x then [] else last x : (reverse' . init) x
改心して少し素直に。
reverse' :: [a] -> [a] reverse' [] = [] reverse' xs = last xs : (reverse' . init) xs
■ repeat関数, replicate関数 
repeat :: a -> [a]
repeat関数は、要素を一個与えられて、それの無限リストを作る関数です。
これは簡単。
repeat' :: a -> [a] repeat' x = x:repeat' x
実行結果です。
*Main> take 10 $ repeat' 123 [123,123,123,123,123,123,123,123,123,123]
replicate関数は個数と要素を指定して、有限リストを作ります。
replicate' :: Int -> a -> [a] replicate' n = (take n) . repeat
repeatを使って無限リストを作り、個数でtakeすればできあがり。
実行結果です。
*Main> replicate' 5 'A' "AAAAA" *Main> replicate' 0 'A' ""
■ maximum関数 
maximum :: Ord a => [a] -> a
maximum関数は、順序づけできる(Ord a)要素のリストから最大のものを得る関数です。
maximum' :: Ord a => [a] -> a maximum' [] = error "empty list" maximum' (x:xs) = iter x xs where iter x [] = x iter x (y:ys) | x > y = iter x ys | otherwise = iter y ys
■ length関数 
length :: [a] -> Int
length関数はリストの要素数。
length' :: [a] -> Int length' [] = 0 length' (x:xs) = 1 + (length' xs)
整数の無限列にナンバリングさせてみましょう。
length' :: [a] -> Int length' [] = 0 length' xs = fst $ last $ zip [1..] xs
■ last関数 
last :: [a] -> a
last関数はinit関数の逆で、リストの最後の一個の要素を返す。
last' :: [a] -> a last' [] = error "empty list" last' [x] = x last' (x:xs) = last' xs
実行結果です。
*Main> last' "" *** Exception: empty list *Main> last' "a" 'a' *Main> last' "abcd" 'd' *Main> last' ['a'..'z'] 'z'
■ iterate関数 
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
■ init関数 
init :: [a] -> [a]
init関数は最後以外の要素からなるリスト。
init' :: [a] -> [a] init' [] = error "empty list" init' (x:[]) = [] init' (x:xs) = x:init' xs
実行結果です。
*Main> init' [] *** Exception: empty list *Main> init' "ABCD" "ABC" *Main> init' "A" "" *Main> init' "ABC" "AB"
長さを使うこともできるかな。
init' :: [a] -> [a] init' [] = error "empty list" init' xs = take ((length xs) - 1) xs
■ foldr関数 
foldr :: (a -> b -> b) -> b -> [a] -> b
よく使うfoldr関数。簡単簡単。
…と思いきや、大苦戦。最初は次のようにしてしまいました。自作のfoldr'です。
-- 正しくない foldr' foldr' :: (a -> b -> b) -> b -> [a] -> b foldr' f x [] = x foldr' f x (y:ys) = f x (foldr' f y ys)
よく見てみると、xはb型のはずなのに、a型として扱っています。正しくは次のようになります(HugsのPrelude.hsをカンニング)。
foldr' :: (a -> b -> b) -> b -> [a] -> b foldr' f x [] = x foldr' f x (y:ys) = f y (foldr' f x ys)
ということは、foldrというのは、引数で独立に与えられたxは尻尾につくんですね。確かめよう。
*Main> foldr (++) "Z" ["A","B","C"] "ABCZ"
ほんとだー。
■ flip関数 
flip :: (a -> b -> c) -> b -> a -> c
flip関数は2引数関数を与えると、引数順をひっくり返した関数を返します。
flip'を自作します。これは簡単。
flip' :: (a -> b -> c) -> b -> a -> c flip' f x y = f y x
実行結果です。
*Main> flip' (>) 3 1 False
■ filter関数 
filter :: (a -> Bool) -> [a] -> [a]
filter関数は述語とリストから、述語を満たす要素だけを集めたリストを作ります…って、以前も作ったっけ。
filter'を自作します。
filter' :: (a -> Bool) -> [a] -> [a] filter' f [] = [] filter' f (x:xs) | f x = x:filter' f xs | otherwise = filter' f xs
実行結果です。
*Main> filter' even [1..10] [2,4,6,8,10] *Main> filter' Char.isUpper "HelloWorld" "HW"
高階関数版…うーん。
- mapは入力リストと出力リストの長さが等しい。
- zipは複数のリストが入力だし、入出力のリストの長さは等しい。
- foldrはリストからスカラー(というか、リストっぽくないもの)を作るんだし。
- anyやallはリストからBoolだし。
- dropWhileとtakeWhileを使えばできそうだが…。断念。
お、breakは使えそう。breakは述語を満たさない前半リストと、述語を満たす要素を先頭に持つ後半リストのペアを返す。
filter' :: (a -> Bool) -> [a] -> [a] filter' f xs = foo f xs where foo f [] = [] foo f xs = bs ++ foo f cs where as = snd (break f xs) bs = fst (break (not . f) as) cs = snd (break (not . f) as)
追記:takatohさんから、foldr版。折りたたむ関数がすごっ。
filter' f xs = foldr (\m n -> if f m then m:n else n) [] xs
追記:hanataniさんから、リストが縮むmapMaybeというのを。GHCiではimport Maybeが必要でした。
import Maybe filter' f = mapMaybe (\x-> if f x then Just x else Nothing)
追記:リストの内包表記(list comprehension)を忘れていました。
filter' :: (a -> Bool) -> [a] -> [a] filter' f xs = [ x | x <- xs, f x ]
■ elem関数 
elem :: Eq a => a -> [a] -> Bool
elem関数はリスト中に要素があるかどうかを調べます。
elem'を自作。再帰版。
elem' :: Eq a => a -> [a] -> Bool elem' x [] = False elem' x (y:ys) | x == y = True | otherwise = elem' x ys
実行結果です。
*Main> elem' 3 [1..5] True *Main> elem' 0 [1..5] False
「高階関数を使え」はいはい〜。
elem' :: Eq a => a -> [a] -> Bool elem' x xs = any (x==) xs
もちろん、これでもOK.
elem' :: Eq a => a -> [a] -> Bool elem' x = any (x==)
■ cycle関数 
cycle :: [a] -> [a]
cycle関数はリストを無限リストにします。無限リストを与えても大丈夫。
cycle'を自作。
cycle' :: [a] -> [a] cycle' xs = cycleWith xs where cycleWith [] = cycleWith xs cycleWith (y:ys) = y : cycleWith ys
実行結果です。
*Main> take 10 $ cycle' [1,2,3] [1,2,3,1,2,3,1,2,3,1] *Main> take 10 $ cycle' [1..] [1,2,3,4,5,6,7,8,9,10]
はっ、もしかしたら、これでいいのか?
cycle' :: [a] -> [a] cycle' xs = xs ++ cycle' xs
実行結果です。
*Main> take 10 $ cycle' [1,2,3] [1,2,3,1,2,3,1,2,3,1] *Main> take 10 $ cycle' [1..] [1,2,3,4,5,6,7,8,9,10]
■ iterateで冪乗 
コメント欄で教えていただきました。冪乗。
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で繰り返す…なるほど。ありがとうございます。
filter' f xs = foldr (\m n -> if f m then m:n else n) [] xs
filter' f = mapMaybe (\x-> if f x then Just x else Nothing)
特にmapを使わない意図はありません。
再帰で書く練習、高階関数で書く練習と段階をわけているのかと穿った見方をしてしまいました。すみません。