きくらげ観察日記

好きなことを、適当に。

OCaml

PFDSを読む: Binomial Heap

Binomial Heapとは、Binomial Treeというデータ構造を使って作られるヒープです。ここで、Binomial Treeとは、以下のようなデータ構造です。 rankが0であるBinomial Treeは、ただ1つのノードからなるシングルトン r > 0 について、rankがrであるBinomial Tre…

PFDSを読む: Weight-biased Leftist Heap

inkar-us-i.hatenablog.comこちらの記事でLeftist Heapの紹介をしましたが、今回はその亜種であるWeight-biased Leftist Heapを紹介します。 このデータ構造はほとんどLeftist Heapと同様ですが、rankのかわりに要素数が左に偏るようになります。すなわち、 …

PFDSを読む: Leftist Heapの実装

inkar-us-i.hatenablog.comこの記事ではLeftist Heapについて語るだけで終わっていたので、今回はバリバリ実装していきます。 その前に、Leftist Heapの定義のついてのおさらいをしておきましょう。 Leftist Heapとは、以下の性質をもつ二分木です。 根の部…

Leftist Heapの性質

Leftist Heapは、純粋関数型的にヒープを操作するために用いられるデータ構造です。Leftist Heapは要素が左に偏っている二分木として実装されます。 データ構造自体は以下のように単純に構成できます。 type 'a heap = | E | T of 'a * 'a heap * 'a heap た…

PFDSを読む: 二分木の改良

長年積んでたPFDSを読み始めることにしました。 積んでる間に邦訳が出たらしいのですが、とりあえず気にしない方針で。まずは単純な二分木 module type SET = sig type elt type set val empty : unit -> set val insert : elt -> set -> set val member : e…

Smith-Waterman法で配列の局所アラインメントを求める

今度は局所アラインメントを求めます。 前回の大域アラインメントと違って、今度は最も一致度の高い部分文字列を求めるアルゴリズムになります。 type alignment = char option list let maximums_by (key : 'a -> 'b) (lst : 'a list) : 'a list = let rec …

OCamlの値の比較について

OCamlには2種類の値の比較方法があります。 ==, != これらの演算子は、右辺と左辺が全く同一のオブジェクトであるかを判定します。==という名前は大抵の言語で使われているので、つい癖で値の比較に使用してしまいそうですが、この演算子はむしろSchemeのeq?…

OCamlのmatch文とbegin..end

OCamlにはオフサイドルールは無いので、例えばmatch文をネストした時に、 let rec zip xs ys = match xs with | x :: xs' -> match ys with | y :: ys' -> (x, y) :: zip xs ys | [] -> [] | [] -> [] これは次のように解釈されます。 let rec zip xs ys = m…

OCamlのFunctorという概念を知らずに自分で再発明していた話

最近わけあってOCamlの勉強をしているのですが、OCamlは多相的な関数を定義する方法として、Functorというものを持っています。 (* 要素の型と、その比較方法を定義するモジュール *) module type Cmp = sig type elt val le : elt -> elt -> bool (* <= *) …

OCaml初心者が戸惑いそうな謎記号一覧

^(キャレット) ^は文字列連結の演算子です。 # "hoge" ^ "fuga";; - : string = "hogefuga" +., -., *., /. 浮動小数点数同士の演算には、元の演算の記号の後にドットが付きます。Schemeと同じですね。 # 3.0 +. 4.0;; - : float = 7. <> <>はノットイコール…