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

`Either`

plays differents roles in your `euc`

and in `apo`

. You are using `Left`

to signal a recursive base case, while `apo`

uses `Left`

to signal early termination of corecursion (that is, to add an extra condition for interrupting an unfold). If you want to express your algorithm using an unfold, though, there is no need for early termination, assuming an adequate structure to be unfolded:

```
{-# 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`

is a coalgebra for `Delayed`

, and `ana psi`

unfolds a `Delayed`

structure with the GCD at its end:

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

To get the final result, we have to consume the `Delayed`

:

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

Given we are doing an `ana`

followed by a `cata`

, we'd better switch to `hylo`

, which efficiently combines them:

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

At this point, we might note that `DelayedF`

is isomorphic to `Either`

. Since for our current purposes we only need `hylo`

, as opposed to `ana`

or `cata`

in isolation, it is actually possible to replace `DelayedF`

with `Either`

and skip defining `Delayed`

altogether (note the type of `hylo`

doesn't mention the implied recursive data structure, only its corresponding base functor):

```
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
```

And thus we reach Joseph Sible's `hylo`

solution, which works because `Either`

is a base functor for a data structure that in some way materialises your recursive algorithm.

- Using pattern synonyms to abstract implementation of text type
- How to avoid listing A as build dependency for internal library/executable E just because E depends on internal library L which depends on A?
- How is the Foldable instance of (,) useful?
- What is the proper way of wrapping an Int (not a general type) in another type if type safety is the only motive?
- What is the most practical way to express a dependency on a library for which we have a local git repository with some changes?
- Htmx POST to haskell servant handling optional field in FormUrlEncoded request
- Haskell fails to infer the return type of a monad after using the sequence operator
- Does extracting values from a multiple Value return in Haskell invoke the function more than once?
- How to specify c/c++ compiler on stack install command
- Why do I get "Unexpected reply type" from notify-send when using this Haskell notification server?
- Don't understand notation of morphisms in Monoid definition
- Foldln in haskell
- Is this property of a functor stronger than a monad?
- How to Instantiate a Custom Data Type with Record Syntax and Multiple Constructors
- How do I make a minimal working example for the a DBus server?
- Is it safe to downgrade Haskell stack version?
- Haskell, list of natural number
- unfamiliar syntax in Haskell / Clash function type signature
- foldM with monad State does not type check
- Why does my Runge-Kutta implementation oscillate to 0?
- How do I get the desired behavior in my TCP server?
- Why does the Haskell PVP describe new functions as non-breaking?
- How do I correctly use toLower in Haskell?
- How can I write a notification server in Haskell?
- Every Lens' is a Traversal'... how?
- How do I crate a value of type a{sv} for a call to org.freedesktop.Notifications.Notify via DBus?
- Web Scraping With Haskell
- Double exclamation marks in Haskell
- Haskell Servant POST FormUrlEncoded for (Vector String) field
- Confusion about list types in Haskell