Haskell の Stream Fusion は不完全？Step 型のデータ構築子が一つ足りない？？？

タイトルの通り、「Haskell の Stream Fusion は不完全？Step 型のデータ構築子が一つ足りない？？？」などと素朴に思った。おそらく誤った感想なわけだが、考えるまでもなく当たり前なためか、もしくは深淵なる理由があるのか。私の考えの誤りを明確化してくれる資料が見つからなかった。

知ってる人が居たら教えてください。



# 実際の Step 型の定義と、私が思う定義

## 実際の定義

[実際の定義](https://hackage.haskell.org/package/stream-fusion-0.1.2.5/docs/Data-Stream.html)は次の３つのデータ構築子から成る。

* `Yield a !s`は、生成された型`a`の値と、次のステップのタネ（seed）となる型`s`の値を持っている。
* `Skip !s`は、次のステップのタネとなる型`s`の値のみを持っている。
* `Done`は、終了（次のステップがないこと）を表す。

```.hs
data Step a s = Yield  a !s
              | Skip     !s
              | Done
```


## 私の思う定義

データ構築子として`Return`を増やしている。`Return a`は、`Done`と同じように終了を表すが、`Yield a !s`のように生成された型`a`の値を持っている。

```.hs
data Step a s = Yield  a !s
              | Skip     !s
              | Return a
              | Done     
```

この命名に合わせるなら`Skip`は`Continue`に、`Done`は`Break`と読み替えるべきかもしれない。それはともかく、型引数の`a`と`s`の有る無しの組み合わせとして４通りないと気持ち悪くない？というのが私の疑問である。


         | 返り値なし | 返り値あり
---------+------------+------------
**終了** | Done       | Return a
**継続** | Skip !s    | Yield a !s


# 末尾再起かつ、末尾余再帰として考えるならやっぱりもう一個欲しい

そんな個人のお気持ちの話をされても困るだろうか。一応、理論的にも４通りの方が綺麗じゃないか、という話をしておく。


## 末尾余再帰の埋め込み

Stream Fusion の`Yield a !s`と`Done`を抜き出せば、これは`Just (a, !s)`と`Noting`の表記を変えただけで、実質的には同じものだろう。つまり`Maybe (a, !s)`は`Step a s`に埋め込まれている。

そういえば、`Stream`型の定義を転記していなかった。

```.hs
data Stream a = forall s. Unlifted s =>
                          Stream !(s -> Step a s)
                                 !s              
```

今、注目したいのは`Stream`型が`s -> Step a s`と`s`の組であるという点である。これはリストの`unfoldr`の引数の型と非常に似ている。

```.hs
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
```

`Maybe (s, !a)`は`Step s a`に埋め込まれているのだから、`unfoldr`の引数の型が`Stream`に埋め込まれていると言える。`unfoldr`はリストを生成するが、カッコつけて言えば末尾余再帰である。つまるところ、`Stream`には末尾余再帰が埋め込まれている。


## 末尾再帰の埋め込み

`Skip !s`と`Return a`を抜き出せば、これは`Right !s`と`Left a`の表記を変えただけで、実質的には同じものだろう。つまり`Either a !s`は`Return a`を加えた`Step a s`に埋め込まれている。さて、末尾余再帰の`unfold`から類推して次のような型を持つ関数を考えてみる。

```.hs
runTailRec :: (b -> Either a b) -> b -> a
runTailRec f x = case f x of
    Left  z -> z
    Right y -> runTailRec f y
```

もはや名前でネタバレしているが、これは末尾再帰（の各ステップを実行する関数）になる。例えば、次のような`factStep`を定義し`runTailRec`に食わせると階乗（`fact`）が計算できる。

`factStep`は`n`が 1 以下であれば、計算結果として`r`を返す。そうでなければ、`n`をデクリメントしつつ、`n * r`を途中結果として計算する。この`factStep`を`Left r`になるまで、連続して実行すれば階乗を計算できる。そして、その`Left`になるまで実行する関数が`runTailRec`である。

```.hs
factStep :: (Int, Int) -> Either Int (Int, Int)
factStep (n, r)
    | n <= 1    = Left r
    | otherwise = Right (n - 1, n * r)

fact :: Int -> Int
fact n = runTailRec factStep (n, 1)

main = putStrLn . show $ fact 5
-- 120
```


末尾呼び出しをスタックセーフにするトランポリンという技法に似ていると感じる人もいるだろう。実のところ、`runTailRec`は末尾再帰に特化させたトランポリンと言える。もっとも、末尾再帰最適化が有効な言語では不要な技法かもしれない。

話を戻そう、`Either a !s`は`Return a`を加えた`Step a s`に埋め込まれているのだから、`runTailRec`の引数の型が`Stream`に埋め込まれていると言える。そして、`runTailRec`は末尾再帰である。つまるところ、`Return a`を加えた`Stream`には末尾再帰が埋め込まれる。

末尾再帰（tail recursion）と末尾余再帰（tail corecursion）の両方、いわば末尾双再帰（tail dual recursion）を埋め込んだほうが理論的には綺麗ではないだろうか。



# `s`を`Maybe`で包めばいいだけと言われればそうなんだけど…

まあ、`Yield x y`を`Yield x (Just y)`で、`Return x`を`Yield x Nothing`で代替すれば、わざわざ`Return x`なんて用意しなくてもいいと言われてしまえば、反論しにくいところはある（`Skip Nothing`は`Done`とみなす）。

ただ、それなら、`Yield x y`を`Yield (Just x) y`で、`Skip y`を`Yield Nothing y`で代替してもいいという話に発展しそうで、それはそれで嫌なのだ。


# おわり

書き出してみると、的外れな考えだから答えがみつからないというのが真実っぽいな。


# 追記（自己解決）

いや、末尾再起で余再帰作るんだから、戻り値の型が`Either (Maybe (a, s)) s`になる関数を考えるべきで、`(1 + a * s) + s = a * s + s + 1`なんだから`a * s`にあたる`Yield`, `s`にあたる`Skip`, `1`にあたる`Done`の三つで正しいわ。