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

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

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

`flip fix`
----------

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

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

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

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

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

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

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

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

```hs
> 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`拡張を有効にしています）
このプログラムは以下のような構造になっています。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/6546031b-b91f-0568-2fe2-da00accccad3.png" width=800px>

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

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

```hs
> 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で教えていただき](https://twitter.com/nobsun/status/1341953192091774977)助かりました :pray: ）。

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

```hs
> 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の平方根をニュートン法を使って求める処理を書いてみましょう。

```hs
> 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で簡単にループを書く"](https://qiita.com/lotz/items/409112751a23689d7d85)）へのコメントで教えていただいたのが最初でした。`flip fix`は考えてる処理が楽に実装できて非常に便利なんですが最適化のこととか何も考えてないので、こういう場合でスペースリークがあるよとかこういう場合でコンパイラの最適化が効かないよとかあったらコメントで教えていただけるとありがたいです :pray: みなさんも`flip fix`を使って[ボーイスカウトHaskellプログラマー](http://willamette.edu/~fruehr/haskell/evolution.html)を目指しましょう〜