Help us understand the problem. What is going on with this article?

Haskellのループ処理は flip fix でだいたい書けそう

Haskellにはfor文もwhile文もありません。
大抵の場合はmap, filter, foldrのような関数を使えば事足りますし、再帰関数を使えばほとんどのループ処理は書けてしまいます。しかし時には今考えているループを実装するために適切な高階関数が思いつかなかったり、計算結果だけが欲しいのに再帰関数をわざわざ定義するのが煩わしくなったりする状況もあるでしょう。

"グラフからコミュニティ構造を抽出する 〜リッチフローによるグラフの時間発展〜"を書いた時にいくつかループ処理を実装する必要があって、その度に再帰関数を定義するのが大変だったので flip fix を使いました。そして思ったより flip fix の使い勝手が良かったので、この記事ではこれにスポットライトを当てて紹介したいと思います。

flip fix

flip はご存知の通り2変数関数の引数の順番を入れ替える関数です。これはPreludeに定義されているので何もimportせずに使うことができます。

flip :: (a -> b -> c) -> b -> a -> c
flip f x y =  f y x

fixData.Function で定義された関数で、与えられた関数の不動点を求める関数です。この関数を使えば大抵の再帰関数を実装することができます(領域理論で言う再帰関数が汎関数の不動点で表されるというアレです)。

fix :: (a -> a) -> a
fix f = let x = f x in x

この2つを組み合わせると以下のような型を持つ関数になります。

> :t flip fix
flip fix :: b -> ((b -> c) -> b -> c) -> c

fix の型を ((b -> c) -> b -> c) -> b -> c だと思って flip すると考えるとこのような型になることが分かるでしょう。とはいえ型だけみても何ができるか分からないと思うので、まずは簡単な例で flip fix の使い方を見てみましょう。

考えるのは"Hello World"を5回出力するという簡単な処理です。

> flip fix 0 \loop n ->
|   if n == 5 then pure ()
|   else do
|     putStrLn "Hello World"
|     loop (n+1)
Hello World
Hello World
Hello World
Hello World
Hello World

(ラムダ式の前に$を書かなくて良いようにBlockArguments拡張を有効にしています)
このプログラムは以下のような構造になっています。

見て分かる通り非常に手続き的な考え方に近い実装になっています(まるでfor(int i = 0; i < 5; i++) { みたいですね)。そのため最適化計算のような"何らかの収束条件を満たすまで計算を繰り返す"だったり、必ずしもデータ構造に沿った形でないような再帰も簡単に書くことができます。

同様の処理をHaskellで実装する際によくあるパターンとしては

> let go 0 = pure ()
|     go n = do
|         putStrLn "Hello World"
|         go (n-1)
| go 5
Hello World
Hello World
Hello World
Hello World
Hello World

というように再帰関数goを一度定義してから実行するという方法ですが、flip fixを使った方法ではgoという関数をわざわざ定義する必要がなくなります。2つループ書きたいときにgo1, go2とか定義したくないですよね :sweat: (僕は最初この部分の理解が曖昧だったのですがTwitterで教えていただき助かりました :pray: )。

またここでは副作用のある関数を例に取り上げましたが、純粋な関数でも同様に使うことができます。簡単な例として1から100まで足し上げる関数を考えてみましょう。

> flip fix (0, 0) \loop (accum, n) ->
|   if n == 100 then accum + 100
|   else loop (accum + n, n + 1)
5050

いやsumを使えよというツッコミは置いておいて、純粋な関数でも flip fix が使えることが分かりました。

先程のgoを使った例を考えるとflip fixは再帰関数を定義して実行するのと同等の記述力を持っており、flip fixで大体のループ処理が書けることが分かるかと思います。しかしmap, filter, foldrなどの高階関数が使える場面ではそれを使ったほうが明らかに記述量が減り可読性も高いですし、時にはgoのようにループ処理に別名をつけることでより読みやすいコードになることもあるので要は適材適所です(要はバランス)。

最後にflip fixを使った実践的な例として2の平方根をニュートン法を使って求める処理を書いてみましょう。

> flip fix 1 \loop x ->
|   let x' = x - (x^2 - 2) / (2*x)
|    in if abs (x' - x) < 1e-3
|         then x'
|         else loop x'
1.4142135623746899

このようにリストが空になったりとか自然数が0になったりとかではなく、値が収束するまでのような柔軟なループ処理の条件を関数定義をせずにその場で書けるのがflip fixの便利なところです。

おわりに

僕が flip fix を知ったのはこちらの記事("fixで簡単にループを書く")へのコメントで教えていただいたのが最初でした。flip fixは考えてる処理が楽に実装できて非常に便利なんですが最適化のこととか何も考えてないので、こういう場合でスペースリークがあるよとかこういう場合でコンパイラの最適化が効かないよとかあったらコメントで教えていただけるとありがたいです :pray: みなさんもflip fixを使ってボーイスカウトHaskellプログラマーを目指しましょう〜

lotz
実用関数型プログラミング言語 Haskell の情報を発信しています
http://lotz84.github.io/
folio-sec
誰もがかんたんに資産運用することができるサービス「フォリオ」を作っているFinTech系スタートアップ
https://corp.folio-sec.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away