30.4K Views
October 27, 24
スライド概要
主要なJVM言語Scala, Kotlin, Clojureの標準ライブラリにおける高階関数mapの実装を探ることを通して、各言語の特徴的なコレクション設計について理解を深めよう。
「楽しく楽にcoolにsmartに」を理想とするprogrammer/philosopher/liberalist/realist。 好きな言語はClojure, Haskell, Python, English, français, русский。 読書、プログラミング、語学、法学、数学が大好き! イルカと海も大好き🐬
map関数の内部実装から探る JVM言語のコレクション Scala, Kotlin, Clojureコレクションの基本的な設計を 理解しよう #jjug_ccc #jjug_ccc_j 1
🐬 lagénorhynque カマイルカ 株式会社スマートラウンドのシニアエンジニア スタートアップの起業家と投資家のための業務効 率化/連携プラットフォームを開発している 主要技術スタック: Kotlin & TypeScript Server-Side Kotlin Meetupの運営企業 Clojure, Haskellなどの関数型言語と関数型プログ ラミングの実践が好き Java, Scala, Clojure, KotlinとJVM言語での開発実務 に長く取り組んできた 2
今回のテーマ Scala, Kotlin, Clojureという主要なJVM言語での高階 関数 map の内部実装をきっかけに、各言語のコレク ションの実装と設計について簡単に解説したい。 🐬< Three Languages in Three Quarters (?) 3
話すこと Scala/Kotlin/Clojure標準コレクションの 内部実装(の一部) 関連するインターフェース/抽象 コレクションの全体像 Javaコレクションとの主な違い 話さないこと Scala/Kotlin/Clojure言語とライブラリの詳細解説 各言語でのコレクションの実践的な利用例 4
1. map関数/メソッドの基本(Javaを例に☕️) 2. 3つのJVM言語での実装とコレクション設計 Scala編 Kotlin編 Clojure編 3. 各言語のコレクションの特徴(Javaとの差異に注目👀) 5
1. map関数/メソッドの基本 ☕️ Javaを例に 6
主なJVM言語の歴史 year 1995年 2004年 2007年 2011年 2014年 event Javaが登場 Scalaが登場 Clojureが登場 Kotlinが登場 Java 8がリリース (ラムダ式とStream APIなど) 以降、関数型言語でよく見られる機能がJava言語にも 徐々に充実して現在に至る 7
代表的な高階関数としての map 関数型プログラミング(FP)に入門するとおそらく 早々に触れるのはラムダ式(無名関数)と高階関数 その高階関数の代表例が map 関数 ほかに filter, reduce/fold は定番 現代のたいていのプログラミング言語にはこの関数 (OOPのスタイルで実装されているならメソッド)が 標準提供されているはず (低レベルにはループ/再帰で実装する)繰り返し処理 の特定のパターンを抽象化した関数のひとつ FPでの設計(デザイン)パターンの一例といえる 8
Javaの map メソッドの利用例
// IntStream => int[]
jshell> IntStream.rangeClosed(1, 10).
...> map(n -> (int) Math.pow(2, n)). // int => int
...> toArray()
$1 ==> int[10] { 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 }
// Set<String> => Stream<String> => Stream<Integer>
//
=> Map<Integer, Integer>
jshell> Set.of("abricot", "banane", "citron").
...> stream().
...> map(String::length). // String => Integer
...> collect(Collectors.groupingBy(
...>
Function.identity(), // ここでキー変換したほうが効率的
...>
Collectors.counting()
...> ))
$2 ==> {6=2, 7=1}
9
map 関数を一般化し発展させた抽象 ※ここでは関数の型(シグネチャ)をHaskell風に示す リストの要素を変換する関数 map :: (a -> b) -> [a] -> [b] リストを平坦化する関数 flatten :: [[a]] -> [a] 両者を合成した関数 flatMap :: (a -> [b]) -> [a] -> [b] map して flatten する(= flatten . map) 10
Haskellではこれらをさらに抽象化している(リスト などのコレクション以外にも再利用できる) fmap :: Functor f => (a -> b) -> f a -> f b 型クラス Functor (≒ map演算が適用できるデ ータ構造)のメソッド (>>=) :: Monad m => m a -> (a -> m b) -> m b 型クラス Monad (≒ flatMap演算が適用できる データ構造)のメソッド 11
2. 3つのJVM言語での実装と コレクション設計 12
Scala編 13
Scalaとは 静的型付きオブジェクト指向/関数型言語 オブジェクト指向と関数型の統合/調和を重視 Smalltalk〜Ruby、ML〜Haskellの双方の系譜の 影響が見られる < OOPをベースにFPが溶け込んだ言語 Martin Oderskyにより2004年に登場 Scala 3でシンタックスに大きな変化があった 名前の由来: scalable language (スケールする言語) イタリア語で scala は「階段」 「はしご」の意味 もある(英語の scale と同根) 🐬 14
Scalaの map メソッドの利用例 // Range => IndexedSeq[Int] scala> (1 to 10). | map(scala.math.pow(2, _).toInt) // Int => Int val res0: IndexedSeq[Int] = Vector(2, 4, 8, 16, 32, 64, 128, 256, 512, 1024) // Set[String] => Seq[String] => Seq[Int] => Map[Int, Int] scala> Set("abricot", "banane", "citron"). | toSeq. | map(_.length). // String => Int | groupMapReduce(identity)(_ => 1)(_ + _) val res1: Map[Int, Int] = Map(6 -> 2, 7 -> 1) 15
Scalaの map メソッドの実装(Scala 3.5.1) 例えば Vector の map を仮に自分で実装するなら class Vector[+A]: ... def map[B](f: A => B): Vector[B] = @tailrec def loop(xs: Vector[A], acc: Vector[B]): Vector[B] = xs match case y +: ys => loop(ys, acc :+ f(y)) case _ => acc loop(this, Vector()) パターンマッチで先頭と残りに分解し、先頭の要素に 関数を適用して末尾追加 16
実際のVectorのmapメソッド実装 scala> Vector(1, 2, 3).getClass.getCanonicalName val res0: String = scala.collection.immutable.Vector1 Vector() で3要素の場合の具象型は Vector1 Vector1.map: scala/collection/immutable/Vector.scala#L410 override def map[B](f: A => B): Vector[B] = new Vector1(mapElems1(prefix1, f)) prefix1 は Vector1 の内部表現の1次元配列 17
VectorStatics.mapElems1:
scala/collection/immutable/Vector.scala#L2135L2145
final def mapElems1[A, B](a: Arr1, f: A => B): Arr1 = {
var i = 0
while(i < a.length) {
val v1 = a(i).asInstanceOf[AnyRef]
val v2 = f(v1.asInstanceOf[A]).asInstanceOf[AnyRef]
if(v1 ne v2)
return mapElems1Rest(a, f, i, v2)
i += 1
}
a
}
18
VectorStatics.mapElems1Rest:
scala/collection/immutable/Vector.scala#L2147L2157
final def mapElems1Rest[A, B](a: Arr1, f: A => B, at: Int,
v2: AnyRef): Arr1 = {
val ac = new Arr1(a.length)
if(at > 0) System.arraycopy(a, 0, ac, 0, at)
ac(at) = v2
var i = at+1
while(i < a.length) {
ac(i) = f(a(i).asInstanceOf[A]).asInstanceOf[AnyRef]
i += 1
}
ac
}
新たな1次元配列をwhileループで破壊的に更新しつつ
関数適用した要素を詰めて Vector1 を構築している
19
実際のListのmapメソッド実装
List.map:
scala/collection/immutable/List.scala#L245-L259
final override def map[B](f: A => B): List[B] = {
if (this eq Nil) Nil else {
val h = new ::[B](f(head), Nil)
var t: ::[B] = h
var rest = tail
while (rest ne Nil) {
val nx = new ::(f(rest.head), Nil)
t.next = nx
t = nx
rest = rest.tail
}
releaseFence()
h
}
}
whileループで Nil と :: から List を構築している
20
実際のSetのmapメソッド実装 scala> Set(1, 2, 3).getClass.get CanonicalName val res1: String = scala.collection.immutable.Set.Set3 Set() で3要素の場合の具象型は Set3 Iterable.map: scala/collection/Iterable.scala#L683 def map[B](f: A => B): CC[B]^{this, f} = iterableFactory.from(new View.Map(this, f)) 21
View.Map: scala/collection/View.scala#L294-L298
class Map[+A, +B](underlying: SomeIterableOps[A]^,
f: A => B) extends AbstractView[B] {
def iterator: Iterator[B]^{underlying, f} =
underlying.iterator.map(f)
override def knownSize = underlying.knownSize
override def isEmpty: Boolean = underlying.isEmpty
}
ここでは Set3 の iterator に対して map すること
になる
22
Iterator.map:
scala/collection/Iterator.scala#L585-L589
def map[B](f: A => B): Iterator[B]^{this, f} =
new AbstractIterator[B] {
override def knownSize = self.knownSize
def hasNext = self.hasNext
def next() = f(self.next())
}
イテレータで次の要素を取り出す際に関数を適用して
いる
23
iterableFactory.from -> Set.from: scala/collection/immutable/Set.scala#L98-L106 def from[E](it: collection.IterableOnce[E]^): Set[E] = it match { case _: SortedSet[E] => (newBuilder[E] ++= it).result() case _ if it.knownSize == 0 => empty[E] case s: Set[E] => s case _ => (newBuilder[E] ++= it).result() } イテラブル(View.Map)から Set を構築している 24
Vector (具象型の例として Vector1): 内部表現の配列を利用してループ処理 List: Nil と :: に対して素直にループ処理 Set (具象型の例として Set3): 上位階層(イテラブル/イテレータ)の実装を利用 共通して: 局所的に var やミュータブル値を利用 map メソッドのレシーバと戻り値の型が同じ 25
Scalaコレクションの全体像 イミュータブルコレクション Iterable Set HashSet Map ListSet SortedSet TreeSet BitSet HashMap Seq IndexedSeq Vector ArraySeq NumericRange String SortedMap SeqMap TreeMap ListMap VectorMap LinearSeq Range List LazyList Queue Scala公式ドキュメントのCollections hierarchyより 26
ミュータブルコレクション Iterable Set HashSet Map SortedSet LinkedHashSet PriorityQueue BitSet HashMap WeakHashMap TreeMap MultiMap ListMap SeqMap LinkedHashMap ArraySeq StringBuilder Seq IndexedSeq Buffer ArrayDeque ArrayBuffer Stack Queue ListBuffer Scala公式ドキュメントのCollections hierarchyより 27
(イミュータブル)コレクションの基本的な体系 Iterable: イテレータで反復処理できるもの Seq: シーケンシャルコレクション IndexedSeq: インデックスアクセス向き e.g. Vector, Range LinearSeq: 線形アクセス向き e.g. List, LazyList Set: 集合 e.g. HashSet Map: キー/値の対応付け e.g. HashMap 28
関数型言語としてイミュータブルコレクションがデ フォルトで使いやすくなっている あらかじめ非修飾名で使える < 実用上ミュータブルコレクションを使う機会 は少ない(存在を忘れても困らない(?)) 🐬 関数型言語らしく再帰処理と相性が良いのは List (単方向連結リスト) 基本的な操作がバランス良く効率的なのは Vector FYI: Performance Characteristics < Clojureで導入されて他言語に広まったとか 🐬 29
Kotlin編 30
Kotlinとは 静的型付きオブジェクト指向言語 プラットフォームとの相互運用性を重視 Scalaの強い影響が見られる一方で、Javaに寄り 添いJavaとの併用や移行もスムーズ < JavaとScalaの中間的な立ち位置の言語 JetBrains社により2011年に登場 2019年にAndroid開発の推奨言語になり、近年は サーバサイド開発の国内事例も増えている 名前の由来: Kotlin Island (コトリン島) cf. Java Island (ジャワ島) 🐬 31
Kotlinの map メソッドの利用例
>>> import kotlin.math.pow
// IntRange => List<Int>
>>> (1..10).
... map { 2.0.pow(it).toInt() } // Int => Int
res1: kotlin.collections.List<kotlin.Int> = [2, 4, 8, 16, 32,
64, 128, 256, 512, 1024]
// Set<String> => List<Int> => Grouping<Int, Int>
//
=> Map<Int, Int>
>>> setOf("abricot", "banane", "citron").
... map { it.length }. // String => Int
... groupingBy { it }.
... eachCount()
res2: kotlin.collections.Map<kotlin.Int, kotlin.Int> = {7=1,
6=2}
※メソッドは「(メンバー)関数」と呼ばれる
32
Kotlinの map メソッドの実装(Kotlin 2.0.21)
List, Set などのイテラブルに対して
Iterable<T>.map:
generated/_Collections.kt#L1556-L1558
public inline fun <T, R> Iterable<T>.map(transform: (T) -> R):
List<R> {
return mapTo(ArrayList<R>(collectionSizeOrDefault(10)),
transform)
}
ArrayList はJVMでは java.util.ArrayList
33
Iterable<T>.mapTo:
generated/_Collections.kt#L1627-L1631
public inline fun <T, R, C : MutableCollection<in R>>
Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
for (item in this)
destination.add(transform(item))
return destination
}
forループで ArrayList に関数適用した要素を追加
している
34
これらのコードは自動生成されている Iterable<T>.map: templates/Mapping.kt#L85-L130 Iterable<T>.mapTo: templates/Mapping.kt#L192-L216 Javaのコレクションがそのまま再利用されている listOf も java.util.Arrays.asList setOf も java.util.LinkedHashSet 35
Kotlinコレクションの全体像 Kotlin公式ドキュメントのCollection typesより 36
コレクションの基本的な体系 Iterable: イテレータで反復処理できるもの Collection: コレクションの共通機能 List: インデックスアクセス向きの順序付きコ レクション Set: 集合 Map: キー/値の対応付け 37
相互運用性重視ゆえかコレクションの体系はJavaを 踏襲している Java/Kotlinの List とScala/Clojure (たいていの 関数型言語)の List は指すものが異なる < Kotlinの List はほぼJavaの ArrayList 読み取り専用(read-only)コレクションからミュータ ブルコレクションが派生している (混同されやすいが) read-only ≠ immutable cf. ミュータビリティとイミュータビリティの狭 間: 関数型言語使いから見たKotlinコレクション Scalaの Vector 相当は標準ライブラリにはない 🐬 cf. kotlinx.collections.immutable.PersistentList 38
Clojure編 39
Clojureとは 動的型付き関数型言語 モダンに再設計されたLisp系言語 simpleであることを重視 Simple Made Easyというプレゼンに設計思想が よく表れている < OOPから距離を置きFPを志向したLisp Rich Hickeyにより2004年に登場 Clojure 1.9でclojure.specが追加された 名前の由来: closure (関数閉包) + C# + Lisp + Java Java/C#の環境で動作する関数型のLisp 🐬 40
Clojureの map 関数の利用例
user=> (require '[clojure.math :as math])
nil
;; ISeq (LongRange) => ISeq (LazySeq)
user=> (map #(long (math/pow 2 %)) ; Long => Long
(range 1 (inc 10)))
(2 4 8 16 32 64 128 256 512 1024)
;; IPersistentSet (PersistentHashSet) => ISeq (LazySeq)
;;
=> IPersistentMap (PersistentArrayMap)
user=> (->> #{"abricot" "banane" "citron"}
(map count) ; String => Integer
frequencies)
{7 1, 6 2}
41
Clojureの map 関数の実装(Clojure 1.12.0) 任意のシーケンス/シーカブル(Seqable)に対して clojure/core.clj#L2744-L2791 (defn map ... ; トランスデューサーのアリティ(後述) ([f coll] (lazy-seq (when-let [s (seq coll)] (if (chunked-seq? s) (let [c (chunk-first s) size (int (count c)) b (chunk-buffer size)] (dotimes [i size] (chunk-append b (f (.nth c i)))) (chunk-cons (chunk b) (map f (chunk-rest s)))) (cons (f (first s)) (map f (rest s))))))) ...) ; 複数のシーケンス/シーカブルをとるアリティ(後述) 42
1. 全体を遅延シーケンス(lazy-seq)として返す 以下の処理は利用側で必要になる(実体化される) まで実行されない 2. 引数 coll をシーケンス化(seq)する 3. その結果が nil => そのまま チャンク化されている(chunked-seq?) => 先頭 チャンクの全要素に関数を適用して残りのチャン クに対して map を再帰呼び出し その他の場合 => 先頭要素に関数を適用して残り の要素に対して map を再帰呼び出し 43
最終引数が複数(可変長)のアリティがある (defn map ... ([f c1 c2] ; シーケンス/シーカブルが2個の場合 (lazy-seq (let [s1 (seq c1) s2 (seq c2)] (when (and s1 s2) (cons (f (first s1) (first s2)) (map f (rest s1) (rest s2))))))) ([f c1 c2 c3] ; シーケンス/シーカブルが3個の場合 ...) ([f c1 c2 c3 & colls] ; シーケンス/シーカブルが4個以上の場合 ...)) 他言語の zip + map (zipWith)相当のことができる user=> (map vector [:a :b :c] [1 2]) ([:a 1] [:b 2]) 44
特殊な関数(transducer)を返すアリティがある
(defn map
([f]
(fn [rf]
(fn
([] (rf)) ; 0引数の場合
([result] (rf result)) ; 1引数の場合
([result input] ; 2引数の場合(基本形)
(rf result (f input)))
([result input & inputs] ; 3引数以上の場合
(rf result (apply f input inputs))))))
...)
reducing function (rf; reduce 関数に渡せる関数):
(result, input) -> result'
transducer: rf -> rf'
45
map のトランスデューサーの利用例 ;; 入力の要素を2倍して和を求める user=> (transduce (map #(* % 2)) + 0 [1 2 3]) 12 ;; 上の例はこれと同等 user=> (reduce ((map #(* % 2)) +) 0 [1 2 3]) 12 ;; 入力の要素を2倍してシーケンス化する user=> (sequence (map #(* % 2)) [1 2 3]) (2 4 6) ;; 入力の要素を2倍してセット化する user=> (into #{} (map #(* % 2)) [1 2 3]) #{4 6 2} 入出力の構造に依存することなく「要素に関数を適用 する」振る舞い(map の本質的な機能)を再利用できる 46
Clojureコレクションの全体像 書籍Clojure Applied, Chapter 2より 47
コレクションの基本的な体系 Seqable: シーカブル(シーケンス化できるもの) IPersistentCollection: コレクションの共 通機能 ISeq: シーケンス(論理的なリスト) IPersistentList: 単方向連結リスト IPersistentVector: ベクター(Scalaの Vector と同等) IPersistentSet: セット(集合) IPersistentMap: マップ(キー/値の対応付け) 48
関数型言語としてネイティブのミュータブルコレク ションは提供されていない cf. Transient Data Structures IPersistent プレフィックスは永続データ構造 FYI: Clojure Performance Guarantees < 『純粋関数型データ構造』 🐬 シーカブルとシーケンスは他言語でのイテラブルと イテレータ相当 Clojureでの中核的な抽象(あらゆるデータがシー ケンスとして扱える) 49
3. 各言語のコレクションの特徴 👀 Javaとの差異に注目 50
Scalaのコレクション 主な特徴: イミュータブルとミュータブルの2系統の独自コ レクション体系 List や Vector など関数型言語らしい実装 便利な仕組み: for式(for内包表記)でコレクションに限らず map, flatMap などを備えた構造を簡潔に扱える Javaとの相互運用: CollectionConvertersによりJavaコレクションと 相互変換 51
Kotlinのコレクション 主な特徴: Javaを踏襲したコレクション体系 読み取り専用とミュータブルなコレクション 便利な仕組み: Javaコレクションを基礎としながらも拡張関数に よりAPIがリッチになっている Javaとの相互運用: mapped typesとしてJavaの型とKotlinの型とが 対応付けられている 52
Clojureのコレクション 主な特徴: イミュータブルのみの独自コレクション体系 コレクションは不変かつ永続的 便利な仕組み: コレクションに限らず多くのデータ構造がシーケ ンスという抽象に統合されているため、あらゆる ものがリストのように扱える Javaとの相互運用: コレクションがJavaインターフェースも実装し、 標準ライブラリ関数がJavaインターフェースにも 対応している 53
Javaとは異なる魅力的な進化をしているJVM言語 Scala, Kotlin, Clojureをぜひ試してみよう 😈 54
Further Reading Scala 公式サイト: https://www.scala-lang.org/ https://docs.scalalang.org/scala3/book/collections-classes.html https://docs.scalalang.org/scala3/book/collections-methods.html https://docs.scala-lang.org/tour/forcomprehensions.html ソースコード: https://github.com/scala/scala3 55
Kotlin 公式サイト: https://kotlinlang.org/ https://kotlinlang.org/docs/collectionsoverview.html https://kotlinlang.org/docs/collectionoperations.html https://kotlinlang.org/docs/java-interop.html ソースコード: https://github.com/JetBrains/kotlin 56
Clojure 公式サイト: https://clojure.org/ https://clojure.org/reference/data_structures https://clojure.org/reference/sequences https://clojure.org/reference/transducers ソースコード: https://github.com/clojure/clojure 書籍Clojure Applied Chapter 2. Collect and Organize Your Data Chapter 3. Processing Sequential Data 57