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

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

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

実際の定義

実際の定義は次の３つのデータ構築子から成る。

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

data Step a s = Yield  a !s
              | Skip     !s
              | Done

私の思う定義

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

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型の定義を転記していなかった。

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

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

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から類推して次のような型を持つ関数を考えてみる。

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である。

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の三つで正しいわ。

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