haskell - 这是递归方案中的某种态射吗？

Question

我最初是按照下面的方式实现欧几里德算法的。

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态射，但我不知道如何将 apo 专门化为 euc。在我看来，它们是完全不同的东西。是否可以将 euc 写成递归方案中的某种态射？

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

问候。

Answer 1

我不知道你是否可以把它写成同态，但我确实看到了一种你可以把它写成同态的方法:

euc = hylo $ either id id

我还找到了一种将它写成 Elgot 代数的方法:

import Data.Functor.Identity
euc psi = elgot runIdentity (fmap Identity . psi)