Zenn
💡

RustでExtensible Effectsをやろうとした記録

2023/07/30に公開
Rust
idea

はじめに

残念ながら、これはRustでExtensible Effectsをやろうとしたけど上手くいってない記録です。
RustでFree Monadをやることはできます。次にExtensible　Effectsをやろうとするのは自然な欲求ですが、後一歩（？）で出来ていません。とはいえ試行錯誤の結果をお蔵入りにするより、公開した方が同様のことを考えている人の役に立つかもしれないのでIdeaとして記事にしてみました。

Free Monad

Free Monadまではリンクした記事通りです。

trait HKT {
    type H<T>;
}

trait Functor: HKT {
    fn fmap<F, A, B>(f: F, fa: Self::H<A>) -> Self::H<B>
    where
        F: FnOnce(A) -> B;
}

trait Monad: Functor {
    fn pure<A>(t: A) -> Self::H<A>;
    fn bind<F, A, C>(f: F, ma: Self::H<A>) -> Self::H<C>
    where
        F: FnOnce(A) -> Self::H<C>;
}

enum Free<F: Functor, A> {
    Pure(A),
    Join(Box<F::H<Free<F, A>>>),
}

struct FreeMonad<F> {
    _type: PhantomData<F>,
}

impl<F: Functor> HKT for FreeMonad<F> {
    type H<T> = Free<F, T>;
}

impl<F: Functor> Functor for FreeMonad<F> {
    fn fmap<G, A, B>(f: G, fa: Self::H<A>) -> Self::H<B>
    where
        G: FnOnce(A) -> B,
    {
        match fa {
            Free::Pure(v) => Free::Pure(f(v)),
            Free::Join(value) => Free::Join(Box::new(F::fmap(|v| FreeMonad::fmap(f, v), *value))),
        }
    }
}

impl<F: Functor> Monad for FreeMonad<F> {
    fn pure<T>(t: T) -> Free<F, T> {
        Free::Pure(t)
    }
    fn bind<G, A, C>(f: G, ma: Self::H<A>) -> Self::H<C>
    where
        G: FnOnce(A) -> Self::H<C>,
    {
        match ma {
            Free::Pure(v) => f(v),
            Free::Join(value) => Free::Join(Box::new(F::fmap(|v| FreeMonad::bind(f, v), *value))),
        }
    }
}

fn lift_f<F: Functor, A>(fa: F::H<A>) -> Free<F, A> {
    Free::Join(Box::new(F::fmap(|a| Free::Pure(a), fa)))
}

こんな感じで実装すると、FunctorをMonadにすることができます。

// WriterはWrite Functor
type WriterMonad<W> = FreeMonad<Writer<W>>;

詳しい使い方はリンク先を参照ください。

Extensible Effectsを目指して

さて、この資料によれば、Extensible Effects Effは、UnionをOpen Unionとすれば、
Eff r a = Free Union r a
です(CPS変換は除く）　。

まず第一の関門はOpen Unionでした。RustでOpen Unionって。。。と数ヶ月考え、frunk crateのCoproductに行きつきました。
https://docs.rs/frunk/latest/frunk/coproduct/enum.Coproduct.html

これを使うと、以下のように「後一歩まで」実装できます。
まずOpen Unionを実装します。

struct Void {}

impl HKT for Void {
    type H<T> = Void;
}

impl Functor for Void {
    fn fmap<F, A, B>(f: F, fa: Self::H<A>) -> Self::H<B>
    where
        F: FnOnce(A) -> B,
    {
        fa
    }
}

impl<F: Functor> HKT for Coprod!(F) {
    type H<T> = Coprod!(F::H<T>);
}

impl<F: Functor> Functor for Coprod!(F) {
    fn fmap<E, A, B>(f: E, fa: Coprod!(F::H<A>)) -> Coprod!(F::H<B>)
    where
        E: FnOnce(A) -> B,
    {
        let uninjected = fa.extract();
        Coproduct::inject(F::fmap(f, uninjected))
    }
}

impl<F: Functor, G: Functor> HKT for Coprod!(F, G) {
    type H<T> = Coprod!(F::H<T>, G::H<T>);
}

impl<F: Functor, G: Functor> Functor for Coprod!(F, G) {
    fn fmap<E, A, B>(f: E, fa: Coprod!(F::H<A>, G::H<A>)) -> Coprod!(F::H<B>, G::H<B>)
    where
        E: FnOnce(A) -> B,
    {
        let uninjected = fa.uninject();
        let ret = match uninjected {
            Ok(v) => Coproduct::inject(F::fmap(f, v)),
            Err(v) => {
                let v = v.uninject();
                match v {
                    Ok(v) => Coproduct::inject(G::fmap(f, v)),
                    Err(_) => panic!("Something Wrong"),
                }
            }
        };
        ret
    }
}

要は、Union[F, G, H]はCoprod(F, Coprod!(G, Coprod!(H, Void)))!として実装します。
本当はCoprod!(F, G, H)の方が綺麗ですが実現方法はわかりません。

次に、Member Traitを実装します。

trait Member<F: Functor>: Functor {
    fn inject<A>(fa: F::H<A>) -> Self::H<A>;
}

impl<F: Functor, G: Functor> Member<F> for Coprod!(F, G) {
    fn inject<A>(fa: F::H<A>) -> Self::H<A> {
        Coproduct::inject(fa)
    }
}

これは、ScalaでExtensible Effectsを実装する記事にあるものと同じく、R: Member<F>でFがRに埋め込めることを表しているつもりです。
しかし、実はここに問題があります。上記の実装では、Coprod!(G, F)にMember<F>がimplできていません。そして単純にimplするのは二重定義となり、不可能です。
他には、Coprod!(H, Coprod!(F, G))もMember<F>を持っていて欲しいですが、これも二重定義になってしまいます。というわけで現状はR: Member<F>と書くのもRの代わりにCoprod!(F, R2)みたいに書くのも変わりません。

さて、そんなわけでうまくいっていないのですが、これを使ったWriter Monadは以下のように実装できます。

type EffMonad<F> = FreeMonad<F>;
type Eff<F, A> = Free<F, A>;
fn lift_eff_<F: Functor, G: Functor + Mem<F>, A>(fa: F::H<A>) -> Eff<G, A> {
    lift_f(G::inject(fa))
}

struct Tell<W, A> {
    a: A,
    w: W,
}
struct Writer<W> {
    _type: PhantomData<W>,
}

impl<W> HKT for Writer<W> {
    type H<T> = Tell<W, T>;
}

impl<W> Functor for Writer<W> {
    fn fmap<F, A, B>(f: F, fa: Self::H<A>) -> Self::H<B>
    where
        F: FnOnce(A) -> B,
    {
        Tell {
            a: f(fa.a),
            w: fa.w,
        }
    }
}

fn tell<W, R: Functor + Mem<Writer<W>>>(w: W) -> Eff<R, ()> {
    lift_eff(Tell { a: (), w })
}

使ってみましょう。

fn run_writer<W, R: Functor, A>(eff: Eff<Coprod!(Writer<W>, R), A>) -> Eff<R, (Vec<W>, A)> {
    match eff {
        Free::Pure(a) => Free::Pure((vec![], a)),
        Free::Join(v) => {
            let v = *v;
            let v: Result<Tell<_, _>, _> = v.uninject();
            let ret = match v {
                Ok(v) => EffMonad::fmap(
                    |(mut ws, a)| {
                        ws.insert(0, v.w);
                        (ws, a)
                    },
                    run_writer(v.a),
                ),
                Err(v) => {
                    let v = v.uninject();
                    match v {
                        Ok(v) => Free::Join(Box::new(R::fmap(run_writer, v))),
                        Err(_) => panic!(""),
                    }
                }
            };
            ret
        }
    }
}

とすれば、

    let a = tell("foo");
    let b = EffMonad::bind(|_| tell("hoge"), a);
    let (vec, _) = run_eff(run_writer(b));

のvecには["foo", "hoge"]が入ります。
次にMaybe Monadを実装してみます。

struct Maybe {}

impl HKT for Maybe {
    type H<T> = Option<T>;
}

impl Functor for Maybe {
    fn fmap<F, A, B>(f: F, fa: Option<A>) -> Option<B>
    where
        F: FnOnce(A) -> B,
    {
        fa.map(f)
    }
}

としてFunctorを定義します。
そうしたら、

fn some<A, R: Functor>(a: A) -> Eff<Coprod!(Maybe, R), A> {
    Eff::Pure(a)
}
fn none<A, R: Functor>() -> Eff<Coprod!(Maybe, R), A> {
    lift_eff(Option::<A>::None)
}
fn run_maybe<R: Functor, A>(eff: Eff<Coprod!(Maybe, R), A>, default: A) -> Eff<R, A> {
    match eff {
        Free::Pure(a) => Free::Pure(a),
        Free::Join(v) => {
            let v = *v;
            let v: Result<Option<_>, _> = v.uninject();
            let ret = match v {
                Ok(_) => Free::Pure(default),
                Err(v) => {
                    let v = v.uninject();
                    match v {
                        Ok(v) => Free::Join(Box::new(R::fmap(|vv| run_maybe(vv, default), v))),
                        Err(_) => panic!(""),
                    }
                }
            };
            ret
        }
    }
}

として、

    let a = some(2);
    let b = EffMonad::bind(|v| some(v + 2), a);
    let ret = run_eff(run_maybe(b, -1)); // 4

    let a = none();
    let b = EffMonad::bind(|v: i32| some(v + 2), a);
    let ret = run_eff(run_maybe(b, -1)); // -1

と使えます。

と、こんな感じに一見上手くいっています。とはいえここまではFree Monadでも良い話です。
やはりExtensible Effectsといったら別のMonadを混ぜることが醍醐味です。そこで、

    let a = tell("foo");
    let b = EffMonad::bind(|_| none(), a);
    let c = EffMonad::bind(|_| tell("hoge"), b);
    let ret = run_eff(run_writer(run_maybe(c, ())));

とやると、これはコンパイルエラーです。

それはそうで、aの型はEff<Coprod!(Writer<&str>, Hoge)>です。しかしEffMonad::bind(|_| none(), a);において欲しいaはEff<Coprod!(Maybe, Foo)>です。そして、Eff<Coprod!(Writer<&str>, Coprod!(Maybe, Hoge))>とEff<Coprod!(Maybe, Coprod!(Writer<&str>, Hoge))>は異なる型です。
残念ながら、ここを突破する方法は思いついていません。

Freer Monad

さて、Extensible EffectsといえばFreer Monadを使いたいところです。ではFreer Monadは実装できるでしょうか？これも、所有権の問題で実現できていません。
Freer Monadは、例えば

struct Coyoneda<F: HKT, A, B>(F::H<A>, Box<dyn FnOnce(A) -> B>); // F[B]

struct CoyonedaFunctor<F: HKT, A> {
    _type: PhantomData<F>,
    _value: PhantomData<A>,
}

impl<F: HKT, A> HKT for CoyonedaFunctor<F, A> {
    type H<T> = Coyoneda<F, A, T>;
}

impl<F: HKT, A> Functor for CoyonedaFunctor<F, A> {
    fn fmap<G, C, D>(f: G, fa: Self::H<C>) -> Self::H<D>
    where
        G: FnOnce(C) -> D,
    {
        Coyoneda(fa.0, Box::new(|v| f(fa.1(v))))
    }
}

// type Freer<F, A, T> = Free<CoyonedaFunctor<F, A>, T>;
// type FreerMonad<F, A> = FreeMonad<CoyonedaFunctor<F, A>>;

とするのが思いつきますが、これは所有権の問題でできません。とにかく合成関数をメンバーとして持っておくのがきつい印象です（それなら関数をvecで持っておけば、というのはそのvecの型が問題になり上手く行きません）。

おわりに

というわけで、RustでExtensible Effectsをやろうとしたけど上手くいっていない話でした。
また進展があれば書きます。

Discussion