4

我最初是通过以下方式实现欧几里得算法的。

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

问候。

4

2 回答 2

3

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

euc = hylo $ either id id

我还找到了一种将其写为 Elgot 代数的方法：

import Data.Functor.Identity
euc psi = elgot runIdentity (fmap Identity . psi)
于 2021-10-26T03:01:04.043 回答
2

Eithereuc在你和中扮演不同的角色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

鉴于我们正在执行 aana后跟 a cata，我们最好切换到hylo，它可以有效地组合它们：

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

此时，我们可能会注意到 与DelayedF同构Either。因为对于我们当前的目的，我们只需要hylo，而不是单独地ana，cata实际上可以完全替换DelayedF并Either跳过定义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

因此我们得到了Joseph Sible 的hylo解决方案，它之所以有效，是因为Either它是数据结构的基本函子，它以某种方式实现了您的递归算法。

于 2021-10-26T05:16:09.800 回答