Rustでの関数型プログラミング

Rust

Rustでの関数型プログラミングについて調べていたのですが、以下のスライドでは高カインド型がないのが問題とされているようなので実装して確認してみました。
https://speakerdeck.com/helloyuk13/rust-demomonadohashi-zhuang-dekirufalseka

Scalaでの高カインド型

高カインド型とは型コンストラクタを型パラメータに取る型らしいのですが、具体例がないとよくわからないと思います。Scalaで以下のサンプルの実装を準備したのですが、Monoid[A] を型パラメータとして受け取る Foldable[F[_]] が高カインド型らしいです。

trait Monoid[A] {
  def op(a1: A, a2: A): A
  def zero: A
}

object Monoid {
  def listMonoid[A] = new Monoid[List[A]] {
    def op(a1: List[A], a2: List[A]) = a1 ++ a2
    val zero = Nil
  }

  def treeMonoid[A] = new Monoid[Tree[A]] {
    def op(a1: Tree[A], a2: Tree[A]): Branch[A] = Branch(a1, a2)
    def zero = sys.error("")
  }
}

trait Foldable[F[_]] {
  def foldRight[A,B](as: F[A])(z: B)(f: (A, B) => B): B
  def foldLeft[A,B](as: F[A])(z: B)(f: (B, A) => B): B
  def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
  def toList[A](as: F[A]): List[A] =
    foldRight(as)(List[A]())(_ :: _)
}

sealed trait Tree[A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

object TreeFoldable extends Foldable[Tree] {
  override def foldMap[A, B](as: Tree[A])(f: A => B)(mb: Monoid[B]): B = as match {
    case Leaf(a) => f(a)
    case Branch(l, r) => mb.op(foldMap(l)(f)(mb), foldMap(r)(f)(mb))
  }
  override def foldLeft[A, B](as: Tree[A])(z: B)(f: (B, A) => B) = as match {
    case Leaf(a) => f(z, a)
    case Branch(l, r) => foldLeft(r)(foldLeft(l)(z)(f))(f)
  }
  override def foldRight[A, B](as: Tree[A])(z: B)(f: (A, B) => B) = as match {
    case Leaf(a) => f(a, z)
    case Branch(l, r) => foldRight(l)(foldRight(r)(z)(f))(f)
  }
}

Scalaでは高カインド型が利用できるので、Tree型の型パラメータがIntやStringであってもfoldMapなどの関数で変換することが出来るようになっています。

val tree1 = Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
println(TreeFoldable.toList(tree1).map(_*2))
println(TreeFoldable.foldMap(tree1)(a => Leaf(a * 2): Tree[Int])(treeMonoid))

val tree2 = Branch(Leaf("a"), Branch(Leaf("b"), Leaf("c")))
println(TreeFoldable.toList(tree2).map(s => s + s))
println(TreeFoldable.foldMap(tree2)(a => Leaf(a + a): Tree[String])(treeMonoid))

Rustでの高カインド型

Rustでは標準の機能に高カインド型がないので、代わりに関連型が利用されているようです。 こちらでは以下のように定義した高カインド型を利用しています。

trait HKT<U> {
    type C; // Current type
    type T; // Type with C swapped with U
}

先ほどのScalaでの実装と同様にTreeのデータ構造に対してfoldMapで変換できるようにしたいと思います。 まず先ほどのHKTトレイトをTreeとVecに対して実装してみます。

#[derive(Clone, Debug)]
enum Tree<A> {
    Empty,
    Leaf(A),
    Branch {
        left: Box<Tree<A>>,
        right: Box<Tree<A>>,
    },
}

trait HKT<U> {
    type Current;
    type Target;
}
impl<A, B> HKT<B> for Vec<A> {
    type Current = A;
    type Target = Vec<B>;
}
impl<A, B> HKT<B> for Tree<A> {
    type Current = A;
    type Target = Tree<B>;
}

先にfoldMapの実装を見てみますと、関数の引数となるcontainerがFoldableトレイトを実装したMonoidになっていまして、mapperが Fn(&<C as HKT<M>>::Current) -> M となっています。 container.reduce の関数は初期値と、containerに対して順番にmapper(curr) を実行して結果がMonoidになるのでacc.combineでそれまでの結果を結合するようにしています。

fn fold_map<M, C, F>(container: C, mapper: F) -> M
where
    M: Monoid,
    C: Foldable<M>,
    F: Fn(&<C as HKT<M>>::Current) -> M,
{
    container.reduce(M::empty(), |acc, curr| acc.combine(mapper(curr)))
}

上記のfold_mapの実装よりMonoidはemptyとcombineが使える必要があり、以下のようにMonoidトレイトに対してEmptyトレイトとSemigroupトレイトを合成しています。

trait Monoid: Empty + Semigroup {}
impl<T: Clone> Monoid for Vec<T> {}
impl<T: Clone> Monoid for Tree<T> {}

EmptyとSemigroupにはそれぞれemptyとcombineを定義するのですが、以下のように実装しています。

trait Empty {
    fn empty() -> Self;
}
impl<T> Empty for Vec<T> {
    fn empty() -> Vec<T> {
        vec![]
    }
}
impl<T> Empty for Tree<T> {
    fn empty() -> Tree<T> {
        Tree::Empty
    }
}

trait Semigroup {
    fn combine(self, other: Self) -> Self;
}
impl<T: Clone> Semigroup for Vec<T> {
    fn combine(self, other: Self) -> Self {
        let mut concat = self.to_vec();
        concat.extend_from_slice(&other);
        concat
    }
}
impl<T: Clone> Semigroup for Tree<T> {
    fn combine(self, other: Self) -> Self {
        Tree::Branch {
            left: Box::new(self),
            right: Box::new(other),
        }
    }
}

最後にFoldableに定義したreduceでMonoidを結合できるようにしています。Rustが高カインド型が使えないのが原因ではないのですが、TreeがEmptyの時のreduceを定義できなかったので、とりあえずTree<i32>に対してFoldableを実装します。

trait Foldable<B>: HKT<B> + Sized {
    fn reduce<F>(self, b: B, ba: F) -> B
    where
        F: Copy + Fn(B, &<Self as HKT<B>>::Current) -> B;

    fn reduce_right<F>(self, b: B, f: F) -> B
    where
        F: Copy + Fn(&<Self as HKT<B>>::Current, B) -> B;
}
impl<A, B> Foldable<B> for Vec<A> {
    fn reduce<F>(self, b: B, fa: F) -> B
    where
        F: Copy + Fn(B, &A) -> B,
    {
        self.iter().fold(b, fa)
    }

    fn reduce_right<F>(self, b: B, fa: F) -> B
    where
        F: Copy + Fn(&A, B) -> B,
    {
        self.iter().rev().fold(b, |x, y| fa(y, x))
    }
}
impl<B> Foldable<B> for Tree<i32> {
    fn reduce<F>(self, b: B, fa: F) -> B
    where
        F: Copy + Fn(B, &i32) -> B,
    {
        match self {
            Tree::Empty => fa(b, &0),
            Tree::Leaf(a) => fa(b, &a),
            Tree::Branch { left, right } => right.reduce(left.reduce(b, fa), fa),
        }
    }

    fn reduce_right<F>(self, b: B, fa: F) -> B
    where
        F: Copy + Fn(&<Self as HKT<B>>::Current, B) -> B,
    {
        match self {
            Tree::Empty => fa(&0, b),
            Tree::Leaf(a) => fa(&a, b),
            Tree::Branch { left, right } => right.reduce_right(left.reduce_right(b, fa), fa),
        }
    }
}

これを使うとTreeに対して以下のようにFoldMapで変換できるようになります。

#[test]
fn test_foldable_tree() {
    let a = Tree::Branch {
        left: Box::new(Tree::Leaf(1)),
        right: Box::new(Tree::Branch {
            left: Box::new(Tree::Leaf(2)),
            right: Box::new(Tree::Leaf(3)),
        }),
    };
    println!(
        "{:?}",
        fold_map(a.clone(), |i: &i32| -> Tree<i32> { Tree::Leaf(*i + 1) })
    );
}