Java の型変数 とイレイジャ - 具体的な型の指定を忘れずに

Java の型変数に慣れるための練習。

例えば、変数を 『箱』 に見たて、「箱の中の値」 と 「別の何らかの値」 を引数として与えると、二つをくっつけて返す takeOut メソッド があるとする。

takeOut (箱の中の値, 別の何らかの値)  =>  2 つをくっつけた値

ただし、この関数は次の制約を満さなければならないという条件付きで。

takeOut メソッドが返す値の型は、箱の中身の型ではなく、もう一方の「別の何らかの値」の型と一致する。

箱を int 型として、もう一方の値を int 型としたときのイメージは以下の通り。

同じく箱を int 型として、もう一つの値を String 型としたときのイメージ。

実装。

public class Main00 {

    public static void main(String[] args) {
        int box = 100;
        System.out.println(box);                 // 100
        System.out.println(takeOut(box, 200));   // 300
        System.out.println(takeOut(box, "円"));  // 100円
    }

    static int takeOut(int box, int val) {
        return box + val;
    }

    static String takeOut(int box, String str) {
        return box + str;
    }
}

 

特定の型に依存している箇所

上記の実装は特定の型に依存している。型に依存している部分は次の 3 つ。

• 箱の中身  … (A)
• 別の何らかの値 (takeOut メソッドの第2引数)  … (B)
• 上記 (A), (B) をくっつける演算子(関数)

これらが可変になるようにしたい。

 

クラスで型変数を宣言

まずは、箱をクラスとして実装し、中身を保持するための型変数を導入。型変数により箱はどんな型でも受け入れることができるようになり、入れた中身の型に応じたメソッドを作成可能。

「箱に入れた中身を取り出す」だけの takeOut メソッドから実装する。

クラスで型変数を宣言し、その型変数を「箱の中身」を保持するためのプライベート変数の型として宣言し、takeOut メソッドはその型変数を返すようにする。中身は箱を生成するときに渡すとするなら、

public class Box<A> {

    private A contents;

    Box(A contents) {
        this.contents = contents;
    }

    A takeOut() {
        return this.contents;
    }
}

 

メソッドで型変数を宣言

先ほどの takeOut メソッドを見ると、「箱の中身」と「別の何らかの値」をくっつける関数は 2 項演算子 `+’ だった。これを、与えられる値の型に応じて、適切な 2 項演算子を適用できるように変更したい。ただし、先ほどの制約は守ることにする。

takeOut メソッドが返す値の型は、箱の中身の型ではなく、もう一方の「別の何らかの値」の型と一致する。

これをイメージしたのが下図。「箱の中身」を型変数 A で、「もう一つの値」に対応したものを型変数 B とし、二項演算子を f で表現した。

ところで、Java は関数を直接メソッドに渡せないので、Strategy パターン でオブジェクトを渡す必要がある。このとき、2項演算子を適用するメソッドを apply とし、インターフェイスを IBinaryOp とする。 apply メソッドの第1引数は「箱の中身」、第2引数は「別のもう一つの値」が渡されるとするなら、

public interface IBinaryOp<A, B> {
    public B apply(A a, B b);
}

第2引数と返り値は、型変数 B で一致させることにより型チェックができる。

これで Box クラスの takeOut メソッドを次のように定義できる。

<B> B takeOut(IBinaryOp<A, B> f, B b) {
 return f.apply(this.contents, b);
}

型変数 B の具体的な型は、Box クラスの生成時に決まるのではなく、このメソッドを使うときに決まる。よって、メソッドにおいて型変数を宣言。もし、これをクラスの型変数としてしまうと、Box の生成時に型を指定しなければならず、また、そのときに指定した型に固定されてしまう。

ここまでのコード。

• Box.java : gist: 316379 – GitHub
• IBinaryOp.java : gist: 316378 - GitHub

 

型変数に具体的な型を指定して使う

Box クラスを作成できたので、Main クラスの main メソッドで使ってみる。はじめは箱に入れた値を取り出すだけ。

Box<Integer> box1 = new Box<Integer>(100);
System.out.println(box1.takeOut());            // 100

Box クラスをインスタンス化する文において、型宣言と new の双方において具体的な型 <Integer> を指定することを忘れずに。

 

匿名クラスでインターフェイスを実装したクラスを作成

次に、「箱から取り出した値」と「別のもう一つの値」を引数に取るメソッドを作成する。これは匿名クラスを利用した。

System.out.println(box1.takeOut(
        new IBinaryOp<Integer, Integer>() {
            public Integer apply(Integer a, Integer b) {
                return a + b;
            }
        },
        200));                                 // 300

先ほどと同じく、IBinaryOp インターフェイスを実装するクラスをインスタンス化するときに具体的な型の指定を忘れずに。これによりコンパイル時に型チェックがされる。

ところで、takeOut 関数の引数と返り値の型は以下の通りだった。

<B> B takeOut(IBinaryOp<A, B> f, B b) {

上例の場合、型変数 B に Integer 型が対応する。よって、takeOut の第2引数の値を文字列にすると、「型が違うよ」とコンパイラが間違いを指摘してくれる。具体的な型を指定してないと型チェックはされず、メソッドでキャストをしなければならない。

もし、 takeOut の第2引数の値を文字列にしたいなら、この定義では以下のように IBinaryOp インターフェイスを実装したクラスのオブジェクトを生成するときに具体的な型として String を指定。

System.out.println(box1.takeOut(
        new IBinaryOp<Integer, String>() {
            public String apply(Integer a, String b) {
                return a + b;
            }
        },
        "円"));                                // 100円

 

型変数のメリット

当然ながら、Box クラスで型変数を利用しているので、箱の中身の型が違っていても問題ない。main メソッドにおいて、中身を文字列に変更して使うなら、

Box<String> box2 = new Box<String>("百");
System.out.println(box2.takeOut());              // 百

System.out.println(box2.takeOut(
        new IBinaryOp<String, String>() {
            public String apply(String a, String b) {
                return a + b;
            }
        },
        "円"));                                  // 百円

 

NetBeans でメソッドの引数と返り値の型を補完

ちなみに、Netbeans を使っている場合、IBinaryOp インターフェイスを実装するときに、

new IBinaryOp<Integer, Integer>()

を入力した後、

メニューより「ソース > コードを修正...」を選択するか、コードの左に出るランプのようなアイコンをクリックすると、「すべての抽象メソッドを実装」がポップアップし、

選択すると型に応じた空のメソッドが生成される。

 

コード全体

ここまでのコード。

• Main.java : gist: 316380 – GitHub
• Box.java : gist: 316379 – GitHub
• IBinaryOp.java : gist: 316378 - GitHub

 

型のイレイジャに注意

ところで、型変数を利用したクラスを使うのは、特定の型に依存した実装ではなく、色々な型に対応でき、かつ、コンパイル時に型のチェックができるからだった。ただし、型変数があるにも関わらず、型を指定せずにコードを書くことも可能。これは、Java総称型メモ(Hishidama's Java Generics Memo) によると、

総称型として定義されているクラスから型パラメータを除去したクラスを「型のイレイジャ（型消去：type erasure）」と呼ぶ。…

つまり「List<T>」に対し「List」、「Map<K, V>」に対し「Map」が“イレイジャ”。

例えば、先ほどの例で Box クラスのオブジェクトを生成するとき、型宣言で具体的な型を指定しなかったとする。

Box box1 = new Box<Integer>(100);

Box クラスの takeOut メソッドは IBinaryOp の 型変数 B が決まると、第2引数と返り値の型が決まるのだった。

<B> B takeOut(IBinaryOp<A, B> f, B b) {

しかし、この場合 box1 の型変数が指定されてないためなのか(?)、コンパイラが型チェックをしてくれない。(イレイジャは関係している型変数のチェックを無効にしてしまうのかな？)

System.out.println(box1.takeOut(
        new IBinaryOp<Integer, Integer>() {
            public Integer apply(Integer a, Integer b) {
                return a + b;
            }
        },
        "hoge"));   

上記は実行した段階で「キャストできません」と例外が投げられる。

Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

具体的な型の指定を忘れるとコンパイル時にチェックされない。ジェネリクスの恩恵を受けるために忘れないように。

 

Haskell の場合

同じ意味合いのコードをHaskell で実装するなら、

data Box a = Box a deriving Show

takeOut         :: Box a -> a
takeOut (Box x) = x

takeOutWith             :: (a -> b -> b) -> b -> Box a -> b
takeOutWith f z (Box x) = x `f` z

main = do let box1 = Box 100
              box2 = Box "Hyaku"
          print $ takeOut box1                                -- 100
          print $ takeOutWith (+) 200 box1                    -- 300
          print $ takeOutWith (\a b -> show a ++ b) "En" box1 -- "100En"
          print $ takeOutWith ((++).show) "En" box1           -- "100En"

          print $ takeOut box2      -- "Hyaku"
          print $ takeOutWith (++) "En" box2     -- "HyakuEn"

う～ん、シンプル。

Java の方は本当にあれでいいのかなぁ。。 (+_+) 実はここで書いた例は、Java で Cons クラスをベースにリストを作り、その上で foldr, foldl に相当するメソッドを実装したらどうなるか試していたとき、型チェックがされなくておかしなぁ～と思い、よりシンプルな例にして試したもの。上記の不自然に見える制約は、foldr, foldl に与える 2項演算子における型と同じようにしたかったので、そのようにした。

 

関連記事

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

参考サイト

• Java総称型メモ(Hishidama's Java Generics Memo)

Firefox が起動できなくなる - プロファイルの cert8.db を削除

この頃、また Firefox がよく落ちる。長時間起動していると激重。久しぶりに再インストールし、まっさらにしたにも関わらず。。 (+_+)  アドオンを入れ過ぎがいけないのだろうか？

しかも、落ちるときに意味不明なことを言われた。

ハードディスクの空き容量が足りない

という旨だったと思うけれど、ハードディスクはガラガラに空いている。仕方がないので、反応が悪くなったら再起動という使い方で我慢。

しかし、終いには次のエラーが表示され、全く起動できなくなった。

セキュリティコンポーネントを初期化できませんでした。多くの場合この原因はこのプログラムのプロファイルフォルダの問題です。プロファイルフォルダへの読み書き権限があるか、ディスクの空き容量が少なくなっていないか確認してください。このままセッションを継続するとセキュリティ機能が異常動作する可能性があるため、このプログラムを一度終了して問題を解消することをお勧めします。

これは「セキュリティコンポーネントを初期化できませんでした」によると、ハードディスクの容量を増やすか、もしくは、

プロファイルフォルダ内の cert8.db ファイルが壊れている可能性があります。Firefox を閉じて、このファイルを削除してください。…

cert8.db ファイルは Firefox の再起動時に再生成されます。これは通常の動作です。

(ファイルが壊れている より)

とのこと。指示に従ったら起動できるようになったし、反応もよくなった。 ^^ この前もこれが原因で調子が悪くなってたのかな？ 長時間起動しておけば動きは悪くなるけれど、以前ほどではなくなった。

Excel で組織図を描く

手順

1. メニューより「挿入 > 図表…」
2. 「図表ギャラリー」が表示されたら、組織図のアイコンを選択。

 

見栄えを良くする

デフォルトで表示される組織図の図形はシンプルなので、見栄えを良くしたい。

1. 作成された組織図を選択
2. 「組織図のツールバー」 で、「組織図スタイルギャラリー」ボタンを押して、表示される適当なスタイルを選ぶ。

 

カスタマイズ

上記と同じく「組織図のツールバー」 で「レイアウト > 組織図のオートレイアウト」を選択。これで図形を自由を移動したり、形を変えたりできる。

 

コネクタ

組織図の線を引くには、画面下のオートシェイプのコネクタを使うのがよい。(オートシェイプが表示されてない場合は、メニューの何もないところで 「右クリック > 図形描画」 を選択。)

適当に図形を配置し、コネクタで接続する。

Firefox のアドオン QuickDrag で選択した文字をドラッグして検索 - EasyDragToGo の代替

追記 (2010.3.29) : Easy DragToGo が 3.6 に対応していたので QuickDrag から乗り換えた。やはり、Easy DragToGo は使いやすい。

---

 

単語の検索、リンクを開く操作はドラッグで

Firefox で閲覧中、

• わからない言葉を検索したい
• リンクを新しいタブで開きたい

場合、対象をドラッグして目的を達成する。この機能を実現してくれるのが Drag de Go だった。しかし、途中から新しい Firefox に対応しなくなり Easy DragToGo に乗り換え。しかし、これまた Firefox 3.6 には対応していない。

アドオン MR Tech Toolkit を使って非対応の Easy DragToGo を使えるようにしようかと思ったけれど、いつもアドオンの入れ過ぎで激重フォックスになり動作がぎこちなくなるので、極力対応していないアドオンは入れない方向で。しかし、ドラッグで検索したり、リンクを開くことは日常的な必須業務。これ使えないと不便。 (+_+)

 

QuickDrag

QuickDrag via kwout

同じ系統のアドオンがないかと探したら、QuickDrag というのがあった。ただし、ドラッグする方向によって、新しいタブを前面・背面で開くということはできない。

基本はバックグランドで新しくタブが開かれる。

前面で開きたい場合は、

Shift キーを押しながドラッグ

操作をする。

 

Tab Mix Plus との併用で一連の動作をスムーズに

Tab Mix Plus via kwout

ドラッグの方向によって操作を切り替えられないのは不便だけれど、アドオン Tab Mix Plus により 「マウスオーバーでタブを開く」 設定 をしておけば、

1. 選択した文字を上方向へドラッグすることによって検索
2. 開かれたタブの上へポインタを移動させる

というように一連の動作を流れるように行なえば我慢できる。

 

関連記事

• Firefox のタブをクリックせずに切替える - Tab Mix Plus
• ようやく Firefox 3.5 へ移行 : 対応していないアドオンを互換と見なす
• Easy DragToGo - Drag de Go の代替
• Drag de Go の初期設定は合理的だった

オブジェクトの相互参照 と 関数の相互再帰 (2) – Haskell の Data.Unique 型で一意な値を生成

「オブジェクトの相互参照 と 関数の相互再帰 (1)」 の続き。

 

オブジェクト識別子

前回 の Python と Haskell のコードには、言語の性格上異なる点がいくつかある。 (cf. gist: 288970, gist: 297114)  その一つは、Python では変数 tarou がオブジェクト識別子 (OID) により、一つの同一性を持ったオブジェクトとして管理されていること。

Python リファレンスマニュアルの 3.1 オブジェクト、値、および型 によると、

オブジェクトはアイデンティティ値 (identity) 、型 (type) 、そして値 (value) を持ちます。…

関数 id() は、オブジェクトのアイデンティティ値を表す整数 (現在の実装ではオブジェクトのメモリ上のアドレス) を返します。

以下を実行すると、オブジェクトのアイデンティティを表わす値が表示される。

print id(tarou)

これに対して、Haskell では OID のようなものは自動的に生成されない。 Haskell の関心はあくまでも型で指定し、データコンストラクタによって生成された値。等値性に関して言うならば、フィールドを元にした値が対象となる。

 

Python と Haskell の等値性の違い

例えば、前回 の Python の例 で考えると、コードを実行することによって tarou さんは「結婚 と 離婚 を経験をした状態」となる。コードの続きに、「同名で独身の tarou2 くん」を生成して、

tarou さんと tarou2 くんが同じ人物か確認をすると、(結婚、離婚は省略)

tarou  = Person("Tarou") # 結婚と離婚を経験した太郎さん
tarou2 = Person("Tarou") # 独身の太郎くん
print tarou == tarou     #=> True
print tarou == tarou2    #=> False

オブジェクト識別子により別ものと認識されるので、別人と判定される。(比較のためのメソッドが実装されていないとして。cf. 要素クラスに比較メソッド __cmp__(self, other) を実装)

 

Python と同じつもりで 前回のHaskell のコード を以下のように変更すると、(結婚、離婚は省略)

main = do let tarou  = born "Tarou"  -- 結婚と離婚を経験した太郎さん
	      tarou2 = born "Tarou"  -- 独身の太郎くん
	  print $ tarou == tarou  -- True
	  print $ tarou == tarou2 -- True

tarou さんと tarou2 くんが同じものと判断される。

Person 型は定義において

… deriving Eq

と 導出インスタンス 宣言がされていた。よって、Person 型のフィールドの値が同じなので、同一人物だと判定される。

 

Data.Unique 型 でオブジェクト識別子を真似る

もし Haskell において Person 型の値をそれぞれ区別したいなら、「値が一意となるフィールド」を持てばよい。例えば、Integer 型のフィールド oid を Person 型に含めるなら、

data Person = Person { oid :: Integer
                     , name :: String
                     , partner :: Partner
                     } deriving Eq

しかし、一意となるように自分で oid を管理するのはちょっと面倒な気がする。 (+_+) 何か便利なライブラリはないものかと探したら、名前からしてそれっぽい Data.Unique モジュールがあった。説明によると、

An abstract interface to a unique symbol generator.

これが使えそうなので、フィールド oid を Unique 型へ変更。

import Data.Unique

data Person = Person { oid :: Unique
                     , name :: String
                     , partner :: Partner
                     } deriving Eq

 

Data.Unique の newUnique 関数

Data.Unique によると、Unique 型の値を生成する関数は、

newUnique :: IO Unique

Creates a new object of type Unique. The value returned will not compare equal to any other value of type Unique returned by previous calls to newUnique. …

newUnique 関数の型を見ると Unique 型の値が IO に包んで返される。 この値を先ほどの oid の値として割り当てればよい。 IO で値が包まれている関数と言えば、お馴染、文字列を読み込むための

getContents :: IO String

がある。main 関数で値を変数に束縛するとき、

do cs <- getContents

のようにするので、これと同じように、

do oid <- newUnique

と使うのがイメージできる。

ところで、IO モナド は Maybe やリストと違い、IO で包んだ中身を取り出せない。The monad laws によると、

標準の Monad クラスではモナドから値を得る手段は定義されていません。…

Haskell の Monad クラスでは、このような関数を要求しないことで、一方向モナドの生成を可能にしています。一方向モナドは値を、return 関数(場合によっては fail 関数)を通じて、モナドに入れることが可能で、モナド中の計算は、バインド関数 >>= および >> を用いて実行することができます。しかし、モナドから値を逆にとり出すことはできません。 …

IO モナドは Haskell におけるよく知られた一方向モナドの例です。IO モナドから脱出することはできませんから、 IO モナド中で計算を行うにもかかわらず、結果の値として型構築子 IO を含まないような関数の定義を書くことは不可能です。…

つまり、newUnique 関数は値を IO で包むので、これを使う関数は値を返すときに IO で包む必要がある。 よって、Person 型の値を生成するとき、return 関数により Unique 型の値を IO で包む。

born n = do oid <- newUnique
            return $ Person oid n Nothing

 

(>>=) の型の確認

… と書いておきながら、何で return で包むのだっけ？と考えてしまった。 ^^;

上記 born 関数を (>>=) で書き直すなら、

born n = newUnique >>= \oid -> return (Person oid n Nothing)

newUnique の型は IO Unique 。これを (>>=) に適用した場合の型を確認すると、

*Main> :t (>>=) newUnique
(>>=) newUnique :: (Unique -> IO b) -> IO b

つまり、(>>=) に与える第1引数が IO Unique である場合、第2引数の型は、

Unique –> IO b

となるので、return により IO で包まなければならない。そうしないと (>>=) で計算をつなげることができない。

 

Person 型の等値性の検査

Unique 型の値で OID のようなものを表現できたので、この値を等値性の検査で利用する。導出インスタンス宣言は削除。

instance Eq Person where
    p1 == p2 = oid p1 == oid p2

 

IO モナドの中の計算

上記 born 関数の型は、

born :: String -> IO Person

main 関数の型は、

main :: IO t

同じ IO モナドを使っているので、main の中で born 関数で生成した Person 型の値を取り出し、他の関数に引き渡して、その結果をまた IO モナドの中に投入できる。

main = do tarou  <- born "Tarou"
          hanako <- born "Hanako"
          let m = marry tarou hanako
              d = divorce m
          print d
          print m

このため、前回の marry, divorce 関数は変更する必要がない。

 

全体のコードを示す。

import Data.Maybe
import Data.Unique

data Person = Person { oid     :: Unique
                     , name    :: String
                     , partner :: Partner
                     }
-- パートナー
type Partner = Maybe Person

instance Show Person where
    show (Person oid n Nothing) = n
    show (Person oid  n p)      = n ++ "{" ++ (name $ fromJust p) ++ "}"

instance Eq Person where
    p1 == p2 = oid p1 == oid p2

-- 誕生
born n = do oid <- newUnique
            return $ Person oid n Nothing

-- 結婚
marry p1 p2 = (p1 { partner = Just p2 }, p2 { partner = Just p1 })

-- 離婚
divorce (p1,p2) = (p1 { partner = Nothing }, p2 { partner = Nothing })

main = do tarou  <- born "Tarou"
          hanako <- born "Hanako"
          let m = marry tarou hanako
              d = divorce m
          print d  -- (Tarou,Hanako)
          print m  -- (Tarou{Hanako},Hanako{Tarou})

          tarou2 <- born "Tarou"
          print $ tarou == tarou  -- True
          print $ tarou == tarou2 -- False

これで以前よりもオブジェクトを使うときのような雰囲気になった。では、次に複数のオブジェクトの状態が変化していく様を模倣するにはどうすればいいのだろう？

オブジェクトの相互参照 と 関数の相互再帰 (1)

オブジェクトの相互参照

例えば、「人」には「名前」があり、将来一人の「パートナー」を得ることができるとする。生まれたてはパートナーがいない状態。「結婚」によりパートナーを得て、「離婚」によりパートナーを失う。ただし、結婚により相互に参照することが可能だとする。これを示したのが下図。

Python で表現するなら、まずはインスタンス変数と get メソッド、print 文に対応するための __str__() を定義。 (cf. print 文でオブジェクトの情報を表示)

class Person:
    def __init__(self, name):
        self.__name = name
        self.__partner = None

    def getName(self): return self.__name

    def __str__(self):
        return self.__name + "<" + (self.__partner.getName() if self.__partner else "None") + ">"

次に、結婚したとき相互に参照できるよう marry() メソッドを定義。既にパートナーがいるときは何もしないことにする。

class Person …

    def marry(self, partner):
        u""" 結婚 """
        if self.__partner: return
        self.__partner = partner
        partner.marry(self)

離婚したときはパートナーを参照できないようにする。ただし、パートナーがいないときは何もしない。

class Person …

    def divorce(self):
        u""" 離婚 """
        if not self.__partner: return
        partner = self.__partner
        self.__partner = None
        partner.divorce()

動作を確かめる。

tarou  = Person("Tarou")
hanako = Person("Hanako")

# 結婚
tarou.marry(hanako)
print tarou, hanako  #=> Tarou<Hanako> Hanako<Tarou>

# 離婚
hanako.divorce()
print tarou, hanako  #=> Tarou<None> Hanako<None>

コード全体はこちら。

 

相互再帰

Python ではオブジェクトが相互参照している状態と、その後、参照をなくすという変化を自然に記述することができる。ここで自然と感じるのは、自分が考える枠組みがそれに馴染んでいるということに過ぎない。では、これと同様のことを表現するのに Haskell ではどうすればいいのだろう？ ただし、まずはオブジェクトシステムにおけるオブジェクト識別子 (OID) のようなものついて考慮しない。

ところで、「相互参照」から連想するのは「相互再帰」という言葉。これは Haskell の let 式の説明で出てきた。

let 式によってつくられる束縛の集りは、相互再帰的 ( mutually recursive )で、パターン束縛は遅延パターンとして扱われます

(A Gentle Introduction to Haskell: Patterns の let 式 より)

Let 式 は let { d₁ ; ... ; d_n } in e という一般形式を持ち、入れ子でレキシカルスコープで相互再帰的な宣言リスト (このような let は他の言語ではよく letrec と呼ばれる) を持つ。

(Haskell 98 Report: 式 の 3.12 let 式 より)

Haskell に限らず一般的な意味として、相互再帰 - Wikipedia によると、

再帰呼び出しの一種であり、2つの関数が互いを使って定義されているものをいう。

 

相互再帰の例

この例として、Mutual recursion - Wikipedia には、数字が奇数であるか (odd?) 偶数か (even?) 判定する関数が互いを使って定義されている。

function even?(number : Integer)
    if number == 0 then
        return true
    else
        return odd?(abs(number)-1)

function odd?(number : Integer)
    if number == 0 then
        return false
    else
        return even?(abs(number)-1)

0 をベースにして、even? は odd? を、odd? は even? を使って定義しているのがわかる。

(cf. Fun with Functional Dependencies における定義も興味深い。理解できてないんだけど… ^^; )

 

また、A Gentle Introduction to Haskell: Patterns の “4.4 遅延パターン” の例 においても、サーバとクライアントのやりとりを表現した関数が定義されているが、ここでもリクエスト (reqs) とレスポンス (resps) が互いを使って定義されている。

reqs                     = client init resps
resps                    = server reqs

A Gentle Introduction to Haskell: Patterns via kwout

このように、オブジェクトが相互参照している状態は、関数の相互再帰によって表現できそう。

 

相互再帰的な関数 (値) の定義

上記を真似て、Person 型の値を相互再帰的に定義することに。まずは Person 型を定義。その後、let 式において互いを使って値を表現する。

ところで、値を生成するのはデータコンストラクタと呼ばれるが、上記の Person 型を調べればわかるように、

*Main> :t Person
Person :: String -> Partner -> Person

データコンストラクタは関数と似ている。違うのはパターンマッチで利用できるということ。よって、データコンストラクタで値を生成するときに、他の式を参照することは関数の相互再帰と同じと考えても良さげ。

data Person = Person { name    :: String
                     , partner :: Person
                     } 

instance Show Person where
    show (Person n p) = n ++ "{" ++ name p ++ "}"

main = do let tarou  = Person "Tarou"  hanako
              hanako = Person "Hanako" tarou
          print tarou  -- Tarou{Hanako}
          print hanako -- Hanako{Tarou}

tarou は hanako を使って定義し、hanako は tarou を使って定義した。

しかし、これは一見奇妙に思える。なぜなら先ほどの Python の例で、Person クラスのコンストラクタの定義を変更して、パートナーも引数として渡せるようにしたとする。

class Person:
    def __init__(self, name, partner):
        self.__name = name
        self.__partner = partner

このクラスを使って以下のように互いを参照するオブジェクトの生成を試みる。

tarou  = Person("Tarou", hanako)
hanako = Person("Hanako", tarou)

実行した結果は、

NameError: name 'hanako' is not defined

変数 tarou に Person 型のオブジェクトを代入しようとしても、オブジェクトを生成する段階でパートナーである hanako がいないのでエラー。上から下へとプログラムが順次実行され、状態の変化を記述するのが命令型言語の特徴なので、エラーが出て当り前。極めて当然な結果。

しかし、同じ目線で Haskell のコードを見ると、「hanako を定義する前に、tarou の定義で hanako を参照しているからコンパルエラーにならないの？」と思えてしまう。これは、そもそも let 式における定義は順序に意味はなく、何が何を参照して定義しているかを表現しているに過ぎないことによる。

延々と再帰呼出しが続かないよう 適切に Person 型を Show クラスのインスタンスにすれば、print 関数の呼出しも問題なし。もし、Person 型で deriving Show とした場合は出力が無限に続く。 tarou のパートナーは hanakoで、hanako のパートナーは tarou で、tarou のパートナーは… というように。

 

Maybe a 型を使ってパートナーが存在しないことを表現

相互再帰的な定義ができることがわかったので、次は Python と同じように、

1. 最初に値を生成したときはパートナーが存在しない
2. 結婚によりパートナーができる
3. 離婚によりパートナーを失う

という方向へ変更してみる。

パートナーが「いるかいないか」は Maybe a 型を利用。 (cf. Haskell の Maybe a 型と Either a b 型 (1) )

import Data.Maybe

data Person = Person { name :: String
                     , partner :: Partner
                     } deriving Eq
-- パートナー
type Partner = Maybe Person

instance Show Person where
    show (Person n Nothing) = n
    show (Person n p)       = n ++ "{" ++ (name $ fromJust p) ++ "}"

-- 誕生
born n = Person n Nothing

-- 結婚
marry p1 p2 =  (p1 { partner = Just p2 }, p2 { partner = Just p1 })

-- 離婚
divorce (p1,p2) = (p1 { partner = Nothing }, p2 { partner = Nothing })

main = do let tarou  = born "Tarou"
              hanako = born "Hanako"
              m = marry tarou hanako
              d = divorce m
          print m  -- (Tarou{Hanako},Hanako{Tarou})
          print d  -- (Tarou,Hanako)

しかし、これでは値の同値性において、Python がオブジェクトシステムを利用した場合の表現とは異なる。また、状態の変化を模倣しているとも言い難い。 (@_@;

 

関連記事

• オブジェクトの相互参照 と 関数の相互再帰 (2) – Haskell の Data.Unique 型で一意な値を生成

Haskell で関数合成 (2)

1 つの引数を取る関数を合成

一つの引数を取る関数を合成する場合、例えば、

*Main> (2*).(3+) $ 4
14

関数合成の定義 は、

(.) f g x = f (g x)

よって、関数合成の部分を定義で置き換えると、

(2*).(3+)
=> \x -> 2 * (3 + x)

これを 4 に適用すると、

(\x -> 2 * (3 + x)) 4
=> 2 * (3 + 4)
=> 14

 

2 つの引数を取る関数と、1 つの引数を取る関数を合成

上記の関数合成 (.) の第 1 引数を、2 つの引数を取る関数 (*) に変更してみる。関数の型を調べると、

*Main> :t (*).(3+)
(*).(3+) :: (Num a) => a -> a -> a

合成された関数が、2 つの引数を取る関数になったことがわかる。

この合成された関数を適当な値に適用してみる。

*Main> ((*).(3+)) 4 5
35

 

関数合成を定義で置き換える

(.) の定義より、上記の関数合成の部分は次のように置き換えられる。

(*).(3+)
=> \x -> (*) (3 + x)

これを 4 に適用すると、

(\x -> (*) (3 + x)) 4
=> (*) (3 + 4)
=> (*) 7

続いて 5 に適用すると、

(*) 7 5
=> 35

 

全体のイメージは、

1. 3 + 4 で 7
2. (*) を 7 に適用し、第２引数が与えられるのを待つ
3. (*) 7 を 5 に適用し => 35

 

2 つの引数を取る関数の引数の型が異なる場合

先ほど関数合成の第１引数に適用したのは (*) だった。(*) が適用する二つの引数の型は同じ。これに対して、リストのデータコンストラクタである

(:)

は、第 1 引数はリストの要素で、第 2 引数はリストを取る。念のため型を確認すると、

*Main> :t (:)
(:) :: a -> [a] -> [a]

これに関数合成を適用する。 (2*) と合成した場合の型を調べると、

*Main> :t (:).(2*)
(:).(2*) :: (Num a) => a -> [a] -> [a]

要素が Num クラスのインスタンスでなければならないという制約が付いた。

これを適当な値で試してみる。

*Main> ((:).(2*)) 3 []
[6]

合成した関数の第 1 引数は要素で、第 2 引数はリストを与える。

 

関数合成を定義で置き換える

関数合成の定義より、合成した関数を置き換える。

(:).(2*)
=> \x -> (:) (2 * x)

これを 3 に適用すると、

(\x -> (:) (2 * x)) 3
=> (:) (2 * 3)
=> (:) 6

そして、空リストに適用したら、

(:) 6 []
=> 6 : []
=> [6]

 

全体のイメージは、

1. 3 に 2 をかける
2. (：) を 6 に適用し、第２引数が与えられるのを待つ
3. (：) 6 を空リストに適用し => [6]

 

map 関数の定義

「なぜ関数プログラミングは重要か」の “3. 関数の貼り合せ” では、map 関数がリストに対する高階関数より導かれている。

先ほどのように (:) と関数を合成し、foldr に適用。例えば、リストの要素を 2 倍する関数であるなら、

*Main> foldr ((:).(2*)) [] [0..5]
[0,2,4,6,8,10]

Fold (higher-order function) のイメージを真似ると、

	対象のリスト [0..5] を木の左の葉の部分に並べる。
	末尾の右の葉に与えられた引数 [] を置く。
	合成した関数 (:).(2*) をノードに配置。
	最初の関数の適用。 これをルートに向けて繰替えす。

 

map 関数

上記より、関数合成の第２引数に関数を渡せるように変更すると、map 関数が導かれる。 (「なぜ関数プログラミングは重要か」 より)

map' f = foldr ((:).f) []

 

関連記事

• Haskell の関数合成

最小構成での動作チェックは大事 - 自作 PC の調子が悪いとき

サウンドカードが原因で Windows 7 の終了がめちゃ長くなる

Windows 7
Home Premium

去年の年末に親父の PC の中身を一新した。それまで CPU は Core 2 Duo を使っていた が、ビデオ編集をしていると他の処理がかなり重くなるため辟易していたようだ。Core i7 だとマザーボードを交換しなくてはいけなかったが、コア 4 つで 同時に 8 スレッド処理できるのは魅力的。Windows 7 も評判が良いようなので、思い切ってごっそり交換することにした。

 

サウンドカードを流用

ONKYO WAVIO PCI
デジタルオーディオボード
SE-90PCI

しかし、なるべくならパーツを再利用したい。 CPU、マザーボード、メモリを交換するのは仕方がないとしても、サウンドカードくらいは同じものを使いたかった。そこで、ONKYO SE-90PCI はそのまま流用し、組立て、Windows 7 をインストール。

 

アップデート後に電源が切れない

OS をインストールするところまでは何の問題もなかった。親父も慣れたもので、時間は結構かかったけれど、「こんなに簡単だったか？」と言っていたほど。しかし、… OS のアップデート後、問題が発生。 (+_+)  Windows 7 は起動や終了が Vista と比べて早い。ハードが変わったことを差し引いてもなかなかのもの。それが突如、3,4 分待たないと電源が切れなくなった。最初、待っても電源が切れないと判断し、強制的に電源をブチッ。

OS のアップデート後だったので、当然ながらアップデートの影響で調子が悪くなると思った。何度も OS の再インストールを繰り返し、どのアップデートが影響しているのかを確かめようとしたけれどはっきりせず。あるときはアップデート A の後 電源 が切れなくなり、あるときはアップデート B の後 不具合発生。 (+_+) それでも諦め切れず色々パターンを試した。終いには「もう電源が落ちるの 3, 4 分待てばいいんじゃない？」と思えてきた。

 

サウンドカードをはずしたら問題なくなった

精神的疲労がピークに達したとき、思い出したのは、

調子が悪かったら、最小構成で起動を試せ

ということ。「そんなこと当り前過ぎてアホらしく、今さらできるか!って気分。」そもそも OS のインストールまでは何の問題もなく、アップデート後におかしくなるのだから、そのときの何かを突き止めなきゃイカンでしょと。しかし、もう限界で藁をもつかむ気持ちでサウンドカードをはずし、どうせ無駄だろうと思いつつ起動と終了を試した。そうしたら、3, 4 分もかかって電源が切れていたのが嘘のように一瞬で終了できるようになった。 パタッ(o_ _)ｏ~†

やはり基本は大事。面倒くさがらず、押さえておくべきところは最初に試しませう。

Haskell でリストから特定の要素を抽出する - 再帰的な定義、末尾再帰、filter, elem, partition, intersect

1. リストから特定の要素を抽出したい

例えば、ある村に、村人が 5 人住んでいたとする。

太郎、花子、次郎、三郎、明美

この村には、指名手配されている犯人がいる。指名手配されている犯人のリストは、以下の通り。

花子、三郎、四郎

これより、村にいる犯人を見つけたい。

 

2. 型の定義と、関数の型

最初に、「人」を表す Person 型を定義する。ここでは名前が一致することで、同じ人であるとする。

data Person = P { name :: String } deriving (Show, Eq)

村人のリストを定義。

ps = [P "Tarou", P "Hanako", P "Jiro", P "Saburou", P "Akemi"]

「指名手配されている犯人のリスト」と、「村人のリスト」が与えられたら、一致した人を、リストで返す関数を extract とする。関数の型は次の通り。

extract :: [Person] -> [Person] -> [Person]

 

3. filter 関数を使い、再帰的に定義

Haskell でリストから抽出するには、filter 関数を利用する。

具体的な処理のイメージは、

1. 「指名手配されている犯人のリスト」から、一人ずつ取り出して、
2. 「村人のリスト」と照合し、
3. 一致するものがあれば返す。

リストの要素を順に見ていく処理は、再帰的な定義をする。

1. 最初にパターンマッチにより、指名手配されている犯人のリストを、「先頭の要素」と「それよりも後ろの要素」に分解。
2. 犯人リストの「先頭の要素」と、村人の「先頭の要素」が一致するか調べる。

extract (x:xs) ps = filter (== x) ps …

「先頭よりも後ろの要素」に対して、同じように一致しているか調べる。その結果を、上記の結果と結合して返す。

extract (x:xs) ps = filter (== x) ps ++ extract xs ps

ところで、指名手配されている犯人のリストを、パターンマッチで分解している。そのため、リストを分解しつくし、空リストになった場合を考える必要がある。よって、「指名手配のリストが空なら、一致する人はいない」という定義を加える。

extract []     _  = []

全体を示すと、

extract []     _  = []
extract (x:xs) ps = filter (== x) ps ++ extract xs ps

このような再帰的な定義の仕方を考えると、頭が混乱する。最近、少し慣れてきたかも。

 

4. 末尾再帰呼出しで定義

再帰的に定義できたので、「末尾再帰呼出し」の形に定義を変えてみる。

末尾再帰呼出しの形にするには、次の二つのことが必要。

1. 結果を累積的に保持する役割を持つ引数を追加。
2. 処理の最後で自分自身を呼出す。

最初に、結果を累積的に保持するための引数を、第 2 引数に置く。

extract' (x:xs) acc ps = 

次に、いきなり自分自身を呼出す。

extract' (x:xs) acc ps = extract' …

最初は acc が空だとして、「指名手配されている犯人のリストの先頭要素で、抽出できるか」試す。

extract' (x:xs) acc ps = extract' … (filter (== x) ps) … 

filter 関数で抽出した結果を acc に加える。

extract' (x:xs) acc ps = extract' … (acc ++ (filter (== x) ps)) … 

指名手配されている犯人のリストの残りも、同じように処理すればいいので、引数 acc に追加した結果を、引数に与えて再帰的な呼出しをする。

extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps 

ただし、先ほどと同じく、パターンマッチで指名手配されている犯人のリストを分解している。そのため、これが空になった場合についても考えなければいけない。

引数 acc に結果が詰め込まれるはずなので、それをそのまま返す。

extract' []     acc _  = acc

全体を示す。

extract' []     acc _  = acc
extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps 

 

関数をラップ

上記で定義した関数を使うには、引数 acc に空リストを与える。

extract' [P "Hanako", P "Saburou", P "Sirou"] [] ps

しかし、毎回、空リストを渡すのは面倒なので、extract’ 関数をラップする関数を定義する。

extract xs ps = extract' xs [] ps
    where
      extract' []     acc _  = acc
      extract' (x:xs) acc ps = extract' xs (acc ++ (filter (== x) ps)) ps 

これで関数のインターフェイスが、最初に定義した関数と同じになった。

末尾再帰呼出すメリットを簡単に言えば、再帰的な関数の呼出しが深くなり過ぎ、スタックオーバーフローしてしまったら、末尾再帰呼出しの形にして正格評価で対処できること。

 

5. 各々の要素が「特定のリストに含まれるか？」検査する方法

「リストの中にある要素が存在するかどうか？」というと、Python の シーケンス型 における `in’ を連想する。

print "Hanako" in ["Tarou", "Hanako", "Jiro"]      #=> True
print "Hanako" not in ["Tarou", "Hanako", "Jiro"]  #=> False

Haskell では elem, notElem 関数に相当する。

*Main> "Hanako" `elem` ["Tarou", "Hanako", "Jiro"]
True
*Main> "Hanako" `notElem` ["Tarou", "Hanako", "Jiro"]
False

問題に戻り、先ほどまでの定義を、

各々の村人を 「指名手配されている犯人のリスト」 から抽出できるか？

に変更。

extract xs ps = filter (\x -> x `elem` xs) ps

部分適用、セクションを利用すると、

extract xs = filter (`elem` xs)

 

抽出ではなく、リストを分割したい場合

抽出ではなく、村人を指名手配されている犯人と、そうでない人に分割したい場合は、Data.List の partition を使う。

import Data.List

extract xs = partition (`elem` xs)

 

6. 共通部分を抽出する方法

村人の集合と指名手配されている人の集合を図に描くと、求めたいのは二つの 集合の共通部分 ということになる。

Data.List には 集合的な操作 として intersect が定義されている。

import Data.List

extract = intersect

つまり、わざわざ自分で関数を定義する必要はなかった。

なぜこれをすぐに連想しなかったのだろう …  パタッ(o_ _)ｏ~†

 

7. Data.Set を利用する

集合の操作をしたいなら、Data.Set モジュールを利用する。

リストと集合の変換は、

fromList  <=>  toList

共通部分 と 差 は、

• intersection
• difference

それぞれ型を見ると、集合の要素が Ord のインスタンスできないといけない。そのため、Person 型に Ord を追加。

import Data.Set

data Person = P { name :: String } deriving (Show, Eq, Ord)

extract xs ps = toList $ xs' `intersection` ps'
    where
      xs' = fromList xs
      ps' = fromList ps

先ほどと同じように、リストを分割したいなら、

extract xs ps = ( toList $ xs' `intersection` ps', 
                  toList $ ps' `difference`   xs' )
    where
      xs' = fromList xs
      ps' = fromList ps

「要素に重複があってはならない」という制約がない限り、partition 使った方が楽かな。