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

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)

Answer 2

Either 在您的 euc 和 apo 中扮演着不同的角色。您正在使用 Left 表示递归基本情况，而 apo 使用 Left 表示核心递归的提前终止（即添加一个额外条件来中断展开）。但是，如果您想使用展开来表达您的算法，则无需提前终止，前提是要展开足够的结构：

{-# LANGUAGE TemplateHaskell, TypeFamilies, KindSignatures #-}
{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
{-# LANGUAGE LambdaCase #-}
import Data.Functor.Foldable
import Data.Functor.Foldable.TH

data Delayed a = Done a | Waiting (Delayed a)
    deriving (Show)
makeBaseFunctor ''Delayed

ghci> :info DelayedF
data DelayedF a r = DoneF a | WaitingF r

psi :: Integral i => (i, i) -> DelayedF i (i, i)
psi (x, y) = case x `mod` y of
    0 -> DoneF y
    m -> WaitingF (y, m)

psi 是 Delayed 的余代数，ana psi 展开一个 Delayed 结构，其 GCD 在其末端：

ghci> delayedGCD = ana psi (14,35) :: Delayed Integer
ghci> delayedGCD
Waiting (Waiting (Done 7))

为了得到最终结果，我们必须消耗 Delayed:

ghci> cata (\case { DoneF n -> n; WaitingF n -> n }) delayedGCD
7

鉴于我们正在做一个 ana，然后是一个 cata，我们最好切换到 hylo，这样可以有效地组合它们：

ghci> hylo (\case { DoneF n -> n; WaitingF n -> n }) psi (14,35)
7

此时，我们可能会注意到 DelayedF 与 Either 同构。因为对于我们目前的目的，我们只需要 hylo，而不是单独使用 ana 或 cata，实际上可以用 Either 替换 DelayedF 并跳过完全定义 Delayed（注意 hylo 的类型没有提到隐含的递归数据结构，只提到它对应的基函子）：

euclid :: Integral a => a -> a -> a
euclid x y = hylo (either id id) psi (x, y)
    where
    psi :: Integral i => (i, i) -> Either i (i, i)
    psi (x, y) = case x `mod` y of
        0 -> Left y
        m -> Right (y, m)

ghci> euclid 14 35
7

因此我们达到了，这是有效的，因为 Either 是一个数据结构的基本仿函数，它以某种方式具体化了你的递归算法。

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

Is this some kind of morphism in the recursion-schemes?

haskell

recursion-schemes

euclidean-algorithm