lagenorhynque/mkslides.yml

速習 FP in Scala with Flix

Flix言語で親しむ純粋関数型のコード設計

#fp_matsuri

#fp_matsuri_a

lagénorhynque🐬カマイルカ

関数型プログラミング(言語)の愛好者/実践者
- 特にClojure, Haskell, Flixがエレガントで好き
関数型まつり2026の運営スタッフ(座長のひとり)
- 主に(CfPを含む)メインコンテンツの準備を担当
株式会社スマートラウンドのシニアエンジニア
- スタートアップと投資家のやり取りを効率化するデータ管理プラットフォームを開発
- ソフトウェア設計/開発とともに会計/財務/法務について探求するのも好き

きっかけ
書籍 FP in Scala とは
Flix言語の基本
(純粋)関数型のコード設計
1. 関数型プログラミング入門
2. 関数型設計とコンビネータライブラリ
3. 関数型設計に共通する構造
4. エフェクトとI/O

1. きっかけ

関数型まつり2025での🐬の発表

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

書籍 Functional Programming in Scala
(FP in Scala)

今年度は関数型プログラミングらしいコード設計/抽象化のパターンにより踏み込んで解説したい
関数型言語について学び始めた頃に取り組んだ本のひとつに FP in Scala があった
- 演習問題が膨大で途中まで進めて積んでいたが😇
関数型まつり2026の「FP入門ハンズオン」の題材として FP in Scala の演習問題を利用することに
- ハンズオン資料: fp-matsuri/2026.fp-hands-on

Flixとの出会い

Clojurianが出会ったsimple志向なJVM関数型言語Flix ——ファーストインプレッション

エフェクトシステムを備えた関数型言語Flix

エフェクトシステムと代数的エフェクトを探求する過程で、Flixという言語に出会った
simple と easy を区別して simplicity を重視するという方向性もFlixの設計指針に含まれている
- Rich Hickeyの有名なプレゼンSimple Made Easyに由来する
- 🐬はClojurianなので大いに感激した😆

[参考] Shibuya.lisp lispmeetup #118での🐬の発表

"Simple Made Easy" Made Easier: Clojureに学ぶsimplicity

「"Simple Made Easy" Made Easier 」の要約

simple は客観的な構造の単純さ、 easy は主観的な(広義の)近さの問題(なのだが誤解されがち)
Clojureエコシステム/コミュニティには様々な simplicity 追求の例がある
抽象度を上げて、客体/モノと主体/ヒトの区別、
さらにはars/τέχνη (技芸)とvita/βίος (人生)の対比と捉えることもできる

2. 書籍 FP in Scala とは

Functional Programming in Scala, Second Edition

Manningの書籍詳細ページより

『Scala関数型デザイン＆プログラミング』
※ Functional Programming in Scala (第1版)の訳書

インプレスブックスの書籍詳細ページより

FP in Scala, a.k.a. The Red Book 📕

オブジェクト指向/関数型言語Scalaで(純粋関数型言語Haskellのような) FP実践を目指す本
- 2014年初版当時のScalaコミュニティでは良くも悪くも"better Java"扱いが珍しくなかった
- ScalaでFP設計を深く学べる(おそらく)最初の本
豊富な演習問題に取り組みながら理解を深め、抽象化の必要性/必然性を体感できる教育的な構成
- ただし、独習では挫折しやすい本でもある🥹

書籍公式リポジトリfpinscala
- 演習問題/ヒント/解答例/テストコード
- Wiki: 追加の解説/チャプターノート
  - Haskellの概説ページも
    - [参考] HaskellコードのFlix移植例 by 🐬
cf. Scala以外の関数型言語による実装
- fp-matsuri/fp-in-scala-exercises
  - FP in Scala ベースの関数型プログラミング演習問題 by 関数型まつり
- lagenorhynque/fp-in-scala
  - Clojure/Flix実装 by 🐬

3. Flix言語の基本

Flixとは

エフェクトシステムの組み込みサポートが特徴的な静的型付き関数型言語
- 副作用を伴う関数には IO エフェクトが付く
- Scalaと関係が深いが非オブジェクト指向言語
  (サブタイピング(部分型)/継承とも無縁)
JVM言語(Scala, Kotlin, Clojureなどと同じ)
主にHaskell, Scala, OCaml, Rustの影響が見られる
- 処理系の実装言語もScala
🐬< 大雑把には「Scalaの皮を被ったHaskell」🐑

ℹ️ 他の関数型言語経験者向けの補足

Hindley-Milner型システムが採用されている
- HaskellやML系言語と同様
- ⚠️ トップレベルの定義のみ敢えて型注釈必須
関数は常にカリー化される
- HaskellやML系言語と同様
- 構文的に多引数関数に見えても実体は1引数関数の連鎖
Haskellによく似た型クラス(type class)がある
- trait というキーワードはRust/Scala由来

コードの書き方(0): 事前準備

mkdir first-flix-project
cd first-flix-project
# プロジェクトを生成
flix init
# プロジェクトルートのモジュールファイルを追加
echo 'pub mod FirstFlixProject {}' > src/FirstFlixProject.flix

flix コマンドでプロジェクトを生成する

コードの書き方(1): モジュールとそのトップレベル関数

// src/FirstFlixProject/SimpleMath.flix
pub mod FirstFlixProject.SimpleMath {
    // パブリック関数
    pub def square(n: Int32): Int32 =
        n * n

    // プライベート関数
    // ⚠️ 未使用のままだとコンパイルエラー
    def double(n: Int32): Int32 =
        n * 2
}

コードの書き方(2): トップレベル関数による定数

// src/FirstFlixProject/SomeModule.flix
pub mod FirstFlixProject.SomeModule {
    // パブリックな0引数関数
    pub def a(): Int32 = 1

    // プライベートな0引数関数
    // ⚠️ 未使用のままだとコンパイルエラー
    def b(): Int32 = 2
}

トップレベル変数は存在しない

コードの書き方(3): モジュールの利用

flix> use FirstFlixProject.{SimpleMath => M}; \
>     M.square(3)
9

flix> use FirstFlixProject.{SimpleMath => M}; \
>     List.map(M.square, List.range(0, 11))
0 :: 1 :: 4 :: 9 :: 16 :: 25 :: 36 :: 49 :: 64 :: 81 :: 100
  :: Nil

flix> use FirstFlixProject.{SimpleMath => M}; \
>     List.range(0, 11) |> List.map(M.square)
0 :: 1 :: 4 :: 9 :: 16 :: 25 :: 36 :: 49 :: 64 :: 81 :: 100
  :: Nil

; は式の区切り文字
\ はREPLでの行継続
|> はパイプ(ライン)演算子

コードの書き方(4): ローカル束縛

flix> \\
> use FirstFlixProject.{SimpleMath => M};
> let x = 5;
> let y = M.square(x);
> "square(${x}) = ${y}"
> \\
square(5) = 25

\\ はREPLでの複数行入力の開始/終了

コードの書き方(5): 無名関数(ラムダ式)

flix> (n -> n * n * n)(2)
8

flix> List.map(n -> n * n * n, List.range(0, 11))
0 :: 1 :: 8 :: 27 :: 64 :: 125 :: 216 :: 343 :: 512 :: 729 ::
  1000 :: Nil

4. (純粋)関数型のコード設計

関数型プログラミング入門
関数型設計とコンビネータライブラリ
関数型設計に共通する構造
エフェクトとI/O

第1部関数型プログラミング入門

関数型プログラミングとは
Flixで始める関数型プログラミング
関数型データ構造
例外によらないエラーハンドリング
正格性と遅延性
純粋関数型の状態

第1章関数型プログラミングとは

キーワード

関数型プログラミング(functional programming)
純粋関数(pure function)
副作用(side effect)
参照透過性(referential transparency)
純粋性(purity)
置換モデル(substitution model)

カフェでコーヒーを注文する過程を表す素朴なコード

// ⚠️ ScalaのOOPかつ非FPなコード
class Cafe:
  def buyCoffee(cc: CreditCard): Coffee =
    val cup = Coffee()
    cc.charge(cup.price)
    cup
class CreditCard:
  def charge(price: Double): Unit =
    println("charging " + price)  // 請求処理(簡単のため標準出力)
class Coffee:
  val price: Double = 2.0

// 利用例
scala> Cafe().buyCoffee(CreditCard())
charging 2.0  // 標準出力
val res0: Coffee = Coffee@353cb7e5  // 戻り値

クレジットカードへの請求処理という副作用が埋め込まれている

OOPで典型的な改善策: インターフェースを導入してDI

// ⚠️ ScalaのOOPかつ非FPなコード
class Cafe:
  def buyCoffee(cc: CreditCard, p: Payments): Coffee =
    val cup = Coffee()
    p.charge(cc, cup.price)
    cup
// インターフェース定義
trait Payments:
  def charge(cc: CreditCard, price: Double): Unit
// インターフェースに対する実装
class SimulatedPayments extends Payments:
  def charge(cc: CreditCard, price: Double): Unit =
    println("charging " + price + " to " + cc)

副作用を含む実装を差し替えやすくなった
しかし依然として:
- テストしやすいとまではいえない
- buyCoffee の再利用性は低い

Flixでの対応A: (非OOPLなので)振る舞いを関数で渡す

mod Coffee {
    // priceフィールドを持つレコードによるCoffee型
    pub enum Coffee({price = Float64})
    // 文字列表現(ToString型クラスの実装)
    instance ToString[Coffee] {
        pub def toString(coffee: Coffee): String =
            let Coffee({price}) = coffee;
            "Coffee({price = ${price}})"
    }
    // コンストラクタ関数(ただの関数)
    pub def make(): Coffee = Coffee({price = 2.0})
}

mod CreditCard {
    // 金額を受け取って何も返さず、IOエフェクト(副作用)を伴う関数
    pub def charge(price: Float64): Unit \ IO =
        println("charging ${price}")
}

mod Cafe {
    use FpInFlix.Exercises.Introduction.FirstExample.Coffee
    // 請求関数を受け取ってコーヒーを返し、IOエフェクトを伴う関数
    pub def buyCoffee(charge: Float64 -> Unit \ IO):
      Coffee \ IO =
        let coffee = Coffee.make();
        let Coffee.Coffee({price}) = coffee;
        charge(price);
        coffee
}

// 利用例
flix> use FpInFlix.Exercises.Introduction.FirstExample.{Cafe,
  CreditCard}; \  // ℹ️ 以降はスペース節約のためuseを省略する
>     Cafe.buyCoffee(CreditCard.charge)
charging 2.0           // 標準出力
Coffee({price = 2.0})  // 戻り値

高階関数によるDI
- 高階関数は様々な設計パターンの基礎になる

Flixでの対応B: 振る舞いをエフェクトで表す

mod CreditCard {
    // 文字列(識別子)を持つCreditCard型(Eq, ToStringは自動導出)
    pub enum CreditCard(String) with Eq, ToString
}
// 決済エフェクト
pub eff Payment {
    // クレジットカードと金額を受け取って何かする関数
    def charge(cc: CreditCard, amount: Float64): Unit
}

mod Cafe {
    use FpInFlix.Exercises.Introduction.SecondExample.{
  Coffee, CreditCard, Payment}
    // 請求関数を受け取ってコーヒーを返し、決済エフェクトを伴う関数
    pub def buyCoffee(cc: CreditCard): Coffee \ Payment =
        let coffee = Coffee.make();
        let Coffee.Coffee({price}) = coffee;
        Payment.charge(cc, price);  // 決済エフェクトの関数を利用
        coffee
}

pub def example(): Unit \ IO =
    let cup = run {
        Cafe.buyCoffee(CreditCard.CreditCard("A"))
    } with handler Payment {  // 決済エフェクトに対するハンドラー
        def charge(cc, amount, resume) = {
            println("charging ${amount} to ${cc}");
            resume()  // エフェクト発生地点から続く処理を再開
        }             //   (継続を呼び出す)
    };
    println("a cup of ${cup}")

// 利用例
flix> example()
charging 2.0 to CreditCard(A)   // 標準出力(Payment.charge)
a cup of Coffee({price = 2.0})  // 標準出力(exampleの最後)
()  // 戻り値

代数的エフェクトとエフェクトハンドラーによるDI
- エフェクトシステムの活用例

Flixでの対応C: 副作用を完全に隔離する

mod Charge {
    use FpInFlix.Exercises.Introduction.ThirdExample.
      CreditCard
    // creditCard, amountフィールドを持つレコードによるCharge型
    pub enum Charge({
        creditCard = CreditCard,
        amount = Float64
    })
    // 文字列表現(ToString型クラスの実装)
    instance ToString[Charge] {
        pub def toString(charge: Charge): String =
            let Charge({creditCard, amount}) = charge;
            "Charge({creditCard = ${creditCard}, amount =
              ${amount}})"
    }

「請求」をただのデータとして表す
- 解釈は利用側に委ねる

    // クレジットカードが同一の場合に限って2つの請求をまとめる純粋関数
    pub def combine(a: Charge, b: Charge): Result[String,
      Charge] =
        let Charge({creditCard=cardA, amount=amountA}) = a;
        let Charge({creditCard=cardB, amount=amountB}) = b;
        if (cardA == cardB) Ok(Charge({creditCard = cardA,
          amount = amountA + amountB}))
        else Err("Can't combine charges to different cards:
          cardA=${cardA}, cardB=${cardB}")

    // 請求リストをクレジットカードごとにまとめる純粋関数
    pub def coalesce(charges: List[Charge]): Result[String,
      List[Charge]] =
        charges
            |> List.groupBy(charge ->  // カードでグループ化
                let Charge({creditCard | _}) = charge;
                creditCard
            )
            |> Traversable.traverse(group ->  // combineで集約
                Foldable.foldLeftM(combine, Nel.head(group),
                  Nel.tail(group)))
}

    mod Cafe {
        use FpInFlix.Exercises.Introduction.ThirdExample.
          {Charge, Coffee, CreditCard}
        // カードを受け取ってコーヒーと請求を返す純粋関数
        pub def buyCoffee(cc: CreditCard): (Coffee, Charge) =
            let coffee = Coffee.make();
            let Coffee.Coffee({price}) = coffee;
            let charge = Charge.Charge({creditCard = cc,
              amount = price});
            (coffee, charge)

        // カードと個数を受け取ってコーヒーリストと請求を返す純粋関数
        pub def buyCoffees(cc: CreditCard, n: Int32):
          Result[String, (List[Coffee], Charge)] =
            let (coffees, charges) = buyCoffee(cc)
              |> List.repeat(n) |> List.unzip;  // n個繰り返し
            charges  // コーヒーリストと請求のタプルに集約
                |> Foldable.foldLeftM(Charge.combine,
                  Charge.Charge({creditCard = cc,
                    amount = 0.0}))
                |> Functor.map(charge -> (coffees, charge))
    }

// 利用例
flix> Cafe.buyCoffee(CreditCard.CreditCard("A"))
(Coffee({price = 2.0}), Charge({creditCard = CreditCard(A),
  amount = 2.0}))  // 戻り値

flix> Cafe.buyCoffees(CreditCard.CreditCard("A"), 3)
Ok((Coffee({price = 2.0}) :: Coffee({price = 2.0}) ::
  Coffee({price = 2.0}) :: Nil, Charge({creditCard =
  CreditCard(A), amount = 6.0})))  // 戻り値

データを変換する純粋関数
多様なデータを表す代数的データ型
- List, Nel (non-empty list), Result, etc.
関数のパターンを抽象化した型クラス
- Traversable, Foldable, Functor, etc.

第2章 Flixで始める関数型
プログラミング

キーワード

再帰関数(recursive function)
- 末尾再帰関数(tail-recursive function)
  - 末尾呼び出し最適化/除去(tail-call optimization/elimination, TCO/TCE)
高階関数(higher-order function)
多相関数(polymorphic function)
- ↔ 単相関数(monomorphic function)
- パラメータ多相(parametric polymorphism)
型駆動開発(type-driven development)

ループ(繰り返し処理)したい ⇒ 再帰関数

// (関数型言語のチュートリアルでお馴染みの)階乗関数
pub def factorial(n: Int32): Int32 =
    @Tailrec  // 末尾再帰であることを保証するアノテーション
    def go(x, acc) =  // 末尾再帰関数(ループ相当に最適化される)
        if (x <= 0) acc           // 基底部
        else go(x - 1, x * acc);  // 再帰部
    go(n, 1)

// 利用例
flix> List.map(factorial, List.range(0, 6))
1 :: 1 :: 2 :: 6 :: 24 :: 120 :: Nil

関数の振る舞いを切り替えたい ⇒ 高階関数

pub def formatAbs(x: Int32): String =
    "The absolute value of ${x} is ${abs(x)}."
pub def formatFactorial(n: Int32): String =
    "The factorial of ${n} is ${factorial(n)}."
// 整数を受け取って整数を返す関数をパラメータ化して高階関数に
pub def formatResult(name: String, n: Int32,
  f: Int32 -> Int32): String =
    "The ${name} of ${n} is ${f(n)}."

// 利用例
flix> formatResult("absolute value", -3, abs)
The absolute value of -3 is 3.

flix> formatResult("factorial", 5, factorial)
The factorial of 5 is 120.

任意の型で再利用したい ⇒ (パラメータ)多相関数

// 文字列のベクターをキーで線形探索してインデックスを返す関数
pub def findFirst(key: String, ss: Vector[String]): Int32 =
    @Tailrec
    def loop(n) =
        if (n >= Vector.size(ss)) -1
        else if (Vector.get(n, ss) == key) n
        else loop(n + 1);
    loop(0)

// 任意の要素型のベクターを述語関数で線形探索してインデックスを返す関数
pub def findFirst(p: a -> Bool, xs: Vector[a]): Int32 =
    @Tailrec
    def loop(n) =
        if (n >= Vector.size(xs)) -1
        else if (xs |> Vector.get(n) |> p) n
        else loop(n + 1);
    loop(0)

第3章関数型データ構造

キーワード

代数的データ型(algebraic data type, ADT)
- 直積型(product type)
- 直和型(sum type)
再帰データ型(recursive data type)
パターンマッチング(pattern matching)
- 網羅性(exhaustiveness)
純粋関数型データ型(purely functional data type), 永続データ型(persistent data type)
- 構造共有(structural sharing)

不変コレクションがほしい ⇒ 代数的データ型

// リスト(単方向連結リスト)
pub enum List[a] with Eq, ToString {  // 等価判定、文字列表現付き
    case Nil               // 空の場合(基底部)
    case Cons(a, List[a])  // 空でない場合(再帰部)
}
// ツリー(二分木)
pub enum Tree[a] with Eq, ToString {
    case Leaf(a)                   // 葉の場合(基底部)
    case Branch(Tree[a], Tree[a])  // 枝の場合(再帰部)
}

Flix標準ライブラリ:
- List, Nel, Vector, Chain, Nec
- Set, Map
- RedBlackTree

データを構造に沿って扱いたい ⇒ パターンマッチング

// リストの長さ
pub def length(l: List[a]): Int32 =
    match l {
        case Nil => 0
        case Cons(_, xs) => 1 + length(xs)
    }
// ツリーの要素数
pub def size(t: Tree[a]): Int32 =
    match t {
        case Leaf(_) => 1
        case Branch(left, right) => 1 + size(left) +
          size(right)
    }

// 利用例
flix> length(Cons("a", Cons("b", Cons("c", Nil))))
3

flix> size(Branch(Branch(Leaf("a"), Leaf("b")), Leaf("c")))
5

データの操作パターンを抽象化したい ⇒ 高階関数

// 右から畳み込む関数(再帰構造に沿った集約関数)
// ⚠️ 愚直な実装では末尾再帰/スタックセーフにならない(工夫が必要)
pub def foldRight(f: (a, b) -> b \ ef, acc: b, l: List[a]):
  b \ ef =
    match l {
        case Nil => acc
        case Cons(x, xs) => f(x, foldRight(f, acc, xs))
    }

// 利用例
flix> foldRight((-), 0, Cons(1, Cons(2, Cons(3, Nil))))
2
//   (1 - (2 - (3 - 0)))
// = (1 - (2 - 3))
// = (1 - (-1))
// = 2

// 左から畳み込む関数(末尾再帰の集約関数)
@Tailrec  // 末尾再帰
pub def foldLeft(f: (b, a) -> b \ ef, acc: b, l: List[a]):
  b \ ef =
    match l {
        case Nil => acc
        case Cons(x, xs) => foldLeft(f, f(acc, x), xs)
    }

// 利用例
flix> foldLeft((-), 0, Cons(1, Cons(2, Cons(3, Nil))))
-6
//   (((0 - 1) - 2) - 3)
// = (((-1) - 2) - 3)
// = ((-3) - 3)
// = -6

ℹ️ 結合法則を満たさない(+ 単位元を持たない)演算では foldRight と foldLeft の結果が異なる

// リストを返す関数を各要素に適用して得られるリストを平坦化して返す関数
pub def flatMap(f: a -> List[b] \ ef, l: List[a]):
  List[b] \ ef =
    // ℹ️ append: (List[a], List[a]) -> List[a] は定義済みとする
    foldRight((x, acc) -> append(f(x), acc), Nil, l)

// 利用例
flix> \\
> flatMap(
>     x -> Cons(x, Cons(x + 1, Nil)),
>     Cons(1, Cons(2, Cons(3, Nil)))
> )
> \\
Cons(1, Cons(2, Cons(2, Cons(3, Cons(3, Cons(4, Nil))))))

// 関数を各要素に適用して得られるリストを返す関数
pub def map(f: a -> b \ ef, l: List[a]): List[b] \ ef =
    flatMap(x -> Cons(f(x), Nil), l)

// 利用例
flix> \\
> map(
>     x -> x * x * x,
>     Cons(1, Cons(2, Cons(3, Nil)))
> )
> \\
Cons(1, Cons(8, Cons(27, Nil)))

// 述語を満たす要素のみのリストを返す関数
pub def filter(p: a -> Bool \ ef, l: List[a]): List[a] \ ef =
    flatMap(x -> if (p(x)) Cons(x, Nil) else Nil, l)

// 利用例
flix> \\
> filter(
>     // ℹ️ バッククォートで括ると中置記法に
>     x -> x `Int32.remainder` 2 != 0,
>     Cons(1, Cons(2, Cons(3, Nil)))
> )
> \\
Cons(1, Cons(3, Nil))

他にも多様な高階関数を定義できる
他のデータ構造についても同様に整備できる

第4章例外によらないエラー
ハンドリング

値の有無を区別したい ⇒ `Option`/`Maybe`

pub enum Option[a] with Eq, ToString {
    case None     // 値がない場合
    case Some(a)  // 値がある場合
}

例外は参照透過性を損なう副作用なので避ける
- 代わりに代数的データ型で表す
- ⇒ コレクションと同様に豊かな操作の対象に
Flix標準ライブラリ: Option

処理の成否を区別したい ⇒ `Either`/`Result`

pub enum Either[e, a] with Eq, ToString {
    case Left(e)   // 失敗の場合: エラー値を持つ
    case Right(a)  // 成功の場合: 成功値を持つ
}

Flix標準ライブラリ: Result

データの操作パターンを抽象化したい ⇒ 高階関数

pub def flatMap(f: a -> Option[b] \ ef, o: Option[a]):
  Option[b] \ ef =
    match o {
        case None => None
        case Some(x) => f(x)
    }

pub def flatMap(f: a -> Either[e, b] \ ef, et: Either[e, a]):
  Either[e, b] \ ef =
    match et {
        case Left(x) => Left(x)
        case Right(y) => f(y)
    }

pub def map(f: a -> b \ ef, o: Option[a]):
  Option[b] \ ef = ???

pub def filter(p: a -> Bool \ ef, o: Option[a]):
  Option[a] \ ef = ???

// 利用例
flix> map(x -> x / 2, Some(42))
Some(21)
flix> map(x -> x / 2, None)
None
flix> filter(x -> x `Int32.remainder` 2 != 0, Some(42))
None
flix> filter(x -> x `Int32.remainder` 2 != 0, None)
None

pub def map(f: a -> b \ ef, et: Either[e, a]):
  Either[e, b] \ ef = ???

// ⚠️ Eitherのfilterは無条件には定義できない
//    (述語を満たさない場合に採用するエラー値が定まらないため)

// 利用例
flix> map(x -> x / 2, (Right(42): Either[String, Int32]))
Right(21)
flix> map(x -> x / 2, Left("falsity"))
Left(falsity)

// 2引数関数を2個のOption値に適用してOptionを返す関数
pub def map2(f: (a, b) -> c \ ef, o1: Option[a],
  o2: Option[b]): Option[c] \ ef =
    flatMap(x -> map(y -> f(x, y), o2), o1)

// 利用例
flix> map2((+), Some(1), Some(2))
Some(3)
flix> map2((+), None, Some(2))
None
flix> map2((+), Some(1), None)
None
flix> map2(((+): (Int32, Int32) -> Int32), None, None)
None

Either についても同様に定義できる

// Optionを返す関数をリストの各要素に適用してリストのOptionを返す関数
pub def traverse(f: a -> Option[b] \ ef, l: List[a]):
  Option[List[b]] \ ef =
    List.foldRight(
        (x, acc) -> map2(List.cons, f(x), acc),
        Some(Nil),
        l
    )
// OptionのリストをリストのOptionにする関数
pub def sequence(l: List[Option[a]]): Option[List[a]] =
    traverse(identity, l)

// 利用例: ℹ️ 標準ライブラリのListを利用
flix>  traverse(x -> if (x `Int32.remainder` 2 != 0) Some(x)
  else None, List#{1, 2, 3})
None
flix>  traverse(x -> if (x `Int32.remainder` 2 != 0) Some(x)
  else None, List#{1, 3, 5})
Some(1 :: 3 :: 5 :: Nil)

Either についても同様に定義できる

エラー値を蓄積したい ⇒ `Validated`/`Validation`

pub enum Validated[e, a] with Eq, ToString {
    case Valid(a)         // 有効な場合: 有効値を持つ
    case Invalid(Nel[e])  // 無効な場合: エラー値の非空リストを持つ
}

Flix標準ライブラリ: Validation
- ℹ️ 性能特性から Nel (non-empty list)ではなく Nec (non-empty chain)が採用されている

第5章正格性と遅延性

キーワード

非正格性(nonstrictness)、非正格評価(nonstrict evaluation)
- ↔ 正格性(strictness)、正格評価(strict evaluation)/先行評価(eager evaluation)
- 遅延性(laziness)、遅延評価(lazy evaluation)
計算の記述(description)と評価(evaluation)の分離
余再帰関数(corecursive function)

必要になるまで実体化されないデータ構造がほしい
⇒ 代数的データ型 + 評価を制御する工夫

pub enum LazyList[a] {  // 言語によってはStreamと呼ばれる
    case Empty
    // ℹ️ Lazyは遅延評価される式を表すFlixの組み込み型
    case Cons(Lazy[a], Lazy[LazyList[a]])
}

pub def take(n: Int32, ll: LazyList[a]): LazyList[a] =
    match ll {
        case Cons(head, tail) if n > 1 =>
            // ℹ️ lazyは直後の式を遅延評価されるようにし、
            //    forceは直後の遅延評価式を実体化する
            Cons(head, lazy take(n - 1, force tail))
        case Cons(head, _) if n == 1 =>
            Cons(head, lazy Empty)
        case _ => Empty
    }

Flix標準ライブラリ: DelayList, DelayMap

// nからの整数列
pub def intsFrom(n: Int32): LazyList[Int32] =
    Cons(lazy n, lazy intsFrom(n + 1))
// フィボナッチ数列
pub def fibs(): LazyList[BigInt] =
    def go(current, next) =
        Cons(lazy current, lazy go(next, current + next));
    go(0ii, 1ii)

// 利用例
flix> LazyList.intsFrom(0) |> LazyList.map(x -> x * x)
  |> LazyList.take(5) |> LazyList.toList
0 :: 1 :: 4 :: 9 :: 16 :: Nil

flix> LazyList.fibs() |> LazyList.take(10) |> LazyList.toList
0 :: 1 :: 1 :: 2 :: 3 :: 5 :: 8 :: 13 :: 21 :: 34 :: Nil

第6章純粋関数型の状態

擬似乱数を生成したい ⇒ 状態を受け渡す純粋関数

// シード値を持つRng (random number generator, 乱数生成器)型
pub enum Rng(Int64) with Eq, ToString
// Rngを受け取って整数と新たなRngを返す関数
pub def nextInt(rng: Rng): (Int32, Rng) =
    let Rng(seed) = rng;
    // 線形合同法による乱数生成
    let newSeed = Int64.bitwiseAnd(
      seed * 25214903917i64 + 11i64, 281474976710655i64);
    let nextRng = Rng(newSeed);
    let n = Int64.rightShift(newSeed, 16)
        |> Int64.truncateToInt32;
    (n, nextRng)
// Rngを受け取って任意のランダム生成値と新たなRngを返す関数の型エイリアス
pub type alias Rand[a] = Rng -> (a, Rng)

Flix標準ライブラリ: Math.Random (エフェクト)

// 自然に定義できるユーティリティ関数の例
pub def unit(a: a): Rand[a] = ???
pub def map(f: a -> b, ra: Rand[a]): Rand[b] = ???
pub def map2(f: (a, b) -> c, ra: Rand[a], rb: Rand[b]):
  Rand[c] = ???
pub def flatMap(f: a -> Rand[b], ra: Rand[a]): Rand[b] = ???
// ランダム関数の例
pub def int(): Rand[Int32] = rng -> nextInt(rng)
pub def boolean(): Rand[Bool] =
    rng ->
        let (i, rng2) = nextInt(rng);
        (i `Int32.remainder` 2 == 0, rng2)

// 利用例
flix> map2((i, b) -> "int: ${i}, boolean: ${b}", int(),
  boolean())(Rng(42i64))
(int: 16159453, boolean: false, Rng(197491923327988))

flix> map2((i, b) -> "int: ${i}, boolean: ${b}", int(),
  boolean())(Rng(197491923327988i64))
(int: -340305902, boolean: true, Rng(149370390209998))

第2部関数型設計とコンビネータ
ライブラリ

純粋関数型の並列処理
プロパティベーステスト
パーサーコンビネータ

第7章純粋関数型の並列処理

並列/並行処理したい ⇒ 処理の記述と実行の分離

// マルチスレッド実行管理オブジェクトを受け取り非同期処理の結果を返す関数
enum Par[a](ExecutorService -> Future[a] \ IO)

pub def unit(a: a): Par[a] =
    Par(_es -> /* ExecutorServiceを利用せず直ちにaを返す */)
pub def fork(pa: Lazy[Par[a]]): Par[a] =
    Par(es -> /* ExecutorServiceを利用して非同期的にタスク実行 */)
pub def runPar(es: ExecutorService, pa: Par[a]):
  Future[a] \ IO =
    let Par(f) = pa;
    f(es)

Flix標準機能:
- par-yield 構文による並列処理
- (Go言語に似た)軽量スレッドと Channel によるCSPベースの並行処理

// 自然に定義できるユーティリティ関数の例
pub def flatMap(f: a -> Par[b], pa: Par[a]): Par[b] = ???
pub def map2(f: (a, b) -> c, pa: Par[a], pb: Par[b]):
  Par[c] = ???
pub def map(f: a -> b, pa: Par[a]): Par[b] = ???
// 並列処理を実行する関数の例
pub def runWithThreadPool(pa: Par[a]): a \ IO =
    let es = Executors.newFixedThreadPool(4);
    let v = runPar(es, pa).get();
    es.shutdown();
    v

// 利用例
flix> map2((a, b) -> a * b, unit(2), unit(3))
  |> runWithThreadPool
6

flix> map2((a, b) -> a ++ b, unit(List#{1, 2}),
  unit(List#{3, 4, 5})) |> runWithThreadPool
1 :: 2 :: 3 :: 4 :: 5 :: Nil

第8章プロパティベーステスト

プロパティベーステスト(PBT)ライブラリがほしい
⇒ 状態を受け渡す純粋関数 + 処理の記述と実行の分離

// PBTのジェネレータ: Rngを受け取ってaと新たなRngを返す関数
enum Gen[a](Rng -> (a, Rng))
pub def map(f: a -> b, ga: Gen[a]): Gen[b] = ???
pub def map2(f: (a, b) -> c, ga: Gen[a], gb: Gen[b]):
  Gen[c] = ???
pub def flatMap(f: a -> Gen[b], ga: Gen[a]): Gen[b] = ???
// サイズ指定付き(sized)のジェネレータ
mod SGen {
    pub enum SGen[a](Int32 -> Gen[a])
    pub def map(f: a -> b, sga: SGen[a]): SGen[b] = ???
    pub def flatMap(f: a -> SGen[b], sga: SGen[a]):
      SGen[b] = ???
}

// 具体的なジェネレータの例
pub def boolean(): Gen[Bool] = ???
pub def int(): Gen[Int32] = ???
pub def list(ga: Gen[a]): SGen[List[a]] = ???

// PBTのプロパティ(テスト対象の性質)
enum Prop((MaxSize, TestCases, Rng) -> Result.Result)

pub def forAll(ga: Gen[a], f: a -> Bool):
  Prop with ToString[a] = ???
pub def forAllSized(sga: Gen.SGen[a], f: a -> Bool):
  Prop with ToString[a] = ???
pub def &&(p1: Prop, p2: Prop): Prop = ???
pub def ||(p1: Prop, p2: Prop): Prop = ???
pub def runProp(p: Prop): Unit \ {IO, Time.Clock} = ???

// 利用例
      // 2回反転したリストは元のリストに一致する
flix> forAllSized(list(int()), xs ->
        xs |> List.reverse |> List.reverse == xs) \
      // リストの先頭要素は反転したリストの最終要素に一致する
>     && forAllSized(list(int()), xs ->
        List.head(xs) == xs |> List.reverse |> List.last) \
>     |> runProp
+ OK, passed 100 tests.
()

第9章パーサーコンビネータ

パーサー(構文解析器)がほしい ⇒ 純粋関数の合成

// パーサーを表すトレイト(a.k.a. 型クラス)
pub trait Parsers[parser: Type -> Type] {
    pub def string(s: String): parser[String]
    pub def char(c: Char): parser[Char]
    pub def regex(r: Regex): parser[String]
    pub def runParser(input: String, p: parser[a]):
      Result[ParseError, a]
    pub def map(f: a -> b, p: parser[a]): parser[b]
    pub def map2(f: (a, b) -> c, p1: parser[a],
      p2: Lazy[parser[b]]): parser[c]
    pub def flatMap(f: a -> parser[b], p: parser[a]):
      parser[b]
    ...
}

// トレイトの実装例
pub enum Parser[a](Location -> ParseResult[a])
instance Parsers[Parser] {
    pub def string(s: String): Parser[String] = ???
    ...
}

// パーサーの例: 非負整数の直後にその数だけaが繰り返す文字列
pub def nConsecutiveAs(): parser[Int32]
  with Parsers[parser] =
    Parsers.flatMap(n ->
        Parsers.map(_ ->
            n,  // n回の繰り返し + 文字aのパーサー
            Parsers.listOfN(n, Parsers.char('a'))
        ),  // 非負整数のパーサー
        nonNegativeInt()
    )

// 利用例
flix> (nConsecutiveAs(): Parser[Int32])
  |> Parsers.runParser("12aaaaaaaaaaaab")
Ok(12)

flix> (nConsecutiveAs(): Parser[Int32])
  |> Parsers.runParser("12aaabaaaaaaaab")
Err(1.6 'a'  // 1行6文字目で文字aのパースエラー

12aaabaaaaaaaa
     ^)

第3部関数型設計に共通する構造

モノイド
モナド
アプリカティブ/トラバーサブルファンクター

第10章モノイド

キーワード

代数的構造(algebraic structure)
モノイド(monoid)
- 結合法則/結合律(associativity, associative law)
- 単位元(identity element)、単位律(identity law)
- → モノイド則(monoid laws)
型クラス(type class)
- アドホック多相(ad-hoc polymorphism)
Foldable 型クラス
高カインド型(higher-kinded type, HKT)

型クラスによるアドホック多相
(型によって異なる振る舞いを与える多相)

// 型クラスの定義: 共通のインターフェース
pub trait HasSize[a] {
    pub def size(x: a): Int32
}

// 型クラスのインスタンス: 型ごとの実装
instance HasSize[String] {
    pub def size(x: String): Int32 = String.length(x)
}

instance HasSize[List[a]] {
    pub def size(x: List[a]): Int32 = List.size(x)
}

instance HasSize[Tree[a]] {  // 第3章で定義したTree (二分木)
    pub def size(x: Tree[a]): Int32 = Tree.size(x)
}

// 利用例
flix> HasSize.size("foo bar")
7

flix> HasSize.size(List#{'a', 'b', 'c'})
3

flix> HasSize.size(Branch(Leaf(1), Branch(Leaf(2), Leaf(3))))
5

cf. パラメータ多相
(型にかかわらず同じ振る舞いを可能とする多相)
Eq や ToString はFlix標準の型クラスの例

型クラス `Monoid` (モノイド):
結合法則を満たす + 単位元が存在する

// 定義
pub trait Monoid[a] {
    // 結合法則を満たす2項演算 a × a
    pub def combine(a1: a, a2: a): a  // 別名mappend
    // 単位元 e
    pub def empty(): a                // 別名mempty
}
// 派生的(定義から導出可能)な関数
pub def combineAll(xs: List[a]): a with Monoid[a] =
    List.foldLeft(Monoid.combine, Monoid.empty(), xs)
pub def foldMap(f: a -> b, xs: List[a]): b with Monoid[b] =
    List.foldLeft((b, a) -> Monoid.combine(b, f(a)),
      Monoid.empty(), xs)

Flix標準ライブラリ: Monoid

`Monoid` の具体例

// 文字列/リストの連結と空文字列/リスト
flix> Monoid.combineAll(List#{"alpha", "beta", "gamma"})
alphabetagamma
flix> Monoid.combineAll(List#{List#{2}, List#{3}, List#{5}})
2 :: 3 :: 5 :: Nil

// 数の和と0 ※ここでは、Int32をラップした型enum SumInt(Int32)
flix> Monoid.foldMap(SumInt, List#{2, 3, 4})
SumInt(9)
// 数の積と1 ※ここでは、Int32をラップした型enum ProductInt(Int32)
flix> Monoid.foldMap(ProductInt, List#{2, 3, 4})
ProductInt(24)

// 論理和とfalse ※ここでは、Boolをラップした型enum Or(Bool)
flix> Monoid.foldMap(Or, List#{true, false, true})
Or(true)
// 論理積とtrue ※ここでは、Boolをラップした型enum And(Bool)
flix> Monoid.foldMap(And, List#{true, false, true})
And(false)

型クラス `Foldable`: `fold` (畳み込み)できる

pub trait Foldable[f: Type -> Type] {  // fは高カインド型
    // 定義 ※いずれか1つの関数から他は導出可能
    pub def foldRight(f: (a, b) -> b, acc: b, fa: f[a]): b
    pub def foldLeft(f: (b, a) -> b, acc: b, fa: f[a]): b
    pub def foldMap(f: a -> b, fa: f[a]): b with Monoid[b]
    // 派生的(定義から導出可能)な関数
    pub def combineAll(fa: f[a]): a with Monoid[a]
    pub def toList(fa: f[a]): List[a]
}

// 利用例
flix> foldMap(constant(SumInt(1)), List#{'a', 'b', 'c'})
SumInt(3)
flix> foldLeft((_, x) -> "value: ${x}", "nothing", Some(42))
value: 42

Flix標準ライブラリ: Foldable

第11章モナド

キーワード

ファンクター/関手(functor)
- 恒等(identity)
- 合成(composition)
- → ファンクター則(functor laws)
モナド(monad): ファンクターの特殊化
- 結合法則/結合律(associativity, associative law)
- 左単位律(left identity law)
- 右単位律(right identity law)
- → モナド則(monad laws)

型クラス `Functor`: `map` (文脈を保って写像)できる

// 定義
pub trait Functor[f: Type -> Type] {
    pub def map(f: a -> b, fa: f[a]): f[b]  // 別名fmap
}

// インスタンスの例: これまでにmapを実装したすべての型を含む
instance Functor[List] {
    pub def map(f: a -> b, fa: List[a]): List[b] =
        List.map(f, fa)
}

// 利用例
flix> Functor.map(x -> x * x * x, List#{1, 2, 3})
1 :: 8 :: 27 :: Nil

Flix標準ライブラリ: Functor

型クラス `Monad`: `flatMap` (文脈を引き継いで連鎖)
できる

pub trait Monad[f: Type -> Type] with Functor[f] {
    // 定義 ※flatMapはcomposeもしくはmapとjoinからも導出可能
    pub def unit(a: a): f[a]  // 別名return
    pub def flatMap(f: a -> f[b], fa: f[a]): f[b]  // 別名>>=
    // 派生的(定義から導出可能)な関数
    pub def compose(f: a -> f[b], g: b -> f[c]): a -> f[c]
    pub def join(ffa: f[f[a]]): f[a]
    pub def map2(f: (a, b) -> c, fa: f[a], fb: f[b]): f[c]
    pub def sequence(fas: List[f[a]]): f[List[a]]
    pub def traverse(f: a -> f[b], xs: List[a]): f[List[b]]
    pub def replicateM(n: Int32, fa: f[a]): f[List[a]]
}

Flix標準ライブラリ: Monad

`Monad` の具体例

// インスタンスの例: これまでにflatMapを実装したすべての型を含む
pub mod State {  // 状態を関数で引き回す型(第6章の乱数生成器の一般化)
    pub enum State[s, a](s -> (a, s))
    pub def map(f: a -> b, sa: State[s, a]):
      State[s, b] = ???
    pub def unit(a: a): State[s, a] = ???
    pub def flatMap(f: a -> State[s, b], sa: State[s, a]):
      State[s, b] = ???
    pub def get(): State[s, s] = ???
    pub def set(s: s): State[s, Unit] = ???
    pub def modify(f: s -> s): State[s, Unit] = ???
    pub def runState(s0: s, sa: State[s, a]): (a, s) = ???
}

instance Functor[State[s]] { /* mapの実装 */ }
instance Monad[State[s]] {
    pub def unit(a: a): State[s, a] = State.unit(a)
    pub redef flatMap(f: a -> State[s, b], fa: State[s, a]):
      State[s, b] = State.flatMap(f, fa)
}

// Stateモナドを活用した関数の例
pub def zipWithIndex(xs: List[a]): List[(Int32, a)] =
    List.foldLeft((acc, x) ->
        Monad.flatMap(ys ->
            Monad.flatMap(n ->
                Functor.map(_ ->
                    (n, x) :: ys,
                    State.set(n + 1)  // 状態を更新
                ), State.get()        // 状態を取得
            ), acc
        ), Monad.unit(Nil), xs
    )  // => State[Int32, List[(Int32, a)]]
        |> State.runState(0)  // => (List[(Int32, a)], Int32)
        |> fst
        |> List.reverse

// 利用例
flix> zipWithIndex(List#{'a', 'b', 'c'})
(0, a) :: (1, b) :: (2, c) :: Nil

Flix標準の `Monad` に対する糖衣構文 `forM`

flix> \\
> Monad.flatMap(x ->
>     Functor.map(y ->
>         x * y,
>         Some(3)
>     ),
>     Some(2)
> )
> \\
Some(6)

flix> \\
> forM(
>     x <- Some(2);
>     y <- Some(3)
> ) yield x * y
> \\  // => Option[Int32]
Some(6)

cf. Scalaのfor式、Haskellのdo記法

// StateがFlix標準のMonadのインスタンスなら、以下のように書ける
pub def zipWithIndex(xs: List[a]): List[(Int32, a)] =
    List.foldLeft((acc, x) ->
        forM(
            ys <- acc;
            n <- State.get();
            _ <- State.set(n + 1)
        ) yield (n, x) :: ys,
        Applicative.point(Nil), xs
    )
        |> State.runState(0)
        |> fst
        |> List.reverse

第12章アプリカティブ/
トラバーサブルファンクター

キーワード

アプリカティブファンクター(applicative functor): ファンクターの特殊化、モナドの一般化
- 左単位律(left identity law)
- 右単位律(right identity law)
- 結合法則/結合律(associativity, associative law)
- 自然(naturality)
- → アプリカティブ則(applicative laws)
半群(semigroup): モノイドの一般化
トラバーサブルファンクター(traversable functor): ファンクターとFoldableの特殊化
モナドトランスフォーマー/モナド変換子(monad transformer)

型クラス `Applicative`: `apply` (多引数関数を適用)
できる

pub trait Applicative[f: Type -> Type] with Functor[f] {
    // 定義 ※applyはmap2からも導出可能
    pub def unit(a: a): f[a]  // 別名point, pure
    pub def apply(fab: f[a -> b], fa: f[a]): f[b]  // 別名ap
    // 派生的(定義から導出可能)な関数
    pub def map2(f: (a, b) -> c, fa: f[a], fb: f[b]): f[c]
    pub def sequence(fas: List[f[a]]): f[List[a]]
    pub def traverse(f: a -> f[b], xs: List[a]): f[List[b]]
    pub def replicateM(n: Int32, fa: f[a]): f[List[a]]
    pub def product(fa: f[a], fb: f[b]): f[(a, b)]
}

Monad まで特殊化せず様々な関数が定義できる
Flix標準ライブラリ: Applicative

`Applicative` の特殊化として再構成した `Monad`

pub trait Monad[f: Type -> Type] with Applicative[f] {
    // 定義 ※flatMapはcomposeもしくはmapとjoinからも導出可能
    pub def flatMap(f: a -> f[b], fa: f[a]): f[b]
    // 派生的(定義から導出可能)な関数
    pub def compose(f: a -> f[b], g: b -> f[c]): a -> f[c]
    pub def join(ffa: f[f[a]]): f[a]
}

特殊化の流れ:
Functor → Applicative → Monad

`Applicative` の具体例

// インスタンスの例: これまでにmap2を実装したすべての型を含む
pub enum ZipList[a](DelayList[a]) with Eq, ToString
instance Functor[ZipList] { /* mapの実装 */ }
instance Applicative[ZipList] {
    pub def unit(a: a): ZipList[a] =  // 無限に続くaの遅延リスト
        DelayList.repeat(a) |> fromDelayList
    pub redef map2(f: (a, b) -> c, fa: ZipList[a],
      fb: ZipList[b]): ZipList[c] =
        DelayList.zip(toDelayList(fa), toDelayList(fb))
            |> DelayList.map(t -> let (a, b) = t; f(a, b))
            |> fromDelayList
}

// 利用例
flix> Applicative.map2((a, b) -> (a, b),
>         fromDelayList(DelayList.startFrom(0)),
>         Applicative.unit('α')
>     ) |> toDelayList |> DelayList.take(5)
DelayList((0, α), (1, α), (2, α), (3, α), (4, α))

Flix標準の `Applicative` に対する糖衣構文 `forA`

flix> \\
> Applicative.map3(
>     (x, y, z) -> List#{x, y, z},
>     Validation.Failure(Nec.singleton("x not found")),
>     Validation.Success(3),
>     Validation.Failure(Nec.singleton("z not found"))
> )
> \\  // => Validation[String, List[Int32]]
Failure(Nec#{x not found, z not found})

flix> \\
> forA(
>     x <- Validation.Failure(Nec.singleton("x not found"));
>     y <- Validation.Success(3);
>     z <- Validation.Failure(Nec.singleton("z not found"))
> ) yield List#{x, y, z}
> \\
Failure(Nec#{x not found, z not found})

cf. HaskellのGHC拡張ApplicativeDo

型クラス `Semigroup`: 結合法則を満たす

pub trait Semigroup[a] {
    pub def combine(a1: a, a2: a): a
}
// Semigroupの特殊化として再構成したMonoid
pub trait Monoid[a] with Semigroup[a] {
    pub def empty(): a
}

// SemigroupだがMonoidではない例: 非空リスト
pub enum NonEmptyList[a](a, List[a]) with Eq, ToString
instance Semigroup[NonEmptyList[a]] {
    pub def combine(a1: NonEmptyList[a],
      a2: NonEmptyList[a]): NonEmptyList[a] =
        let NonEmptyList(head1, tail1) = a1;
        let NonEmptyList(head2, tail2) = a2;
        NonEmptyList(head1, tail1 ++ (head2 :: tail2))
}

Flix標準ライブラリ: SemiGroup

型クラス `Traversable`: `traverse` (走査)できる

// ℹ️ 書籍のScalaコードでは事情によりTraverseと命名されている
pub trait Traversable[f: Type -> Type]
  with Functor[f], Foldable[f] {
    // 定義 ※traverseはmapとsequenceからも導出可能
    pub def traverse(f: a -> g[b], fa: f[a]): g[f[b]]
      with Applicative[g]
    // 派生的(定義から導出可能)な関数
    pub def sequence(fga: f[g[a]]): g[f[a]]
      with Applicative[g]
    pub def mapAccum(f: (a, s) -> (b, s), s: s, fa: f[a]):
      (f[b], s)
}

Flix標準ライブラリ: Traversable

// mapAccumの実装例: 文脈を保って写像しつつStateモナドで状態を読み書き
pub def mapAccum(f: (a, s) -> (b, s), s: s, fa: f[a]):
  (f[b], s) =
    traverse(a ->
        Monad.flatMap(s1 ->
            let (b, s2) = f(a, s1);
            Functor.map(_ ->
                b,
                State.set(s2)
            ), State.get()
        ), fa
    ) |> State.runState(s)

// mapAccumで実装できる関数の例
pub def zipWithIndex(fa: f[a]): f[(a, Int32)]
  with Traversable[f] =
    fa
        |> Traversable.mapAccum((a, s) -> ((a, s), s + 1), 0)
        |> fst

`Traversable` の具体例

// インスタンスの例: これまでにtraverseを実装したすべての型を含む
instance Traversable[List] { ... }
instance Traversable[Option] { ... }
instance Traversable[Map[k]] with Order[k] { ... }

// 利用例
// リストの要素がインデックス付きに
flix> zipWithIndex(List#{'a', 'b', 'c'})
(a, 0) :: (b, 1) :: (c, 2) :: Nil

// OptionのSomeの値がインデックス付きに
flix> zipWithIndex(Some(42))
Some((42, 0))

// マップのエントリーの値がインデックス付きに
flix> zipWithIndex(Map#{'α' => 'a', 'β' => 'b', 'γ' => 'g'})
Map#{α => (a, 0), β => (b, 1), γ => (g, 2)}

第4部エフェクトとI/O

外部エフェクトとI/O
局所エフェクトと可変状態
ストリーム処理とインクリメンタルI/O

第13章外部エフェクトとI/O

キーワード

エフェクト/作用(effect)
- 副作用(side effect)
埋め込み/内部DSL (embedded/internal DSL)
IO モナド
Free モナド
- cf. 代数的エフェクト(algebraic effect)
トランポリン(trampolining)
tagless final

副作用が発生しうるコードの表現と解釈を分離したい
⇒ `Free` モナドによるDSL

// ℹ️ 書籍のScalaコードとは異なりHaskell標準ライブラリの定義を採用した
mod Free {
    pub enum Free[f: Type -> Type, a: Type] {
        case Pure(a)              // 基底部: 計算の結果
        case Free(f[Free[f, a]])  // 再帰部: 計算の継続
    }
    // fがFunctorならFree[f]はMonadになる
    instance Functor[Free[f]] with Functor[f] { ... }
    instance Applicative[Free[f]] with Functor[f] { ... }
    instance Monad[Free[f]] with Functor[f] { ... }
    // f[a]をFree[f, a]に持ち上げるユーティリティ
    pub def liftF(fa: f[a]): Free[f, a] with Functor[f] =
        Free(Functor.map(a -> Pure(a), fa))
}

ℹ️ 関数型のDSL実装手法は Free によるもの以外にもいろいろある

`Free` モナドによるDSLの例: コンソール入出力

pub enum Console[next] {
    case ReadLine(Option[String] -> next)  // 文字列の入力
    case PrintLine(String, next)           // 文字列の出力
}
// ConsoleをFunctorとすればFree[Console]は自動的にMonadに
instance Functor[Console] {
    pub def map(f: a -> b \ ef, fa: Console[a]):
      Console[b] \ ef =
        match fa {
            case ReadLine(g) => ReadLine(s ->
              // ⚠️ エフェクトを含む型と噛み合わずキャストが必要
              unchecked_cast(f(g(s)) as _ \ {}))
            case PrintLine(s, next) => PrintLine(s, f(next))
        }
}

コンソール入出力DSLの具体例

// DSLの構成要素
pub def readLn(): Free[Console, Option[String]] =
    Free.liftF(ReadLine(identity))
pub def printLn(line: String): Free[Console, Unit] =
    Free.liftF(PrintLine(line, ()))

// DSLでのコード表現の例
pub def exampleExpr(): Free[Console, Unit] =
    forM(  // Free[Console]はMonadなので糖衣構文forMも使える
        _ <- printLn("Enter a temperature in °F: ");
        d <- readLn() |> Functor.map(Option.flatMap(
          Float64.fromString));
        _ <- printLn("In °C: ${Option.map(fToC, d)}")
    ) yield ()
// 華氏から摂氏への換算関数
def fToC(f: Float64): Float64 =
    (f - 32.0) * 5.0 / 9.0

DSLに対するインタープリタA (副作用あり)

pub def interpretWithSysConsole(expr: Free[Console, a]):
  a \ Sys.Console =
    match expr {
        case Free.Pure(a) => a
        case Free.Free(ReadLine(next)) =>
            interpretWithSysConsole(next(Sys.Console.readln()))
        case Free.Free(PrintLine(line, next)) =>
            Sys.Console.println(line);
            interpretWithSysConsole(next)
    }

// 利用例
flix> interpretWithSysConsole(exampleExpr())
Enter a temperature in °F:
77  // ユーザー入力
In °C: Some(25.0)
()

DSLに対するインタープリタB (副作用なし)

pub def interpretWithBuffer(in: List[String],
  expr: Free[Console, a]): (a, List[String]) =
    def loop(x, inBuf, outBuf) =
        match x {
            case Free.Pure(a) => (a, List.reverse(outBuf))
            case Free.Free(ReadLine(next)) =>
                match inBuf {
                    case Nil => loop(next(None), Nil, outBuf)
                    case s :: ss =>
                      loop(next(Some(s)), ss, outBuf)
                }
            case Free.Free(PrintLine(line, next)) =>
                loop(next, inBuf, line :: outBuf)
        };
    loop(expr, in, Nil)

// 利用例
flix> interpretWithBuffer(List#{"77"}, exampleExpr())
((), Enter a temperature in °F:  :: In °C: Some(25.0) :: Nil)

Flixらしい別解: 代数的エフェクト

pub eff Console {
    def readLn(): Option[String]     // 文字列の入力
    def printLn(line: String): Unit  // 文字列の出力
}

// Consoleエフェクトを活用した関数の例
pub def exampleFn(): Unit \ Console =
    Console.printLn("Enter a temperature in °F: ");
    let d = Console.readLn() |> Option.flatMap(
      Float64.fromString);
    Console.printLn("In °C: ${Option.map(fToC, d)}")

Flix標準ライブラリ: Sys.Console

エフェクトハンドラーA (副作用あり)

pub def runWithSysConsole(f: Unit -> a \ ef):
  a \ ef - Console + Sys.Console =
    run {
        f()
    } with handler Console {
        def readLn(resume) =
            resume(Sys.Console.readln())
        def printLn(line, resume) = {
            Sys.Console.println(line);
            resume()
        }
    }

// 利用例
flix> run { exampleFn() } with runWithSysConsole
Enter a temperature in °F:
77  // ユーザー入力
In °C: Some(25.0)
()

エフェクトハンドラーB (副作用なし)

pub def runWithBuffer(in: List[String], f: Unit -> a \ ef):
  (a, List[String]) \ ef - Console =
    region rc {
        let inBuf = Ref.fresh(rc, in);
        let outBuf = Ref.fresh(rc, Nil);
        let a = run {
            f()
        } with handler Console {
            def readLn(resume) = ???
            def printLn(line, resume) = ???
        };
        (a, outBuf |> Ref.get |> List.reverse)
    }

// 利用例
flix> run { exampleFn() } with runWithBuffer(List#{"77"})
((), Enter a temperature in °F:  :: In °C: Some(25.0) :: Nil)

第14章局所エフェクトと可変状態

局所的に可変性がほしい ⇒ `ST` モナド

mod St {
    enum St[s, a](s -> (a, s))
    instance Functor[St[s]] { ... }
    instance Applicative[St[s]] { ... }
    instance Monad[St[s]] { .... }
    // ⚠️ st: forall s. Unit -> St[s, a] のようには書けない
    pub def runSt(st: Unit -> St[s, a]): a = ???
}

mod StRef {  // STモナドで局所化された可変参照
    // ⚠️ Flixでは可変参照を扱うと必ず r: Region が現れる
    struct StRef[_s: Type, a: Type, r: Region] {
        mut cell: a
    }
    // ⚠️ エフェクトを含む型と噛み合わずキャストを多用することになる
    pub def make(rc: Region[r], a: a): St[s, StRef[s, a, r]]
      \ r = ???
    pub def read(r: StRef[s, a, r]): St[s, a] \ r = ???
    pub def write(a: Lazy[a], r: StRef[s, a, r]): St[s, Unit]
      \ r = ???
}

mod StArray {  // STモナドで局所化された可変配列
    // ⚠️ Flixでは(可変)配列を扱うと必ず r: Region が現れる
    struct StArray[_s: Type, a: Type, r: Region] {
        mut value: Array[a, r]
    }
    // ⚠️ エフェクトを含む型と噛み合わずキャストを多用することになる
    pub def fromList(rc: Region[r], xs: List[a]):
      St[s, StArray[s, a, r]] \ r = ???
    pub def read(i: Int32, arr: StArray[s, a, r]):
      St[s, a] \ r = ???
    pub def write(i: Int32, a: a, arr: StArray[s, a, r]):
      St[s, Unit] \ r = ???
    ...
}

少なくともFlixには適さないアプローチ
- エフェクトシステムでのより良い方法がある

Flixらしい別解: リージョン(region)機構

mod MyRef {  // リージョンで局所化された可変参照
    struct MyRef[a: Type, r: Region] {
        mut cell: a
    }
    pub def make(rc: Region[r], cell: a): MyRef[a, r] \ r =
        new MyRef @ rc {cell = cell}
    pub def read(r: MyRef[a, r]): a \ r =
        r->cell
    pub def write(a: a, r: MyRef[a, r]): Unit \ r =
        r->cell = a
}

Flix標準ライブラリ: Ref

mod MyArray {  // リージョンで局所化された可変配列
    struct MyArray[a: Type, r: Region] {
        mut value: Array[a, r]
    }
    pub def fromList(rc: Region[r], xs: List[a]):
      MyArray[a, r] \ r =
        new MyArray @ rc {value = List.toArray(rc, xs)}
    pub def read(i: Int32, arr: MyArray[a, r]): a \ r =
        Array.get(i, arr->value)
    pub def write(i: Int32, a: a, arr: MyArray[a, r]):
      Unit \ r =
        Array.put(a, i, arr->value)
    ...
}

Flix標準ライブラリ: Array

// 局所的な可変性を活用した純粋関数の例
pub def quickSort(xs: List[Int32]): List[Int32] =
    if (List.isEmpty(xs)) xs
    else region rc {  // 可変性を閉じ込めるリージョンブロック
        let arr = MyArray.fromList(rc, xs);  // リストを配列化
        qs(rc, 0, MyArray.size(arr) - 1, arr);
        MyArray.freeze(arr)                  // 配列をリスト化
    }

def qs(rc: Region[r], l: Int32, r: Int32,
  arr: MyArray[Int32, r]): Unit \ r =  // リージョンエフェクト付き
    if (l < r)
        let pi = partition(rc, l, r, l + (r - l) / 2, arr);
        qs(rc, l, pi - 1, arr); qs(rc, pi + 1, r, arr)
    else ()
def partition(rc: Region[r], l: Int32, r: Int32,
  pivot: Int32, arr: MyArray[Int32, r]): Int32 \ r =
    let vp = MyArray.read(pivot, arr);
    MyArray.swap(pivot, r, arr);
    let j = MyRef.make(rc, l);
    Range.forEach(i ->
    // 以下に実装が続く……

第15章ストリーム処理と
インクリメンタルI/O

外部リソースに安全に宣言的にアクセスしたい
⇒ ストリーム変換

// ℹ️ 書籍ではScalaの(FS2類似の)ストリーム処理ライブラリを実装している
// ストリームの文字列を華氏温度と解釈して摂氏の数値に換算する
def conversion(iter: Iterator[String, ef, r]):
  Iterator[Float64, ef, r] =
    iter
        |> Iterator.map(String.trim)
        |> Iterator.filter(s -> not String.isEmpty(s))
        |> Iterator.filter(s ->
            not String.startsWith(prefix = "#", s)
        )
        |> Iterator.filterMap(Float64.fromString)
        |> Iterator.map(toCelsius)

def toCelsius(fahrenheit: Float64): Float64 =
    (5.0 / 9.0) * (fahrenheit - 32.0)

Flix標準ライブラリ: Iterator

// ファイルI/Oユーティリティ
// ℹ️ 現時点のFlix標準ライブラリには見当たらないためJava APIで自作

// インクリメンタルに行を読み出すイテレータ
def lineIterator(rc: Region[r], reader: BufferedReader):
  Iterator[String, r + IO, r] \ r =
    Iterator.iterate(rc, _ ->
        let line = reader.readLine();
        if (Object.isNull(line)) None
        else Some(line),
        ""
    )

// バッファリング機能付きの文字列ストリームリーダー/ライター
def bufferedReader(file: String): BufferedReader \ IO =
    Files.newBufferedReader(Paths.get(file))
def bufferedWriter(file: String): BufferedWriter \ IO =
    Files.newBufferedWriter(Paths.get(file))

// ローン(loan)パターンのリソース管理ユーティリティ
def withResource(
  acquire: Unit -> Closeable \ ef1,
  handle: Closeable -> a \ ef2
): Result[IOException, a] \ ef1 + ef2 + IO =
    region rc {
        let closable = Ref.fresh(rc, Option.empty());
        let result = try {
            Ref.put(Some(acquire()), closable);
            closable |> Ref.get |> Option.foldLeft((_, c) ->
                c |> handle |> Ok,
                Err(new IOException("unexpected"))
            )} catch { case e: IOException => Err(e) };
        closable |> Ref.get |> Option.forEach(c -> c.close());
        result }

def withReader(file: String, handle: BufferedReader -> a \ ef
  ): Result[IOException, a] \ ef + IO = ???
def withWriter(file: String, handle: BufferedWriter -> a \ ef
  ): Result[IOException, a] \ ef + IO = ???

// ストリーム変換を活用した関数の例
pub def convert(inputFile: String, outputFile: String):
  Result[String, Unit] \ IO =
    withReader(inputFile, reader ->
        withWriter(outputFile, writer ->
            region rc {
                lineIterator(rc, reader)
                    |> conversion
                    |> Iterator.forEach(a -> {
                                                writer.write("${a}");
                                                writer.newLine()
                    })
            }))
        |> Result.flatten
        |> inspectEx

// 利用例
flix> convert("input.txt", "output.txt")
> \\
Ok(())

$ bat input.txt output.txt  # 入出力ファイル例
─────┬──────────────────────────────────────────
     │ File: input.txt
─────┼──────────────────────────────────────────
   1 │ -12.3
   2 │ # 0
   3 │ abc
   4 │ 77
─────┴──────────────────────────────────────────
─────┬──────────────────────────────────────────
     │ File: output.txt
─────┼──────────────────────────────────────────
   1 │ -24.61111111111111
   2 │ 25.0
─────┴──────────────────────────────────────────

おわりに: 関数型プログラミングの抽象化過程

書籍 FP in Scala から見えてくる、また、Flix言語でも推奨されている段階的な習熟/活用のステップ:

再帰、代数的データ型とパターンマッチに親しむ
よくある操作パターンを高階関数として定義/利用できるようになる
様々な型で繰り返し現れる(高階)関数を型クラスとして抽象化できるようになる
エフェクト/作用を上手く扱えるようになる

🐬< FP in Scala もFlixも(純粋)関数型プログラミングの深淵への入口として非常にオススメ😈

	slides:
	charset: utf-8
	theme: night
	highlight_theme: monokai-sublime
	separator_vertical: ^\s----\s$
	revealjs:
	transition: convex
	plugins:
	- extra_css:
	- https://cdnjs.cloudflare.com/ajax/libs/meyer-reset/2.0/reset.min.css

	#!/usr/bin/env bash

	# pip install mkslides

	open http://localhost:8000 \
	&& mkslides serve *.md

lagenorhynque/mkslides.yml

速習 FP in Scala with Flix

Flix言語で親しむ純粋関数型のコード設計

lagénorhynque🐬カマイルカ

1. きっかけ

関数型まつり2025での🐬の発表

書籍 Functional Programming in Scala (FP in Scala)

Flixとの出会い

エフェクトシステムを備えた関数型言語Flix

[参考] Shibuya.lisp lispmeetup #118での🐬の発表

「"Simple Made Easy" Made Easier 」の要約

2. 書籍 FP in Scala とは

FP in Scala, a.k.a. The Red Book 📕

3. Flix言語の基本

Flixとは

ℹ️ 他の関数型言語経験者向けの補足

コードの書き方(0): 事前準備

コードの書き方(1): モジュールとそのトップレベル関数

コードの書き方(2): トップレベル関数による定数

コードの書き方(3): モジュールの利用

コードの書き方(4): ローカル束縛

コードの書き方(5): 無名関数(ラムダ式)

4. (純粋)関数型のコード設計

第1部 関数型プログラミング入門

第1章 関数型プログラミングとは

キーワード

カフェでコーヒーを注文する過程を表す素朴なコード

OOPで典型的な改善策: インターフェースを導入してDI

Flixでの対応A: (非OOPLなので)振る舞いを関数で渡す

Flixでの対応B: 振る舞いをエフェクトで表す

Flixでの対応C: 副作用を完全に隔離する

第2章 Flixで始める関数型プログラミング

キーワード

ループ(繰り返し処理)したい ⇒ 再帰関数

関数の振る舞いを切り替えたい ⇒ 高階関数

任意の型で再利用したい ⇒ (パラメータ)多相関数

第3章 関数型データ構造

キーワード

不変コレクションがほしい ⇒ 代数的データ型

データを構造に沿って扱いたい ⇒ パターンマッチング

データの操作パターンを抽象化したい ⇒ 高階関数

第4章 例外によらないエラーハンドリング

値の有無を区別したい ⇒ Option/Maybe

処理の成否を区別したい ⇒ Either/Result

データの操作パターンを抽象化したい ⇒ 高階関数

エラー値を蓄積したい ⇒ Validated/Validation

第5章 正格性と遅延性

キーワード

必要になるまで実体化されないデータ構造がほしい ⇒ 代数的データ型 + 評価を制御する工夫

第6章 純粋関数型の状態

擬似乱数を生成したい ⇒ 状態を受け渡す純粋関数

第2部 関数型設計とコンビネータライブラリ

第7章 純粋関数型の並列処理

並列/並行処理したい ⇒ 処理の記述と実行の分離

第8章 プロパティベーステスト

プロパティベーステスト(PBT)ライブラリがほしい ⇒ 状態を受け渡す純粋関数 + 処理の記述と実行の分離

第9章 パーサーコンビネータ

パーサー(構文解析器)がほしい ⇒ 純粋関数の合成

第3部 関数型設計に共通する構造

第10章 モノイド

キーワード

型クラスによるアドホック多相(型によって異なる振る舞いを与える多相)

型クラス Monoid (モノイド): 結合法則を満たす + 単位元が存在する

Monoid の具体例

型クラス Foldable: fold (畳み込み)できる

第11章 モナド

キーワード

型クラス Functor: map (文脈を保って写像)できる

型クラス Monad: flatMap (文脈を引き継いで連鎖)できる

Monad の具体例

Flix標準の Monad に対する糖衣構文 forM

第12章 アプリカティブ/トラバーサブルファンクター

キーワード

型クラス Applicative: apply (多引数関数を適用)できる

Applicative の特殊化として再構成した Monad

Applicative の具体例

Flix標準の Applicative に対する糖衣構文 forA

型クラス Semigroup: 結合法則を満たす

型クラス Traversable: traverse (走査)できる

Traversable の具体例

書籍 Functional Programming in Scala
(FP in Scala)

第1部関数型プログラミング入門

第1章関数型プログラミングとは

第2章 Flixで始める関数型
プログラミング

第3章関数型データ構造

第4章例外によらないエラー
ハンドリング

値の有無を区別したい ⇒ `Option`/`Maybe`

処理の成否を区別したい ⇒ `Either`/`Result`

エラー値を蓄積したい ⇒ `Validated`/`Validation`

第5章正格性と遅延性

必要になるまで実体化されないデータ構造がほしい
⇒ 代数的データ型 + 評価を制御する工夫

第6章純粋関数型の状態

第2部関数型設計とコンビネータ
ライブラリ

第7章純粋関数型の並列処理

第8章プロパティベーステスト

プロパティベーステスト(PBT)ライブラリがほしい
⇒ 状態を受け渡す純粋関数 + 処理の記述と実行の分離

第9章パーサーコンビネータ

第3部関数型設計に共通する構造

第10章モノイド

型クラスによるアドホック多相
(型によって異なる振る舞いを与える多相)

型クラス `Monoid` (モノイド):
結合法則を満たす + 単位元が存在する

`Monoid` の具体例

型クラス `Foldable`: `fold` (畳み込み)できる

第11章モナド

型クラス `Functor`: `map` (文脈を保って写像)できる

型クラス `Monad`: `flatMap` (文脈を引き継いで連鎖)
できる

`Monad` の具体例

Flix標準の `Monad` に対する糖衣構文 `forM`

第12章アプリカティブ/
トラバーサブルファンクター

型クラス `Applicative`: `apply` (多引数関数を適用)
できる

`Applicative` の特殊化として再構成した `Monad`

`Applicative` の具体例

Flix標準の `Applicative` に対する糖衣構文 `forA`

型クラス `Semigroup`: 結合法則を満たす

型クラス `Traversable`: `traverse` (走査)できる

`Traversable` の具体例

第4部エフェクトとI/O

第13章外部エフェクトとI/O

副作用が発生しうるコードの表現と解釈を分離したい
⇒ `Free` モナドによるDSL

`Free` モナドによるDSLの例: コンソール入出力

第14章局所エフェクトと可変状態

局所的に可変性がほしい ⇒ `ST` モナド

第15章ストリーム処理と
インクリメンタルI/O

外部リソースに安全に宣言的にアクセスしたい
⇒ ストリーム変換