黒曜の吹き溜まり

不動点と不動点コンビネータ

2011-12-06 プログラミング

ある関数 $f(x)$ について、 $x_0 = f (x_0)$ となる $x_0$ が存在するとき、 $x_0$ を $f$ の不動点といいます。
また、 $x_0$ に十分近い $x$ に対し、列 $x, f(x), f(f(x)), \ldots$ が $x_0$ に収束するとき、 $x_0$ は $f$ の吸引的不動点である、といいます。
(参考:Wikipedia)

吸引的不動点は、値が変化しなくなるまで関数適用を繰り返すだけなので、プログラムで簡単に書くことができます。
以下のfixは初期値xからfの吸引的不動点を求める関数です。
汎用性のため、一致検査関数はequalとして引数で取ります。

let rec fix equal f x =
  let x' = f x in
    if equal x x' then x
    else fix equal f x'

第一級モジュール

2011-12-05 プログラミング

OCamlには、3.12から「第一級モジュール」の機能が加わっているらしいです。
第一級モジュールとは、第一級オブジェクトとしてモジュールが扱える、つまり変数や関数と同じように関数への受け渡しや代入操作が出来るものです。
公式マニュアル7.14 第一級のモジュールに詳しい説明があります。

let多相と値多相

2011-12-04 プログラミング

先日、関数合成を使うと、無駄なletやfunを減らせていいよね、という話をしました。

let (>>) f g x = g (f x)

で、関数合成を多用していると、2引数関数に対しても合成をしたくなる局面が出てきます。
たとえば、compareを元にしてequalを作ろうと思った場合、素直なコードは以下になります。

let equal x y =
  compare x y =

これは、「xとyをcompareして、その値が0と等しいかを検査する」という関数になります。
これをcompareと(=) 0の関数合成で書こうとするとさっきの関数合成関数ではできません。(後述するカリー化とアンカリー化を使えば出来ますが)

OCamlでSetをmapする関数

2011-11-30 プログラミング

今日も今日とてOCamlでプログラムをガリガリ書いていたのですが、どうしても気になってSetをmapする関数を作って見ました。
とはいえ、さすがにSetに組み込むのは無理なので、外部で似たようなことをやるための汎用関数ですが。

let mapper folder adder empty f s =
  folder (f >> adder) s empty

こんな感じです。

F#のパイプライン演算子・関数合成をOCamlで実装

2011-11-29 プログラミング

最近F#が気になっているのだけれど、F#で魅力を感じる機能の一つに、パイプライン演算子というのがあります。
これはUnixのパイプライン処理に類似するもので、値をある処理に与えて、その結果をまた別の処理に与えて……というのをかなり見やすく記述できる、というものです。
例えば、リストの各要素を2乗してから和を取る、という関数sqr_sumは、素直に書くと次の様になります。

let sqr_sum l = List.fold_left (+)  (List.map (fun x -> x * x) l)

まぁ読めなくはないですが、どこから処理されるのか一瞬迷いますよね。
もっと複雑に、リストのうち奇数であるような要素のみを取り出し、これを2乗して和を取る、なんてのを書いてみましょう。

OCamlのSet.Sにmap関数はない

2011-11-27 プログラミング

最近研究でOCamlのSetやMapを多用するんですが、Set.Sの中にmap関数はないんですね。
タプルの特定要素を取り出したり情報を付与したりするときにSet->Set変換する必要があるんですが、いちいちfoldするのが面倒……
Listなんかにはmap関数があるのであってもよさそうなものですが、よく考えるとこの関数、型として表現が難しい(というかできない)のですね。

Setはファンクターなので、例えばint型のSetなら(作れないですが)

int Set

ではなく

module IntSet = Set.Make  (struct    type t = int    let compare = compare   end)

といった感じになります。
要素の型や比較関数をまとめてストラクチャーとしてファンクターに与えることで、内部の型が固定されたストラクチャーが返されるわけです。

んで、ファンクターの内部では集合自体の型はt、要素の型はeltで表されてるわけです。例えば

empty : tadd : elt -> t -> t

といった具合です。(OCamlマニュアルより)
ところがここでmap関数を考えると、

map : (elt -> 'a) -> t -> 'a set(?)

といった具合で、出力が’aを要素とするSetになるわけですが、当然ファンクターはそんな型を知らないので定義できません。
with type構文とか使えないかなーと一瞬考えましたが、あれはSet.Sに型を与えてシグネチャを作るだけでしたね。全然関係ないです。

Newer posts