bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskell ドリル13 map関数

1.概略

Haskellの起源はLispである。Lipsは沢山あるプログラミング言語の中でも最も古い言語の一つで、1958年のジョン・マッカーシーの論文に始まる。Lispを使っていたころ、mapcarという関数がとても好きだった。この関数は、あるリストから別のリストへと変換してくれる優れた道具であった。今日は、mapcarと同じ機能を有するmapの話である。

mapはある世界から別の世界へと誘ってくれる関数である(Haskell圏論という数学に基礎をおいている。圏論はある世界から別の世界への変換を主要な理論としている。一般にこの変換はファンクタ(関手)と呼ばれている。しかし、ここでは圏論の言葉を使わないで説明する)。

ここでは、話を分かりやすくするために、下図のように、文字の世界と文字列の世界を考えることにする。文字の世界は型Charで表される世界である。文字列の世界はStringで表される世界である。なお、Stringは [Char] の言い換えである。
f:id:bitterharvest:20141213072206p:plain

文字の世界を考えると、そこには、小文字と大文字が存在する。小文字はある関数を用いれば大文字に変換してくれる。この関数をtoCapitalとする。

一方、文字Charをリストにすると文字列Stringとなる。文字から、文字列への変換は[ ]で行うことができる。そこで、小文字の文字から大文字単語の文字列を得ることを考える。これには二通りの道がある。一つの道は、小文字の文字を大文字の文字に変換し、それを大文字単語の文字列にする方法である。もう一つは、小文字の文字を小文字単語の文字列に変換し、それを大文字単語の文字列にする方法である。上の図で、前者の道は右に行って下に行く。後者の道は下に行って右に行く。いずれの道をたどっても、小文字の文字から同じ大文字単語の文字列が得られるのであれば、文字の世界から文字列への世界の変換は、ファンクタであるという。なお、ファンクタは、型クラスである。

一般に、ファンクタは、ある世界から別の世界への変換F(先の例では[ ])が次の性質を満たす時に言う(ファンクタの正確な定義は後の記事で説明する。ここでは、直感的な説明にとどめておく)。ファンクタの条件:ある世界の中でその中へ写像する関数g(先の例ではtoCapital)があった時に、関数gを施してから変換Fを施しても、変換Fを施してから関数gを施しても同一である。即ち、F(g(x))=g'(F(x)) であるときFをファンクタという。但し、g’ はgを要素ごとに施す関数である。Haskellでは、g’ = map gと表している。先の例では、map toCapitalである。

mapの型シグネチャを見ると

Prelude> :t map
map :: (a -> b) -> [a] -> [b]

となっている。 (a -> b) の部分は関数を表す。この関数は、aをbに変換する関数である。先ほどの説明で使用した関数gを用いるとb=g(a) である。また、 [a] は入力がリストであることを、 [b] は出力がリストであることを示し、リストの要素ごとに関数gによりaからbに変換されることを示す。

2.例題

問題:与えられた文字列を大文字に変換する関数toCapitalを作成しなさい。その後、mapを用いて、適当な文字列から小文字を大文字に変換した文字列を得なさい。

toCapitalのプログラムは次のようになる。

toCapital :: Char -> Char
toCapital a 
 | a `elem` small = getCapital' a pair
 | otherwise = a 
 where
  small = ['a'..'z']
  capital = ['A'..'Z']
  pair = zip small capital
  getCapital' :: Char -> [(Char, Char)] -> Char
  getCapital' _ [] = error "A capital letter does not exist."
  getCapital' a' ((ySmall, yCapital):ys)
   | a' == ySmall = yCapital
   | otherwise = getCapital' a' ys

次が実行結果である。

*Main> map toCapital "I was 17 years old."
"I WAS 17 YEARS OLD."

3.問題

それでは、「map」を用いて次の問題を解けるようにしなさい。

問題1:自然数のリスト[1,2..]より各要素を5だけ増やしたリストを作成する。即ち、[6,7..]を作成する。

問題2:自然数のリスト[1,2..]より各要素を二乗したリストを作成する。

問題3:自然数のリスト[1,2..]より3の倍数のリストを作成する。

問題4:アルファベットだけからなる文字列を得て、各文字を一つ後の文字に変更した文字列を出力する。但し、z,Zの後の文字は、それぞれa,Aとする。

問題5:リストが与えられた時、各要素に対して、自分とそれに続く要素を対にしたリストを作成する。例えば、[1,2..]は、[(1,2),(2,3),(3,4)…]となる。

問題6:数のリストが与えられた時、各要素に対して、自分とそれに続く要素とを足したリストを作成する。

問題7:リストが与えられた時、大文字を小文字に変更したリストを作成する。

問題8:文字列が与えられた時、それぞれの文字を小文字、大文字を区別しないで、アルファベットの順番、例えば、a,Aは1、h,Hは8、に変換したリストを作成する。

問題9:数字のリストが与えられた時、奇数であれば1に偶数であれば0に変換したリストを作成する。

問題10:数字のリストが与えられた時、それぞれを3で割った余りに変換したリストを作成する。