4

Euclid のアルゴリズムは、最初は次のように実装しました。

euclid x 0 = x
euclid x y = euclid y (x `mod` y)

アルゴリズムは末尾再帰で、 recursion-schemesで直感的に書けると思います。そして、次のeucは再帰部分の抜粋です。このeuclid関数はeucを使用しますが、psiはワンステップ処理に専念しています。

euc :: (a -> Either t a) -> a -> t
euc psi = either id (euc psi) . psi

euclid :: Integral a => a -> a -> a
euclid x y = euc psi (x, y)
  where psi (x, y) | m == 0    = Left  y
                   | otherwise = Right (y, m)
          where m = x `mod` y

euc関数はapo射に似ていますが、 apoeucに特化する方法がわかりません。それらはまったく別のもののように私には思えます。再帰スキームである種のモーフィズムとしてeucを書くことは可能ですか?

apo :: Functor f => (t -> f (Either (Fix f) t)) -> t -> Fix f
apo psi = In . fmap (uncurry either (id, apo psi)) . psi

よろしく。

4

2 に答える 2