top page > computer > haskell > web_lecture > for_programmer > plusplus_def.html
更新日:
文責: 重城良国

関数(++), concat, reverse

pluspluses.hs

関数(++)

動作

リストの結合だ。

% ghci
Prelude> "monk" ++ "ey"
"monkey"

(.++), (.++.), (.++..) :: [a] -> [a] -> [a]

生の再帰

(x : xs) .++ ys = x : (xs .++ ys)
[] .++ ys = ys

リストXの残りのリストとリストYを結合したものにXの先頭の値を追加したものはXとYを結合したものだ。

関数foldr

xs .++. ys = foldr (:) ys xs

foldrが(:)と[]を置き換える関数であることを思い出そう。ここでは(:)はそのまま(:)に[]はysに置き換えている。

x1 : x2 : x3 : ... : []
-> x1 : x2 : x3 : ... : ys

関数flipを使えば仮引数を消すことができる。

(.++.) = flip $ foldr (:)

関数unfoldr

(.++..) = curry . unfoldr $ \xys -> case xys of
(x : xs, ys) -> Just (x, (xs, ys))
(_, y : ys) -> Just (y, ([], ys))
_ -> Nothing

ひとつめのリストが空でなければそれを削っていき空ならばふたつめのリストを削っていく。

関数concat

動作

リストのリストの全要素を結合してリストにする。

Prelude> concat ["He", "And", "She", "Know", "Everyone", "Likes", "Lisp"]
"HeAndSheKnowEveryoneLikesLisp"

concatRaw, concatF :: [[a]] -> [a]

生の再帰

concatRaw (xs : xss) = xs ++ concatRaw xss
concatRaw _ = []

残りの要素同士を結合したものに先頭の要素を結合する。

関数foldr

concatF = foldr (++) []

リストの(:)をすべて(++)におきかえれば良い。

関数reverse

動作

リストを逆順にする。

Prelude> reverse "gateman"
"nametag"

reverseRaw, reverseF :: [a] -> [a]

生の再帰

reverseRaw = rv []
where
rv rs (x : xs) = rv (x : rs) xs
rv rs _ = rs

関数rvは状態としてリストrsを持つ。リストrsの先頭にもともとのリストの要素を追加していく。トランプの山を右から左に1枚ずつ動かしていくのを想像してみよう。カードの並びは逆順になるはずだ。

関数foldl

reverseF = foldl (flip (:)) []

foldlは左結合でリストの要素を結合する。ここでflip (:)を(!:)とすると以下のようになる。

((([] !: x1) !: x2) !: x3) !: ...

xs !: xでカードの山xsにカードxをのせるということだ。よってうえの式は空の山にx1をのせそのうえにx2をのせ...といった処理になる。

関数unfoldrでは定義しない理由

リストを後ろから削っていくという形でunfoldrによる定義は可能だ。しかし、リストはn番目の要素に到達するのにO(n)時間かかる。よってこのようなやりかただとO(n^2)時間かかってしまい非効率である。

まとめ

関数(++), concat, reverseの定義を学んだ。関数(++)はfoldrの、関数reverseはfoldlの性質をよく示す例だ。とくにreverseはリストに対する反復的処理の性質をよく表している。

「関数zip, zipWith, unzip」へもどる 「関数repeat, replicate, cycle」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics