OCaml

3 Some Familiar Data Structures in a Functional Setting ぱらぱらめくる『Purely Functional Data Structures』

Leftist heaps、Binomial queues、red-black trees 手続き型言語が持つデータ構造は、関数型言語に移しやすいものとそうでないものがある 移しやすい例 leftist heaps : 手続き・関数のどちらでも実装しやすい binomial queues: 関数型でやりやすい red-blac…

2 Persistence ぱらぱらめくる『Purely Functional Data Structures』

リスト・二分岐木 Persistence データ構造オブジェクト(の一部)をコピーして作るようなときに、元のオブジェクトは維持して、値呼び出しための番地操作によって対応すれば、元のオブジェクトも含めて、いつまでも使いまわせる。逆に言えば、書き換えはしない…

1 Introduction ぱらぱらめくる『Purely Functional Data Structures』

データ構造を説明する前に用語の混乱を避けるための注意をしておく An abstract data type : 型と型のために作られた関数群のことで、abstractionと呼ぶことにする An concrete realization of an abstract data type : Implementation(実装)のことを指す。…

Preface、SML概観 ぱらぱらめくる『Purely Functional Data Structures』

Haskellは関数型言語。Standard MLもそう。SMLはOCalm系らしい。似ている点もあれば違う点もある(こちら)。 共通点 First-class support for algebraic datatypes (disjoint unions) Pattern matching on primitive and custom values Arbitrarily higher or…

ぱらぱらめくる『Purely Functional Data Structures』

関数型プログラミングによるデータ構造の扱いを知るためにSML使用者が書いた本を眺めてみる。ハスケルコードも付録についている Purely Functional Data Structures作者: Chris Okasaki出版社/メーカー: Cambridge University Press発売日: 1999/07/01メディ…