Fix関数の教科書 (Haskell)

fix関数についての解説記事が少なかったので、頑張ってかき集めた情報をまとめておこうと思います。

内容としては、

- fix関数 <- 今ココ
- MonadFixと再帰的do記法
- ArrowLoopと再帰的arrow記法

を複数の記事に分けて紹介します。

- fix関数なら大体知っているよっていう人は、説明を飛ばして、後ろの[練習問題](#練習問題)から始めても楽しいと思います。

- fix関数の仕組みはいいから、使い方だけ教えて～～っていう人は、[fix関数の活用法](#fix関数の活用法)から始めると幸せかもしれません。

この記事に載せているソースコードは、モジュールのimport文を省いています。なので、実際に手元の環境で動かしてみるときは、次のimport文をソースコードの冒頭に追加して実行してください。

```haskell
import Control.Monad.Fix -- fix関数をインポート
import Control.Monad.State -- Stateモナドをインポート
import Text.Read -- readMaybe関数をインポート
```

## 前提知識

Haskellの基本的な使い方は説明しません\_(.\_.)\_

- 変数や関数の定義方法
- 関数のカリー化と部分適用
- 基本的な関数たち（`id`、`const`、`take`とか）

は知っておいた方が読み易いと思います。

Haskellerの登竜門といわれるモナドについては、知らなくても大きな問題はありません。ただ、練習問題２ではStateモナドを使っているので、そこだけはモナドの知識が必要です。

それでは、準備はよろしいですか？

## fix関数

```haskell:定義
fix :: (a -> a) -> a
fix f = let x = f x in x
```

定義から分かる通り、fix関数は関数を引数に取る[高階関数](https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96%A2%E6%95%B0)です。

とりあえず、適当な関数を放り込んでみましょう。恒等関数`id`を引数として渡してみます。

```haskell
fix id
```

。。。(-_-)zzz

いつまで経っても処理が終わりませんね。ご察しの通り、無限ループになってしまいました。

ループの中で、Haskell処理系がどんな処理をしているのか覗いてみましょう。

```haskell
  fix id
-- fixを関数適用
= let x = id x in x
-- 変数xを展開
= id x
-- idを関数適用
= x
-- 変数xを展開
= id x
-- idを関数適用
= x
-- 変数xを展開
= id x
...
```

なるほど、いつまで経っても処理が終わらないわけです。

次に、定値関数`const 0`を引数として渡してみましょう。

```haskell
fix (const 0)

-- 0
```

今度は値が求まりましたね。

さっきと同じように、Haskell処理系の動きを覗いてみましょう。

```haskell
  fix (const 0)
-- fixを関数適用
= let x = const 0 x in x
-- 変数xを展開
= const 0 x
-- constを関数適用
= 0
```

確かに、答えは0になりました。

今回とさっきは何が違うかったかというと、関数`f`の値を決めるために引数`x`の値が必要[^3]かどうかが違いました。

恒等関数`id`の場合は、

```haskell
id x = x
```

だったので、関数`id`の値を決めるために引数`x`の値が必要でした。

一方、定値関数`const 0`の場合は、

```haskell
const 0 x = 0
```

だったので、関数`const 0`の値を決めるために引数`x`の値は必要ではありません。

一般に、関数`f`の値が引数`x`の値によらず決まるとき、そしてその時に限り、fix関数は無事に終了してその値を返します。

### 不動点

ここでは、fix関数が返す値の意味を考えます。

fix関数は、

```haskell:定義（再掲）
fix :: (a -> a) -> a
fix f = let x = f x in x
```

と定義されていたので、`fix f`の返り値を`a`とすると、

```haskell
a = f a
```

が成り立ちます。つまり、値`a`は関数`f`に通しても、そのまま出てきます。

このような値のことを、関数`f`の不動点といいます。

関数の不動点は一つとは限りません。例えば、恒等関数`id`では、あらゆる値が不動点となります。

それでは、fix関数が返す不動点はどのように選ばれるのでしょうか。答えは、その関数の"最も定義されていない"(least-defined)不動点を返します。最も定義されていないとはどういうことなのかは、難しいので説明しません（=できません）。詳しくは、[Denotational semantics - Wiki](https://ja.wikibooks.org/wiki/Haskell/Denotational_semantics)を参照してください\_(.\_.)\_

数多ある値の中で、最も定義されていない値はボトム`⊥`です。ボトム`⊥`として、Haskellでは`undefined`が実装されています。また、計算が終わらず無限ループする場合もボトム`⊥`が返されたと考えます。

つまり、fix関数は、関数`f`がボトム`⊥`を不動点としてもつ場合は、必ずボトム`⊥`を返します（=計算が終わらないorエラーが出る)。実はこれは、

> 関数fの値が引数xの値によらず決まるとき、そしてその時に限り、fix関数は無事に終了してその値を返します

の言い換えになっています。

### fix関数が終了しない場合

fix関数が終了しなくてもよい場合があります。

例えば、fix関数を使って無限リストを作る場合などです。ここでは、1が無限に続くリストをfix関数で作ってみます。

```haskell
ls = fix $ \x -> 1:x -- (*)
```

実際に先頭の10要素を取ってくると、

```haskell
take 10 ls
-- [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
```

となっています。

ちょっと待ってください！！

(*)式の右辺を展開してみると、

```haskell
  fix $ \x -> 1:x
= let x = (\x -> 1:x) x in x
= (\x -> 1:x) x
= 1:x
= 1:((\x -> 1:x) x)
= 1:(1:x)
= 1:1:x
...
```

となって、計算は終了しないはずです。しかし、(*)式は終了します。

？？？

これは、Haskellが計算結果を遅延評価するためです。つまり、必要になるまで(*)の右辺は計算されずにほったらかしにされます。この状態のことを[サンク](https://en.wikipedia.org/wiki/Thunk)といいます。

サンクは必要になったら必要な分だけ評価されます（=計算が進められます）。

例えば、(*)式の右辺のサンクは、`take 5 ls`によって、

```haskell
ls = 1:1:1:1:1:x
```

まで計算が進められます。

この仕組みによって、fix関数は、たとえ終了しなくても意味のある結果を返すことが出来るようになっています。

### fix関数を使った設計法

> この章は[MonadFix is Time Travel](https://elvishjerricco.github.io/2017/08/22/monadfix-is-time-travel.html)を下敷きとして書いています。詳しくは、ネタ元の記事をご覧ください。

ここまではfix関数の性質を紹介してきましたが、この章ではじゃあ実際にどうやってfix関数を使ったプログラムを組むのかを紹介します。

fix関数の定義をもう一度見返してみましょう。

```haskell:定義（再掲）
fix f = let x = f x
```

関数`f`に自身の返り値`x`が引数として渡されていますね。ということは、関数`f`は実行前に自身の実行結果を知ることができると考えることができます。そして、実行結果をもとにして関数を実行することができます。なんと、未来のことが分かるんです！！

この考えのもとで、次のfibonacci数列を生成するプログラムを見ていきましょう。

```haskell
fix $ \fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)
```

ここでは、fix関数に渡す関数`f = \fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)`は、

```haskell
f fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
```

と定義されているとみなせます。

実行結果のリスト`fibs`と、そのリストを一つずらしたリスト`tail fibs`を足し合わせたリストを、第３項以降につなぎ合わせています。数列として書き直すと、

```math
[a_1 = 1,\ a_2 = 1,\ a_3 ... = [a_1,\ a_2,\ ...] + [a_2,\ a_3,\ ...]]
```

となっています。整理すると確かに、

```math
[a_1,\ a_2,\ a_3 = a_1 + a_2,\ a_4 = a_2 + a_3,\ ...\ ,\ a_n = a_{n-2} + a_{n-1}]
```

となっていますね。

## fix関数の活用法

ここからは、fix関数が現実のプログラムでどのように使われるのか、実例を紹介していきます。

### 活用法１：無限リスト

fix関数を使うと無限リストが簡単に作れます。

```haskell
ls = fix $ \xs -> [1:2:xs]

-- take 5 ls
-- [1, 2, 1, 2, 1]
```

この例だけでは、cycle関数（[Haskellの無限リスト系関数 - Qiita](https://qiita.com/TTsurutani/items/2ec2824bb4ccc120a69c)を参照）を使えばいいじゃないかというマサカリが飛んできそうなので、もう少し複雑な例も挙げておきます。

```haskell
ls = fix $ \fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)

-- take 5 ls
-- [1, 1, 2, 3, 5]
```
([What does fixIO do? - StackOverflow](https://stackoverflow.com/questions/25876042/what-does-fixio-do)より引用)

皆さんご存じのfibonacci数列です。こんな手の込んだ無限リストもfix関数を使えば作れます。

### 活用法２：forループ

[Haskellのループ処理は flip fix でだいたい書けそう - Qiita](https://qiita.com/lotz/items/0894079a44e87dc8b73e)に詳しく書かれていますが、fix関数を使うと他言語でいうforループを実装できます。

例えば、階乗を求める関数`fact`は、Pythonではfor文をつかって、

```python:Python
def fact(n):
    r = 1
    for i in range(n):
        r *= (i + 1)
    return r

# fact(5)
# 120
```

と書けます。

これをHaskellでは、

```haskell
fact n = (flip fix) n p where
    p _ 1 = 1
    p f i = i * f (i - 1)

-- fact 5
-- 120
```

と書くことができます。

### 活用法３：再帰関数の書き直し（ちょいムズ）

あらゆる再帰関数は、fix関数を使って"見かけ上"[^1]再帰形でない形に書き直すことができます。

ちょっと抽象的で分かりづらいですが、あらゆる再帰関数`f`は適切な高階関数`g`を使って、

```haskell
f = g (f) -- (*)
```

と書き表すことができます。

これをfix関数を使って書き直すと、

```haskell
f = fix g
```

となります。fix関数を使うと右辺から関数`f`を消去できるので、関数`f`は見かけ上再帰形ではなくなります。


この説明だけだと、何のこっちゃ？？となっていると思いますので、具体例としてfibonacci数を求める関数を考えてみます。

まずは、再帰関数で書いてみます。

```haskell
fib n = if n <= 1 then n else fib (n - 1) + fib (n - 2)
```

次に、右辺を`fib`を引数にとる高階関数で書き直します。

```haskell
fib n = g (fib) n where
    g f = \x -> if x <= 1 then x else f (x - 1) + f (x - 2)
``` 

さらに、関数`fib`の引数`n`を消去して、ポイントフリースタイルに書き直します。

```haskell
fib = g (fib) where
    g f = \x -> if x <= 1 then x else f (x - 1) + f (x - 2)
```

(*)の形になりました。

最後に、fix関数を使って関数`fib`を書き直します。

```haskell
fib = fix g where
    g f = \x -> if x <= 1 then x else f (x - 1) + f (x - 2)
```

あるいは、高階関数`g`を少し直して、

```haskell
fib = fix g where
    g f x = if x <= 1 then x else f (x - 1) + f (x - 2)
```

となります。

ところで、あらゆるループは再帰関数に書き直せる[^2]のでした。そして、あらゆる再帰関数はfix関数で書き直せるということは、、、

あらゆるループはfix関数で書き直すことができます！！

詳しくは、不動点コンビネータで[検索](https://www.google.com/search?q=%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF)してね。

### 活用法４：無限ループ

fixを使うと無限ループを簡単に作ることができます（怖い！！）。通常の処理では無限ループは避けるべきものですが、例えばインタープリタなどの[REPLプログラム](https://e-words.jp/w/REPL.html#:~:text=REPL%E3%81%A8%E3%81%AF%E3%80%81%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E8%A8%80%E8%AA%9E,%E3%82%A4%E3%83%B3%E3%82%BF%E3%83%97%E3%83%AA%E3%82%BF%E3%81%AE%E4%B8%80%E7%A8%AE%E3%80%82)では、ユーザーの入力を受け付け続ける必要があるので、main関数を無限ループにする必要があります。そういう時は、main関数をfix関数を使って定義することができます。

例として、ユーザーに数字を入力してもらい、その数字の偶奇判定をするプログラムを書いてみます。なお、ユーザーが数字以外を入力した場合には停止します。

まずは、ループなし版を示します。ユーザー入力後に偶奇判定をして、そのまま終了するプログラムです。

```haskell
main = do
    p <- readMaybe <$> getLine
    case p of
        Just x | x `rem` 2 == 0 -> print "Even"
               | otherwise      -> print "Odd"
        Nothing -> print "Quit"

-- < 123
-- > Odd
```

次に、fix関数を使ってループさせます。

```haskell
main = fix $ \m -> do
    p <- readMaybe <$> getLine
    case p of
        Just x | x `rem` 2 == 0 -> print "Even" >> m
               | otherwise      -> print "Odd" >> m
        Nothing -> print "Quit"

-- < 123
-- > Odd
-- < 122
-- > Even
-- < abc
-- > Quit
```

### 活用法５：メモ化

>[メモ化](https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E5%8C%96)については、[再帰関数とメモ化とフィボナッチ数列](https://keymale.xyz/2020/09/01/post-726/)を参考にしてください。参考記事ではpythonを使っていますが、メモ化の実装についてはHaskellでの実装よりも分かりやすいので、この章のプログラムと見比べてみると理解が進むと思います。

Haskellの関数は参照透明性があるため、メモ化との相性がとても良いです。一方で、リストの改変や変数の再代入が許されないため、計算結果をどうやってメモするのかは悩みどころとなります。その方法の一つがfix関数を使うやり方です。

fix関数を使ったfibonacci数列の求め方（再掲） <- めっちゃ速い！！

```haskell
sequence = fix $ \fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)

-- take 5 sequence 
-- [1, 1, 2, 3, 5]
```
([What does fixIO do? - StackOverflow](https://stackoverflow.com/questions/25876042/what-does-fixio-do)より引用)

特定のfibonacci数を求める方法は他にも、

```haskell
fib :: (Int -> Integer) -> Int -> Integer
fib f 0 = 1
fib f 1 = 1
fib f n = f (n - 1) + f (n - 2)

memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)

fibMemo :: Int -> Integer
fibMemo = fix (memoize . fib)

-- fibMemo 4
-- 5
```

([Memorization - Wiki](https://wiki.haskell.org/Memoization#Memoizing_fix_point_operator)より引用)

両方とも、途中計算をリストにメモすることで計算量をO(N)に抑えているため、高速に処理できています。

途中計算をリストにメモできるのは、Haskellが遅延評価で動く言語であり、さらにグラフ簡約という方法でプログラムを実行しているからです。詳しくは、[遅延評価の仕組み](https://xtech.nikkei.com/it/article/COLUMN/20070305/263828/)や[Graph Reduction (Reduction + Sharing) - Wiki](https://en.wikibooks.org/w/index.php?title=Haskell/Graph_reduction&section=7#Graph_Reduction_(Reduction_+_Sharing))を参照してください。

## 練習問題

### 1. fibonacci数列改（難易度★）

通常のfibonacci数列の漸化式は、

```math
a_{n+2} = a_{n} + a_{n+1}
```

で、fibonacci数列を求めるプログラムはfix関数を使って、

```haskell
fix $ \xs -> 1:1:zipWith xs (tail xs)
```

と書けるのでした。

この数列を改造し、漸化式が、

```math
a_{n+3} = a_{n} + a_{n+1} + a_{n+2}
```

となる数列を求めるプログラムをfix関数を使って書いてみてください。

<details><summary>解答例</summary><div>

zipWith関数を３つのリストに適用すればよさそうですね。

```haskell
fix $ \xs -> 1:1:1:foldr (zipWith (+)) (repeat 0) [xs, tail xs, (tail . tail) xs]

-- take 10 ls
-- [1,1,1,3,5,9,17,31,57,105]
```

他にも、[ParallelListComp言語拡張](https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/parallel_list_comprehensions.html)を使うとすっきりと書けます。

```haskell
{-# LANGUAGE ParallelListComp #-}
fix $ \xs -> 1:1:1:[a + b + c | a <- xs | b <- tail xs | c <- (tail . tail) xs]
```

</div></details>

### 2. ハノイの塔（難易度★）

再帰関数で解く問題で最も有名なのは[ハノイの塔](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94)だと思います。

fix関数の[活用法３](#活用法３再帰関数の書き直しちょいムズ)で紹介した、fix関数を使った再帰関数の書き換え方を応用して、ハノイの塔の円盤の動きをシミュレートするプログラムをfix関数で書いてください。

ちなみに再帰関数を使うと、

```haskell
type Tower = [[Int]]

-- 円盤を1枚iからjに移動
move :: Int -> Int -> State Tower ()
move i j = do
    tw <- get
    let k = 3 - i - j
        ti = tw !! i
        tj = tw !! j
        tk = tw !! k
    
    let (ti', tj') = go (ti, tj)
    put $ build (i, ti') (j, tj') (k, tk)
    where
        go ([], ys)   = ([], ys)
        go (x:xs, ys) = (xs, x:ys)
        key (i, _) (j, _) = compare i j
        build xp yp zp = map snd $ sortBy key [xp, yp, zp]

-- 円盤をn枚iからjに移動
trans :: Int -> Int -> Int -> State Tower ()
trans i j 1 = move i j
trans i j n = do
    let k = 3 - i - j
    trans i k (n - 1)
    trans i j 1
    trans k j (n - 1)

solve n = execState (trans 0 2 n) tw
    where tw = [[1..n], [], []]

-- solve 5
-- [[], [], [1, 2, 3, 4, 5]]
```

と書けます。

<details><summary>解答例</summary><div>

再帰形になっているのは関数`trans`の部分なので、そこをfix関数で書き直せばよいですね。
今回は引数の数が３つに増えているので、その点に注意して書き直しましょう。

```haskell
type Tower = [[Int]]

-- 円盤を1枚iからjに移動（そのまま）
move :: Int -> Int -> State Tower ()
move i j = do
    tw <- get
    let k = 3 - i - j
        ti = tw !! i
        tj = tw !! j
        tk = tw !! k
    
    let (ti', tj') = go (ti, tj)
    put $ build (i, ti') (j, tj') (k, tk)
    where
        go ([], ys)   = ([], ys)
        go (x:xs, ys) = (xs, x:ys)
        key (i, _) (j, _) = compare i j
        build xp yp zp = map snd $ sortBy key [xp, yp, zp]

-- 円盤をn枚iからjに移動（fixで書き直し）
trans' :: Int -> Int -> Int -> State Tower ()
trans' = fix g where
    g f i j 1 = move i j
    g f i j n = do
        let k = 3 - i - j
        f i k (n - 1)
        f i j 1
        f k j (n - 1)

solve n = execState (trans' 0 2 n) tw
    where tw = [[1..n], [], []]

-- solve 5
-- [[], [], [1, 2, 3, 4, 5]]
```

</div></details>

### 3. 動的計画法（難易度★★）

fix関数の[活用法５](#活用法５メモ化)では、fix関数を使ってメモ化ができると紹介しました。

メモ化が有効に活用できる分野は非常に多いですが、その中でも動的計画法（DP）ではメモ化が中心的な役割を果たしています。

次の問題を動的計画法で解くプログラムを書いてみてください。なお、メモ化を忘れずに！！

>N 個の足場があって、i 番目の足場の高さは hi です。
最初、足場 1 にカエルがいて、ぴょんぴょん跳ねながら足場 N へと向かいます。カエルは足場 i にいるときに

>足場 i から足場 i+1 へと移動する (そのコストは |hi−hi+1|)
足場 i から足場 i+2 へと移動する (そのコストは |hi−hi+2|)
のいずれかの行動を選べます。カエルが足場 1 から足場 N へと移動するのに必要な最小コストを求めよ。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/126131/2773ce55-1665-8001-f6e8-418109f64c04.png)

([動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集](https://qiita.com/drken/items/dc53c683d6de8aeacf5a#%E3%82%AD%E3%83%BC%E3%83%9D%E3%82%A4%E3%83%B3%E3%83%88)より引用)

ヒントとして、テストケースとPythonでの解答例を載せておきます。

|N|hs|最小コスト|
|-|-|-|
|4|10, 30, 40, 20|30|
|2|10, 10|0|
|6|30, 10, 60, 10, 60, 50|40|
|7|2,9,4,5,1,6,10|8|

```python:Python
inf = 1000000 # すごく大きな数

def solve(N, hs):
    dp = [0] * N
    
    def cost(i, j):
        if i < 0:
            return inf
        else:
            return dp[i] + abs(hs[j] - hs[i])

    for i in range(1, N):
        dp[i] = min (cost(i - 2, i), cost(i - 1, i))
    
    return dp[N - 1]
```

<details><summary>解答例</summary><div>

メモの型は`[(Int, Int)]`で、その意味は`[(i, 足場iまでの最小コスト)]`としました。

足場の高さのリスト`hs`にアクセスするために、足場の番号もメモに含める必要があります。

```haskell
-- 足場iから足場jへと移動するときのコスト
cost :: [Int] -> Int -> Int -> Int
cost hs i j = abs (hi - hj) where
    hi = hs !! i
    hj = hs !! j

-- 足場iまでの最小コストと足場j(=i+1)までの最小コストから、
-- 足場k(=i+2)までの最小コストを計算
calc :: [Int] -> (Int, Int) -> (Int, Int) -> (Int, Int)
calc hs (i, wi) (j, wj) | i + 1 == j = 
    let k = j + 1
        ci = wi + cost hs i k
        cj = wj + cost hs j k
    in (k, min ci cj)

-- 足場nまでの最小コストを動的計画法で計算
solve :: Int -> [Int] -> Int
solve n hs = snd $ (!! (n - 1)) $ fix g where
    g ws = (0, 0):(1, cost hs 1 0):zipWith (calc hs) ws (tail ws)

-- solve 7 [2, 9, 4, 5, 1, 6, 10]
-- 8
```

足場の番号をメモに含めたくない場合は、zipWith関数ではなくmap関数を使い、メモのベースとなるリストから足場の番号を取得するとよいです。

```haskell
inf :: Int
inf = 100000 -- すごく大きな数

-- 足場iから足場jへと移動するときの足場jでの最小コストを計算
cost :: [Int] -> [Int] -> Int -> Int -> Int
cost hs ws i j
    | i < 0 = inf
    | otherwise = wi + abs (hi - hj) where
        wi = ws !! i
        hi = hs !! i
        hj = hs !! j

-- 足場(n-2)までの最小コストと足場(n-1)までの最小コストから、
-- 足場nまでの最小コストを計算
calc :: [Int] -> Int -> [Int] -> Int
calc hs n ws = 
    let ci = cost hs ws (n - 1) n
        cj = cost hs ws (n - 2) n
    in min ci cj

-- 足場nまでの最小コストを計算
solve :: Int -> [Int] -> Int
solve n hs = (!! (n - 1)) $ fix $ \ws ->
                let f 0 = 0            -- 足場の番号が0のとき
                    f i = calc hs i ws -- 足場の番号がiのとき
                in map f [0..] -- 足場の番号のリスト

-- solve 7 [2, 9, 4, 5, 1, 6, 10]
-- 8
```

</div></details>

## 参考文献

### fix関数

- [不動点と再帰 - Wiki](https://ja.wikibooks.org/wiki/Haskell/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%81%A8%E5%86%8D%E5%B8%B0)
- [Haskellのループ処理は flip fix でだいたい書けそう - Qiita](https://qiita.com/lotz/items/0894079a44e87dc8b73e)
- [MonadFix is Time Travel](https://elvishjerricco.github.io/2017/08/22/monadfix-is-time-travel.html)
- [Fix and recursion - Wiki](https://en.wikibooks.org/wiki/Haskell/Fix_and_recursion)
- [おとうさんにもわかるYコンビネータ！(絵解き解説編)](https://r-west.hatenablog.com/entry/20090417/1239972722)
- [不動点とfix演算子](https://succzero.hatenablog.com/entry/2015/06/18/022428)
- [不動点コンビネータ - Wikipedia](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF#:~:text=%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF%EF%BC%88%E3%81%B5%E3%81%A9%E3%81%86,%E6%B1%82%E3%82%81%E3%82%8B%E9%AB%98%E9%9A%8E%E9%96%A2%E6%95%B0%E3%81%A7%E3%81%82%E3%82%8B%E3%80%82&text=%E3%81%93%E3%81%93%E3%81%A7%E9%96%A2%E6%95%B0f%E3%81%AE,x%E3%81%AE%E3%81%93%E3%81%A8%E3%82%92%E3%81%84%E3%81%86%E3%80%82)

### 遅延評価

- [正格性のすべて (翻訳)](https://haskell.e-bigmoon.com/posts/2018/06-25-all-about-strictness)
- [正格評価と遅延評価（詳細編）](https://qiita.com/ruicc/items/31a269f93404268d80d7)
- [遅延評価の仕組み](https://xtech.nikkei.com/it/article/COLUMN/20070305/263828/)
- [Graph reduction - Wiki](https://en.wikibooks.org/w/index.php?title=Haskell/Graph_reduction)
- [サンクの構造を見る](https://qiita.com/ruicc/items/4db532d33e648fca5b99)
- [反駁不可パターン](https://scrapbox.io/mrsekut-p/%E5%8F%8D%E9%A7%81%E4%B8%8D%E5%8F%AF%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3)
- [Strict拡張を使用する際の注意点](https://haskell.jp/blog/posts/2020/strict-gotchas.html)
- [Weak head normal form - Wiki](https://en.wikipedia.org/wiki/Lambda_calculus_definition#Weak_head_normal_form)
- [Thunk - Wikipedia](https://en.wikipedia.org/wiki/Thunk)

### ソースコード
- [fix](https://hackage.haskell.org/package/base-4.16.0.0/docs/src/Data.Function.html#fix)

[^1]: fix関数が再帰形で定義されているので、実質的には再帰関数のままです。つまり、再帰関数を使うときに起こる、スペースリークや関数呼び出しのオーバーヘッドといった問題は、fix関数で書き直すことでは解消されません。
[^2]: [ループを再帰関数にする考え方](https://qiita.com/ozwk/items/4ffdba8e83df1171ac39)に実例が載っています。
[^3]: 関数`f`の値を決めるために、引数`x`の値が必要なことを、関数`f`は引数`x`について正格であると言います。詳しくは、[fixと不動点 - Wiki](https://ja.wikibooks.org/wiki/Haskell/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%81%A8%E5%86%8D%E5%B8%B0#fix_%E3%81%A8%E4%B8%8D%E5%8B%95%E7%82%B9)を参照してください。