Comments 2
Спасибо, как кстати. На днях копался в библиотеке с похожим подходом.
Попробовал перевести пример на Rust
Правда, обобщить свертку, чтобы принимал Fix<F> на вход, не получилось. Не хватает абстракций?
use std::{fmt::Display, marker::PhantomData};
use ListF::*;
/// Lower `type -> type` to `type`
trait Apply<T> {
type Out;
}
struct Fix<F: Apply<Self>> {
unfix: Box<<F as Apply<Self>>::Out>,
}
enum ListF<A, B> {
Nil,
Elem(A, B),
}
fn fix<A, B, F>(xs: ListF<A, B>) -> Fix<F>
where
F: Apply<Fix<F>, Out = ListF<A, B>>,
{
Fix {
unfix: Box::new(xs),
}
}
type List<A> = Fix<ListFKind<A>>;
struct ListFKind<A>(PhantomData<A>);
impl<A> Apply<Fix<Self>> for ListFKind<A> {
type Out = ListF<A, Fix<Self>>;
}
fn fold_fix<A, B, F, FOLD>(fold: FOLD, fixed: List<A>) -> B
where
F: Apply<Fix<F>, Out = ListF<A, B>>,
FOLD: Copy + Fn(ListF<A, B>) -> B,
{
match *fixed.unfix {
Nil => fold(Nil),
Elem(x, xs) => fold(Elem(x, fold_fix::<_, _, F, _>(fold, xs))),
}
}
fn unfold_fix<A, B, F, UNFOLD>(unfold: UNFOLD, folded: B) -> Fix<F>
where
F: Apply<Fix<F>, Out = ListF<A, Fix<F>>>,
UNFOLD: Copy + Fn(B) -> ListF<A, B>,
{
match unfold(folded) {
Nil => fix(Nil),
Elem(x, folded_tail) => fix(Elem(x, unfold_fix(unfold, folded_tail))),
}
}
fn show_list<A: Display>(list: List<A>) -> String {
return fold_fix::<_, _, StrKind<_>, _>(show_listf, list);
struct StrKind<A>(PhantomData<A>);
impl<A> Apply<Fix<Self>> for StrKind<A> {
type Out = ListF<A, String>;
}
fn show_listf<A: Display>(list: ListF<A, String>) -> String {
match list {
Nil => "[]".into(),
Elem(x, acc) => format!("(: {x} {acc})"),
}
}
}
#[test]
fn test_show_list() {
let xs: List<u32> = fix(Elem(1, fix(Elem(2, fix(Nil)))));
assert_eq!(show_list(xs), "(: 1 (: 2 []))");
let xs: List<bool> = fix(Nil);
assert_eq!(show_list(xs), "[]");
}
#[test]
fn test_unfold_fix() {
let xs = unfold_fix(|x| if x <= 3 { Elem(x, x + 1) } else { Nil }, 0);
assert_eq!(show_list(xs), "(: 0 (: 1 (: 2 (: 3 []))))");
}
+3
Тут я подсказать не смогу, я на расте только пару структур данных реализовывал, после чего его несколько месяцев не трогал. Я думаю, что возможно реализовать свёртку на расте. Есть пакет, в котором трейт для функторов определяется. Думаю, можно попробовать его использовать
+1
Sign up to leave a comment.
Применение обобщённой свёртки для обработки синтаксических деревьев