I implemented Euclid's algorithm in the following way at first.
euclid x 0 = x
euclid x y = euclid y (x `mod` y)
The algorithm is tail-recursion, and I expect that it can be intuitively written with recursion-schemes. Then, the following euc is an extract of the recursive part. This euclid function uses euc, while psi is devoted to one-step processing.
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
The euc function looks like the apo morphism, but I don't know how to specialize apo to euc. It seems to me that they are completely different things. Is it possible to write euc as some kind of morphism in recursion-schemes?
apo :: Functor f => (t -> f (Either (Fix f) t)) -> t -> Fix f
apo psi = In . fmap (uncurry either (id, apo psi)) . psi
Regards.
I came up with this solution using apomorphism: Using the Delayed structure from @duplode would probably make this code better.
gcd' x y = cata alg $ apo coalg (x, y)
where
alg NilF = 0
alg (ConsF a b) = a + b
coalg (a, b) = case a `mod` b of
0 -> ConsF b (Left (Fix NilF))
m -> ConsF 0 $ Right (b, m)