Как стать автором
Обновить

Комментарии 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 []))))");
}

Тут я подсказать не смогу, я на расте только пару структур данных реализовывал, после чего его несколько месяцев не трогал. Я думаю, что возможно реализовать свёртку на расте. Есть пакет, в котором трейт для функторов определяется. Думаю, можно попробовать его использовать

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории