Est-ce une sorte de morphisme dans les schémas de récursion ?

Question

Au début, j'ai implémenté l'algorithme d'Euclide de la manière suivante.

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

L'algorithme est une récursion de queue, et je m'attends à ce qu'il puisse être écrit intuitivement avec schémas de récursion . Alors, les éléments suivants euc est un extrait de la partie récursive. Ce site euclide la fonction utilise euc alors que psi est consacré au traitement en une étape.

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

El euc ressemble à la fonction apo morphisme, mais je ne sais pas comment spécialiser apo a euc . Il me semble que ce sont des choses complètement différentes. Est-il possible d'écrire euc comme une sorte de morphisme dans les schémas de récursion ?

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

Regards.

Answer 1

Je ne sais pas si on peut l'écrire comme un apomorphisme, mais je vois une façon de l'écrire comme un hylomorphisme :

euc = hylo $ either id id

J'ai aussi trouvé un moyen de l'écrire comme une algèbre d'Elgot :

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

Answer 2

Either joue différents rôles dans votre euc et en apo . Vous utilisez Left pour signaler un cas de base récursif, tandis que apo utilise Left pour signaler la fin précoce d'une corecursion (c'est-à-dire pour ajouter une condition supplémentaire pour interrompre un unfold). Si vous voulez exprimer votre algorithme en utilisant un unfold, cependant, il n'y a pas besoin de terminaison anticipée, en supposant une structure adéquate à déplier :

{-# 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 est une coalgebra pour Delayed y ana psi déploie un Delayed structure avec le GCD à son extrémité :

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

Pour obtenir le résultat final, il faut consommer le Delayed :

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

Étant donné que nous faisons un ana suivi d'un cata nous ferions mieux de passer à hylo qui les combine efficacement :

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

A ce stade, nous pouvons noter que DelayedF est isomorphe à Either . Puisque pour nos besoins actuels, nous n'avons besoin que de hylo par opposition à ana o cata de manière isolée, il est en fait possible de remplacer DelayedF con Either et de ne pas définir Delayed tout à fait (notez le type de hylo ne mentionne pas la structure de données récursive implicite, mais seulement le foncteur de base correspondant) :

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

Et ainsi nous arrivons Joseph Sible hylo solution ce qui fonctionne parce que Either est un foncteur de base pour une structure de données qui matérialise en quelque sorte votre algorithme récursif.