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

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

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

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

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

一昨日(20131128)はHaskell勉強会の２回目 Haskell(とそれを含む関数型言語)はType Theory(Wiki記事)と関係があるという Type Theoryは煎じ詰めると"In type theory, every "term" has a "type" and operations are restricted to terms of a certain type."…

昨日はHaskell勉強会の２回目。３週間ぶり？にHaskell。ちょっと時間が余ったので、こちらものぞいてみる 『Haskellは関数型言語なので、プログラムを書くときは、コンピュータに実行すべき命令列を伝える代わりに、必要となるであろう全ての関数の定義を与…