HN 日本語サマリー

← 一覧へ戻る
プログラミング

hicaにおける関数型プログラミング

Functional Programming in hica (hica.dev)

38 pointsby cladamski799 コメント

要約

hicaは、状態を変更する命令のシーケンスを記述するのではなく、関数を合成してプログラムを構築する関数型プログラミング(FP)スタイルを中心に設計されています。hicaでは、データはデフォルトで不変(immutable)であり、ほとんどすべてが式(expression)として扱われ、関数は第一級の値として扱われます。これにより、コードの推論やテストが容易になり、より堅牢なプログラム開発が可能になります。

全文翻訳

hicaにおける関数型プログラミング

関数型プログラミング(FP)とは、状態を変更する命令列を書くのではなく、関数の合成によってプログラムを構築するスタイルです。hicaは、不変データ、あらゆる場所での式、そして第一級の値としての関数を中心に設計されています。

すべての例は実行可能です。FPの経験は必要ありません。関数を書き、マッチ式を読めれば十分です。

式、ステートメントではない

ほとんどの言語では、ステートメントは何かを行い、式は値を生成します。hicaでは、if、match、ブロックを含む、ほぼすべてのものが式です。これは、値が期待される場所ならどこでもそれらを使用できることを意味します。

fun sign(x) => if x < 0 { "negative" } else { "non-negative" }

{}ブロックの本体は、その最後の式の値です。returnキーワードはありません。

fun clamp(x, lo, hi) {
  if x < lo { lo }
  else if x > hi { hi }
  else { x }
}

この単一のルールが、FPのほとんどを理解する助けとなります。すべてに値がある場合、すべてを合成できます。

デフォルトで不変

FPは、共有されるミュータブルな状態を避けます。作成後に値を変更できない場合、関数は推論やテストが容易になります。

hicaでは、不変バインディングにletを使用します。

let name = "Alicia"
let scores = [85, 92, 78]

scoresをインプレースで変更することはありません。代わりに、新しいリストを作成します。

let updated = scores + [95]          // 新しいリスト: [85, 92, 78, 95]
let doubled = map(scores, (x) => x * 2)

ミューテーション(カウンター、ループ変数)が必要な場合は、varを使用します。これはローカルスコープであり、関数から漏れ出すことはありません。

var total = 0
for x in scores {
  total = total + x
}

varはオプトインです。それ以外はすべて不変のままです。

純粋関数

純粋関数は、同じ入力に対して常に同じ出力を返し、副作用(印刷、ファイルI/O、ミュータブルな状態など)を持ちません。純粋関数はテストや合成が容易です。

fun add(a, b) => a + b
fun square(x) => x * x
fun to_celsius(f: float) => (f - 32.0) * 5.0 / 9.0

hicaでは、関数はデフォルトで純粋です。型システム(Kokaから継承)はI/Oのようなエフェクトを追跡するため、関数が副作用を持つ場合、それはその型で可視化されます。

純粋関数は、構築に使用するものです。それ以外は合成です。

第一級の値としての関数

FPでは、関数は整数や文字列のような値です。変数に格納したり、他の関数に渡したり、関数から返したりできます。

fun apply(f, x: int) => f(x)

fun main() {
  let double = (x) => x * 2
  let greet  = (name) => "Hello, " + name

  println(apply(double, 5))  // 10
  println(greet("Olle"))     // Hello, Olle
}

別の関数を受け取ったり返したりする関数は高階関数と呼ばれます。上記のapplyはその一つです。

クロージャ

クロージャとは、周囲のスコープから変数をキャプチャする関数です。

fun make_adder(n) => (x) => x + n

fun main() {
  let add5  = make_adder(5)
  let add10 = make_adder(10)

  println(add5(3))   // 8
  println(add10(3))  // 13
}

make_adderは呼び出されるたびに新しい関数を返します。その関数はnをクロージャします。つまり、make_adderが返された後でも、作成されたときのnの値を記憶しています。

このパターンにより、オンデマンドで特殊化された関数を作成できます。

fun make_multiplier(factor) => (x) => x * factor

fun main() {
  let triple = make_multiplier(3)
  let nums = [1..5]
  println(map(nums, triple))   // [3, 6, 9, 12, 15]
}

map、filter、fold

これらの3つの関数は、リストを扱う上で必要なことのほとんどをカバーします。

map: 各要素を変換
fun main() {
  let nums = [1..5]
  println(map(nums, (x) => x * x))   // [1, 4, 9, 16, 25]
  println(map(nums, show))            // ["1", "2", "3", "4", "5"]
}

mapはリストと関数を受け取ります。関数を各要素に適用し、同じ長さの新しいリストを返します。

filter: 条件に合う要素を保持
fun main() {
  let nums = [1..8]
  let evens = filter(nums, (x) => x % 2 == 0)
  println(evens)   // [2, 4, 6, 8]
}

filterは、述語がtrueを返す要素のみを保持します。

fold: 単一の値に集約
fun main() {
  let nums = [1..5]
  let total = fold(nums, 0, (acc, x) => acc + x)
  println(total)   // 15

  let product = fold(nums, 1, (acc, x) => acc * x)
  println(product)  // 120
}

foldは結果を集約します。初期値から開始し、各要素に順番に関数を適用します。accは実行中の結果を保持し、xは現在の要素です。

foldを使用して多くのリスト操作を実装できます。

fun my_length(xs) => fold(xs, 0, (acc, _) => acc + 1)
fun my_max(xs)    => fold(xs, 0, (acc, x) => if x > acc { x } else { acc })
fun my_reverse(xs) => fold(xs, [], (acc, x) => [x] + acc)

flattenとflat_map

mapは各要素を変換します。しかし、mapに渡す関数自体がリストを返す場合があります。結果はリストのリストになり、通常は望ましくありません。

fun main() {
  let sentences = ["hello world", "foo bar", "one two three"]
  let split_words = map(sentences, (s) => split(s, " "))
  println(split_words)
  // [["hello", "world"], ["foo", "bar"], ["one", "two", "three"]]
}

すべての単語のフラットなリストを求めていました。2つの関数がこれを解決します。

concat: ネストを1レベル解消
fun main() {
  let nested = [[1, 2], [3, 4], [5, 6]]
  println(concat(nested))   // [1, 2, 3, 4, 5, 6]
}

concatはリストのリストを受け取り、1レベルを解消します。(他の言語ではflattenと呼ばれます。)

flat_map: mapとflattenを1ステップで

flat_mapは関数を各要素に適用し、結果として得られたすべてのリストを結合します。これはmapの後にconcatを実行するのと同等ですが、1ステップで記述されます。

fun main() {
  let sentences = ["hello world", "foo bar", "one two three"]
  let all_words = flat_map(sentences, (s) => split(s, " "))
  println(all_words)
  // ["hello", "world", "foo", "bar", "one", "two", "three"]
}

mapする関数がリストを返す場合はいつでもflat_mapを使用します。

パイプラインでの要素の展開

flat_mapはパイプラインに自然に適合します。単一の要素が複数の要素になるステップで使用します。

fun expand(n) => [n, n * 10]   // 各要素が2つに展開される

fun main() {
  let result = [1, 2, 3]
    |> flat_map(expand)           // [1, 10, 2, 20, 3, 30]
    |> filter((x) => x > 5)      // [10, 20, 30]
  println(result)
}

flat_mapがない場合、[[1, 10], [2, 20], [3, 30]]となり、filterは数値ではなくリストに対して操作することになります。

Maybeでも同じ考え方が適用される

パターン:ラップされた値を生成する関数を適用し、その後ラッパーをフラット化するという考え方は、Maybeでも現れます。map_maybeはMaybe内の値を変換します。しかし、関数自体がMaybeを返す場合、Maybe<Maybe<x>>という結果になります。and_thenは extra layer を自動的にフラット化することで、二重ラップを防ぎます。

fun parse_pos(s: string) : maybe<int> {
  let n = parse_int(s)?
  if n > 0 { Some(n) } else { None }
}

fun main() {
  // and_then は Maybe を返すステップを連鎖させる — ネストなし、ネストされたマッチなし
  let result = Some("42")
    |> and_then((s) => parse_int(s))     // 文字列をパース → maybe<int>
    |> and_then((n) => parse_pos(show(n)))
    |> map_maybe((n) => n * 2)
  println(result)   // Some(84)

  let bad = Some("-5")
    |> and_then((s) => parse_int(s))
    |> and_then((n) => parse_pos(show(n)))
    |> map_maybe((n) => n * 2)
  println(bad)   // None
}

リストのflat_mapとMaybeのand_thenは、名前は違えど同じ考え方です。関数型プログラマーはこれをbindと呼びます。このパターンを理解すること、「ラップされた値に対して、それ自体がラップされた値を返す関数でマップし、二重ラップしない」ということは、型が何であれ、持ち帰るべきことです。

|>による合成

パイプ演算子|>は、ある式の結果を次の関数に渡します。左から右へ読み取られ、操作の順序と一致します。

fun main() {
  let result = [1..10]
    |> filter((x) => x % 2 == 0)     // [2, 4, 6, 8, 10]
    |> map((x) => x * x)             // [4, 16, 36, 64, 100]
    |> fold(0, (acc, x) => acc + x)  // 220

  println(result)
}

|>がない場合、次のように書きます。

let result = fold(map(filter([1..10], (x) => x % 2 == 0), (x) => x * x), 0, (acc, x) => acc + x)

|>を使用すると、各ステップは独自の行に配置され、変換が実行される順序で読み取ることができます。それがポイントです。各ステップは1つの関数であり、それらが連鎖します。

ポイントフリースタイル

ラムダが単に引数を関数に直接渡すだけの場合、ラムダを完全に省略できます。

fun is_even(x) => x % 2 == 0
fun square(x)  => x * x

fun main() {
  let result = [1..5]
    |> filter(is_even)   // filter(nums, (x) => is_even(x)) と同じ
    |> map(square)
  println(result)   // [4, 16]
}

このスタイル(ラムダでラップするのではなく、関数に名前を付けること)はポイントフリーと呼ばれます。名前がラムダよりも多くを語る場合にそれを使用してください。

遅延ストリーム

mapやfilterのような標準的なリスト変換を連鎖させると、パイプラインの各ステップは完全に新しいリストを割り当てます。

[1..20] |> filter(is_even) |> map(square) |> take(5)

このパイプラインでは、filterは10個の要素を持つ新しいリストを割り当て、mapはさらに10個の要素を持つリストを割り当て、最後にtakeが5個の要素を持つリストを割り当てます。

遅延ストリーム(std/streamで提供)は、すべての操作を単一のトラバーサルに結合することで、これらの途中リストの割り当て問題を解決します。要素はパイプラインを1つずつ流れます。中間リストは構築されず、終端条件が満たされるとすぐに処理が停止します。

遅延ストリームを使用するには、std/streamをインポートし、リストをstream関数でラップします。

import "std/stream"

fun main() {
  // 1. ゼロアロケーションパイプライン
  let result = stream([1..20])
    .filter((x) => x % 2 == 0)
    .map((x) => x * x)
    .take(5)
    .collect() // ストリームを標準リストに具体化

  println(result) // [4, 16, 36, 64, 100]
}
早期終了

標準リストでは、[1..1000]をフィルタリングすると、述語関数が1000回実行されます。ストリームでは、ジェネレータはパイプラインの要件(take(3)など)が満たされるとすぐに停止し、プロセッササイクルを節約します。

import "std/stream"

fun main() {
  let first_multiples = stream([1..1000])
    .filter((x) => x % 7 == 0)
    .take(3)
    .collect()

  println(first_multiples) // [7, 14, 21]
}
ストリーム操作と終端処理

ストリームは、さまざまな変換と終端集約をサポートします。

  • 変換(遅延): map、filter、take、zip、enumerateなど。要素を評価せずに新しいストリームをすぐに返します。
  • 終端処理(即時): collect(リストを返す)、fold(単一の値に集約する)、foreach(副作用を実行する)。これらはストリームの評価を強制します。
import "std/stream"

fun main() {
  // 中間リストの割り当てなしでストリームを直接foldする
  let sum_of_squares = stream([1..1000])
    .filter((x) => x % 2 == 0)
    .map((x) => x * x)
    .take(10)
    .fold(0, (acc, x) => acc + x)

  println(sum_of_squares) // 1540

  // enumerate() で要素を遅延的にインデックス付けする
  let indexed = stream(["a", "b", "c"])
    .enumerate()
    .collect()

  println(indexed) // [(0, "a"), (1, "b"), (2, "c")]
}

パイプラインのトランスデューサー

遅延ストリームはゼロアロケーション処理に優れていますが、データソースにすぐにバインドする必要があります。ストリーム変換パイプラインを単独で構築し、変数に保存して、異なるデータソース間で再利用することはできません。

トランスデューサー(std/xformで提供)がこれを解決します。これらは変換ロジックを基盤となるデータ構造から分離し、再利用可能でソースに依存しないクエリパイプラインを定義できるようにします!

トランスデューサーの定義と合成

トランスデューサーは、xf_で始まるトランスデューサーコンストラクタを使用して構築されます。

  • 開始コンストラクタ: xf_filter(pred)、xf_map_start(f)、xf_take_start(n)など。
  • 連鎖コンストラクタ: xf_map(xform, f)、xf_filter_with(xform, pred)、xf_take(xform, n)、xf_take_while(xform, pred)、xf_drop_while(xform, pred)、xf_flat_map(xform, f)。

hicaはa |> f(b)をf(a, b)にデシュガーするため、トランスデューサーはパイプ演算子|>を使用して左から右へ完璧に合成できます。

import "std/stream"
import "std/xform"

// 再利用可能なパイプラインを定義(まだデータソースはバインドされていない!)
let double_evens =
  xf_filter((x) => x % 2 == 0)
  |> xf_map((x) => x * 2)
  |> xf_take(3)
transduceによるトランスデューサーの適用

リストにトランスデューサーを適用するには、transduce(list, xform)関数を使用します。これはリストをストリームに変換し、トランスデューサーパイプラインを通過させ、結果を単一のゼロアロケーションパスで収集します。

import "std/stream"
import "std/xform"

fun main() {
  let pipeline =
    xf_filter((x) => x % 2 == 0)
    |> xf_map((x) => x * 2)
    |> xf_take(5)

  let numbers1 = [1..10]
  let numbers2 = [11..20]

  // 同じパイプラインを異なるソースに適用!
  let r1 = numbers1 |> transduce(pipeline)
  let r2 = numbers2 |> transduce(pipeline)

  println(r1) // [4, 8, 12, 16]
  println(r2) // [24, 28, 32, 36, 40]
}

トランスデューサーをマッピング関数で開始したい場合は、xf_map_startを使用します。

import "std/stream"
import "std/xform"

fun main() {
  let double_only =
    xf_map_start((x) => x * 2)
    |> xf_filter_with((x) => x > 10)

  let r = [1..10] |> transduce(double_only)
  println(r) // [12, 14, 16, 18, 20]
}

再帰

FPは、命令型コードがループを使用する場所で再帰を使用します。再帰関数は、ベースケースに到達するまで、より小さい入力で自身を呼び出します。

fun sum(xs) => match xs {
  []          => 0,
  [x, ..rest] => x + sum(rest)
}

fun main() {
  println(sum([1..5]))   // 15
}

[x, ..rest]パターンは、リストを最初の要素と残りの部分に分割します。これは再帰と自然にペアになります。

fun contains(xs, target) => match xs {
  []          => false,
  [x, ..rest] => x == target || contains(rest, target)
}

fun map_r(xs, f) => match xs {
  []          => [],
  [x, ..rest] => [f(x)] + map_r(rest, f)
}

相互再帰(互いに呼び出す2つの関数)の場合、前方宣言は不要です。

fun is_even(n) => if n == 0 { true } else { is_odd(n - 1) }
fun is_odd(n)  => if n == 0 { false } else { is_even(n - 1) }

実際には、明示的な再帰よりもmap/filter/foldをはるかに多く使用しますが、再帰はツリー構造のデータに適したツールであり、それを知っていると他人のコードを読むのに役立ちます。

代数的データ型

関数型プログラミングでは、さまざまな形状を持つデータをモデル化するために代数的データ型(ADT)を使用します。hicaには2種類あります。

Structs: 積型

構造体はフィールドをバンドルします。

struct Point { x: int, y: int }
struct Person { name: string, age: int }

fun greet(p: Person) => "Hi, {p.name}!"

fun distance(a: Point, b: Point) : int {
  let dx = a.x - b.x
  let dy = a.y - b.y
  dx * dx + dy * dy
}

構造体は不変です。フィールドを「更新」するには、新しい構造体を作成します。

struct Player { name: string, score: int }

fun add_score(p: Player, points: int) : Player =>
  Player { name: p.name, score: p.score + points }
Enums: 和型

列挙型は、それぞれ独自のデータを持つことができる、異なるバリアント間の選択を表します。

type Shape {
  Circle(radius: float),
  Rect(width: float, height: float),
  Point
}

fun area(s: Shape) : float => match s {
  Circle(r)  => 3.14159 * r * r,
  Rect(w, h) => w * h,
  Point      => 0.0
}

コンパイラは網羅性をチェックします。バリアントを忘れると警告が表示されます。これにより、新しいバリアントの追加が安全になります。コンパイラは更新が必要なすべての場所を教えてくれます。

列挙型は再帰的になりうるため、ツリー構造のデータをモデル化する方法です。

type Tree {
  Leaf,
  Node(value: int, left: Tree, right: Tree)
}

fun tree_sum(t: Tree) : int => match t {
  Leaf           => 0,
  Node(v, l, r)  => v + tree_sum(l) + tree_sum(r)
}

MaybeとResult

2つの組み込み型が例外なしで失敗を処理します。

Maybe: 存在しない可能性のある値
fun find_first(xs, pred) => match xs {
  []          => None,
  [x, ..rest] => if pred(x) { Some(x) } else { find_first(rest, pred) }
}

fun main() {
  let nums = [1, 3, 5, 4, 7]
  match find_first(nums, (x) => x % 2 == 0) {
    Some(n) => println("First even: {n}"),
    None    => println("No evens found")
  }
}

Some(x)は値をラップし、Noneは不在を示します。コンパイラは両方のケースを処理するように強制します。

コンビネータによる連鎖

すべてのステップに対してネストされたmatchはすぐに扱いにくくなります。コンビネータはチェーンをフラットに保ちます。また、微妙な点があります。適用したい関数自体がMaybeを返す場合、map_maybeを使用するとMaybe<Maybe<x>>が得られます。and_thenは、リストのflat_mapと同じ仕事をして、 extra layer をフラット化することで二重ラップを防ぎます。

fun main() {
  // map_maybe は内部の値を変換し、None はそのままにする
  let x = Some(21) |> map_maybe((n) => n * 2)
  println(x)   // Some(42)

  // and_then はそれ自体が Maybe を返す関数を連鎖させる
  let y = Some("42")
    |> and_then((s) => parse_int(s))
    |> map_maybe((n) => n + 1)
  println(y)   // Some(43)

  // 最初の None でショートサーキットする
  let z = Some("nope")
    |> and_then((s) => parse_int(s))
    |> map_maybe((n) => n + 1)
  println(z)   // None
}
Result: 成功または特定のエラー

Resultは失敗時にエラーメッセージを運びます。

fun safe_divide(a, b) =
  if b == 0 { Err("division by zero") }
  else { Ok(a / b) }

fun validate_positive(n) =
  if n > 0 { Ok(n) }
  else { Err("must be positive") }

fun main() {
  let result = safe_divide(100, 4)
    |> and_then_result((n) => validate_positive(n))
    |> map_result((n) => n * 2)
  println(result)   // Ok(50)

  let bad = safe_divide(100, 0)
    |> and_then_result((n) => validate_positive(n))
  println(bad)   // Err("division by zero")
}
?演算子

多くのフォールブルなステップを連鎖させる関数では、?はコードをフラットに保ちます。ステップが失敗した場合、NoneまたはErrで早期に返します。

fun add_strings(a: string, b: string) : maybe<int> {
  let x = parse_int(a)?
  let y = parse_int(b)?
  Some(x + y)
}

fun main() {
  println(add_strings("10", "32"))    // Some(42)
  println(add_strings("10", "oops"))  // None
}

知っておくべき3つの制約があります。

  • 戻り値の型注釈は、囲む関数に必要です。コンパイラは早期リターンを正しく発行するためにそれが必要です。
  • ラッパー型は一致する必要があります。maybeの?はmaybeを返す関数内でのみ機能し、resultの?はresultを返す関数内でのみ機能します。
  • main()では?は使用できません。main()は()を返します。フォールブルなロジックをヘルパー関数に移動し、matchを使用してmain()から呼び出してください。

まとめ

構造体、純粋関数、クロージャ、パイプ、パターンマッチング、maybeをすべてまとめたプログラムです。

struct Student { name: string, grade: int }

fun letter_grade(g: int) : string => match g {
  90..=100 => "A",
  80..=89  => "B",
  70..=79  => "C",
  60..=69  => "D",
  _        => "F"
}

fun passing(s: Student) : bool => s.grade >= 60

fun summarise(students: list<Student>) {
  let passing_students = filter(students, passing)
  let names = map(passing_students, (s) => s.name)
  let avg = fold(passing_students, 0, (acc, s) => acc + s.grade)
    / length(passing_students)

  println("Passing: {join(names, ", ")}")
  println("Average grade (passing): {avg}")
  println("Letter grade: {letter_grade(avg)}")
}

fun main() {
  let students = [
    Student { name: "Alicia", grade: 92 },
    Student { name: "Björn",  grade: 55 },
    Student { name: "Cecilia", grade: 78 },
    Student { name: "David",  grade: 61 }
  ]
  summarise(students)
}

出力:

Passing: Alicia, Cecilia, David
Average grade (passing): 77
Letter grade: C

持ち帰るべき主要なアイデア

コンセプトhica
不変データデフォルトでlet、必要ならvar
第一級関数(x) => x * 2、fun add(a, b) => a + b
クロージャfun make_adder(n) => (x) => x + n
合成`
リストの変換map、filter、fold
フラット化 / 展開concat(フラット化)、flat_map(map + フラット化)
ラップされた値の連鎖and_then (Maybe)、and_then_result (Result)、flat_mapと同じ考え方
遅延ストリームstream(xs)、.map()、.filter()などを連鎖させ、.collect()、.fold()で終端処理
パイプラインのトランスデューサーstd/xform(例: xf_filter `
再帰データtype Tree { Leaf, Node(...) }
安全な失敗Maybe (Some/None) と Result (Ok/Err)
網羅的なマッチコンパイラチェック付きバリアントを持つmatch

ポイントはループを避けることではありません。それは、小さく合成された関数が、テスト、命名、再利用が容易になる傾向があるということです。hicaの設計は、それを自然なデフォルトにしています。