Clojureコレクションで探るimmutableでpersistentな世界

コレクションで探る immutableでpersistentな世界 Clojure

lagénorhynque 🐬 カマイルカ (defprofile lagénorhynque :id @lagenorhynque :readings ["/laʒenɔʁɛ̃ k/" "ラジェノランク"] :aliases ["カマイルカ" " "] 🐬 :languages [Java Japanese Clojure Haskell English français] :interests [programming language-learning law politics mathematics]) ; native languages ; functional languages ; European languages

• https://twitter.com/lagenorhynque

改めて関数型プログラミング(言語)とは? と のコレクションを調べてみよう コレクションの全体像 4. 局所的にミュータビリティがほしいとき 5. 独自コレクションを実装しよう 1. 2. Java Clojure 3. Clojure

改めて関数型プログラミング(言語)とは?

定義例 関数型プログラミング(functional programming; FP) 副作用を可能な限り避ける(局所化する)プログラ ミングスタイル 関数型プログラミング言語(functional programming language; FPL) 関数型プログラミングが実践しやすいように設計 されている言語

再代入不可な変数が定義可能であればFPL? const, final, val, etc. それを活用していればFPしていることになる? ラムダ式があり高階関数が豊富に提供されていれば FPL? filter, map, reduce, etc. それを活用していればFPしていることになる?

確かにFP/FPLに近づいている感じがする。 でも、それで満足?

私🐬が期待する実用的なFPLのイメージ: 不変で永続的なデータ構造(immutable persistent data structures) が豊富に提供さ れ、容易に定義可能 そうでないデータ構造は非中心的な位置付け i.e. immutableでpersistentがデフォルト FP も できる言語をFPLと呼びたくはない

永続的(persistent) 関数型データ構造を更新する際には、更新前と更新 後のバージョンが両方ともその後の処理で利用でき ることを期待する 複数のバージョンをサポートするデータ構造は永続 的(persistent) ←→ 同時に1つのバージョンしか許さないデータ 構造は刹那的(ephemeral) FPLはすべてのデータ構造が自然と永続的になると いう興味深い性質を持つ 命令型データ構造は概して刹那的 『純粋関数型データ構造』(p. 13)

• https://asciidwango.jp/post/160831986220/純粋関数型データ構造

と のコレクションを調べてみよう Java Clojure

Java

オブジェクト指向・非関数型言語
静的型付き言語
JVM言語
関数型プログラミング関連機能が充実してきた
// メソッドの定義
jshell> void hello(Object x) {
...>
System.out.println("Hello, %s!".formatted(x));
...> }
| created method hello(Object)
// メソッドの呼び出し
jshell> hello("Java")
Hello, Java!

Clojure 非オブジェクト指向・関数型言語 動的型付き言語 JVM言語 オブジェクト指向を嫌い関数型を志向したLisp ;; 関数の定義 user=> (defn hello [x] (println (str "Hello, " x "!"))) #'user/hello ;; 関数の呼び出し(適用) user=> (hello "Clojure") Hello, Clojure! nil

参考: Scala オブジェクト指向・関数型言語 静的型付き言語 JVM言語 オブジェクト指向に関数型が溶け込んだ言語 // メソッドの定義 scala> def hello(x: Any): Unit = | println(s"Hello, $x!") def hello(x: Any): Unit // メソッドの呼び出し scala> hello("Scala") Hello, Scala!

[Java] java.util.ArrayList user=> (def xs (java.util.ArrayList.)) #'user/xs user=> xs [] user=> (def ys ; ysに束縛 #_=> (doto xs #_=> (.add 1) ; 破壊的に要素追加 #_=> (.add 2) #_=> (.add 3))) #'user/ys user=> ys [1 2 3] user=> (identical? xs ys) ; オブジェクトの同一性を確認 true の実装のひとつ mutableでephemeralな可変長配列 java.util.List

• https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/ArrayList.html

[Java] unmodifiable (view) list user=> (def xs #_=> (doto (java.util.ArrayList.) #_=> (.add 1) #_=> (.add 2) #_=> (.add 3))) #'user/xs user=> xs [1 2 3] user=> (def ys (java.util.Collections/unmodifiableList xs)) ; 変 #'user/ys user=> (.add ys 4) ; 破壊的更新操作はできない Execution error (UnsupportedOperationException) at java.util.Col modifiableCollection/add (Collections.java:1067). null

user=> true user=> [1 2 3 user=> [1 2 3 (.add xs 4) xs 4] ys 4] ; もとのリストは破壊的更新操作ができる ; 変更不可能なビューにも波及する コレクション(ここではList)に対する変更不可能な ビュー もとのコレクションやその要素がmutableなら immutableではない もとのコレクションが(実質的に) immutableであ る、もしくはこのビューを介してのみ操作できる 状態であれば実質的にimmutable cf. java.util.Collection

• https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Collection.html

[Clojure] ベクター(vector) user=> (def xs []) ; 初期化 #'user/xs user=> xs [] user=> (def ys (conj xs 1 2 3)) ; 要素追加してysに束縛(破壊的更新操作 #'user/ys user=> ys [1 2 3] user=> (identical? xs ys) ; オブジェクトの同一性を確認 false の実装 immutableでpersistentな可変長配列 HAMT (hash array mapped trie)の一種 clojure.lang.IPersistentVector

• https://clojure.org/reference/data_structures#Vectors
• https://en.wikipedia.org/wiki/Hash_array_mapped_trie

コレクションの全体像 Clojure

コレクションに関するインターフェース Clojure ref. Clojure Applied (p. 38)

• https://pragprog.com/titles/vmclojeco/clojure-applied/

参考: Scala不変コレクションのトレイト Traversable Iterable IndexedSeq Seq Set LinearSeq SortedSet Map SortedMap BitSet ref. 可変コレクションおよび不変コレクション | Collections | Scala Documentation

• https://docs.scala-lang.org/ja/overviews/collections/overview.html

コレクションの性能特性 Clojure ref. Clojure Performance Guarantees

• https://www.innoq.com/blog/st/2010/04/clojure-performance-guarantees/

不変コレクション(列型)の性能特性 Scala ref. 性能特性 | Collections | Scala Documentation

• https://docs.scala-lang.org/ja/overviews/collections/performance-characteristics.html

のデータ構造の応用について気になったら 書籍 Clojure Applied を読もう Clojure

• https://pragprog.com/titles/vmclojeco/clojure-applied/

Further Reading

Clojure Clojure Clojure - Data Structures Clojure - Sequences Clojure - Transient Data Structures Clojure - Datatypes: deftype, defrecord and reify Clojure Applied: From Practice to Practitioner Clojure Performance Guarantees [Stefan Tilkov’s Blog] clojure/core.rrb-vector: RRB-Trees in Clojure

• https://clojure.org/
• https://clojure.org/reference/data_structures
• https://clojure.org/reference/sequences
• https://clojure.org/reference/transients
• https://clojure.org/reference/datatypes
• https://pragprog.com/titles/vmclojeco/clojure-applied/
• https://www.innoq.com/blog/st/2010/04/clojure-performance-guarantees/
• https://github.com/clojure/core.rrb-vector

Scala Scala 可変コレクションおよび不変コレクション | Collections | Scala Documentation 性能特性 | Collections | Scala Documentation Java Java SE 17 & JDK 17 The Collections Framework (Java SE 17 & JDK 17)

• https://www.scala-lang.org/
• https://docs.scala-lang.org/ja/overviews/collections/overview.html
• https://docs.scala-lang.org/ja/overviews/collections/performance-characteristics.html
• https://docs.oracle.com/en/java/javase/17/docs/api/index.html
• https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/doc-files/coll-index.html

Kotlin Kotlin/kotlinx.collections.immutable: Immutable persistent collections for Kotlin JavaScript immutable-js/immutable-js: Immutable persistent data collections for Javascript which increase efficiency and simplicity. Python tobgu/pyrsistent: Persistent/Immutable/Functional data structures for Python

• https://github.com/Kotlin/kotlinx.collections.immutable
• https://github.com/immutable-js/immutable-js
• https://github.com/tobgu/pyrsistent