なぜHaskellは美しいと言われるのか?

https://peatix.com/event/5095532

#netadashi #Haskell

Transcript

1. なぜHaskellは美しいと言われるのか? なぜHaskellは美しいと言われるのか? 〜関数型言語と遅延評価を使ったプログラミングとは〜 写真撮影 SNS投稿 歓迎 発表資料 sigma sigma (Ryosuke (Ryosuke Tomita) Tomita) Netadashi Meetup #17 / 2026-08-28
2. 資料はこちら ソースコードもあるのでスキャン推奨!
3. はじめに: Haskellは美しい! Python 3: メモ化でキャッシュを持つ Haskell: 数列そのものを定義する memo = {} fibs :: [Integer] def fib(n): fibs = 0 : 1 : zipWith (+) fibs (tail fibs) if n in memo: return memo[n] if n < 2: return n memo[n] = fib(n - 1) + fib(n - 2) return memo[n] ・Haskellはシンプルで美しい記述ができる! ・今日はその秘密を教えます 3 / 52
4. 目次 1. Haskellの制約と誓約 2. 関数型プログラミング 3. 遅延評価(制約で得た力) 4. 応用例: フィボナッチ数列 #netadashi #Haskellはいいぞ(ツイートしてね🐦) 発表内容は個人の見解であり、所属する組織の公式見解ではありません。 4 / 52
5. 01 Haskellの制約と誓約 Haskellの制約と誓約 “ 誓約と覚悟が大きいほど念は強く働く!! — クラピカ『HUNTER×HUNTER』(幻影旅団編) 5 / 52
6. 0 1 Haskellの制約と誓約 Haskellは、「制約と誓約」で力を得た言語 強い制約を課すことで、強力なパワーを得る HUNTER×HUNTERの念能力: 自らに 強力なパワー 遅延評価(lazy evaluation): 値が必要になる瞬間まで評価を先送りできる。 その結果、無限リストを宣言できるなど、プログラムの表現力が拡張された。 ・制約① 純粋関数 ・制約② 束縛(不変性) ・制約③ 副作用も型に出す 6 / 52
7. 0 1 Haskellの制約と誓約 制約① 純粋関数 ・参照透過性: 同じ入力に対して常に同じ結果を返す ・副作用を持たない 純粋でないものの例(他言語の例として): ・IO処理(ファイル、ネットワーク、画面出力) ・例外を投げる ・ランダムな値を使う ・グローバル変数やインスタンス変数の変更 7 / 52
8. 0 1 Haskellの制約と誓約 制約② 束縛(不変性) ・Javaは final をつけて再代入を禁止できる ・Haskellでは変数への代入ではなく、値と名前を結びつける束縛(binding) ・再代入はコンパイルエラー。更新するときは別の名前に束縛し直す x = 1 x = 2 -- error: Multiple declarations of 'x' x = 1 x' = x + 1 (パフォーマンス上の理由で更新が必要な場合には範囲を絞って制約を緩め、安全 に更新できる仕組みもあるが割愛) 8 / 52
9. 0 1 Haskellの制約と誓約 制約③ 副作用も型に出す ・システムは現実世界に影響を及ぼすために副作用が必要 ・副作用を起こす手続きを型付きの値にすることで、関数を純粋に保ったまま副 作用を扱える readFile :: FilePath -> IO String find :: Foldable t => (a -> Bool) -> t a -> Maybe a ・ IO は副作用を起こす手続き ・ Maybe -> 例外を投げずに「失敗」を値として返す 型は関数の性質を表明するドキュメントにもなる。 9 / 52
10. 02 関数型プログラミング 関数型プログラミング “ プログラムは人が読むために書くものであり、機械が実行する のはついでである — エイブルソン, サスマン『計算機プログラムの構造と解釈』(1984年) 10 / 52
11. 0 2 関数型プログラミング 関数型プログラミングとは? Wikipediaより 関数型プログラミングとは、数学的な意味での関数を主に使うプログラミング のスタイルである Haskellは純粋関数の組み合わせでプログラムを記述する。 11 / 52
12. 0 2 関数型プログラミング 関数型の雰囲気を感じてみよう! リストの合計を求める関数の実装をPythonとHaskellで比較してみる。 12 / 52
13. 0 2 関数型プログラミング Not関数型: 再代入とループで書く(Python) # 関数型でない例: 箱を用意して、ループで書き換えていく def my_sum(xs): 状態を持つ変数 for x in xs: # ループ total += x # 再代入で状態を更新 total = 0 # return total 書き換えとループが、Haskellでは制約(純粋関数と束縛)により(基本的に) total の 使えない 13 / 52
14. 0 2 関数型プログラミング Haskell パターンマッチと再帰で書く リストは [] (空) or (x : xs) (先頭と残り)の 2つの形がある mySum :: [Int] -> Int mySum [] ① = 0 -- 再帰の停止条件 mySum (x : xs) ① = x + mySum xs ② ・再帰1回ごとにリストの要素が一つずつ消費 され、空になると再帰が止まる ① パターンマッチ 引数の構造で場合分けし、上 から順に試して最初にマッチ した行が使われる。 ② 再帰 自分自身を呼び出す関数。 ・宣言的なコードに 14 / 52
15. 0 2 関数型プログラミング 再帰の進み方イメージ: mySum [1,2,3] mySum [1,2,3] → 1 + mySum [2,3] -- (x : xs) にマッチ。x = 1, xs = [2,3] → 1 + (2 + mySum [3]) → 1 + (2 + (3 + mySum [])) → 1 + (2 + (3 + 0)) -- [] にマッチ。ここで再帰が止まる → 1 + (2 + 3) → 1 + 5 → 6 15 / 52
16. 0 2 関数型プログラミング 畳み込みで抽象度の高いコードに ・再帰とパターンマッチを使った実装は畳み込みを使って抽象化できる mySum :: [Int] -> Int mySum xs = foldr (+) 0 xs ・畳み込みとは、リストの : を演算子に、 [] を初期値に置き換える操作 ・ [1,2,3] は 1 : 2 : 3 : [] の糖衣構文 ・ : を + に、 [] を 0 にしたものがリストの合計 ・e.g. 1 : 2 : 3 : [] を初期値0、 + で畳み込むと 1 + 2 + 3 + 0 になる 16 / 52
17. 0 2 関数型プログラミング 畳み込みは演算子と初期値を変えるだけでいろいろできる mySum xs = foldr (+) 0 xs -- 合計 myProduct xs = foldr (*) 1 xs -- 総積 insertSort xs = foldr insert [] xs -- 挿入ソート where insert x [] = [x] insert x (y : ys) | x <= y = x : y : ys | otherwise = y : insert x ys 17 / 52
18. 0 2 関数型プログラミング 関数型は、定義を書くのでシンプルな記述に リストの合計を求めるとは? ・再代入とループ: 箱を用意し、ループして、足し合わせる -> 計算の手順 ・パターンマッチと再帰: 空リストの合計は0、 x : xs の合計は x + mySum xs -> 合計の定義 ・畳み込み: 初期値 0 、 + で畳み込む -> 合計の定義 遅延評価のための制約がHaskellにおける関数型の最初の目的だった が、関数型によって宣言的かつ、抽象度の高いコードが書けて嬉しい (関数型は遅延評価の前提条件ではない) 18 / 52
19. 03 遅延評価 遅延評価 “ 人はいつか時間さえ支配することができるさ — アムロ・レイ『機動戦士ガンダム 逆襲のシャア』(宇宙世紀0093年) 19 / 52
20. 0 3 遅延評価 遅延評価: 必要になるまで評価しない ・一般的な言語は正格評価のため、式は即座に評価される e.g. 1+1=2 ・遅延評価では式はすぐに評価されず、サンクという「評価の予約」が積まれる ・値が本当に必要になった瞬間に、式が評価されて値になる ghci> let x = 1 + 1 -- サンクが積まれる ghci> print x -- サンクが潰れて2になる ・逆に必要のない式は評価されず、サンクのまま ・cond = False なら expensive は一度も評価されない let x = expensive in if cond then x + x else 0 20 / 52
21. 0 3 遅延評価 サンクの共有(グラフ簡約) ・複数の式が同じサンクを共有することができ、同じ評価が二度行われない ・一度評価されたサンクは結果そのもので置き換わるので、2回目以降は値を読む だけ let x = expensive in if cond then x + x else 0 ・ cond = True のとき x は2回現れるが、 expensive の評価は1回だけ (後ほど紹介するフィボナッチ数列の例で共有の真価が感じられる) 21 / 52
22. 0 3 遅延評価 対話型実行環境(GHCi)の :sprint で遅延評価を観 察してみる 22 / 52
23. 0 3 遅延評価 デモ① 無限リストを宣言するとサンクが作られる ghci> let xs = [1..] :: [Int] ghci> :sprint xs -- 状態確認 xs = _ ・ _ は未評価の印 ・ヒープ上には「リストを作る予約」としてサンクだけが置かれている 23 / 52
24. 0 3 遅延評価 デモ① head で先頭だけ要求すると先頭だけ評価される ghci> head xs 1 ghci> :sprint xs xs = 1 : _ ・先頭の 1 だけが評価された ・残りはサンクのまま ・必要な分しか評価しないことで無限リストを扱える 24 / 52
25. 0 3 遅延評価 デモ② length は「構造」だけを評価する length は無限リストに使うと停止しないので、有限のリストを用意する から10のリスト(map (+1)の理由は巻末参照) -- 1 ghci> let ys = map (+1) $ [0..9] :: [Int] ghci> length ys 10 ghci> :sprint ys ys = [_,_,_,_,_,_,_,_,_,_] 構造は必要だが、要素の中身は評価不要 長さを数えるのにリストの 25 / 52
26. 0 3 遅延評価 デモ③ find は見つかるまでしか評価しない ghci> import Data.List (find) ghci> let ys = map (+1) $ [0..9] :: [Int] ghci> find (==3) ys Just 3 ghci> :sprint ys ys = 1 : 2 : 3 : _ ・ 3 を探すために先頭から評価し、 1, 2, 3 まで見て見つかったので評価が止 まる 26 / 52
27. 0 3 遅延評価 デモ④ 表示すれば、すべて評価される ghci> let ys = map (+1) $ [0..9] :: [Int] ghci> show ys "[1,2,3,4,5,6,7,8,9,10]" ghci> :sprint ys ys = [1,2,3,4,5,6,7,8,9,10] ・ show は全要素の値が必要 -> 全サンクが評価される ・ここでようやく、素直なリストの形になった 27 / 52
28. 0 3 遅延評価 遅延評価ネタコード(リストの最小値) import Data.List (sort) minimum' :: Ord a => [a] -> a minimum' xs = (head . sort) xs ・見た目は「全部ソートして先頭を取る」= マージソートのため、O(n log n)に 見える ・しかし head は先頭の1要素しか要求しない ・遅延評価により、ソートは先頭を確定させる分までしか進まない ・計算量は、おおよそO(n)に 28 / 52
29. 0 3 遅延評価 (参考)O(n)とO(n log n)はどれくらい違うのか(log2 nの場合) ​ 演算回数(相対) n log n 600 n 約6.6倍 400 200 0 0 25 50 75 100 ) 要素数 n( 29 / 52
30. 0 3 遅延評価 遅延評価のまとめと補足 ・遅延評価を使うと必要になるまで評価が進まない ・これを使うとプログラミング言語の表現力が向上する ・補足: 今回は時間の都合上、遅延評価がうれしい例だけを紹介している ・(むしろ、Haskellは実行速度が速い言語ではない) 30 / 52
31. 04 応用例: 応用例: フィボナッチ数列 フィボナッチ数列 “ エレガント!! ベリーエレガント!! — ヘンリー・ヘンダーソン『SPY×FAMILY』 31 / 52
32. 0 4 応用例: フィボナッチ数列 フィボナッチ数列 an = an−1 + an−2 ​ ​ ​ (a0 = 0, a1 = 1) ​ ​ 漸化式をそのまま再帰で実装すればよい? 番目のフィボナッチ数を返す(パフォーマンスが悪い) -- n fib :: Int -> Int fib n | n == 0 = 0 | n == 1 = 1 | otherwise = fib (n - 1) + fib (n - 2) 同じ fib が何度も評価されてしまい、指数関数的に計算量が増える 32 / 52
33. 0 4 応用例: フィボナッチ数列 Python 3: パフォーマンス改善のためにメモ化 ・メモ化: 計算した結果をキャッシュ memo = {} def fib(n): if n in memo: # キャッシュを引く return memo[n] if n < 2: return n result = fib(n - 1) + fib(n - 2) memo[n] = result # return result キャッシュに入れる 33 / 52
34. 0 4 応用例: フィボナッチ数列 Haskell: 遅延評価の共有がメモ化代わりに ・Haskellの遅延評価では、同じサンクを指す複数の式で結果が共有されるので、 二度評価されない ・自分自身を1つずらして足し合わせる形で、フィボナッチ数列本体を定義可能 ・(評価が遅延されるので、自己参照構造が書ける) fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) fibs !! 4 -- 3 34 / 52
35. 0 4 応用例: フィボナッチ数列 fibs a0 tail fibs a1 zipWith (+) fibs (tail fibs) a0 +a1 ∥ a2 ​ ​ ​ ​ ​ ​ a1 a2 a1 +a2 ∥ a3 ​ ​ ​ ​ ​ ​ a2 a3 a2 +a3 ∥ a4 ​ ​ ​ ​ ​ ​ a3 a4 a3 +a4 ∥ a5 ​ ​ ​ ​ ​ ​ ​ ⋯ ⋯ ⋯ ⋯ 遅延評価×関数型ではより宣言的なコードが書けるのがうれしい 35 / 52 ​
36. 0 4 応用例: フィボナッチ数列 まとめ #Haskellはいいぞ ・Haskellは遅延評価を使うため、純粋関数・束縛・副作用も型に出すという制約 がある ・関数型を使うのは制約のためであったが、結果として見通しの良いコードに ・遅延評価があることで表現力が拡張 ・遅延評価と関数型を組み合わせると相乗効果でより美しいコードが書ける Elegant! 36 / 52
37. 05 おまけ: おまけ: 型の恩恵 型の恩恵 “ まだだ! まだ終わらんよ! — クワトロ・バジーナ『機動戦士Ζガンダム』(宇宙世紀0087年) 37 / 52
38. 0 5 おまけ: 型の恩恵 Functor: 構造を保ったまま中身だけを写す ・ Functor は「型の文脈(箱)の中身に関数を適用する」ための型クラス。圏論で いう関手の概念をHaskellに取り込んだもの class Functor f where fmap :: (a -> b) -> f a -> f b fmap (+1) [1, 2, 3] -- [2,3,4] fmap (+1) (Right 2) -- Right 3 fmap (+1) (Left "error") -- Left "error" 38 / 52
39. 0 5 おまけ: 型の恩恵 Functorを使うと安全に関数合成できる ・Haskellは純粋(数学的)関数による関数合成で処理を記述 -> 数学の理論が使える ・関手則を満たすように fmap を実装することで文脈を壊さない安全な関数合成 が可能 -- 何もしない関数の写像はなにもしない(恒等射の保存) fmap id [1, 2, 3] -- -- [1, 2, 3] 関数合成してから写像と写像してから関数合成は同じ結果(射の合成の保存) fmap ((*2) . (+1)) [1, 2, 3] -- [4, 6, 8] (fmap (*2) . fmap (+1)) [1, 2, 3] -- [4, 6, 8] 39 / 52
40. 0 5 おまけ: 型の恩恵 失敗情報を上層に送りたい(Java) チェック例外 型に例外 現れる( throws ) 課題 層をまたぐたびに try-catch / throws を 強制 失敗の存在も、失敗の中身も型からわから 非チェック例外 現れない ない ・例外が発生することが型で見えるとうれしい ・例外情報を上層に伝えるためだけの try-catch を書きたくない! 40 / 52
41. 0 5 おまけ: 型の恩恵 Haskellのサンプルコード概要 リポジトリ層 findUser DB users ドメイン層 アプリケーション層 greet handle userName ・失敗の可能性があるのはDBアクセスをする findUser だけ ・リポジトリ層の失敗情報が必要なのは handle のみを想定 41 / 52
42. 0 5 おまけ: 型の恩恵 Functorで、失敗情報を安全に上層まで持ち上げ可能 data Either e a = Left e | Right a -- 失敗 or 成功 data UserError = NotFound UserId | DbDown String -- リポジトリ層: DBアクセスの結果は失敗情報 or 成功した結果 findUser :: UserId -> Either UserError User userName :: User -> String greet -- :: String -> String ドメイン層 -> アプリケーション層: 失敗したかを気にせずにすむ greeting :: UserId -> Either UserError String greeting uid = fmap greet (fmap userName (findUser uid)) 42 / 52
43. 0 5 おまけ: 型の恩恵 最外層で、初めて失敗を取り出す コントローラー: 成功失敗に応じた結果をユーザに返す -- handle :: UserId -> Response handle uid = case greeting uid of Right msg -> ok 200 msg Left (NotFound _) -> err 404 "user not found" Left (DbDown detail) -> err 500 detail ・ fmap は Right (成功)のときだけ中身に関数適用し、 Left (失敗)は素通り ・ユーザにエラーメッセージを返すまで失敗の取り出しを遅延できる 43 / 52
44. 0 5 おまけ: 型の恩恵 Functor まとめ ・Haskellは純粋関数型のため、数学(圏論)と親和性が高い。Functorもその一つ ・処理が失敗したかどうかを中間層で確認せずに上層まで処理結果を持ち上げる ことができる例を紹介 ・ fmap でつなぐことで、型の文脈を壊さずに関数合成ができる ・例外ではなく、失敗情報 or 成功結果のどちらかを持つ Either を使って失敗 情報を扱う Very Elegant!! (今回は失敗するかもしれない処理は1つだったが、複数扱う場合にはMonadや Applicativeを使う) 44 / 52
45. ご清聴ありがとうございました ご清聴ありがとうございました you can you can outsource outsource your your thinking thinking but but you you cannot outsource cannot outsource your your understanding understanding 発表資料(再掲) Haskellの記事
46. Reference① 文献・書籍 敬称略 ・ Lazy evaluation - HaskellWiki ・ 3. Pure Functions, Laziness, I/O, and Monads - School of Haskell(Bartosz Milewski、2014) ・ 関数型プログラミング - Wikipedia ・ A History of Haskell: Being Lazy with Class(Paul Hudak / John Hughes / Simon Peyton Jones / Philip Wadler、HOPL III, 2007) ・ Why Functional Programming Matters(John Hughes、1990) ・ Beating the Averages(Paul Graham) ・ 単体テストの考え方/使い方(Vladimir Khorikov、須田智之 訳、マイナビ出版) ・ 関数型ドメインモデリング(Scott Wlaschin、猪股健太郎 訳、アスキードワンゴ) 46 / 52
47. Reference② 発表・記事・ポスト 敬称略 ・ なぜ業界で使われないHaskellが、業界に決定的な影響を与えているのか(YouTube) ・ 長く活躍できるエンジニアになるためには? 技術者として大切にしたいこと(伊藤直也) ・ アルゴリズムは何を圧縮しているのか ─ Haskell から育った「圧縮代数」というメンタルモデル(伊藤直 也) ・ 【高校数学でわかる】Haskellで実装するフィボナッチ数列(sigma) ・ 関数型プログラミングを知らない人向けに、「Haskellって何が面白いの?」と聞かれた時の回答(sigma) ・ lotz(@lotz84_)のポスト 47 / 52
48. Appendix 補足 補足 デモ②の ys の作り方 / fibs の共有条件 / foldr と foldl' 48 / 52
49. A p p e n d i x 補足 デモ②の ys の作り方: [0..9] だとサンクが観察 できない ・デモ②で観察したかったのは「要素がサンクのままの状態」 ・しかし [0..9] :: [Int] だと、Int型の場合、サンクではなく評価済みの値が そのまま配置される最適化が行われてしまう ghci> let as = [0..9] :: [Int] ghci> length as 10 ghci> :sprint as as = [0,1,2,3,4,5,6,7,8,9] -- サンクがない! 49 / 52
50. A p p e n d i x 補足 解決: map (+1) を一枚挟む ghci> let ys = map (+1) $ [0..9] :: [Int] ghci> length ys 10 ghci> :sprint ys ys = [_,_,_,_,_,_,_,_,_,_] ・ map (+1) を通すと、要素位置が「あとで (+1) を適用する」というサンクに なる ・ length は構造だけをたどるので、そのサンクは潰れない ・-> 狙いどおり ys = [_,_,_,_,_,_,_,_,_,_] が観察できる 50 / 52
51. A p p e n d i x 補足 fibs の共有は「トップレベル・単相」で効く 発表スライド「Haskell: 遅延評価の共有がメモ化代わりに」の補足 fibs :: [Integer] -- 単相な束縛なので、サンクが共有される fibs = 0 : 1 : zipWith (+) fibs (tail fibs) fibsPoly :: Num a => [a] -- 多相にすると共有されない fibsPoly = 0 : 1 : zipWith (+) fibsPoly (tail fibsPoly) ・多相にすると Num a の辞書を受け取る関数になり、束縛ではなく呼び出しごと の計算になる ・結果としてサンクが共有されず、メモ化の効果が消える 51 / 52
52. A p p e n d i x 補足 foldr (+) 0 は大きなリストで落ちる 発表スライド「畳み込みで抽象度の高いコードに」の補足 発表で使った説明用の定義 mySum xs = foldl' (+) 0 xs -- 実用ではこちら(Data.List) mySum xs = foldr (+) 0 xs -- Haskellのfoldl、foldl’、foldrを比較してみた(sigma) 52 / 52