これは何?
こちらのAdvent Calendarの2日目の記事です。
関数型言語がおもろいぞ!という話は1日目の記事でするので、本記事ではHaskellのおもしろさを少しでもお伝えできたら良いなと思います。
目的1: 関数型言語のエッセンスを学びたい
Haskellはただの関数型言語ではなく、純粋関数型言語であるため、コンテスト中に命令形に逃げにくい
一般的に関数型言語と分類される言語であっても、純粋でない言語が結構多い。
Wikipedia 関数型プログラミングの表を純粋かそうでないかで分けてみた。
純粋関数型言語
| 名前 | 型付け | 純粋性 | 評価戦略 | 理論的背景 |
|---|---|---|---|---|
| Clean | 静的型付け | 純粋 | 遅延評価 | |
| Elm | 静的型付け | 純粋 | 正格評価 | |
| Haskell [2] | 静的型付け[2] | 純粋[2] | 遅延評価[2] | 型付きラムダ計算 [3] |
| Idris | 静的型付け | 純粋 | 正格評価 | 型付きラムダ計算 |
| Lazy K | 型なし | 純粋 | 遅延評価 | コンビネータ論理 |
| Miranda | 静的型付け | 純粋 | 遅延評価 | |
| Lean | 静的型付け | 純粋 | 正格評価 | 型付きラムダ計算 |
非純粋関数型言語
| 名前 | 型付け | 純粋性 | 評価戦略 | 理論的背景 |
|---|---|---|---|---|
| Erlang | 動的型付け | 非純粋 | 正格評価 | |
| F# | 静的型付け | 非純粋 | 正格評価 | |
| LISP 1.5 | 動的型付け? | 非純粋 | 正格評価? | 型無しラムダ計算? [3] |
| Scheme | 動的型付け | 非純粋 | 正格評価 | 型無しラムダ計算 [3] |
| Common Lisp | 動的型付け | 非純粋 | 正格評価 | 型無しラムダ計算 [3] |
| Clojure | 動的型付け | 非純粋 | 正格評価 | 型無しラムダ計算 [3] |
| ML | 静的型付け | 非純粋 | 正格評価 | |
| Standard ML | 静的型付け | 非純粋 | 正格評価 | |
| OCaml | 静的型付け | 非純粋 | 正格評価 | |
| Scala | 静的型付け | 非純粋 | 正格評価 | |
| Unlambda | 型なし | 非純粋 | 正格評価 | コンビネータ論理 |
| LISP系方言 [3] | 方言による | 非純粋 | 方言による |
(私は非純粋型言語をきちんと扱ったことがないため想像にすぎないのだが)
- 競技プログラミングのような時間制約のある場面で非純粋型言語を採用していた場合、土壇場で関数型でないコードに逃げてしまう可能性がある
- (コンテスト期間外に)LLMに質問した際、関数型でない解答が示される可能性がある
という2点が関数型言語のエッセンスを学ぶという目的を達成する上で不適切だと考えた。
目的2: アルゴリズムを学び直したい
Haskellで書かれたアルゴリズムは宣言的であるため、どういうアルゴリズムかイメージしやすい
私は、2020年と2023年に少しだけアルゴリズムの勉強を少しだけした(このときは競技プログラミングのコンテストには出ず)。
この際に私実際にアルゴリズムを実装したにも関わらず、アルゴリズムに対する理解度が時間を経つと下がると感じていた。
この問題に対して、Haskellを使うことで関数型という別視点からアルゴリズムにスポットを当てることができ、理解度向上につながるのではないかと考えている。
クイックソートを使って比較してみる。
筆者はFortranの次である2番目にPythonを学んでおり、Pythonは得意な言語の一つです。
そのため、比較する際にPythonを使うのがわかりやすいと考えているだけであり、Pythonを貶める意図はありません。
# 再帰なし
def qsort_iter(xs):
xs = list(xs) # 破壊を避けるならコピー
stack = [(0, len(xs) - 1)]
while stack:
left, right = stack.pop()
if left >= right:
continue
# パーティション
pivot = xs[right]
i = left
for j in range(left, right):
if xs[j] < pivot:
xs[i], xs[j] = xs[j], xs[i]
i += 1
xs[i], xs[right] = xs[right], xs[i]
# 右側・左側をスタックに積む（順序は任意）
stack.append((left, i - 1))
stack.append((i + 1, right))
return xs
久しぶりにこれを見た際にパッと見でどう動くかをシミュレートしずらいと私は感じている。
では、Haskellの場合はどうだろうか。
Why Haskell mettersに記載のあった、クイックソートはもっと簡潔でわかりやすいと思う。
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort more
where less = filter (<x) xs
more = filter (>=x) xs
これには型がついているなどの理由もあると思うが、以下の構造は完全にクイックソートの特徴をわかりやすく記述しており美しいと感じる。
- 配列の先頭とそれ以外を
xとxsに分ける(xがピボットになる) -
xをqsort lessとqsort moreの真ん中に配置される(再帰) -
lessはxより小さいxsの要素、moreはx以上のxsの要素である。
もちろん、Pythonでも再帰を使った実装は可能である。
# ChatGPTに似せて書いてもらった。
def qsort(xs):
if not xs:
return []
x, *rest = xs
less = [a for a in rest if a < x]
more = [a for a in rest if a >= x]
return qsort(less) + [x] + qsort(more)
しかし、Haskellを使う場合、
- 再帰を使う強制力が一定働くことと
- より宣言的でわかりやすい
- Haskellの場合、
qsort (x:xs) = qsort less ++ [x] ++ qsort moreだけを見ればクイックソートの本質を思い出せる - Pythonの場合、再帰に
lessやmoreの定義が目に入ってしまう。x, *rest = xs less = [a for a in rest if a < x] more = [a for a in rest if a >= x] return qsort(less) + [x] + qsort(more)
- Haskellの場合、
と言った観点からアルゴリズムをより深く理解し、記憶に定着させることができるのではないだろうか。
フィボナッチ数列を使って比較してみる
# ChatGPTに似せて書いてもらった
def fibonacci_number(n: int) -> int:
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_number(n - 1) + fibonacci_number(n - 2)
Haskellではガードを使ってより数式っぽく書くこともできる。
(完全に個人的な好み)
-- フィボナッチ数列の計算（再帰定義）
-- NOTE: メモ化されていないためパフォーマンスは悪いが例として
fibonacciNumber :: Int -> Int
fibonacciNumber n
| n == 0 = 0
| n == 1 = 1
| otherwise = fibonacciNumber (n - 1) + fibonacciNumber (n - 2)
さらに、以下のようなよりエッセンシャルな書き方もできる点を魅力に感じている。
fibs :: [Int]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
詳細はこちらの記事を参照されたし。
非技術的観点でHaskellに取り組むモチベーション(ポエム)
- naoya_itoさんの影響: (直接お会いしたことはないが、以下の資料に感銘を受けており、自分もお手本にさせていただきたい)
- 強いエンジニアの人は尖った言語を経験している(体感)
-
Why Haskell mettersで引用されていた、Paul Grahamの Beating the AveragesのBlub Paradoxの話
- 仮想言語Blubよりもパワーの低い言語は、彼らが慣れ親しんだ機能が欠けているため、明らかにパワーが低いと理解できる。
- しかし、逆はわからない。それはBlubで考えているからである。このことから、HaskellやLispのような強いパワーを持つ言語に取り組むことで見える世界が変わるのではないかと考えている。
原文
As long as our hypothetical Blub programmer is looking down the power continuum, he knows he's looking down. Languages less powerful than Blub are obviously less powerful, because they're missing some feature he's used to. But when our hypothetical Blub programmer looks in the other direction, up the power continuum, he doesn't realize he's looking up. What he sees are merely weird languages. He probably considers them about equivalent in power to Blub, but with all this other hairy stuff thrown in as well. Blub is good enough for him, because he thinks in Blub.
- 2025年11月現在育休中であるため、業務へのキャッチアップなどを考えずに自由に勉強内容を選択できる環境にある。機会損失の観点から変わったことをやりたい。