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で繰り返す…なるほど。ありがとうございます。

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

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

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

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

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

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

hyuki2006/06/05 08:31え、あ、うーん？そ、そうですか？（いまいちよくわかっていない）

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

トラックバック - http://haskell.g.hatena.ne.jp/hyuki/20060604

		2006/06
日	月	火	水	木	金	土
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

結城浩のHaskell日記

2006-06-04

■ makehtmlを作る(4)

■ makehtmlを作る(3)

■ makehtmlを作る(2)

■ makehtmlを作る(1)

■ span関数

■ scanl関数

■ reverse関数

■ repeat関数, replicate関数

■ maximum関数

■ length関数

■ last関数

■ iterate関数

■ init関数

■ foldr関数

■ flip関数

■ filter関数

■ elem関数

■ cycle関数

■ iterateで冪乗