ペンギン村 Tech Blog

技術をこよなく愛するエンジニア集団が在住するペンギン村から、世界へ役立つ(かもしれない)技術情報を発信する技術系ブログです。某アラレちゃんが済む村とは一切関係ありません。んちゃ!

5. リストと再帰 :: Swift プログラマのための Haskell 入門

さて、前回は Swift の配列における典型的な操作(filter / map / reduce)について、Haskell の場合にどのように書けるのか見てきました。

今回は、リストの正体と再帰について見ていきます。

前回の訂正

前回の記事で 1 add 2 という書き方を「セクション記法」と説明していましたが、 正しくは (+1) のように演算子を部分適用する書き方が「セクション記法」でした。(記事は修正済みです)

blog.penginmura.tech

リストの実体

さて、リストは配列と同じように、同じ型の連続した値を持つことができるデータ構造です。例えば、配列と同じように任意のデータ型を扱えます。

xs :: [Int]
xs = [1, 2, 3, 4, 5]

ys :: [Char]
ys = ['a', 'b', 'c']

zs :: [String]
zs = ["Hello", "Haskell"]

前回の filtermapfoldl のことも考えると、配列とリストは見た目には殆ど変わらないように見えます。

大きく異なるのはメモリ上のデータ表現で、配列は連続したメモリデータとして確保されますが、リストは単方向連結リストとして表現されます。

可視化すると以下のような感じでしょうか。

f:id:yu_dotnet2004:20210308131757p:plain

リストは「要素」と「次の要素への参照(ポインタ)」を持った構造になっており、それがチェーンすることによって一連のデータ構造を表すことになります。なお、最後の要素は「次の参照先」が存在しないため、末端を表す値を指すようになっています1

配列は固定サイズの要素が連続するため、インデックスによるアクセス(array[2] など)は高速に行えますが、リストの場合は順にたどっていく必要があるため低速な点に注意が必要です。

リストを定義する

さて、このようなリストを Swift で定義するにはどうしたら良いでしょうか?

いくつか方法が考えられるかもしれませんが、最も素直なのは再帰的な enum を使った定義でしょう。

enum List<E> {
    case empty
    indirect case element(E, List<E>) // 再帰的に定義する際は `indirect` キーワードが必要
}

再帰的な enum を定義したことが無い方も多いかもしれませんが、先ほどの図と対応させるとそれほど難しくないでしょう。

List は「末端(および空リスト)を表現する empty 」または「要素を表現する element 」で表現され、element は「値」と「次の List への参照」を持つ、と読むと分かりやすいかもしれません。

配列 [1, 2, 3] に対応するリストは以下のように生成できます。

let xs: List<Int> = .element(1, . element(2, . element(3, .empty)))

ちょっと()がネストしていて読みづらいですね。演算子 <> を定義して読みやすいようにしてみます。

precedencegroup ListPrecedence {
    lowerThan: FunctionArrowPrecedence
    associativity: right
}

infix operator <>: ListPrecedence

func <> <T>(_ value: T, _ tail: List<T>) -> List<T> {
    .element(value, tail)
}

let xs: List<Int> = 1 <> 2 <> 3 <> .empty

ここでは演算子の定義についてはあまり重要でないため説明は割愛したいと思いますが、演算子 <> によってリストを末尾から組み立てているのが分かるかと思います。末端である .empty の先頭に値 3 を追加し、さらにその先頭に 2 を追加し、さらにその先頭に 1 を追加・・・と読めるかと思います。

Haskell のリストの実体

実は、Haskell におけるリストは先ほど Swift で定義したものと同じ構造になっています。リストを生成する [1, 2, 3] という表記は、実は以下のコードのシンタックスシュガーになっています。

xs :: [Int]
xs = 1 : 2 : 3 : []

先ほどの Swift のコードと並べると、対応関係が分かりやすいですね。

let xs: List<Int> = 1 <> 2 <> 3 <> .empty

末端(および空リスト)を表す値が .empty ではなく []、先頭に値を追加するのが <> ではなく : に対応することが分かります(実際には : は値コンストラクタとして定義されており、概念的には Swift コードでの .element(E, List<E>) に対応されているのですが、その点はややこしいので後述します)。

なお、Swift で書いたようにリストのデータ構造を Haskell で定義すると以下のようになるでしょう。

data List a = Empty
            | Element a (List a)

xs :: List Int
xs = Element 1 (Element 2 (Element 3 Empty))

これも Swift 版と比較すると分かりやすかと思います。

enum List<T> {
    case empty
    indirect case element(T, List<T>)
}

let xs: List<Int> = .element(1, . element(2, . element(3, .empty)))

このように Haskell では再帰的な直和型によってリストが実装されています。

このようなリストは一般的に「コンスリスト」と呼ばれ、関数型プログラミング言語において非常に重要なデータ構造になっています2

再帰的な関数

さて、ここまでリストの実体について詳しく解説したのは、実は再帰的な関数について説明するためです。Swift で再帰的な関数が定義できるように、当然ながら Haskell でも定義することが可能です。

(あまりに使い古された例ですが)以下は Swift で n 番目のフィボナッチ数を求める関数です。

func fib(_ n: Int) -> Int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fib(n - 1) + fib(n - 2) // 再帰呼び出し
    }
}

(1...7).map(fib) // [1, 1, 2, 3, 5, 8, 13]

0番目のフィボナッチ数は 1 、1番目のフィボナッチ数も 1 、それ以外のフィボナッチ数は1つ前と2つ前のフィボナッチ数を足し合わせたものである、とフィボナッチ数の定義そのままのコードになっているのが分かります。

Haskell のコードでは以下のように定義できます。

fib :: Int -> Int 
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2) -- 再帰呼び出し

あるいはガード構文を利用した書き方もできます。

fib :: Int -> Int 
fib n
    | n == 0 = 0
    | n == 1 = 1
    | otherwise = fib (n - 1) + fib (n - 2) -- 再帰呼び出し

リストの再帰処理

さて、先ほど Swift で enum を利用して自分でリストを定義しました。

enum List<T> {
    case empty
    indirect case element(T, List<T>)
}

配列における map のような働きをする関数はどのように書いたら良いでしょうか?

答えはパターンマッチと再帰を使って以下のように実装することです。

func map<A, B>(_ f: (A) -> B, _ list: List<A>) -> List<B> {
    switch list {
    case .empty:
        return .empty
    case .element(let x, let xs): // 要素と後続リストに分解
        return f(x) <> map(f, xs)
    }
}

let xs: List<Int> = 1 <> 2 <> 3 <> .empty
print(map({ $0 * 2 }, xs)) // [2, 4, 6] 相当

順番に見ていきましょう。

まず、関数のシグネチャから List<A> から List<B> に変換するもので、その変換関数として A -> B 型の関数を受け取る作りになっているのが分かります。AB はジェネリックパラメータとなっており、この関数のシグネチャを満たすものであれば任意の型を受け取ることができます。

次に、関数の実装として switch で与えられたリストが「末端である .empty」か「要素である element 」かを切り分けています。

まず .empty のケースではそのまま .empty を返しています。これは意図が分かりづらいかもしれませんが、「空の配列に map したら、その結果は空の配列である」のと同じ意味です。すなわち [].map(f) == [] であり、 map(f, .empty) == .empty ということです。

では .element のケースはどうでしょうか?まずパターンマッチによって「要素の値 value 」と「後続のリスト xs」に分解しています。そして、要素の値 x に関数 f を適用して変換し、それを後続のリスト xs を再帰的に map したリストにつなげています。

文章にするとややこしいですが、1つずつ動作イメージを考えると分かりやすいでしょう。以下は、処理の流れを正確に表したものではありませんが、動作イメージを理解する上での助けにはなるかもしれません。

f:id:yu_dotnet2004:20210308131830p:plain

Haskell では以下のように定義できます。

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

Swift での switch と対応させるように case of を使用すると以下のようにも書けます。

map :: (a -> b) -> [a] -> [b]
map f list = case list of
    []     -> []
    (x:xs) -> f x : map' f xs

コードの見た目が大分異なりますが、やっていることは Swift のコードと変わりません。

まず、関数の型注釈に現れている ab型変数と呼ばれ、Swift におけるジェネリックパラメータに対応するものです。型 a から型 b に変換する関数( a -> b )と a 型のリストを引数として受け取り、b 型のリストを返す、と読むことができます。

関数の実装としては、同じようにパターンマッチを行って、空のリストである末端がきたら末端をそのまま返し、そうでなければ「要素の値 x 」と「後続のリスト xs」に分解し、値 x には関数 f を適用し、後続のリストに再帰的に map を適用したものに繋げています。

リストのパターンマッチ

先ほどのコードに出てきた (x:xs) というリストを「先頭 x」と「後続リスト xs」に分解するパターンマッチは Haskell のコードにおいて非常に頻繁に登場するものです。

『Haskell のリストの実体』で、: が実際には値コンストラクタであり、Swift における.element(E, List<E>) に対応するものであると書きましたが、パターンマッチとして使用できている点からもそれが分かります。すなわち、Haskell におけるリストは以下のように定義されていると考えることができます。

data [a] = []
         | (a : [a])

リスト [a] は「末端(または空リスト)」を表現する [] または「要素と後続のリスト」を表現する a : [a] で定義される、と読むことができます。これは奇妙に見えるかもしれませんが、リストの定義やパターンマッチのコードを対応させると、なんとなく意味が見えてくるのではないでしょうか。

-- 空リスト
xs = []

-- 要素1のリスト
ys = 1 : [] -- [1] と同等

-- 要素2のリスト
zs = 1 : 2 : [] -- [1, 2] と同等

-- map関数
map :: (a -> b) -> [a] -> [b]
map f []       = ... -- 空リスト `[]` にマッチ
map f (x : xs) = ... -- 要素と後続のリスト `(a : [a])` にマッチ

map f (x : xs) について、ys の場合は map f (1 : [])zs の場合は map f (1 : (2 : [])) と、具体的な値に置き換えてみると分かりやすいでしょう。

ちなみに、(x : y : ys) といったように一度に複数の先頭要素を一気にマッチさせることも可能です。zs の場合には (1 : 2 : []) に分解されることになります。また、[x][x, y] といったように、要素数1のリストや要素数2のリストに具体的にマッチさせるような書き方も可能です。

以下は、先頭から最大3つまでの要素を足し合わせる(使いどころのわからない)関数の例です。

sumThree :: [Int] -> Int
sumThree []              = 0
sumThree [x]             = x
sumThree [x, y]          = x + y
sumThree (x : y : z : _) = x + y + z

sumThree []           -- 0
sumThree [1]          -- 1
sumThree [1, 2]       -- 3
sumThree [1, 2, 4, 8] -- 7

これらは使っていくうちに慣れていくと思うので、まずは基本となる [](x:xs) のパターンマッチだけ抑えておく感じでよいかなと思います。

再帰的な型・関数が重要な理由

さて、ここまで読んで「なぜ再帰なんて考える必要があるんだ?ループで回せば良いじゃないか!」と思った方も多いかもしれません。これは Haskell が純粋関数型言語であるため、命令形言語でおなじみのループが利用できないためです。

ループなしに繰り返しをどのように表現したらよいか、という答えが再帰処理であり、Haskell では一見ループが使われてそうな処理もすべて再帰関数によって実現されています。

前回見てきたように、リストについては標準で filtermapfoldl などの多数の操作が標準提供されているため、自分で再帰的な処理を考えずとも済みますが、自身で定義したデータ構造などでは再帰的な処理を記述する必要が出てきます。

そのため、Haskell を使う以上、再帰的な型や関数は切っても切れないものとなっています。

再帰的な考え方に慣れる

おそらく、再帰的な処理は慣れないうちは非常に難しく感じると思います。とくに自分で再帰的な処理を書こうとすると、思った以上に書き方がわからずに苦労するかもしれません。

再帰的な処理に慣れるためには、具体的なコード例を読むこと自分で考える練習をすることの2点が必要不可欠だと私は感じています。その中でもリスト操作は再帰的な考え方を鍛えるのにもっとも優れていると考えています。

今回の記事の終わりとして、いくつかのリスト操作用の関数を見ていきます。

length

length は、リストの個数を返す関数です。

length []        -- 0
length [1, 2, 3] -- 3

これは以下のように実装できます(自分でコードを書いて試す場合、標準の length と競合しないように length’length2 といったように関数名を変更しましょう)。

length :: [a] -> Int 
length []     = 0
length (_:xs) = 1 + length xs

パターンマッチの部分が、先ほどの x:xs ではなく _:xs となっていますが、_ は Swift と同様に値が不要なときに捨てるという意味になっています。

さて、関数シグネチャを見ると、任意の型 a のリストを受け取り、数値型である Int を返す、となっています。実装としては、空のリストであれば要素数は0、そうでなければ後続のリスト xs の要素数を再帰的に求め、それに +1 しています。

各要素が要素数 1 に置き換わると考えると分かりやすいかもしれませんね。

f:id:yu_dotnet2004:20210308131901p:plain

ここまで登場した fibmap の例でもそうでしたが、再帰関数では処理の基底部そうでない部分に分割することができます

”基底部”というとなんだか難しく聞こえますが、ようは再帰処理を伴わずに定義できる明白な部分のことです。例えば fib の例では1番目と2番目は 1 と定義されていましたし、 map ではリストが空の場合は空リスト、今回の length ではリストが空の場合は 0 、とそれぞれ具体的な値で表現できる、明白なパターンが含まれていました。このような基底部から考えるのが、再帰的な処理を書くコツとよく言われています。

そして、基底部ではない部分については、すでに再帰的な関数が完成している前提で、その再帰的な関数を使ってどのように定義したらよいか考えると良い、と言われています。fib の例では、fib nfib (n - 1)fib (n - 2) を足したものであると定義しました。また length の例では、リストを「先頭の値」と「後続のリスト」に分解し、先頭の値は要素数 1 で、後続のリストの長さ length xs を足したものがリスト全体の長さである、と定義しました。map についてもだいたい length と考え方は同じです。

filter

もう一つ例として filter の実装例を見てみます(処理が分かりやすいように過度に改行を入れています)。

filter :: (a -> Bool) -> [a] -> [a]
filter _ []     = [] -- 基底部
filter f (x:xs) =
    if f x
        then x:ys -- `x`が条件を満たす場合
        else ys   -- `x`が条件を満たさない場合
    where
        ys = filter f xs

基底部はリストが空の場合で、その時は当然ながら空のリストになります。filter f [] == [] ということですね。

基底部でない部分は、いつものように「先頭の要素 x」と「後続のリスト xs」に分解し、要素が条件を満たすならそれを残して後続をフィルタリングしたリストと繋げ、条件を満たさないなら単に後続をフィルタリングしたリストを返しています。

このコードは where を使ったローカルな変数の例にもなっています。 ys に相当する部分がいずれも filter f xs と同じコードとなるためローカルな変数 ys を定義しています。

練習問題

余力のある人は、Swift で定義したリスト List<T> に対して、同じように length 関数および filter 関数を定義してみてもよいでしょう。

let xs: List<Int> = 1 <> 2 <> 3 <> 4 <> .empty

length(xs) // => 2

filter({ 2 < $0 }, xs} // => [3, 4] 相当

他にも Swift の配列で可能なたくさんの操作を同じように定義してみたり、Haskell のコードで定義してみたりすると、再帰処理について考える良い練習になると思います。

まとめ

さて、今回のまとめです。

  • Haskell のリストは単方向連結リストである。
  • リストは直和と再帰によって定義されている。
  • Haskell でも再帰関数が定義できる。
  • 純粋関数型言語はループ処理が使えないため、繰り返しは再帰で表現する。
  • 基底部そうでない部分に分けて考えるのがコツ。
  • リストの再帰処理では、パターンマッチ [](x:xs) を利用するのが基本。
  • [x][x, y] といった書き方も可能。

今回は Haskell というよりも再帰処理の考え方という側面が強かったかもしれません。再帰処理を学ぶのがこの連載のテーマではないのですが、Haskell を学ぶ以上どうしても再帰的な考え方には慣れておく必要があると思い、今回の記事で取り上げた次第です。

次回は、後回しにしていていたレコード構文や多相型、そして Swift には無い概念であるカインドなどについて見ていく予定です。

blog.penginmura.tech

あとがき

『虫姫さまふたり Ver 1.5』のマニアックを5機設定でようやくワンコインクリアしました。(通常の3機設定でクリアできる気がしない・・・


  1. 関数型プログラミング言語において、このようなリストのことは「コンスリスト」と呼ばれ、末端のことを nil と表現することが多いのですが、Swift における nil リテラルと混同しやすいと思われるため、この記事では単に「末端」と表記しています。

  2. ”コンス”は”コンストラクタ”の略称で、データを構築するという意味からこの名称が使用されているようです。