てきとうなメモ

本の感想とか技術メモとか

Haskellの勉強 (5) - リスト (2)

PreludeListその2

concat,concatMap

concat :: [[a]] -> [a]
concat xss = foldr (++) [] xss


concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f = concat . map f

concatはリストのリストを連結する.文字列は文字型のリストなので,文字列の連結にconcatを用いることができる.

Prelude> concat ["Ha", "sk", "ell"]
"Haskell"

concatMapはリストの各要素に関数fを適用したものをconcatする.例えば,

Prelude> putStr $ concatMap (++"\n") ["These", "are", "multiple", "lines"]
These
are
multiple
lines

これは各文字列に改行文字を付加してconcatした文字列をputStrで出力している.

関数適用演算子 ($)

infixr 0  $
($) :: (a -> b) -> a -> b
f $  x    =  f x

先ほどの例では$演算子を用いている.$は関数適用の演算子である.通常の関数適用と異なるのは右結合であり,優先順序が一番低い(0)であることである.通常の関数適用は左結合であるため,f g xは(f g) xとなる.逆にf $ g xとするとこれはg xの優先順序が高いのでf (g x)となる.

iterate, repeat, replicate, cycle

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


repeat           :: a -> [a]
repeat x         =  xs where xs = x:xs


replicate        :: Int -> a -> [a]
replicate n x    =  take n (repeat x)


cycle            :: [a] -> [a]
cycle []         =  error "Prelude.cycle: empty list"
cycle xs         =  xs' where xs' = xs ++ xs'

iterate, repeat, cycleは無限リストを返す関数である.

iterateは関数fをxに適用した無限リストを返す.すなわち

iterate f x = [x, (f x), (f (f x), ..., (f ... (f (f x)))]

例えば

Prelude> take 10 $ iterate (1+) 0
[0,1,2,3,4,5,6,7,8,9]

repeatは同じ値の無限リストを返す.

repeat           :: a -> [a]
repeat x         =  xs where xs = x:xs

ここで,where xs = x:xsはxsの定義にxsを用いていてxsが何を表しているのかわからないように思える.しかし,Haskellでは遅延評価を行っており,必要になったときに展開されるとみなせば,

take 2 (repeat 2)
-> take 2 [2:(repeat 2)]
-> 2 : (take 1 (repeat 2))
-> 2 : (take 1 [2, (repeat 2)])
-> 2 : 2 : (take 0 (repeat 2))
-> 2 : 2 : []
-> [2, 2]

となる.

replicateは値がn個連続するリストを返す.

Prelude> replicate 3 2
[2,2,2]

cycleはリストを繰り返した循環リストを返す.

例えば

Prelude> take 10 $ cycle [1, 2, 3]
[1,2,3,1,2,3,1,2,3,1]

repeatはcycleを用いて定義できる.

repeat x = cycle [x]

逆にcycleはrepeatを用いて定義できる

cycle = concat . repeat

ここで,.は関数合成(function composition)を表す.すなわち(f . g) x = f (g x)である.

(.)              :: (b -> c) -> (a -> b) -> a -> c
f . g            =  \x -> f (g x)

また,repeatはiterateを用いて定義できる

repeat = iterate id

takeWhile, dropWhile, span, break

takeWhile               :: (a -> Bool) -> [a] -> [a]
takeWhile p []          =  []
takeWhile p (x:xs) 
            | p x       =  x : takeWhile p xs
            | otherwise =  []

dropWhile               :: (a -> Bool) -> [a] -> [a]
dropWhile p []          =  []
dropWhile p xs@(x:xs')
            | p x       =  dropWhile p xs'
            | otherwise =  xs


span                   :: (a -> Bool) -> [a] -> ([a],[a])
span p []            = ([],[])
span p xs@(x:xs') 
            | p x       =  (x:ys,zs) 
            | otherwise =  ([],xs)
                           where (ys,zs) = span p xs'

takeWhile述語pとリストxsを引数に取り,リストの要素xに対してp xが真である間takeする.dropWhileはそのdrop版でp xが真である間dropする.

Prelude> takeWhile odd [1,3,5,6,8]
[1,3,5]
Prelude> dropWhile odd [1,3,5,6,8]
[6,8]

oddは奇数のとき真を返す関数である.

spanはtakeWhileとdropWhileのペアを作る.

Prelude> span odd [1,3,5,6,8]
([1,3,5],[6,8])

こうすると,oddが偽になった時点でリストを分割しているように見える.

spanは

span        :: (a -> Bool) -> [a] -> ([a],[a])
span p xs = ((takeWhile p xs), (dropWhile p xs))

でも定義できるが,リストを2回走査してしまうので非効率である.

breakは逆に真になった時点でリストを分割する関数である.

Prelude> break even [1, 3, 5, 6, 8]
([1,3,5],[6,8])

evenは整数が偶数の時真を返す関数である.

関数合成演算子(.)

spanの定義では関数合成演算子を用いている.これは以下のように定義できる.

 (.)              :: (b -> c) -> (a -> b) -> a -> c
f . g            =  \ x -> f (g x)

要するに

(f . g) (x) = f(g(x))

となる.

例えば,

Prelude> (not . not) True
True

となる.

lines, words, unlines, unwords

lines            :: String -> [String]
lines ""         =  []
lines s          =  let (l, s') = break (== '\n') s
                      in  l : case s' of
                                []      -> []
                                (_:s'') -> lines s''


words            :: String -> [String]
words s          =  case dropWhile Char.isSpace s of
                      "" -> []
                      s' -> w : words s''
                            where (w, s'') = break Char.isSpace s'


unlines          :: [String] -> String
unlines          =  concatMap (++ "\n")


unwords          :: [String] -> String
unwords []       =  ""
unwords ws       =  foldr1 (\w s -> w ++ ' ':s) ws

lines(words)は文字列を行(単語)のリストに分割する.unlines, unwordsはその逆変換である.

Prelude> lines "Hello\nHaskell\nWorld\n"
["Hello","Haskell","World"]
Prelude> words "Hello  Haskell\tWorld"
["Hello","Haskell","World"]
Prelude> unlines ["Hello", "Haskell", "World"]
"Hello\nHaskell\nWorld\n"
Prelude> unwords ["Hello", "Haskell", "World"]
"Hello Haskell World"

あまり複雑なことは行っておらず,linesは改行で分割する,wordsは空白文字で区切るということしかしない.ゆえに,

Prelude> lines "Hello\n\nHaskell\nWorld\n"
["Hello","","Haskell","World"]
Prelude> words "Hello \"Haskell World\""
["Hello","\"Haskell","World\""]

空行はリストの一つの要素と認識され,引用符のチェックなどは行われない.

reverse

reverse          :: [a] -> [a]
reverse          =  foldl (flip (:)) []

reverseはリストを反転させる.

Prelude> reverse [1,2,3,4,5]
[5,4,3,2,1]

flipはf(x, y)をf(y, x)に変換する関数.

flip             :: (a -> b -> c) -> b -> a -> c
flip f x y       =  f y x

reverseは':'のflipをfoldlしているので以下のように展開される.

reverse [1,2,3]
=> foldl (flip (:)) ((flip (:)) [] 1) [2,3]
=> foldl (flip (:)) (1:[]) [2,3]
=> foldl (flip (:)) ((flip (:)) [1] 2) [3]
=> foldl (flip (:)) (2:[1]) [3]
=> foldl (flip (:)) ((flip (:)) [2,1] 3) []
=> 3:[2,1]
=> [3,2,1]

any, all

any, all         :: (a -> Bool) -> [a] -> Bool
any p            =  or . map p
all p            =  and . map p

anyは述語pとリストxsをとり,xsの各要素のどれかに対してpが真となれば真を返す.allは全ての要素に対して真である時のみ真を返す.

Prelude> any odd [0, 2, 4, 8, 16]
False
Prelude> any odd [1, 2, 4, 8, 16]
True
Prelude> all even [0, 2, 4, 8, 16]
True
Prelude> all even [1, 2, 4, 8, 16]
False

elem, notelem

elem, notElem    :: (Eq a) => a -> [a] -> Bool
elem x           =  any (== x)
notElem x        =  all (/= x)

elenはxがリストxsの中にあるとき真を返し.notElemはその逆である.

Prelude> elem 2 [1, 2, 3, 4, 5]
True
Prelude> elem 6 [1, 2, 3, 4, 5]
False
Prelude> notElem 6 [1, 2, 3, 4, 5]
True
Prelude> notElem 2 [1, 2, 3, 4, 5]
False

これは先ほどのanyとallを用いて定義できる.

lookup

lookup           :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup key []    =  Nothing
lookup key ((x,y):xys)
    | key == x   =  Just y
    | otherwise  =  lookup key xys

lookupはタプルのリスト[(key,value),...]を連想配列とみなして,keyと一致するタプルのvalueを返す.

Prelude> lookup "foo" [("foo","bar"), ("spam","egg")]
Just "bar"

ここでは型Maybe bの値を返すことになっている.これはkeyが連想配列に存在しなかった時,型bのなんらかの値を返すことができない.そのため,Nothing(何もない)という値を持つ型Maybe bを返り値の型にしている.

zip系

zip              :: [a] -> [b] -> [(a,b)]
zip              =  zipWith (,)


zip3             :: [a] -> [b] -> [c] -> [(a,b,c)]
zip3             =  zipWith3 (,,)


zipWith          :: (a->b->c) -> [a]->[b]->[c]
zipWith z (a:as) (b:bs)
                 =  z a b : zipWith z as bs
zipWith _ _ _    =  []


zipWith3         :: (a->b->c->d) -> [a]->[b]->[c]->[d]
zipWith3 z (a:as) (b:bs) (c:cs)
                 =  z a b c : zipWith3 z as bs cs
zipWith3 _ _ _ _ =  []


unzip            :: [(a,b)] -> ([a],[b])
unzip            =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])


unzip3           :: [(a,b,c)] -> ([a],[b],[c])
unzip3           =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
                          ([],[],[])

zipWithは2項演算子を2つのリストの対応する各要素に適用したリストを返す.例えばベクトルの足し算などを行うことができる.

Prelude> zipWith (+) [1,2,3,4] [2,3,4,5]
[3,5,7,9]

zipWith3はその3項演算子バージョンである.

Prelude> zipWith3 (\x y z-> x + y + z) [1..5] [2..6] [3..7]
[6,9,12,15,18]

zipWithを用いてフィボナッチ数列を記述することができる.

fib = 1:1:(zipWith (+) fib (tail fib))

フィボナッチ数列の3項バージョンがトリボナッチ数列である.

trib = 1:1:2:(zipWith3 (\x y z -> x+y+z) trib (tail trib) (tail $ tail trib))
> take 10 fib
[1,1,2,3,5,8,13,21,34,55]
> take 10 trib
[1,1,2,4,7,13,24,44,81,149]

zipは2リストの各要素をタプルにしてそのリストを作る.unzipはその逆.

Prelude> zip [1,2,3] ['a'..'c']
[(1,'a'),(2,'b'),(3,'c')]
Prelude> unzip [(1,'a'),(2,'b'),(3,'c')]
([1,2,3],"abc")

zip3とunzip3は3つ引数をとるバージョン.

Prelude> zip3 [1..3] ['a'..'c'] [True,False,True]
[(1,'a',True),(2,'b',False),(3,'c',True)]
Prelude> unzip3 [(1,'a',True),(2,'b',False),(3,'c',True)]
([1,2,3],"abc",[True,False,True])

unzipやunzip3の定義に用いている~はirrefutable patternと呼ばれる.パターンにマッチしていなくてもマッチしているかのように動作するらしいのだが,なぜここで使われているのかよくわからない.

リスト内包表記 (2)

リスト内包表記を用いるときに注意することがある.複数の無限リストを用いるときに

Prelude> take 10 [ (x, y) | x <- [1..], y <- [1..]]
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)]

とすると,yの方を先に変化させてxが変化しないまま無限ループに陥る.これを防ぐためには何らかの方法でn次元の座標を数え上げる必要がある.例えばx + yを一定の値に押さえて数え上げるという方法がある.

lattice n = [ (i, n-i) | i <- [0..n] ]
all_lattice = concat [lattice i |  i <- [0..] ]

lattice nは合計がnとなる2次元のタプルである.

> lattice 10
[(0,10),(1,9),(2,8),(3,7),(4,6),(5,5),(6,4),(7,3),(8,2),(9,1),(10,0)]

0から無限大まで各lattice iをconcatすると2次元座標を全て数え上げることができる.

> take 10 all_lattice
[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3),(1,2),(2,1),(3,0)]


これをn次元に拡張すると以下のようになる.今回はタプルではなくリストを用いる.

lattice 1 n = [[n]]
lattice d n = [ i:xs | i <- [0..n], xs <- lattice (d - 1) (n - i)]
all_lattice d = concat [lattice d i |  i <- [0..] ]

lattice d nはd次元の座標の合計がnである座標のリストを表している.

> lattice 2 2
[[0,2],[1,1],[2,0]]
> lattice 3 3
[[0,0,3],[0,1,2],[0,2,1],[0,3,0],[1,0,2],[1,1,1],[1,2,0],[2,0,1],[2,1,0],[3,0,0]]

これをconcatするとn次元の座標を数え上げることが出来る.

> take 10 $ all_lattice 2
[[0,0],[0,1],[1,0],[0,2],[1,1],[2,0],[0,3],[1,2],[2,1],[3,0]]
> take 10 $ all_lattice 3
[[0,0,0],[0,0,1],[0,1,0],[1,0,0],[0,0,2],[0,1,1],[0,2,0],[1,0,1],[1,1,0],[2,0,0]]
> 

これを用いるとピタゴラス数などを計算できる.

ptgrs = [[x,y,z] | [x,y,z] <- all_lattice 3, x > 0, y > 0, z > 0, x < y, y < z, x ^ 2 + y ^ 2 == z ^ 2]
> take 5 ptgrs
[[3,4,5],[6,8,10],[5,12,13],[9,12,15],[8,15,17]]