純LISPから考える

関数型言語のプリミティブ

Clojure, Elixir, Haskell, Scala

#lispmeetup

---

lagénorhynque🐬カマイルカ

• 株式会社スマートラウンドのシニアエンジニア
  • スタートアップの起業家と投資家のための業務効率化/連携プラットフォームを開発している
  • 主要技術スタック: Kotlin & TypeScript
  • Server-Side Kotlin Meetupの運営企業
• 関数型プログラミング(言語)とLispの熱烈な愛好者
  • 仕事や趣味でClojure, Scala, Haskellなどに長く触れてきた(JVM言語の割合高め)

---

[PR] カンファレンス「関数型まつり2025」6月開催

• 近日中にセッションリスト公開、チケット販売予定
• 企業/個人スポンサー募集中
  • Lisperの皆様もぜひご検討ください🙏

---

関数型言語テイスティング: Haskell, Scala, Clojure, Elixirを比べて味わう関数型プログラミングの旨さ

取り上げる予定の4つの関数型言語について、Lispの観点から改めて探ってみるのが今回のテーマ

---

1. 純LISP
2. 関数型言語Clojure, Elixir, Haskell, Scala
3. 4つの言語でのリストとオペレータ
4. 4つの言語での高階関数の再実装

---

純LISP

---

[IMO] Lispとは

• "list processing"に由来する言語群

  • ⭐ リストを中核とした言語

• 重要な特徴

  • S式(S-expression)

    • 同図像性(homoiconicity)

  • ⭐ 関数型言語(のプロトタイプ)

    • LISPからLisp族とML族へ

  • 高度なREPL開発環境

---

Pythonのリスト内包表記はチューリング完全だから純LISPだって実装できる by t-sin > 純LISPって？

---

コンスセル(によるリスト)とその操作

純LISP	現代の言語での表現例
コンスセル構造	(連結)リスト, タプル, レコード
空値/偽値 nil	空リスト, nil/null, false
コンスセル構築 cons	cons/:, リスト/タプル/レコードリテラル
コンスセル分解 car, cdr	head, tail, パターンマッチング

---

その他の基本オペレータ

純LISP	現代の言語での表現例
アトム判定 atom	型判定述語
等価判定 eq	==, eq
条件式 if, cond	if, match
ラムダ式 lambda	=>, ->
定義式 define	def, =
クォート quote	(非Lisp系言語では稀)

---

関数型言語Clojure, Elixir, Haskell, Scala

---

	Clojure	Elixir	Scala	Haskell
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

---

4つの言語でのリストとオペレータ

---

リスト(類似コレクション)のリテラル: Clojure

;; (連結)リスト
'(1 2 3)  ; クォートにより要素は評価されない
(list 1 2 3)
()  ; 空リスト
nil  ; nil値

;; ベクター
[1 2 3]
(vector 1 2 3)
[]  ; 空ベクター

;; シーケンス(論理的なリストのインターフェース)
(seq [1 2 3])  ; この例ではベクター由来

---

リスト(類似コレクション)のリテラル: Elixir

# (連結)リスト
[1, 2, 3]
[]  # 空リスト

# タプル
{1, 2, 3}
{}  # 空タプル

---

リスト(類似コレクション)のリテラル: Scala

// (連結)リスト
List(1, 2, 3)
List(), List.empty  // 空リスト
Nil  // nil値

// ベクター
Vector(1, 2, 3)
Vector(), Vector.empty  // 空ベクター

// (リストやベクターを含む)シーケンシャルコレクションのインターフェース
Seq(1, 2, 3)

// タプル
(1, 2, 3)

---

リスト(類似コレクション)のリテラル: Haskell

-- (連結)リスト
[1, 2, 3]
[]  -- 空リスト

-- タプル
(1, 2, 3)

---

リスト(類似コレクション)の構築・分解: 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)]

---

リスト(類似コレクション)の構築・分解: 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]

---

リスト(類似コレクション)の構築・分解: 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

---

リスト(類似コレクション)の構築・分解: 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])

---

> (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]

---

判定述語: Clojure

;; 型判定
user=> (seq? [])  ; シーケンス判定
false
user=> (seqable? [])  ; シーケンス化可能(シーカブル)判定
true
;; 空判定
user=> (seq [])  ; シーケンス化(nil punningで非空判定)
nil
user=> (empty? [])  ; コレクション/シーケンスの空判定
true
;; 等価判定
user=> (= 1 2)
false
user=> (not= 1 2)
true

---

判定述語: 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

---

判定述語: 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

---

判定述語: Haskell

-- 静的型付き言語なので動的に型判定することは稀

-- 空判定
> null []
True
it :: Bool
-- 等価判定
> 1 == 2
False
it :: Bool
> 1 /= 2
True
it :: Bool

---

条件式 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

---

ラムダ式(a.k.a. 関数リテラル)

;; Clojure
(fn [x] (* x x))

#(* % %)  ; 略記法

# Elixir
fn x -> x * x end

&(&1 * &1)  # 略記法

// Scala
x => x * x

-- Haskell
\x -> x * x

---

定義式: 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

---

定義式: 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  -- 上と等価な定義

---

クォート: Clojure, Elixir

;; Clojure
user=> '(+ 1 2)
(+ 1 2)

# Elixir
iex(1)> quote do: 1 + 2
{:+,
 [
   context: Elixir,
   imports: [{1, Kernel}, {2, Kernel}]
 ], [1, 2]}

---

4つの言語での高階関数の再実装

---

高階関数 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

---

高階関数 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

---

高階関数 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]

---

高階関数 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]

---

高階関数 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]

---

高階関数 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]

---

まとめ

• 純LISP相当のデータ構造とオペレータは現代の関数型言語でも重要な役割を果たしている

  • コレクション操作は関数型プログラミングの基盤のひとつだといえる
  • 関数型言語の入門時に最初に探るのもオススメ

• リストに対する最小限のオペレータからボトムアップにライブラリを充実させることができる

  • 実際の標準ライブラリではより効率的かつ汎用的に実装されている(はず)

---

Further Reading

• Clojure: https://clojure.org/

• Elixir: https://elixir-lang.org/

• Scala: https://www.scala-lang.org/

• Haskell: https://www.haskell.org/

• サンプルコード: Reimplementation of typical higher-order functions in Clojure, Elixir, Scala and Haskell