haskellrecursion-schemeseuclidean-algorithm

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


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.


Solution

  • 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)