Recursion Schemes
- 再帰のデータと構造を分離したもの?
文字列の結合
fn recurse(base: String, values: List) -> String {
match values {
List::Cons(head, tail) => format!("{} :: {}", head, recurse(base, *tail)),
List::Nil => base,
}
}- step: (i32, String) -> String
fn recurse<S>(base: String, step: &S, values: List) -> String
where
S: Fn(i32, String) -> String,
{
match values {
List::Cons(head, tail) => step(head, recurse(base, step, *tail)),
List::Nil => base,
}
}- String -> A
- loop closure化
- valueをカリー化
#![feature(fn_traits)]
use recur_fn::{recur_fn, RecurFn};
fn fold<'a, A: Clone + 'a>(base: A, step: &'a dyn Fn(i32, A) -> A) -> impl RecurFn<List, A> + '_
where
S: Fn(i32, A) -> A,
{
recur_fn(move |lop, state| match state {
List::Cons(head, tail) => step(head, lop.call((*tail,))),
List::Nil => base.clone(),
})
}ListをOption<(i32, List)>にマップするproject
fn fold<'a, A: Clone + 'a>(
base: A,
step: &'a dyn Fn(i32, A) -> A,
project: &'a dyn Fn(List) -> Option<(i32, List)>,
) -> impl RecurFn<List, A> + 'a {
recur_fn(move |lop, state| match project(state) {
Some((head, tail)) => step(head, lop.call((tail,))),
None => base.clone(),
})
}
let step = |h, r| format!("{} :: {}", h, r);
let project = |state| match state {
List::Cons(head, tail) => Some((head, *tail)),
List::Nil => None,
};
let ret = fold("nil".to_string(), &step, &project).call(list);import Control.Monad.Fix
type Step = Int -> String -> String
type Project = [Int] -> Maybe (Int, [Int])
recurse :: String -> Step -> Project -> [Int] -> String
recurse base step project =
fix (\loop -> \state ->
case project state of
Just (head, tail) -> step head (loop tail)
Nothing -> base)
main :: IO ()
main =
let
step = \h r -> (show h) ++ "::" ++ r
project = \state ->
case state of
(head : tail) -> Just (head, tail)
[] -> Nothing
in
print $ recurse "nil" step project [1, 2, 3]baseとstepをopに
fn fold<'a, A: Clone + 'a>(
op: &'a dyn Fn(Option<(i32, A)>) -> A,
project: &'a dyn Fn(List) -> Option<(i32, List)>,
) -> impl RecurFn<List, A> + 'a {
recur_fn(move |lop, state| op(match project(state) {
Some((head, tail)) => Some((head, lop.call((tail,)))),
None => None,
}))
}
let op = |o| match o {
Some((head, r)) => format!("{} :: {}", head, r),
None => "nil".to_string(),
};
let ret = fold(&op, &project).call(list);ListF<T> = Option<i32, T>
import Control.Monad.Fix
type ListF a = Maybe (Int, a)
fold :: (ListF a -> a) -> ([Int] -> ListF [Int]) -> [Int] -> a
fold op project =
let
go =
\state f -> case state of
Just (head, tail) -> Just (head, f tail)
Nothing -> Nothing
in
fix (\loop -> \state -> op $ go (project state) loop)
op :: ListF String -> String
op o =
case o of
Just (x, res) -> (show x) ++ "::" ++ res
Nothing -> "nil"
project :: [Int] -> ListF [Int]
project state = case state of
(head : tail) -> Just (head, tail)
[] -> Nothing
main :: IO ()
main = do
print $ fold op project [1, 2, 3]type ListF<T> = Option<(i32, T)>;
fn fold<'a, A: Clone + 'a>(
op: &'a dyn Fn(ListF<A>) -> A,
project: &'a dyn Fn(List) -> ListF<List>,
) -> impl RecurFn<List, A> + 'a {
recur_fn(move |lop, state| {
op(match project(state) {
Some((head, tail)) => Some((head, lop.call((tail,)))),
None => None,
})
})
}def fold[A](
op : ListF[A] => A,
project: List => ListF[List]
): List => A = {
def loop(state: List): A =
op(go(project(state), loop))
def go(state: ListF[List], f: List => A): ListF[A] =
state match {
case Some((head, tail)) => Some((head, f(tail)))
case None => None
}
loop
}ListFの functor を実装
implicit val listFFunctor = new Functor[ListF] {
override def map[A, B](list: ListF[A], f: A => B) =
list match {
case Some((head, tail)) => Some((head, f(tail)))
case None => None
}
}def cata[F[_]: Functor, A, B](
algebra : F[A] => A,
project: B => F[B]
): B => A = {
def loop(state: B): A = algebra.map(project(state), loop)
loop
}