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 の型変数 とイレイジャ - 具体的な型の指定を忘れずに
• 再帰のイメージ

JavaScript のクロージャ と オブジェクト指向

1. JavaScript における重要な概念

久しぶりに JavaScrip を書こうと思ったら、ほとんど頭の中から抜けている。 (+_+)

this とか prototype って何だっけ？というレベル。てゆうか考えてみたら、その辺読んだけど何かごちゃごちゃしていて頭に入らなったので面倒くさくなって言語仕様読むのやめたんだった。 ^^; シンプルなもの以外理解も記憶もできない。

ところで、以前に JavaScript のコードを書くときに参考にした本は、

• Douglas Crockford の 「JavaScript: The Good Parts」

JavaScript に関する本は、これしかまともに読んだことがない。

特に以下の部分が、JavaScript を使う上で参考になった。

• 3.9  グローバル領域の利用を減らす, p28
• 4.10 クロージャ, p43
• 5.2   オブジェクト指定子, p57
• 5.4   関数型, p59

上記の内容を思い出すために、例を考えながら、復習することに。

以下のコードは、 Aptana で書いて、 Firebug 上で実行した。

 

2. クロージャの意味

クロージャとは、レキシカルな環境において、束縛された自由変数を含む関数

まずはクロージャから。 Closure – Wikipedia によると、

… a closure is a first-class function with free variables that are bound in the lexical environment. Such a function is said to be "closed over" its free variable.

上記の First-class function とは、First-class function - Wikipedia によると、言語が以下の機能をサポートしていることを意味する。

• constructing new functions during the execution of a program,
• storing them in data structures,
• passing them as arguments to other functions,
• returning them as the values of other functions.

JavaScript は上記の要件を満たしているので、関数は first-class function 。この関数がレキシカルに束縛される自由変数を伴なっているものがクロージャ。

「レキシカル」 とは、Scope (programming) - Wikipedia によると、

With lexical scope, a name always refers to its (more or less) local lexical environment.

実行時のことを考えなくても書かれているコードを見れば、名前が何を指し示しているのかわかる。

「自由変数」 とは、Free variables and bound variables - Wikipedia によると、

… a free variable is a variable referred to in a function that is not a local variable or an argument of that function.

関数において、ローカル変数でも引数でも変数。

こういった関数がどのような状況で生じるかと言えば、先ほどの Closure – Wikipedia に戻り、

In some languages, a closure may occur when a function is defined within another function, and the inner function refers to local variables of the outer function.

関数の中で関数を定義し、内側の関数が外側の関数のローカル変数を参照する。

(cf. Ruby におけるクロージャの例 : Proc オブジェクトを返すメソッド )

 

関数を返す関数

例えば、「初期値」 と 「増分」 を持つ 「カウンター」 をモデル化するのにクロージャを利用してみる。次のことを念頭に置いて関数を定義。

• 関数の引数は 「カウンター」 の 「初期値」 と 「増分」。
• 返り値は、関数を呼出すごとに値を増分だけインクリメントする関数。
• 最初に与えた初期値を保持する変数を、インクリメントするたびに現在の値に更新する。

オブジェクト指向からの類推で言えば、

1. 関数の引数がプライベートなインスタンス変数
2. 返される関数がメソッド

var counter = function(val, step){
    return function(){
        val += step;
        return val;
    };
};

これを実行すると、

var c1 = counter(0, 1);
console.log(c1());        // 1
console.log(c1());        // 2
console.log(c1());        // 3

var c2 = counter(100, 10)
console.log(c2());        // 110
console.log(c2());        // 120
console.log(c2());        // 130

 

3. オブジェクト指定子とは

上記の関数における引数は、必要となる値を直接渡していた。 しかし、JavaScript: The Good Parts の 「5.2 オブジェクト指定子」 (p57) にはこのデメリットについて、次のように述べられている。

コンストラクタが受け取るパラメータの数が非常に多くなってしまうことは、よくあることだ。しかしそうなると、引数の順番を覚えるのがとても大変になってしまい、トラブルの原因にもなりやすい。

これに従い、オブジェクトを関数の引数として与えるように変更する。

var counter = function(spec){
    return function(){
        spec.val += spec.step;
        return spec.val;
    };
};

カウンターを生成する部分を変更。

var c1 = counter({val:0, step:1});

var c2 = counter({val:100, spec:10});

生成するときに、与える変数の順番を気にしなくていいところが便利。また、与える変数を増やす場合も、関数側で定義する引数を変更する手間が省ける。

 

4. オブジェクトを返す関数

上記では関数を返す関数を定義した。今度はオブジェクトを返す関数を定義してみる。ただし、上記と同様にクロージャが生成されるような構成にする。

関数を返す関数はメソッドが一つのオブジェクト。オブジェクトを返す関数は複数のメソッドがオブジェクトに詰め込まれているというイメージ。

例えば、「名前」 をフィールドに持つ 「人」 をモデル化したオブジェクトを返す関数を定義してみる。ここで生成される 「人」 オブジェクトは、メソッドとして 「名前」 を取得する関数と設定する関数を持つとする。

var person = function(spec) {
    return { getName : function(){ return spec.name; }
           , setName : function(n){ spec.name = n; }
    };
};

これを使い、

var tarou = person({name: "Tarou"});
console.log(tarou.getName());        // Tarou

tarou.setName("太郎");
console.log(tarou.getName());        // 太郎

 

アクセス制御

重要な点は、以下のように person 関数によって生成されたオブジェクトの内部的なプロパティにアクセスできないということ。 (cf. JavaScript: The Good Parts, p59)

console.log(tarou.name);             // undefined

これに対して new を用いて関数を呼出した場合は、クラスにおけるプライベート変数のような用い方ができない。

var Person = function(name){
    this.name = name;
};
var tarou = new Person("Tarou");
console.log(tarou.name);          // プロパティに直接アクセス
tarou.name = "太郎";               // プロパティを直接変更
console.log(tarou.name);

this が指すものは、呼出されたメソッドをプロパティとして持つオブジェクトであり、そのプロパティは外部からアクセス可能。

 

オブジェクトを返す関数 と クラス指向の言語におけるコンストラクタ

ところで、典型的なクラス指向の言語では、クラスを雛形とし、 new 演算子によりクラスに定義されたコンストラクタが呼出されオブジェクトが生成される。これに対して、上記で定義した関数 person はオブジェクトを返す普通の関数だった。

この点を考えると、クラス指向の言語でオブジェクトを生成する方法は、関数 person と同じくオブジェクトを生成するための手段であり、オブジェクトを生成することを意味的に明確にするための方便であることがわかる。

その意味で Douglas Crockford が勧めている「関数型」 (JavaScript: The Good Parts, p59) と呼んでいる 「クロージャを使ってオブジェクト生成する方法」 は、関数という手段のみが使われているシンプルな方法。わざわざ  new 演算子を導入する必要がない。

JavaScript で new 演算子と併用する this や prototype チェーンを使う前に、関数だけで書ける事柄は余計なものを使わずに書く方が頭の中がスッキリして良さげ。

 

プライベートメソッド

先ほどの person 関数は返すオブジェクトの中にメソッドが定義されていた。JavaScript: The Good Parts (p.61) ではこれを、

1. 関数の定義
2. 関数をオブジェクトのプロパティとして設定

の 2 段階に分けて書くことが推奨されている。

var person = function(spec) {
    var that = {};
    
    var getName = function(){ return spec.name; };
    that.getName = getName;
    
    var setName = function(n){ spec.name = n; };
    that.setName = setName;       // これを削除
    
    return that;
};

これにより、setName 関数を that のプロパティに設定しなければ、setName はプライベートメソッドになる。

 

5. 継承

次にオブジェクト指向の拡張に相当するものを書いてみる。(cf. JavaScript: The Good Parts , p60)

その前に準備として、「人」 オブジェクトを以下のように変更。

• 年齢をフィールドに持つ
• 年齢を問い合わせても答えない

ただし、「人」 を継承したオブジェクトは年齢を答えるものとする。また、継承したオブジェクトから利用できるメソッドを 「人」 オブジェクトは持つものとし、これを defaultGetAge 関数とするなら、

var person = function(spec, my){
    my = my || {};
    var that = {};
    
    var getName = function(){
        return spec.name;
    };
    that.getName = getName;
    
    var defaultGetAge = function(){
        return "私の年齢は" + spec.age + "です";
    };
    my.defaultGetAge = defaultGetAge;
    
    return that;
};

上記 my の使われ方は、person 関数を拡張した関数を見てからの方が理解しやすい。少なくとも、that のプロパティに defaultGetAge 関数が設定されてないので、「人」 オブジェクトは年齢に関して答えることができないことはわかる。

「人」を継承した 「羽の生えた人」 と 「ヒレのある人」 を想定する。

/**
 * 羽の生えた人
 */
var personWithWings = function(spec, my){
    my = my || {};
    var that = person(spec, my);
    
    var fly = function(){
        return "飛んでるぅ～";
    };
    that.fly = fly;
    
    var getAge = function(){
        return my.defaultGetAge();
    }
    that.getAge = getAge;
    
    return that;
}

/**
 * ヒレのある人
 */
var personWithFin = function(spec, my){
    my = my || {};
    var that = person(spec, my);
    
    var swim = function(){
        return "泳いでるぅ～";
    };
    that.swim = swim;
    
    var getAge = function(){
        return my.defaultGetAge();
    };
    that.getAge = getAge;
    
    return that;
}

拡張した関数から、拡張元の関数に変数 my を渡し、そこへ未公開の関数を詰め込んでもらうイメージ。

これを使ってみる。

var hanako = person({
    name: "Hanako",
    age: 15
});

var jiro = personWithWings({
    name: "Jiro",
    age: 15
});

var tarou = personWithFin({
    name: "Tarou",
    age: 21
});

console.log(hanako.getName());     // Hanako

console.log(jiro.getAge());        // 私の年齢は15です
console.log(jiro.fly());           // 飛んでるぅ～

console.log(tarou.getAge());       // 私の年齢は21です
console.log(tarou.swim());         // 泳いでるぅ～

「Javascript から見る Ruby のイテレータ – Enumerable」 ヘつづく。

 

関連記事

• Google 検索と同時に Google ブックマーク の検索結果を表示する Greasemonkey スクリプト

参考

• プログラミング言語の進化を追え：大人のためのブラックボックス読解講座――クロージャとオブジェクトの微妙な関係 (1/2) - ITmedia エンタープライズ
• Lexical scoping

Haskell のモジュールの階層化と、型クラス - パラメータ多相とアドホック多相

0. 目次

• 1. 同じ名前のフィールドラベルを持つ型を定義したい
• 2. モジュールを分割し、階層化する
• 3. 型の意味
• 4. 型クラスの役割
• 5. パラメータ多相と、アドホック多相
• 6. 多相性とオブジェクト指向
• 7. 演算子の意味
• 8. 継承とジェネリクス
• 9. Ad hoc の意味
• 10. 型クラスの定義と、インスタンス化
• 11. 余談： モジュールに分けない場合

 

1. 同じ名前のフィールドラベルを持つ型を定義したい

2 つの型が、類似している場合、フィールド名に同じ名前を使いたい。

例えば、「名前」と「年齢」を持つ、「犬」型を定義する。

このとき、フィールドラベルを使うなら、

data Dog = Dog {name :: String, age :: Int} deriving Show

「犬」型と同様のフィールドを持つ、「猫」型も定義。

data Cat = Cat {name :: String, age :: Int} deriving Show

しかし、同一モジュール (ここでは Main モジュール) で、同じフィールド名を持つ型を定義すると、エラーが発生する。 (+_+)

Multiple declarations of `Main.name'
...
Multiple declarations of `Main.age'
...

理由は、3.15 フィールドラベルをもつデータ型 の 3.15.1 フィールドの選択 によると、、

フィールド名は選択子関数として使用する。変数として使用するときは、 フィールド名はオブジェクトからそのフィールドを取り出す関数として働く。 選択子はトップレベルの束縛なので局所変数によって覆い隠される。しかし、 同じ名前の他のトップレベルの束縛とは衝突することは出来ない。…

(太字は引用者による)

フィールド名は、単なる名前ではなく、フィールドの値を返す関数。名前空間は、トップレベルに所属するので、代数的データ型の中に書いているように見えても、バッティングに注意が必要ということ。

つまり、以下のように、フィールドラベルは「関数」となるので、同じ名前の関数を二つ作れない。

*Main> name $ Dog "pochi" 3
"pochi"

 

2. モジュールを分割し、階層化する

では、同じフィールド名を持つ、異なる型を定義したい場合、どうすればいいのだろう？

2.2.1. Modules vs. filenames によると、

How does GHC find the filename which contains module M? Answer: it looks for the file M.hs, or M.lhs.

GHC の場合、各々の型を別モジュールに定義し、別ファイルに含めるということ。

つまり、先ほどの例の場合、「犬」と「猫」型に対応したモジュールを作成し、それぞれのファイルに記述すれば良い。

説明に従い、最初に、「犬」型を ファイル Dog.hs に定義。

module Dog where
    data Dog = Dog {name :: String, age :: Int} deriving Show

ところで、GHC ではモジュールを階層化できる。

• cf. 7.3.3. Hierarchical Modules

The Glorious Glasgow Haskell Compilation System User's Guide, Version 6.10.2 の 5.6.1. Haskell source files によると、

Usually, the file should be named after the module name, replacing dots in the module name by directory separators. For example, on a Unix system, the module A.B.C should be placed in the file A/B/C.hs, relative to some base directory.

モジュールのベースとなるディレクトリを想定し、そこからの相対位置で、モジュール名が決まる。モジュール名は、モジュールを配置したディレクトリの階層に対応させ、`.’ により階層化していることを示すということ。

• cf. 8.3.3. Hierarchical Modules

例えば、先ほどの「猫」型をやめ、「三毛猫」型を Cat 階層に作りたい。この場合、

1. Cat ディレクトリを作成し、
2. 下記のモジュールを Mike.hs に記述し、Cat ディレクトリに配置。
3. その際、モジュール名は、モジュールを配置したディレクトリに対応させるために Cat.Mike とする。

module Cat.Mike where
    data Mike = Mike {name :: String, age :: Int}

全体では、以下のようにファイルを配置する。

Dog.hs
Cat
-- Mike.hs

ただし、メインモジュールにおいて、フィールドラベルを用いて「名前」を表示したい場合、関数名 (フィールドラベル) をモジュール名で修飾しなくてはならない。

import Dog
import Cat.Mike
main = do print $ Dog.name $ Dog "pochi" 3
          print $ Cat.Mike.name $ Mike "tama" 2

できることなら、関数を適用するとき、モジュール名で修飾せず、シンプルに name と書きたい。

そのためには、「型クラス」を使い、関数のオーバーロードを行う必要がある。

 

3. 型の意味

その前に、「型」について整理しておく。

「データベース実践講義」の「2.3 型とは」(p34) によると、

型とはいったい何か。基本的には、値の名前付き有限集合である。…

すべての型が、その型の値もしくは変数に作用する演算子の連想集合を持つ …

Data type - Wikipedia, the free encyclopedia には、

In a broad sense, a data type defines a set of values and the allowable operations on those values.

つまり、「型」とは

1. 値の集合と、
2. その値に対する、操作が定義されたもの。

上記より、オブジェクト指向における「クラス」を連想した。なぜなら、

1. 「値」に相当するインスタンスと、
2. 「操作」に相当するメソッドを持つため。

Data type - Wikipedia には、型 (データ型) と呼ばれるものには、いくつか種類があることが示されている。

• 2.1 Abstract data types
• 2.2 Algebraic data types
• 2.3 Composite data types
• 2.4 Function types
• 2.5 Machine data types
• 2.6 Object types
• 2.7 Pointer and reference data types
• 2.8 Primitive data types

上記データ型の違いの一例を挙げると、オブジェクト型では、内部状態を持つのに対して、Haskell のような代数的データ型では、値の集合を定義するのみで、操作を定義する場合、別に関数定義する。

 

4. 型クラスの役割

では、「型クラス」とは何か？

Type class - Wikipedia によると、

Type classes first appeared in the Haskell programming language, and were originally conceived as a way of implementing overloaded arithmetic and equality operators in a principled fashion.

 A Gentle Introduction to Haskell: Classes には、

There is one final feature of Haskell's type system that sets it apart from other programming languages. The kind of polymorphism that we have talked about so far is commonly called parametric polymorphism. There is another kind called ad hoc polymorphism, better known as overloading.

Here are some examples of ad hoc polymorphism:

• The literals 1, 2, etc. are often used to represent both fixed and arbitrary precision integers.
• Numeric operators such as + are often defined to work on many different kinds of numbers.
• The equality operator (== in Haskell) usually works on numbers and many other (but not all) types.

(太字は引用者による)

型クラスは、Haskell の特徴の一つで、Haskell で初めて導入された。多相性には、パラメータ多相と、アドホック多相があり、後者はオーバーロードと呼ばれる。

型クラス（Type class - Wikipedia） の説明に戻る。

a type class is a type system construct that supports ad-hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and a type variable a, and means that a can only be instantiated to a type whose members support the overloaded operations associated with T.

上記について、「Haskell の代数的データ型と型クラス、instance 宣言の関係」で使い方を確認した。しかし、そのとき、代数的データ型と、型クラスの関係が理解しにくく、知識として定着しなかった。

オブジェクト指向におけるオーバーロード、オーバーライドには馴染みがある。しかし、パラメータ多相、アドホック多相、それに加えて、型クラスがどう絡んでいるのかイメージがしずらい。(+_+)

「アドホック多相は、関数を適用する対象を制約するための手段。 Haskell では、それを型クラスによって実現している。」

と頭に叩き込もうとした。しかし、直観的に理解できず、しっくり来なかった。 (@_@;)

しかし、次のように考えたら、スッキリした。

1. 型は値をグループ化する。
2. 型クラスは、型をグループ化する。
3. その結果、型クラスの制約が付いた関数は、その型クラスのグループに属していない型には適用できない。
4. インスタンス化とは当該の型クラスに所属する宣言。

 

5. パラメータ多相と、アドホック多相

Type polymorphism - Wikipedia によると、Christopher Strachey が、二つの異なる多相について述べていたとのこと。

それによると、「アドホック多相」とは、

If the range of actual types that can be used is finite and the combinations must be specified individually prior to use …

それに対して、「パラメータ多相」とは、

If all code is written without mention of any specific type and thus can be used transparently with any number of new types …

つまり、アドホック多相は、関数を適用する型を制限するのに対して、パラメータ多相は、具体的な型について言及しないことにより、新しい型に対応できるようにするということ。

 

6. 多相性とオブジェクト指向

パラメータ多相と、アドホック多相は、オブジェクト指向において、どのように対応しているのだろうか？

Polymorphism (computer science) - Wikipedia によると、

In object-oriented programming, subtype polymorphism or inclusion polymorphism is a concept in type theory wherein a name may denote instances of many different classes as long as they are related by some common super class.^[1] Inclusion polymorphism is generally supported through subtyping, i.e., objects of different types are entirely substitutable for objects of another type (their base type(s)) and thus can be handled via a common interface. Alternatively, inclusion polymorphism may be achieved through type coercion, also known as type casting.

オブジェクト指向においては、サブタイプ多相と呼ばれる。オブジェクトが、共通のインターフェイスを実装している場合、他のオブジェクトに置き換えることができるというもの。

また、Operator overloading - Wikipedia によると、

(less commonly known as operator ad-hoc polymorphism) …

operators like +, =, or == have different implementations depending on the types of their arguments.

演算子オーバーロードは、アドホック多相に相当するとのこと。

オーバーロードと言えば、以下のようにいくつか種類がある。

Function overloading, a software engineering process whereby multiple functions of different types are defined with the same name

Operator overloading, a software engineering process whereby operators such as + or - are treated as polymorphic functions having different behaviours depending on the types of arguments used

Method overloading a type of polymorphism where different functions with the same name are invoked based on the data types of the parameters passed

(Overload - Wikipedia, the free encyclopedia より)

 

7. 演算子の意味

ところで、「演算子」というと、Java しか知らなかったとき、メソッドとの違いを明確にイメージしていた。

`+’ のように、「メソッド名にできない記号が演算子」と言う意識。

この Java の仕様は、以下で述べられている。

Sun deliberately chooses not include operator overloading in the Java language.

(Operator overloading - Wikipedia, the free encyclopedia より)

Ruby は Java と違い、再定義可能な演算子 がある。

|  ^  &  <=>  ==  ===  =~  >   >=  <   <=   <<  >>
+  -  *  /    %   **   ~   +@  -@  []  []=  `

Haskell は、 Haskell 98 字句構造 で述べられている。

Python は、__XXXXX__() という形の 特殊メソッド を、クラスが実装することによって、同様のことが可能。

• cf. Ruby における演算子の再定義と、Python の演算子オーバーロード - コンテナの要素を添え字で参照するためメソッド

そういえば、Haskell に触れるようになってから、関数と演算子の差異をあまり感じなくなった。なぜなら、関数の中置記法があるため。

• cf. Haskell のセクションと中置記法

演算子 – Wikipedia とは、

コンピュータプログラミングにおいては、主に記号を用いて演算を指示するものが演算子と呼ばれる。概ね数式などの記述を模倣しているが、一部の演算子に通常と異なる記号が用いられたり、副作用を持っていることがあるなど、数学の演算子とは異なる点もある。

関数 f(x) の "f( )" も単項演算子であり、符牒となる文字列 "f" を関数子などと呼ぶ場合もある。関数子としては任意の文字列を使用することができ、代表的なものとして三角関数 "sin", "cos", "tan" などが挙げられる

つまり、演算子も関数も、使える記号と記法が違うだけで、本質的な違いはない。

考えてみれば、メソッドオーバーロードは、同一クラス内で、異なる引数に対する処理に、同じ名前を付けること。メソッドの引数を、関数プログラミングで言う適用する対象と見れば、メソッドオーバーロードは、メソッドが所属するクラスは同じでも、適用する対象が異なるという点で、演算子オーバーロードと似ている。

「メソッドのシグニチャは、なぜ返り値を含まないんだ？」

と、以前から疑問に思っていた。しかし、1 + 2 と 3 + 4 の結果、型が異なるような実装ができたらおかしいか。

• cf. Haskell の返り値の型を指定する関数

 

8. 継承とジェネリクス

話を戻して、オブジェクト指向におけるアドホック多相とは、オーバーロードに相当する。

先に挙げた Christopher Strachey  の言うところの

「メソッドの引数の型がある範囲に限られている」

ということによる。

型が「限られている」という点から見ると、

Ad-hoc polymorphism is generally supported through object inheritance, …

(Type polymorphism - Wikipedia より)

オブジェクト指向の継承も、アドホック多相に相当する。

逆に、「限定されていない」と言うのは、

In the object-oriented programming community, programming using parametric polymorphism is often called generic programming.

ジェネリクスのこと。

 

9. Ad hoc の意味

ところで、「アドホック」というと

「アドホックな仮説 - Wikipedia」

という使われ方を連想する。言葉自体に、良いイメージがない。

そもそもの意味は Yahoo!辞書 - ad hoc によると、

((限定))そのためだけに［の］, 特別に［な］

Ad hoc - Wikipedia には、

Ad hoc is a Latin phrase which means "for this [purpose]". It generally signifies a solution designed for a specific problem or task, non-generalizable, and which cannot be adapted to other purposes.

 

10. 型クラスの定義と、インスタンス化

さて、最初の「犬・猫」型のコードに戻る。型クラスを使い、異なる型に、同じ関数名を適用できるようにしたい。

そのためには、型をグループ化する、型クラスを定義する。

Name.hs

module Name where
    class Name a where
            getName :: a -> String

次に Dog.hs

module Dog where
    import Name
    data Dog = Dog {name :: String, age :: Int} deriving Show
    instance Name Dog where
           getName (Dog name age) = name

同じようにして Cat/Mike.hs

module Cat.Mike where
    import Name
    data Mike = Mike {name :: String, age :: Int}
    instance Name Mike where
                getName (Mike name age) = name

ついでに、メインモジュールにおいて、getName 関数を利用して

「こんにちは！○○.」

と出力する hello 関数も定義する。

import Dog
import Person
import Name
import Cat.Mike

hello :: Name a => a -> String
hello x = "Hello! " ++ getName x ++ "."

main = do print $ getName (Mike "mike" 100)
          putStrLn $ hello (Mike "mike" 30)

 

11. 余談： モジュールに分けない場合

もし、モジュールに分けずにシンプルに書くとしたら、

1. 犬と猫に共通の Pet 型を作り、
2. そこで名前と年齢を持たせる。

ついでに、犬と猫を同じ型にして、定義してみた。

data Pet = Pet { name :: String, age :: Int }
data MyPet = Dog Pet | Cat Pet

getName :: MyPet -> String
getName (Dog p) = name p
getName (Cat p) = name p

main = do print $ getName $ Dog (Pet "Pochi" 10)
          print $ getName $ Cat (Pet "Tama" 3)

 

関連記事

• Haskell の数値 – Int は型で Num は型クラス

関連サイト

• 型変数

配列を「集計」するときの手順のわかりにくさ

1. 配列の要素を集計をするときに感じた違和感

配列の要素を集計をすることを考える。

例えば、1 ~ 5 までの整数に対して、

1 + 2 + 3 + 4 + 5

の答えを求める場合、次のような手順を踏む。

Ruby で書くなら、

ary = [1, 2, 3, 4, 5]

total = 0
for elem in ary
  total += elem
end

puts total

もちろん、慣れているので、この計算の方法に抵抗は感じない。

しかし、この手順を初めて見たとき、

「わかりにくい」

と感じた。極めてシンプルなコードなんだけれど、どこか頭が混乱するような、そんな感覚に陥ったことを覚えている。

では、その原因はどこにあったのだろうか？

 

2. わかりにくい理由は、「要素の走査」「計算」「変数の再代入」を行なっているから

頭が混乱する印象を受けたのは、以下の箇所。

total += elem

コードの意味を、わかりやすくするために、書きなおす。

total = total + elem

全体のコードで行なっていることは、

1. for によって要素を走査し、
2. その途中で計算を行う。

気になるのは、total の使い方。 配列を走査している最中に、

1. 集計するための total から値を取り出し、
2. それを計算の後、再び total へ設定する。

つまり、以下の 3 つの要素が絡み合っているため、何をやっているのか想像しにくい。

• 「要素の走査」
• 「計算」
• 「変数の再代入」

 

3. 最初は集計の方法をイディオムとして覚えた

プログラミングを始めた当初は、厳密にどのように動いているかというよりも、

このようなイディオムによって集計を行うんだ

と、感覚的な理解をしていた。

今では、配列の要素を「集計」しようと考えたとき、自然と上記のようなコードを書く。しかし、これがどのように動くかを、頭の中で全て思い描けるかと言えば、実はあやしい。デバッガを動かし、それぞれの変数の動きを目で追い、「なるほどなぁ」と思う。それでもコードを見ると、だまされたような感覚に陥る。

ところで、自分の頭の容量は小さい。同時に色々なことを覚えておくことも、把握しておくこともできない。将棋の棋士は、同時に何手先も読むと言うが、あれはいったいどういう頭の仕組みをしているのだろうか。だから、自分の「集計」に対する理解は、まるで刺激に対する反応するようなものだと感じる。これが要求されたら、この方法をとる。まるで、条件付けされているパブロフの犬のようだ。

 

4. 計算の様子をイメージすると、わかりにくい理由がより明確になる

集計をするコードに戻る。

変数 total が、全体を理解する上で、やっかいな存在。 最初に変数が宣言されているのが、for ループの外にある。つまり、要素を走査することとは、別の文脈に存在する。それが要素を走査している文脈に絡んでくるからわかりにくい。

「いつ、どこで、何をしているのか？」

が把握しにくい。

特に、total に elem の値を加算した後、自分自身に再代入しているので、

「誰がどうなったの？」

って感じる。 (@_@;)

イメージしにくいので、絵を描いてみる。そうするば、見通しが立てやすくなる。

1. 配列の要素を elem に割当てる。
2. total と elem を加算する。
3. 上記の結果を total に割当てる。

1 ~ 3 を要素ごとに繰り返す。

絵を描いてみると、「加算」を行っている文脈と、 total が存在する文脈が異なっていることがはっきりする。しかし、コード上では、

total = total + elem

のように、一文で簡潔に表現しされている。

この点が、自分のように容量の小さい頭には、イメージするのが難しい所。複数の文脈が一箇所に集約されていることが混乱の元になっている。

 

5. 計算の手順を分離し、各々役割をクラスに与える

では、これを理解しやすくするには、どうすればいいのだろう？

「要素の走査」「計算」「変数の再代入」を、次のように二つに分けて考えることにした。

• 「要素の走査」
• 「計算」「変数の再代入」

下図のようなイメージした。

集計をするための Total クラスを作り、集計をするための役割を与えた。つまり、「計算」「変数の再代入」の操作を Total クラスにカプセル化。 (まぁ、普通こんなことはしないけれど ^^;)

# 集計の値を保持するクラス
class Total   attr_reader :value  # 集計の値   # 初期化   def initialize    @value = 0   end   # 集計の値に val を加算   def add(val)    @value += val   end
end

add メソッドの中身を見ると、「与えられた値を、これまでの値に加算する」という、極めてシンプルな役割を持っていることがわかる。

このクラス使うには、以下のようにする。

ary = [1, 2, 3, 4, 5, 6]

total = Total.new
for elem in ary
  total.add(elem)
end

puts total.value

for ループの中身を見ると、要素を走査し、Total に「要素の値を追加してね☆」とお願いしているだけになる。

繰り返すが、普通こんなコードは書かない。ただし、自分のようにワーキングメモリの小さい脳みそにとって、このような表現の方が、動作の理解はしやすいと感じる。

 

6. Enumerable の inject を使う場合

ところで、Ruby を使っているなら、イテレータを使って、次のように書くことができる。

total = 0
[1, 2, 3, 4, 5, 6].each do |elem|
  total += elem
end
puts total

Enumerable の inject メソッドを使えば、より簡潔に、

puts [1, 2, 3, 4, 5, 6].inject{|result, item| result + item}

ただし、シンプルだけど、動作をイメージしにくい。

Enumerable - Rubyリファレンスマニュアル によると、

inject([init]) {|result, item| ... }

最初に初期値 init と self の最初の要素を引数にブロックを実行します。2 回目以降のループでは、前のブロックの実行結果と self の次の要素を引数に順次ブロックを実行します。そうして最後の要素まで繰り返し、最後のブロックの実行結果を返します。 ...

初期値 init を省略した場合は、最初に先頭の要素と 2 番目の要素をブロックに渡します。この場合、要素が 1 つしかなければブロックを実行せずに最初の要素を返します。要素が空なら nil を返します。

inject の意味は、Yahoo!辞書 - inject によると、

1 …を（…に）注入する((into ...))；…に（…を）注入［導入］する, 入れる((with ...))

inject a tank with water ［＝inject water into a tank］ タンクに水を注ぎ入れる

ブロックで実行した結果を、再注入するという意味合いなのだろうか？

あぁ～、それにしても動作を想像しにくい。 パタッ(o_ _)ｏ~†

とりあえず、絵に描いておこう。

1. 先頭から 2 つ要素を取り出し、ブロック変数へ入れる。
2. ブロックで実行した結果と、次に要素を取り出し、ブロック変数へ入れる。

これを末尾まで繰り返す。

 

7. 「再帰」で集計するには

for ループを使った計算は、再帰的な定義で置き換えることができる。

ary = [1, 2, 3, 4, 5, 6]

def total(ary)
  return ary[0] if ary.size == 1
  return ary[0] + total(ary[1..ary.size-1])
end

puts total(ary)

これは、次のように集計の手順を考えていると言える。

合計 = 要素の先頭 + 2 番目以降の要素の合計

要素が一つしかない場合は、当然、次のようになる。

合計 = 要素の先頭

イメージとしては、

「先頭と、それ以降、という構造」が、リストの至るところで見られると見なし、順次関数を適用していく方法。

この方法では、「要素の走査」という部分が、「再帰的な関数の適用」にすりかわり、「変数の再代入」が消失し、「計算」のみが残っている。しかし、これが直観的にわかりやすいかどうかと問われたら、微妙。 ^^;

慣れの問題なのかな？