前回の続きです。例によって、この記事は入門したばかりの素人が書いてるので、信憑性のない個人用のメモとして捉えてください。

リストとタプル

タプル

(element_1, element_2, ..., element_n)

リストと類似していますが、リストとの違いは異なる型の要素を同一のタプルに格納できるという点です。ただし、注意しなければならない点は、タプルでは要素数が固定でなけれならないという点です。よって、cons演算子を浸かって動的にタプルを生成することは出来ません。また、Haskellでは一度定めた要素は不変ですので、タプルの要素を置き換えることもできません。

例：

Prelude> (True, 1, 'a')
(True,1,'a')
Prelude> (1,2,3)
(1,2,3)
Prelude> (,,) True 1 'a'
(True,1,'a')

以下では要素数が一致しない（要素数2のタプルに対し3つ格納しようとしている）のでエラー。

Prelude> (,) True 1 'a'

<interactive>:16:1: error:
    • Couldn't match expected type ‘Char -> t’
                  with actual type ‘(Bool, b0)’
    • The function ‘(,)’ is applied to three arguments,
      but its type ‘Bool -> b0 -> (Bool, b0)’ has only two
      In the expression: (,) True 1 'a'
      In an equation for ‘it’: it = (,) True 1 'a'
    • Relevant bindings include it :: t (bound at <interactive>:16:1)

もちろん、タプルとリストを併用することもできます。

Prelude> (1, 2, [3, 4])
(1,2,[3,4])
Prelude> [(1,2), (3,4)]
[(1,2),(3,4)]

ただし、リストにタプルを格納するときは、タプルの要素数が異なるとエラーになるので注意。

Prelude> [(1,2), (3,4,5)]

<interactive>:20:9: error:
    • Couldn't match expected type ‘(a, b)’
                  with actual type ‘(a0, b0, c0)’
    • In the expression: (3, 4, 5)
      In the expression: [(1, 2), (3, 4, 5)]
      In an equation for ‘it’: it = [(1, 2), (3, 4, 5)]
    • Relevant bindings include
        it :: [(a, b)] (bound at <interactive>:20:1)

タプルのアクセス関数

リストと同じ用に、タプルにもアクセス関数が存在します。

fst：1つ目の要素
snd：2つ目の要素

Prelude> fst(123, 456)
123
Prelude> snd(123, 456)
456

ただし、これらは要素数が2のタプルにしか使えません。以下の例では要素数が3なのでエラー。

Prelude> fst(123, 456, 789)

<interactive>:24:4: error:
    • Couldn't match expected type ‘(a, b0)’
                  with actual type ‘(a0, b1, c0)’
    • In the first argument of ‘fst’, namely ‘(123, 456, 789)’
      In the expression: fst (123, 456, 789)
      In an equation for ‘it’: it = fst (123, 456, 789)
    • Relevant bindings include it :: a (bound at <interactive>:24:1)
Prelude> snd(123, 456, 789)

<interactive>:25:4: error:
    • Couldn't match expected type ‘(a0, b)’
                  with actual type ‘(a1, b0, c0)’
    • In the first argument of ‘snd’, namely ‘(123, 456, 789)’
      In the expression: snd (123, 456, 789)
      In an equation for ‘it’: it = snd (123, 456, 789)
    • Relevant bindings include it :: b (bound at <interactive>:25:1)

レンジ

リストの規則性を列挙し、値域を示すことで、簡単な表記でリストの定義が可能です。

表記法：

[element_start .. element_last]

このように、最初の値と最後の値の間に..と入れてやればOK。
例：

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

リストの規則性を示すには、..の左側に2つ以上の要素を示します。例えば、奇数の要素だけを持つリストを生成するには

Prelude> [1, 3 .. 10]
[1,3,5,7,9]

1, 3, …と続き、10までのリストを示してやればOK。ただし、10は偶数なのでリストには含まれません。

無限リスト

要素数が無限のリスト。C言語のような多くの言語では要素数は有限ですが、Haskellでは無限のリストを扱えることができます。これは関数型プログラミング言語ならではの機能です。もちろん、無限といっても要素の規則性は決まっている必要があります。

例えば、以下の例では1〜∞のリストを生成します。実行すると無限に数字の羅列が表示されます。

Prelude> [1 ..]
[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,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167 （以下略）

万が一実行してしまった場合はCtrl+Cを押すなどして中断させましょう。

take関数

リストの最初の要素からn番目の要素までを取り出します。

take n <List>

例：

Prelude> take 3 [100, 200 ..]
[100,200,300]

リスト内包表記

リストを内包表記で示すことも可能。

[Var | Var <- [a .. z]]

例：

Prelude> [i | i <- [1 .. 10]]
[1,2,3,4,5,6,7,8,9,10]
Prelude> [i+1 | i <- [1 .. 10]]
[2,3,4,5,6,7,8,9,10,11]
[i-1 | i <- [1 .. 10]]
[0,1,2,3,4,5,6,7,8,9]
Prelude> [(i,j) | i <- [1 .. 3], j <- [1,2]]
[(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)]

なお、偶数ならTrueを返す関数even、奇数ならTrueを返す関数oddも利用可能。
偶数からなるリストを生成：

Prelude> [2*i | i <- [1 .. 5]]
[2,4,6,8,10]
Prelude> [i | i <- [1 .. 10], even i]
[2,4,6,8,10]

奇数からなるリストを生成：

Prelude> [2*i-1 | i <- [1 .. 5]]
[1,3,5,7,9]
Prelude> [i | i <- [1 .. 10], odd i]
[1,3,5,7,9]

すなわち、関数を使うことで特定の要素を取り出すこともできます。

条件分岐

if文

普通のif文です。

if <条件式> then <式1> else <式2>

thenの後にはその条件式が成立するときの式を、elseの後には条件が成立しないときの式を書きます。

例：引数=0なら”zero”、0以外なら”non zero”を返す関数

bunki :: Int -> String
bunki x = if x == 0 then "zero"
          else "non zero"

*Main> bunki 0
"zero"
*Main> bunki 1
"non zero"

ガード

if文とは異なる条件分岐の書き方です。複数の条件式を並べて書きます。

<関数> <引数1> ... <引数n>
  | <ガード条件1> = <式1>
  | <ガード条件2> = <式2>
  | otherwise = <式3>

ガード条件は|で区切って書きます。ここで気をつけなければならないのは、|の前に半角の空白2文字が必要になるという点です。これは前半で紹介したwhereと同じです。
最後のotherwiseというのはいずれの条件式にも当てはまらなかったときに実行される式で、if文でいうelseに該当します。

例：引数=0なら”zero”、0以外なら”non zero”を返す関数

guard :: Int -> String
guard x
  | x == 0 = "zero"
  | otherwise = "non zero"

*Main> guard 0
"zero"
*Main> guard 1
"non zero"

もちろん、複数の条件を並べて書くことも可能。

guard_2 :: Int -> String
guard_2 x
  | x == 0 = "zero"
  | x == 1 = "one"
  | x == 2 = "two"
  | otherwise = "other numbers"

*Main> guard_2 0
"zero"
*Main> guard_2 1
"one"
*Main> guard_2 2
"two"
*Main> guard_2 3
"other numbers"

不等号も使えます。

guard_3 :: Int -> String
guard_3 x
  | x == 0 = "zero"
  | x == 1 = "one"
  | x == 2 = "two"
  | x < 0 = "less than 0"
  | x > 2 = "more than 2"

*Main> guard_3 3
"more than 2"
*Main> guard_3 (-1)
"less than 0"

再帰

再帰を利用することで、繰り返し処理を実現できます。C言語などと同じです。
再帰に必要なものは以下の2つ。

停止条件
引数の操作

停止条件がなければ、関数は無限にループしてしまいます。また、毎回何らかの引数が変化しなければ、停止条件には永遠にたどり着きません。

例：リストの要素の総和を求める関数

sum_list :: [Integer] -> Integer
sum_list l
  | l == [] = 0
  | otherwise = head l + sum_list (tail l)

*Main> sum_list [1, 2, 3]
6

上の関数sum_listでは、1回の処理でリストの先頭要素を取り出し、残りの要素はsum_listを再帰的に呼び出すことで処理します。また、リストが空であれば0を返します。結果的に、後ろから順に要素を足し合わせることを再帰的に繰り返します。

sum_list [1, 2, 3]
= 1 + sum_list [2, 3] 
= 1 + (2 + sum_list[3])
= 1 + (2 + (3 + sum_list []))
= 1 + (2 + (3 + 0))
= 6

途中計算は入れ子構造になっており、これは数学的帰納法に基づいた処理です。この記事では、再帰的処理は今後もよく使います。

末尾再帰

上記のやり方では、コンピュータの内部の処理に着目するとスタックを利用します。スタックはループが長くなれば長くなるほど深くなりますので、要素数が多いとスタックオーバーフローを起こしてしまいます。

そこで利用するのが末尾再帰。普通の関数再帰では後ろから先頭に向かって入れ子構造で順に処理していますが、末尾再帰では先頭から後ろに向かって順に処理を行います。説明するのは難しいですが、要は引数を使って途中の計算結果を記憶させるだけです。

例：

sum_list_2 :: [Integer] -> Integer -> Integer
sum_list_2 l acc
  | l == [] = acc
  | otherwise = sum_list_2 (tail l) (acc + head l)

*Main> sum_list_2 [1, 2, 3] 0
6

先程示したsum_listと同じ計算結果を返します。引数にはアキュムレータとしてaccが追加され、ここの途中計算の結果が格納されます。リストの先頭要素を読み出してaccに足し合わせていき、最後に終了条件としてリストが空になったらaccをそのまま返します。関数を実行する際は初期値としてacc = 0とします。
処理としてはこんな感じ。

sum_list_2 [1, 2, 3] 0 
= sum_list_2 [2, 3] (0 + 1)
= sum_list_2 [2, 3] 1
= sum_list_2 [3] (1 + 2)
= sum_list_2 [3] 3
= sum_list_2 [] (3 + 3)
= sum_list_2 [] 6
= 6

これを見れば分かる通り、入れ子構造になっていません。よってスタックを使わずに、前から順に計算を行っていることがわかります。

補助関数

末尾関数ではスタックを使わずに再帰処理を実現できますが、実行時にアキュムレータに正しい初期値を与えなければなりません。例えば、sum_list_2でアキュムレータの初期値を間違えてacc = 1とした場合、

*Main> sum_list_2 [1, 2, 3] 1
7

このように、意図しない計算結果になってしまいます。

そこで、関数の中に補助関数として末尾再帰関数を宣言し、外側の関数でアキュムレータに正しい初期値を与えてやれば、実行時にアキュムレータの初期値を気にする必要はありません。

例：

sum_list_3 :: [Integer] -> Integer
sum_list_3 l = sum_list_3_aux l 0
  where
  sum_list_3_aux :: [Integer] -> Integer -> Integer
  sum_list_3_aux l acc
    | l == [] = acc
    | otherwise = sum_list_2 (tail l) (acc + head l)

上記の例では、外側の関数としてsum_list_3を定義し、その内部に補助関数としてsum_list_3_auxを定義しています。sum_list_3はsum_list_3_auxに対し、引数のリストと初期値acc=0を与えて実行します。これにより、実行時に初期値を指定することなく末尾再帰関数を実行できます。

*Main> sum_list_3 [1, 2, 3]
6

パターンマッチング

今までは関数の中で条件分岐を使って、引数に応じた関数を処理を定義していました。でも、もっと簡単かつ見やすい定義方法があります。それがパターンマッチングです。パターンマッチングでは、引数のパターンに応じて個別に処理を定義できます。

例：

sum_list_4 :: [Integer] -> Integer
sum_list_4 [] = 0
sum_list_4 l = head l + sum_list (tail l)

*Main> sum_list_4 [1, 2, 3]
6

上記の例では末尾再帰は浸かっていませんが、リストが空なら0を返し、それ以外ならhead l + sum_list (tail l)を返す、というように定義しています。パターンマッチングを用いずに定義した

sum_list :: [Integer] -> Integer
sum_list l
  | l == [] = 0
  | otherwise = head l + sum_list (tail l)

に比べれば、かなり見やすくなったと思います。
パターンマッチングでは上から下に向かって順に引数のパターンが合致するかを確認し、合致した時点で=の右側を実行します。よって、

sum_list_4 :: [Integer] -> Integer
sum_list_4 l = head l + sum_list (tail l)
sum_list_4 [] = 0

このように定義してしまうと、リストが空だろうが空でなかろうがsum_list_4 lにパターンマッチしてしまいますので、最後のsum_list_4 [] = 0にたどり着くことができません。

もちろん、複数のパターンを定義できます。
例えば、数値から文字列に変換する関数num_englishは

num_english :: Integer -> String
num_english 1 = "one"
num_english 2 = "two"
num_english 3 = "three"
num_english 4 = "four"
num_english 5 = "five"
num_english 6 = "six"
num_english 7 = "seven"
num_english 8 = "eight"
num_english 9 = "nine"
num_english 10 = "ten"

*Main> num_english 3
"three"
*Main> num_english 8
"eight"

このように定義できます。ただし、これでは未定義の値を実行するとエラーが発生します。

*Main> num_english 11
"*** Exception: main.hs:(24,1)-(33,22): Non-exhaustive patterns in function num_english

ここで、未定義の値が与えられたら「未定義だよ」と表示させたいと思います。「値はなんでもいいよ」という状態を示す際にはアンダースコア_を使います。

num_english :: Integer -> String
num_english 1 = "one"
num_english 2 = "two"
num_english 3 = "three"
num_english 4 = "four"
num_english 5 = "five"
num_english 6 = "six"
num_english 7 = "seven"
num_english 8 = "eight"
num_english 9 = "nine"
num_english 10 = "ten"
num_english _ = "undefined"

*Main> num_english 11
"undefined"

リストが空白であるパターンを示すには[]を使います。

list_empty :: [a] -> Bool
list_empty [] = True
list_empty _ = False

*Main> list_empty [1,2,3]
False
*Main> list_empty []
True

もちろん、パターンマッチングは複数の引数に対して利用可能。

f :: (Num a, Eq a) => a -> a -> String
f _ 0 = "Pattern1"
f 0 _ = "Pattern2"
f _ _ = "undefined"

*Main> f 1 0
"Pattern1"
*Main> f 0 1
"Pattern2"
*Main> f 0 0
"Pattern1"
*Main> f 2 2
"undefined"

マッチしたときの引数をそのまま返す

<変数名>@<パターン>という表記を用いることで、アンダースコア_を用いたパターンに対してもそのときの引数をそのまま返すことも可能。

g :: (Bool, Int) -> (Bool, Int)
g t@(True, _) = t
g t@(x, _) = (x, 0)

*Main> g (True, 123)
(True,123)
*Main> g (False, 123)
(False,0)

もちろん、引数パターンを返り値に組み込んで使うこともできます。

num_english_ex :: Integer -> String
num_english_ex 1 = "one"
num_english_ex 2 = "two"
num_english_ex 3 = "three"
num_english_ex 4 = "four"
num_english_ex 5 = "five"
num_english_ex 6 = "six"
num_english_ex 7 = "seven"
num_english_ex 8 = "eight"
num_english_ex 9 = "nine"
num_english_ex 10 = "ten"
num_english_ex t@_ = "undefined: " ++ show t

*Main> num_english_ex 5
"five"
*Main> num_english_ex 8
"eight"
*Main> num_english_ex 11
"undefined: 11"

タプルのマッチング

タプルは要素数が最初から決まっていますので、特定の位置の要素を取り出すということも可能です。

i :: (Bool, Int) -> Int
i (True, x) = x
i (False, x) = x * 2

*Main> i (True, 123)
123
*Main> i (False, 123)
246

リストの先頭要素の取り出し

パターンマッチングでは、引数に与えられたリストに対し(x:xs)などと表記することで、リストの先頭要素と先頭以外の要素を別々に取り出すことができます。これはアクセス関数のheadとtailの機能と同じです。

j :: [a] -> a
j (x:xs) = x

k :: [a] -> [a]
k (x:xs) = xs

*Main> j [1, 2, 3]
1
*Main> k [1, 2, 3]
[2,3]

関数jは引数のリストの先頭要素xを返す関数で、関数kは引数のリストの先頭以外の要素xsを返す関数です。引数に[1, 2, 3]を与えたとき、jでは先頭要素1が、kでは先頭以外の要素[2, 3]が取り出されています。

パターンマッチングの再帰処理への利用

パターンマッチングの機能を用いて再帰処理を実現すれば、今までよりももっと見やすくなります。
例えば、冒頭で作成したsum_listであれば、

sum_list :: [Integer] -> Integer
sum_list l
  | l == [] = 0
  | otherwise = head l + sum_list (tail l)

↓

sum_list_pm :: [Integer] -> Integer
sum_list_pm [] = 0
sum_list_pm (x:xs) = x + sum_list_pm xs

これだけで記述可能。

応用例

リスト同士の結合を実装

引数に与えられた2次元リストの中身の各リストを1次元のリストに結合します。

append :: Eq a => [[a]] -> [a]
append [] = []
append (l:ls)
  | l == [] = append ls
  | otherwise = (head l):append (tail l:ls)

*Main> append [[1,2,3],[4,5,6]]
[1,2,3,4,5,6]

各リストに関数を適用して結合

第2引数に与えられた2次元リストの中身の各リストに、第1引数で与えられた関数を適用して結合します。上で定義したappendを使います。

append_map :: Eq a => ([a] -> [a]) -> [[a]] -> [a]
append_map f l = append t
  where 
  t = append_map_aux f l
    where
    append_map_aux :: Eq a => ([a] -> [a]) -> [[a]] -> [[a]]
    append_map_aux _ [] = []
    append_map_aux f (l:ls) = (f l):append_map_aux f ls

*Main> append_map reverse [[3,2,1],[6,5,4]]
[1,2,3,4,5,6]

第1引数に与えた関数reverseはリストを逆順にする関数です。内部ではこんな処理が行われます。

append_map reverse [[3,2,1],[6,5,4]] = append t
  t = append_map_aux reverse [[3,2,1],[6,5,4]]
    append_map_aux reverse [[3,2,1],[6,5,4]] = (reverse [3,2,1]) : append_map_aux reverse [[6,5,4]]
      append_map_aux reverse [[6,5,4]] = (reverse [6,5,4]) : append_map_aux reverse []
        append_map_aux reverse [] = []
      append_map_aux reverse [[6,5,4]] = [4,5,6] : []
    append_map_aux reverse [[3,2,1],[6,5,4]] = [1,2,3] : [[4,5,6]]
  t = [[1,2,3],[4,5,6]]
append [[1,2,3],[4,5,6]] = [1,2,3,4,5,6]

リストから特定の要素の除去

第2引数に与えられたリストから、第1引数に与えられた引数を除去します。なお、1番最初に出てきた要素だけ除去すればいいものとします。

remove :: Integer -> [Integer] -> [Integer]
remove x [] = []
remove x (l:ls)
  | x == l = ls
  | otherwise = l:(remove x ls)

*Main> remove 2 [1,2,3,3,2,1]
[1,3,3,2,1]

前から順に再帰的に走査し、第1引数と同じ値の要素が見つかれば、後ろのリストをそのまま返します。

レンジ

引数nに対し、0〜(n-1)までの順に並んだリストを返します。末尾再帰で実装しています。

range :: Integer -> [Integer]
range n = range_aux n []
  where
  range_aux :: Integer -> [Integer] -> [Integer]
  range_aux 0 l = l
  range_aux n l = range_aux (n Prelude.- 1) ((n Prelude.- 1):l)

なお、Prelude.-というのはマイナス記号のことです。自分の環境ではMainのマイナス記号とPreludeのマイナス記号が混在しているようで、このように表記しないと実行できませんでした。本来はこんな関数になります。

range :: Integer -> [Integer]
range n = range_aux n []
  where
  range_aux :: Integer -> [Integer] -> [Integer]
  range_aux 0 l = l
  range_aux n l = range_aux (n - 1) ((n - 1):l)

*Main> range 10
[0,1,2,3,4,5,6,7,8,9]

終わりに

見慣れない概念が多く疲れました。しばらくHaskellは触りたくないです。

Haskellの入門メモ（後半）