純LISPから考える関数型言語のプリミティブ: Clojure, Elixir, Haskell, Scala

純LISPのミニマルなデータ構造とオペレータの観点から現代の関数型言語について探ってみよう!

Transcript

1. 純LISP から考える 関数型言語のプリミティブ Clojure, Elixir, Haskell, Scala #lispmeetup 1
2. のシニアエンジニア スタートアップの起業家と投資家のための業務効 率化/ 連携プラットフォームを開発している 主要技術スタック: & TypeScript の運営企業 関数型プログラミング( 言語) とLisp の熱烈な愛好者 仕事や趣味で , , などに長く 触れてきた(JVM 言語の割合高め) lagénorhynque 🐬カマイルカ 株式会社スマートラウンド Kotlin Server-Side Kotlin Meetup Clojure Scala Haskell 2
3. [PR] カンファレンス 6 月開催 近日中にセッションリスト公開、チケット販売予定 募集中 Lisper の皆様もぜひご検討ください🙏 「関数型まつり2025 」 企業/ 個人スポンサー 3
4. 取り上げる予定の4 つの関数型言語について、Lisp の 観点から改めて探ってみるのが今回のテーマ 関数型言語テイスティング: Haskell, Scala, Clojure, Elixir を比べて味わう関数型プログラミングの旨さ 4
5. 1. 純LISP 2. 関数型言語Clojure, Elixir, Haskell, Scala 3. 4 つの言語でのリストとオペレータ 4. 4 つの言語での高階関数の再実装 5
6. 純LISP 6
7. [IMO] Lisp とは "list processing" に由来する言語群 ⭐ リストを中核とした言語 重要な特徴 S 式(S-expression) 同図像性(homoiconicity) ⭐ 関数型言語( のプロトタイプ) LISP からLisp 族とML 族へ 高度なREPL 開発環境 7
8. by > 純LISP って？ Python のリスト内包表記はチューリング完全だから純 LISP だって実装できる t-sin 8
9. コンスセル( によるリスト) とその操作 純LISP 現代の言語での表現例 コンスセル構造 ( 連結) リスト, タプル, レコード 空値/ 偽値 nil 空リスト, nil/null, false コンスセル構築 cons cons/:, リスト/ タプル/ レコー ドリテラル コンスセル分解 car, cdr head, tail, パターンマッチン グ 9
10. その他の基本オペレータ 純LISP 現代の言語での表現例 アトム判定 atom 型判定述語 等価判定 eq ==, eq 条件式 if, cond if, match ラムダ式 lambda =>, -> 定義式 define def, = クォート quote ( 非Lisp 系言語では稀) 10
11. 関数型言語Clojure, Elixir, Haskell, Scala 11
12. paradigm FP FP OOP, FP FP typing dynamic dynamic static static first appeared 2007 2012 2004 1990 related Lisp Lisp ML ML 🐬's note modern functional Lisp Erlang + Ruby + Clojure OOPL in FPL's skin lazy/pure FPL standard Clojure Elixir Scala Haskell 12
13. 4 つの言語でのリストとオペレータ 13
14. リスト( 類似コレクション) のリテラル: Clojure ;; ( 連結) リスト '(1 2 3) ; クォートにより要素は評価されない (list 1 2 3) () ; 空リスト nil ; nil 値 ;; ベクター [1 2 3] (vector 1 2 3) [] ; 空ベクター ;; シーケンス( 論理的なリストのインターフェース) (seq [1 2 3]) ; この例ではベクター由来 14
15. リスト( 類似コレクション) のリテラル: Elixir # ( 連結) リスト [1, 2, 3] [] # 空リスト # タプル {1, 2, 3} {} # 空タプル 15
16. リスト( 類似コレクション) のリテラル: Scala // ( 連結) リスト List(1, 2, 3) List(), List.empty // 空リスト Nil // nil 値 // ベクター Vector(1, 2, 3) Vector(), Vector.empty // 空ベクター // ( リストやベクターを含む) シーケンシャルコレクションのインターフェース Seq(1, 2, 3) // タプル (1, 2, 3) 16
17. リスト( 類似コレクション) のリテラル: Haskell -- ( 連結) リスト [1, 2, 3] [] -- 空リスト -- タプル (1, 2, 3) 17
18. リスト( 類似コレクション) の構築・分解: Clojure user=> (cons 1 (cons 2 (cons 3 ()))) (1 2 3) ; シーケンス user=> (->> () (cons 3) (cons 2) (cons 1)) ; threading macro (1 2 3) ; シーケンス user=> (conj () 3 2 1) (1 2 3) ; リスト/ シーケンス user=> (conj [] 1 2 3) [1 2 3] ; ベクター user=> (first [1 2 3]) 1 user=> (rest [1 2 3]) (2 3) ; ベクター由来のシーケンス ;; 分配束縛 user=> (let [[x & xs] [1 2 3]] [x xs]) ; ベクターをタプルのように使ってまとめて確認 [1 (2 3)] 18
19. リスト( 類似コレクション) の構築・分解: Elixir iex(1)> [1 | [2 | [3 | []]]] [1, 2, 3] iex(2)> Tuple.append(Tuple.append(Tuple.append({}, 1), 2), 3) {1, 2, 3} iex(3)> {} |> Tuple.append(1) |> Tuple.append(2) |> ...(3)> Tuple.append(3) # パイプ演算子 {1, 2, 3} iex(4)> hd([1, 2, 3]) 1 iex(5)> tl([1, 2, 3]) [2, 3] # パターンマッチング iex(6)> [x | xs] = [1, 2, 3] [1, 2, 3] iex(7)> {x, xs} # タプルでまとめて確認 {1, [2, 3]} iex(8)> {a, b, c} = {1, 2, 3} {1, 2, 3} iex(9)> [a, b, c] # リストでまとめて確認 [1, 2, 3] 19
20. リスト( 類似コレクション) の構築・分解: Scala scala> 1 :: 2 :: 3 :: Nil val res0: List[Int] = List(1, 2, 3) scala> Vector() :+ 1 :+ 2 :+ 3 val res1: Vector[Int] = Vector(1, 2, 3) scala> List(1, 2, 3).head val res2: Int = 1 scala> List(1, 2, 3).tail val res3: List[Int] = List(2, 3) // パターンマッチング scala> val x :: xs = List(1, 2, 3): @unchecked val x: Int = 1 val xs: List[Int] = List(2, 3) scala> val ys :+ y = Vector(1, 2, 3): @unchecked val ys: Vector[Int] = Vector(1, 2) val y: Int = 3 scala> val (a, b, c) = (1, 2, 3) val a: Int = 1 val b: Int = 2 val c: Int = 3 20
21. リスト( 類似コレクション) の構築・分解: Haskell > 1 : 2 : 3 : [] [1,2,3] it :: Num a => [a] > head [1, 2, 3] 1 it :: Num a => a > tail [1, 2, 3] [2,3] it :: Num a => [a] -- パターンマッチング > x : xs = [1, 2, 3] x :: Num a => a xs :: Num a => [a] > (x, xs) -- タプルでまとめて確認 (1,[2,3]) it :: (Num a1, Num a2) => (a1, [a2]) 21
22. > (a, b, c) = (1, 2, 3) a :: Num a => a b :: Num b => b c :: Num c => c > [a, b, c] -- リストでまとめて確認 [1,2,3] it :: Num a => [a] 22
23. 判定述語: Clojure ;; 型判定 user=> (seq? []) ; シーケンス判定 false user=> (seqable? []) ; シーケンス化可能( シーカブル) 判定 true ;; 空判定 user=> (seq []) ; シーケンス化(nil punning で非空判定) nil user=> (empty? []) ; コレクション/ シーケンスの空判定 true ;; 等価判定 user=> (= 1 2) false user=> (not= 1 2) true 23
24. 判定述語: Elixir # 型判定 iex(1)> is_list([]) # リスト判定 true iex(2)> is_tuple({}) # タプル判定 true # 空判定 iex(3)> Enum.empty?([]) # Enumerable の空判定 true # 等価判定 iex(4)> 1 == 2 false iex(5)> 1 != 2 true 24
25. 判定述語: Scala // 静的型付き言語なので動的に型判定することは稀 // 空判定 scala> List().isEmpty val res0: Boolean = true scala> Vector().isEmpty val res1: Boolean = true // 等価判定 scala> 1 == 2 val res2: Boolean = false scala> 1 != 2 val res3: Boolean = true 25
26. 判定述語: Haskell -- 静的型付き言語なので動的に型判定することは稀 -- 空判定 > null [] True it :: Bool -- 等価判定 > 1 == 2 False it :: Bool > 1 /= 2 True it :: Bool 26
27. 条件式 if ;; Clojure user=> (if (= 1 2) :t :f) :f # Elixir iex(1)> if 1 == 2, do: :t, else: :f :f // Scala scala> if (1 == 2) 't' else 'f' val res0: Char = f -- Haskell > if 1 == 2 then 't' else 'f' 'f' it :: Char 27
28. ラムダ式(a.k.a. 関数リテラル) ;; Clojure (fn [x] (* x x)) #(* % %) ; 略記法 # Elixir fn x -> x * x end &(&1 * &1) # 略記法 // Scala x => x * x -- Haskell \x -> x * x 28
29. 定義式: Clojure, Elixir ;; Clojure (def x 42) (def f (fn [x] (* x x))) (defn g [x] (* x x)) ; 上とほぼ等価な定義( メタデータに差が生じうる) # Elixir x = 42 f = fn x -> x * x end # 無名関数を束縛した変数 defmodule SomeModule do def g(x), do: x * x # モジュールの名前付き関数 end 29
30. 定義式: Scala, Haskell // Scala val x = 42 val f = (x: Int) => x * x // 関数オブジェクトを束縛した変数 def g(x: Int) = x * x // メソッド(eta-expansion で上と等価に) -- Haskell x = 42 f = \x -> x * x g x = x * x -- 上と等価な定義 30
31. クォート: Clojure, Elixir ;; Clojure user=> '(+ 1 2) (+ 1 2) # Elixir iex(1)> quote do: 1 + 2 {:+, [ context: Elixir, imports: [{1, Kernel}, {2, Kernel}] ], [1, 2]} 31
32. 4 つの言語での高階関数の再実装 32
33. 高階関数 reduce: Clojure, Elixir user=> (defn reduce' [f val coll] (if (empty? coll) val (recur f (f val (first coll)) (rest coll)))) #'user/reduce' user=> (reduce' * 1 [1 2 3 4 5]) 120 iex(1)> defmodule MyPrelude do ...(1)> def reduce([], acc, _), do: acc ...(1)> def reduce([x | xs], acc, f), ...(1)> do: reduce(xs, f.(acc, x), f) ...(1)> end {:module, MyPrelude, ..., {:reduce, 3}} iex(2)> MyPrelude.reduce([1, 2, 3, 4, 5], 1, &(&1 * &2)) 120 33
34. 高階関数 foldLeft: Scala, Haskell scala> def foldLeft[A, B](list: List[A])(acc: B) (f: (B, A) => B): B = | if (list.isEmpty) acc | else foldLeft(list.tail)(f(acc, list.head))(f) def foldLeft[A, B](list: List[A])(acc: B)(f: (B, A) => B): B scala> foldLeft(List(1, 2, 3, 4, 5))(1)(_ * _) val res0: Int = 120 > :{ ghci| foldLeft :: (b -> a -> b) -> b -> [a] -> b ghci| foldLeft _ acc [] = acc ghci| foldLeft f acc (x:xs) = foldLeft f (f acc x) xs ghci| :} foldLeft :: (b -> a -> b) -> b -> [a] -> b > foldLeft (*) 1 [1, 2, 3, 4, 5] 120 it :: Num a => a 34
35. 高階関数 map: Clojure, Elixir user=> (defn reverse' [coll] (reduce' #(cons %2 %1) () coll)) #'user/reverse' user=> (defn map' [f coll] (reduce' #(cons (f %2) %1) () (reverse' coll))) #'user/map' user=> (map' #(* % %) [1 2 3 4 5]) (1 4 9 16 25) iex(3)> defmodule MyPrelude do ...(3)> # def reduce ... ...(3)> def reverse(list), ...(3)> do: reduce(list, [], &([&2 | &1])) ...(3)> def map(list, f), ...(3)> do: reduce(reverse(list), [], &([f.(&2) | &1])) ...(3)> end {:module, MyPrelude, ..., {:map, 2}} iex(4)> MyPrelude.map([1, 2, 3, 4, 5], &(&1 * &1)) [1, 4, 9, 16, 25] 35
36. 高階関数 map: Scala, Haskell scala> def reverse[A](list: List[A]): List[A] = | foldLeft(list)(List())((acc, x) => x :: acc) def reverse[A](list: List[A]): List[A] scala> def map[A, B](list: List[A])(f: A => B): List[B] = | foldLeft(reverse(list))(List())((acc, x) => | f(x) :: acc) def map[A, B](list: List[A])(f: A => B): List[B] scala> map(List(1, 2, 3, 4, 5))(x => x * x) val res1: List[Int] = List(1, 4, 9, 16, 25) > :{ ghci| reverse' :: [a] -> [a] ghci| reverse' = foldLeft (flip (:)) [] ghci| map' :: (a -> b) -> [a] -> [b] ghci| map' f = foldLeft (\acc x -> f x : acc) [] . reverse' ghci| :} map' :: (a -> b) -> [a] -> [b] reverse' :: [a] -> [a] > map' (\x -> x * x) [1, 2, 3, 4, 5] [1,4,9,16,25] it :: Num b => [b] 36
37. 高階関数 filter: Clojure, Elixir user=> (defn filter' [pred coll] (reduce' (fn [acc x] (if (pred x) (cons x acc) acc)) () (reverse' coll))) #'user/filter' user=> (filter' odd? [1, 2, 3, 4, 5]) (1 3 5) iex(5)> defmodule MyPrelude do ...(5)> # def reduce ... ...(5)> # def reverse ... ...(5)> def filter(list, pred), ...(5)> do: reduce(reverse(list), [], fn acc, x -> ...(5)> if pred.(x), do: [x | acc], else: acc ...(5)> end) ...(5)> end {:module, MyPrelude, ..., {:filter, 2}} iex(6)> require Integer Integer iex(7)> MyPrelude.filter([1, 2, 3, 4, 5], &Integer.is_odd/1) [1, 3, 5] 37
38. 高階関数 filter: Scala, Haskell scala> def filter[A](list: List[A])(pred: A => Boolean): List[A] = | foldLeft(reverse(list))(List())((acc, x) => | if (pred(x)) x :: acc else acc) def filter[A](list: List[A])(pred: A => Boolean): List[A] scala> filter(List(1, 2, 3, 4, 5))(_ % 2 != 0) val res2: List[Int] = List(1, 3, 5) > :{ ghci| filter' :: (a -> Bool) -> [a] -> [a] ghci| filter' pred = foldLeft (\acc x -> ghci| if pred x then x : acc else acc) [] . reverse' ghci| :} filter' :: (a -> Bool) -> [a] -> [a] > filter' odd [1, 2, 3, 4, 5] [1,3,5] it :: Integral a => [a] 38
39. まとめ 純LISP 相当のデータ構造とオペレータは現代の関数 型言語でも重要な役割を果たしている コレクション操作は関数型プログラミングの基盤 のひとつだといえる 関数型言語の入門時に最初に探るのもオススメ リストに対する最小限のオペレータからボトムアッ プにライブラリを充実させることができる 実際の標準ライブラリではより効率的かつ汎用的 に実装されている( はず) 39
40. Further Reading Clojure: Elixir: Scala: Haskell: サンプルコード: https://clojure.org/ https://elixir-lang.org/ https://www.scala-lang.org/ https://www.haskell.org/ Reimplementation of typical higher-order functions in Clojure, Elixir, Scala and Haskell 40