Free monad hoistFree implementation.

[Mic43]

Is there a possibility to implement hoistFree, from Haskell free monad in C#?
I've recently found this great project, which, as I found, is doing something I'm implementing myself in order to learn Haskell.
One thing i struggle to implement is aforementioned higher order function, which given a function transforming two different functors of the same type and free monad built upon first functor, produces free monad upon second functor:
hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b
My (not finished) implementation looks like this:

(...)
public static IKind<Free<TFunctorB>, T> Hoist<T, V, TFunctorB>(
Func<IKind<TFunctor, V>, 
IKind<TFunctorB, V>> fun,
IKind<Free<TFunctor>, T> free) where TFunctorB : IFunctor<TFunctorB>
{
  switch (free.To())
  {
      case Pure<TFunctor, T> pure:
          return Free<TFunctorB>.Pure(pure.Value);
      case Roll<TFunctor, T> roll:
          var res = TFunctor.Map(roll.Free, free => Hoist(fun, free).To());
          fun(res);

      default:
          throw new ArgumentOutOfRangeException();
  }
}

The problem is that compiler does not allow calling fun(res) because it cannot convert from IKind<TFunctor,Free<TFunctorB, T>> to IKind<TFunctor, V>. Is there a workaround to this?

[louthy]

I can show you with the Free monad built in to language-ext. Which you can adapt to your implementation...

The first thing to notice from the original signature:

hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b

... is that there's a forall a embedded within it. That forall a is like having another generic parameter in the middle of the definition.

It can't be represented in C#. See below, where the asterisks are, they're generic on usage of f, not on usage of Hoist.

Free<G, B> Hoist<F, G, B>(Func<F<*>, G<*>> f, Free<F, B> fb)

We can get around this though. But we can't use Func...

If you know your category-theory, then f a -> g a should be instantly recognisable as a Natural Transformation.

So, if we create a type called Natural to represent that transformation:

public interface Natural<out F, in G>
{
    public static abstract K<G, A> Transform<A>(K<F, A> fa);
}

Notice how the A isn't attached to the Natural signature, but instead to the Transform method. This allows us to provide the generic parameter 'late'.

We can now implement Hoist:

public static Free<G, B> Hoist<N, F, G, B>(Free<F, B> fb)
    where N : Natural<F, G>
    where F : Functor<F>
    where G : Functor<G> =>
    fb switch
    {
        Pure<F, B>(var x)  => Free.pure<G, B>(x),
        Bind<F, B>(var xs) => Free.bind(N.Transform(xs).Map(Hoist<N, F, G, B>))
    };

You'll notice the implementation is almost exactly the same as the Haskell version:

hoistFree :: Functor g => (forall a. f a -> g a) -> Free f b -> Free g b
hoistFree _ (Pure a)  = Pure a
hoistFree f (Free as) = Free (hoistFree f <$> f as)#

The main difference is that f (the variable, not the type) has become N and the invocation of f as has been replaced with N.Transform(xs).

Next you'll need to define the natural-transformations for the types that support it. Here's an example of Option -> Seq:

public class OptToSeq : Natural<Option, Seq>
{
    public static K<Seq, A> Transform<A>(K<Option, A> fa) => 
        fa.As().Match(Some: Seq, None: Seq<A>);
}

Then you can invoke it with a lifted functor:

var fa = Free.pure<Option, int>(100);
var ga = Hoist<OptToSeq, Option, Seq, int>(fa);

I've got some prototypes of a Natural type that I'll be adding the language-ext eventually, but hopefully in the meantime this is useful to you 👍

[Mic43]

Thanks very much. I've noticed 'forall' but I thought that adding another generic parameter will suffice. Of course it's not case, cause the Func must work for all possible functor's type parameters, not only for type specified for specific Hoist call, to mimic Haskell definition.
Just as You mentioned, now I see it.
Your workaround is a very nice idea. I will surely use it in my project :)

[Mic43]

Again thanks for support, I managed to implement natural transformation You mentioned via standard interface:

public interface INaturalTransformation<TFunctorA,TFunctorB>
    where TFunctorA:IFunctor<TFunctorA>
    where TFunctorB:IFunctor<TFunctorB>
{
    public IKind<TFunctorB, T> Transform<T>(IKind<TFunctorA, T> functor);
}

Interface overload is passed to Hoist as standard input parameter.
Everything works fine, now I can map between sub DSL's and combined DSL easily, without too much boilerplate.

[louthy]

That was my first approach, but it's slightly less efficient, so I figured the static approach would be better (even if it requires a few more generic parameters to be specified)

[Mic43]

Do You mean "less efficient" in terms of raw performance?

[louthy]

It avoids the need to allocate the natural-transformation type. This is useful because for nearly all pairs of functors (where a natural transformation exists), there's usually only one viable transformation.

You see it throughout this library: ToIO(), ToEither(), ToOption(), etc, they're all singular natural-transformations between two functors.

Not that there aren't pairs of functors where there are more viable transformations, but it's more rare.

There's also a little bit of bias (in my preference) for a static approach. My plan for language-ext is to use Natural<F, G> as a trait for types that support natural-transformations.

So, for example, the Option trait-implementations might look like this:

public class Option : 
    Monad<Option>, 
    Fallible<Unit, Option>,
    Traversable<Option>, 
    Alternative<Option>,
    Natural<Option, Arr>,
    Natural<Option, Lst>,
    Natural<Option, Seq>,
    Natural<Option, Iterable>,
    Natural<Option, Eff>,
    Natural<Option, OptionT<IO>>,
    Natural<Option, Fin>
{
   ...

    static K<Arr, A> Natural<Option, Arr>.Transform<A>(K<Option, A> fa) => 
        fa.As().ToArr();

    static K<Lst, A> Natural<Option, Lst>.Transform<A>(K<Option, A> fa) => 
        fa.As().ToLst();

    static K<Seq, A> Natural<Option, Seq>.Transform<A>(K<Option, A> fa) => 
        fa.As().ToSeq();

    static K<Iterable, A> Natural<Option, Iterable>.Transform<A>(K<Option, A> fa) => 
        fa.As().ToIterable();

    static K<Eff, A> Natural<Option, Eff>.Transform<A>(K<Option, A> fa) => 
        fa.As().ToEff();

    static K<OptionT<IO>, A> Natural<Option, OptionT<IO>>.Transform<A>(K<Option, A> fa) => 
        fa.As().ToIO();

    static K<Fin, A> Natural<Option, Fin>.Transform<A>(K<Option, A> fa) => 
        fa.As().ToFin();

   ...
}

Which supports all the To* functions attached to Option<A>.

I can then have a different hoist implementation:

public static Free<G, A> hoist<F, G, A>(Free<F, A> fb)
    where F : Natural<F, G>, Functor<F>
    where G : Functor<G> =>
    fb switch
    {
        Pure<F, A>(var x)  => pure<G, A>(x),
        Bind<F, A>(var xs) => bind(F.Transform(xs).Map(hoist<F, G, A>)),
        _                  => throw new NotSupportedException()
    };

This assumes that F is both a Functor and has a Natural<F, G> implementation.

Invocation then becomes more elegant:

Free.hoist<Option, Seq, int>(fa)

No need for a separate N argument.

So yeah, slight performance benefit, but also (for this library, at least) simpler usability once all the types have implemented their Natural traits. It would still be possible to take a more ad-hoc approach (as I implemented before), but this makes the happy path easy.