Haskell でリストに対する関数を考えるときの視点 - オブジェクト指向からの類推

Haskell のリストに対する関数の定義

データコンストラクタによる値の生成

Haskell ではリストが特別扱いされている。(3.7 リスト)

リストを生成したいときは、

[0,1,2,3]

のように書く。

他の代数的データ型と違い、組込みの構文を使って表現できるため、最初リストにデータコンストラクタがあることに気がつかなかった。

データコンストラクタを使って書くなら、

0:1:2:3:[]

しかし、これまた随分長いこと

(：)

がデータコンストラクタであるという認識なし。二項演算子 (:) は、要素とリストをくっつけるために標準で用意されている一般的な関数だと思っていた。 ^^; (cf. Haskell の cons (コンス) )

更に言えば、

[]

もデータコンストラクタだと思わず。なんだかよくわからないけれど、要素のないリストを表わすのに [] を使うと覚えていただけ。

大学で情報系を専攻していたら、Lisp や Scheme などの所謂王道 (?) を学んだろうから、リストを生成するための cons は馴染深く、上記のような疑問を抱かなかったはず。いかんせん心理学だったもので、 Lisp は認知系の教科書の片隅にあった AI に関したコラムで見たのみ。その頃、括弧だらけの変態プログラミング言語だと思っていた。

 

関数を定義するときの場合分けはなぜ？

ところで、リストに関する関数の定義を見ると、

• 空の場合
• 要素がある場合

に場合分けるすることが多い。

例えば、リストの長さを返す関数を定義したいなら、

length []     = 0
length (x:xs) = 1 + length xs

「空リスト」 と 「空ではないリスト」 の場合に定義が分けられている。

リストの先頭要素を返す Prelude の head 関数 を見ても同じ。

head                    :: [a] -> a
head (x:_)              =  x
head []                 =  badHead

badHead :: a
badHead = errorEmptyList "head"

「空リスト」 に head を適用するとエラーを返すだけなのだけれど、定義がキチンとされている。

もちろん、定義してなくても動作しないことはない。その場合、

Non-exhaustive patterns in function head

というように、パターンマッチで失敗したことが通知される。

しかし、実装では空リストに対して head を適用すると、以下のエラーが返される。

*** Exception: Prelude.head: empty list

length 関数の定義に話を戻す。

はじめてこの定義を見たとき、どうも腑に落ちなかった。直感的に理解できないと言うか、定義が十分であることを肌で感じ取れないというか…。 (+_+)

命令型の言語にどっぷり浸っていたので、for 文のような繰り返しのための制御文で大きさを数えられないのかな？と最初思ったり。

 

宣言的という意味は？

関数型言語の説明としてよく聞くのが、

… 処理方法ではなく対象の性質などを宣言することでプログラミングする…

( 宣言型プログラミング - Wikipedia より )

A program that describes what computation should be performed and not how to compute it

( Declarative programming - Wikipedia より、太字は引用者による )

というもの。これが何を意味しているのかはさて置き、額面通り素直に受け取るなら、lenght の空リストに対する定義は、

length []     = 0

次のように解釈できる。

空リストの 「大きさ」 という性質は 0

これに対し、「空ではないリスト」 の定義はどう解釈したら性質を宣言していると言えるのだろう？

length (x:xs) = 1 + length xs

例えば、

リストの大きさは、先頭要素以外のリストの「大きさ」に 1 足した値

一見わかりずらい日本語。

ここで最初に気になったのは、パターンマッチでリストを 「先頭」 と 「残りの要素」 に分けて考えている処理。何となく what というよりは how を意識しているような気がするので、果たしてこれが性質を表わしていると言えるのか。…てゆうか、そもそも何をもって what による定義であると見なせるのかわからない。

また、再帰的な定義は、性質 (what) を記述しているのか、それとも処理方法 (how) を示しているのかどうかも判断できず。 (@_@;

ここまでをまとめると、以下の 3 点が不明。

• リストに対する関数で場合分けをすること
• how ではなく what により計算を表現すること
• 再帰的な定義が上記 2 点から見て何を意味するか

 

Control flow

まずは、宣言的なプログラミングについてもう少し調べる。

Declarative programming - Wikipedia によると、

declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow.^[1]

上記 Control flow - Wikipedia とは、

control flow (or alternatively, flow of control) refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated.

宣言的なプログラミングとは、「あれやってから、これやって…」 というように順序を記述することなく、計算のロジックを表現する方法だと。確かに例として挙げられている SQL の SELECT は、順序を指定することなく欲しいデータを取得できる。

Control flow に関しては、Neil Mitchell's Haskell Blog: Functional Flow Control の説明もわかりやすい。

In normal programming languages, there are many keywords for flow control, such as for, while etc. These flow control keywords encode a particular pattern of iteration, such as looping over a range (in the case of for) or continuing until some condition holds (while). Imperative programming languages continue to add more iteration keywords: both C#/Java have introduced some form of for-each; Python/C# have yield; Ada has many variants.

( 太字は引用者による。)

for や while などの control flow を表わすキーワードは、特別な計算のパターンを符号化していると。

計算のパターンに関して、CiNii 論文 -  関数プログラミングの実際 (<特集>関数型プログラミングと計算の基礎) では次のように述べられている。

構造的プログラミングは... 洗練された制御構造とデータ構造を用いてプログラムを設定・作成すべきであるという教えであり...
手続き型言語の文の構造化機構 ( if e then c1 else c2 や while e do c など ) とデータ構造化機構 ( array[T1] of T2 や record...end など) によって、文やデータの構成要素をより大きな構成単位に組み上げるという機能を利用している。つまり、これらは構成要素を結びつける糊(glue)の役割を果たしている...

関数プログラミングにおいては、関数を組み合わせる関数がプログラムの構成要素を結合する糊になる...

手続き型の糊の弱さのひとつに、そこでは構成要素を結合する際の計算のパターン、たとえば if e then c1 else c2 が制御の流れしか捉えていないということがある。

関数プログラミングの考え方は計算のパターンを抽象化して捉え、そこで成り立つ法則を用いてプログラムを合成したり、その性質を調べたりすることが特徴的である。... 計算パターンの性質は個々の構成要素とは独立しており、それ自体としても関数としての存在意義をもっている。...
関数 map のように、計算パターンを関数によって抽象することができる...
内包表記を map とほかのいくつかの関数を用いた式に変換することもできる...
左右のそれぞれの「たたみ込み(fold)」を行う計算パターンも一般的である。...
計算パターンを表わす関数の形式的な定義は再帰的に行う...

つまり、関数プログラミングでは、制御の流れも関数により表現し、そういった計算のパターンは再帰的に定義することができると。

先ほど 「リストの大きさを知りたいとき、for ループで数え上げればいいじゃん」 と反射的に思ったのは、「制御の流れを示す flow control を使う」という命令型の考え方であると言える。

ついでなので、length 関数を foldr や map などの計算のパターンを表現した関数を使って定義するなら、

length = foldr (\_ acc -> acc+1)  0

length = sum . map (\_ -> 1) 

数え上げるという意味では、末尾再帰により特定の変数にカウンタの役割を持たせた方が自然なのかも。

length xs = length' xs 0
    where
      length' [] acc     = acc
      length' (x:xs) acc = length' xs (acc+1)

話を元に戻して、上記から考えると、

length (x:xs) = 1 + length xs

の定義は、「あの計算をしてから、この計算をする」 ということが明示的に述べらていないことから宣言的な定義であると言えそうな気もするし、イヤイヤ、再帰的な定義そのものが実際には制御の流れを統制している計算のパターンだから、この部分が計算の how を表現しているとも言えそうな気がする。

それにしても、このままwhat と how について考えても length 関数の直感的な理解へと進みそうにない。また、制御の流れを意識しない定義は、定義としては満足かもしれないけれど、どうしてもイメージとして府に落ちないし、しっくり来ない。これは命令型脳であることの証左なのか。。

ともあれ、先ほど挙げた疑問の内、what / how について考えるのは諦め、以下の 2 点について直感的なイメージができるようにしたい。

• リストに対する関数の場合分けをする意味
• how ではなく what により計算を表現すること
• 再帰的な定義が何を意味するか

 

Java で cons 相当のクラスを定義して Haskell のリストを再考

自分の場合、直感的な理解ができたと感じるのは、オブジェクト指向からの類推で何が何に相当するのか対応付けができたとき。もう少し正確に言うなら、計算を担当する小人さんを想定し、小人たちのコラボレーションをイメージできた場合。 独立したモジュールを想定し、影響を与える範囲をほどほどに限定して、各々に役割を与え詳細を隠蔽。 「あれして、これして」 と各々に頼み、自分が知っている情報を用いて計算を行ってもらうというモデルは素朴でわかりやすい。

 

Cons クラスを元にリストを定義

では、Java で Haskell のリストのような構造を定義する場合、どのように考えればいいのだろう？Haskell のリストは特別に組込まれているが、代数的データ型で定義できるとしたら以下の通り。

data  [a]  =  [] | a : [a]  deriving (Eq, Ord)

( 6.1.3 リスト より )

2 つのデータコンストラクタからリスト型の値が作られる。

1. 空リスト
2. 型 a である要素 と リスト型をフィールドに持つ値

A Gentle Introduction to Haskell: Classes によると、

Haskell のクラスは大筋では Java のインタフェースに類似している。 Java のインタフェース宣言とおなじように、Haskell のクラス宣言はオブジェクトそのものを定義するのではなく、オブジェクトを使う手順を定義 している。

よって Java で定義するなら、リスト型をインターフェイスと見なし、それを実装したクラスが二つ。

1. 空リストに対応したクラス : Nil
2. 先頭要素 と 残りの要素に対する参照をフィールドとして持つクラス : Cons

全体として Composite パターン。

 

リストの大きさを返す length メソッドを実装するなら、IList インターフェイスの定義は、

public interface IList {

    public int length();
}

空リストに相当するクラス Nil は、

public class Nil implements IList {

    /**
     * リストの要素数を返す
     * @return 空リストなので 0
     */
    public int length() {
        return 0;
    }

    @Override
    public String toString() {
        return "Nil";
    }
}

(：) に相当する Cons クラスは、

public class Cons<T> implements IList {

    private T a;        // 先頭要素
    private IList l;    // 残りの要素

    public Cons(T a, IList l) {
        this.a = a;
        this.l = l;
    }

    /**
     * このリストの先頭に要素を追加する
     * @param a 先頭に追加する要素
     * @return 先頭に要素を追加したリスト
     */
    public Cons cons(T a) {
        return new Cons<T>(a, this);
    }

    /**
     * このリストの要素数を返す
     * @return リストの要素数
     */
    public int length() {
        return 1 + this.l.length();
    }

    @Override
    public String toString() {
        return this.a.toString() + "," + this.l.toString();
    }
}

試してみる。

public class Main {

    public static void main(String[] args) {
        Cons<Integer> l = new Cons<Integer>(3, new Nil()).cons(2).cons(1);
        System.out.println(l);
        System.out.println(l.length());
    }
}

結果は、

1,2,3,Nil
3

 

他の実装方法

下図のように Node クラスのオブジェクトを一方向につなぎ、次の Node オブジェクトを指し示していないオブジェクトを末尾と見なすという実装も考えられる。(cf. gist: 307278 - GitHub)

 

Haskell の代数的データ型の定義と Java のクラス定義を対比して

しかし、Haskell のリストをオブジェクト指向から類推するとき、むしろ先ほどのように型をインターフェイスと見なし、各々のデータコンストラクタをクラスと対応させる方がしっくり来る。なぜなら、

同じ型だけれど、それぞれが違うもの

ということが印象付けられ、各々の型がどう振る舞うべきかを考えるよう自然に動機付けられるから。つまり、IList インターフェイスにメソッドの宣言を追加したら、それを実装する Nil クラスと Cons クラスにメソッドを実装しなくてはならないことをコンパイラによって嫌でも意識させられる。

同じように Haskell で [a] 型の値に対する関数を定義するとき、上記に基いて考えると、データコンストラクタ [] と (:) によって生成される値に対する関数を定義する必要があることに思いが至る。

ただし、Haskell の場合、以下のように関数の型を宣言しても、必ずしも [] と (:) に対して定義しなければコンパイル時にエラーが出るわけではないことに注意。

length :: [a] -> Integer
length []     = 0
-- length (x:xs) = 1 + length xs

 

オブジェクト指向で実装するときのイメージ

ところで、先ほどの Haskell と Java の length の実装を比較するとよく似ている。

length []     = 0
length (x:xs) = 1 + length xs

Java の Nil クラス …

    public int length() {
        return 0;
    }

Cons クラス …

    public int length() {
        return 1 + this.l.length();
    }

Java で実装したときの頭の中のイメージは下図の通り。

• Nil クラスは要素を持たない。 よって、length の問い合わせで 0 を返す。
• Cons クラスは、
  • 自分が直接持っている要素は 1 つ。
  • リストに対する参照を持っており、これに対し length の問い合わせができる。その結果に自分が持っている要素の数を 1 つ足して、最終的な lenght の問い合わせに答える。

この実装方法は、極めて自然に考えることができる。特に、再帰的な関数の呼び出しが、連鎖しているオブジェクトの連続的な呼び出しとして表現されるので、動作しているイメージをしやすい。

 

Haskell をオブジェクト指向的に見ると…

この見方をしたとき、Haskell のデータコンストラクタによるパターンマッチの動作と、再帰的な定義の意味が違って見えるようになった。

ここでリストの値がデータコンストラクによって生成されることを明確に意識するために、リストを代数的データ型で定義する。

data List a = Nil 
            | Cons a (List a) 
              deriving Show

これで Java で定義したインターフェイスとクラスに対応させて考えやすくなる。

List a 型に対して、リストの大きさを返す関数を定義。

length             :: List a -> Int
length Nil         = 0
length (Cons x xs) = 1 + length xs

これに対して次のような見方をする。

1. パターンマッチにおけるデータコンストラクタ Cons をクラスと見なす。
2. データコンストラクタにより分解されたフィールドの値は、Cons クラスのプライベート変数。
3. x は Cons クラスが直接持っている値で、xs は List a 型の値への参照。

length 関数を Cons クラスのメソッドと見なし、右辺は Cons クラスのフィールドにアクセスできると考える。関数の適用する対象をオブジェクトと見なすなら、

length (Cons x xs)   =>   (Cons x xs).length()

length xs   =>   xs.length()

のように見立てると対応付けやすい。

「Java で型変数を利用して Cons , Nil クラスによるリスト表現 – map, filter, foldr, foldl の実装 」 につづく

 

関連記事

• Haskell の cons (コンス) - リストを生成するための演算子 (:)
• Java の型変数 とイレイジャ - 具体的な型の指定を忘れずに
• 再帰のイメージ