summaryrefslogtreecommitdiff
path: root/receme/src/hylo.rs
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2022-11-15 12:01:28 +0800
committerJSDurand <mmemmew@gmail.com>2022-11-15 12:01:28 +0800
commitcb7bcfad4ab0041aaf3fde3185e27ee46bb37788 (patch)
treea4fd99b138b72617b6c4c2b04f5d2655d0fedcc5 /receme/src/hylo.rs
Initial commit
Basic GNU standard files are added, and we now stop worrying about monadic anamorphisms. The current focus is on testing the correctness of the algorithm, so I need convenient support for manipulating, interpreting, examining, and per chance animating nondeterministic automata.
Diffstat (limited to 'receme/src/hylo.rs')
-rw-r--r--receme/src/hylo.rs41
1 files changed, 41 insertions, 0 deletions
diff --git a/receme/src/hylo.rs b/receme/src/hylo.rs
new file mode 100644
index 0000000..8d26c19
--- /dev/null
+++ b/receme/src/hylo.rs
@@ -0,0 +1,41 @@
+//! This file defines the behaviour of hylomorphisms.
+//!
+//! A hylomorphism is a composition of an anamorphism with a
+//! catamorphism. But it is separated into a distinct trait as we can
+//! implement hylomorphisms more efficiently by short-circuiting
+//! during the expansion by the anamorphism.
+
+use crate::{
+ algebra::Algebra,
+ catana::{Ana, Cata},
+ coalgebra::Coalgebra,
+ functor::Functor,
+};
+
+/// A type implementing Hylo is able to expand from a value of type
+/// `U` into a recursive structure holding values of type `G`, and
+/// also to collapse from that recursive structure to a value of type
+/// `T`.
+///
+/// Types which implement [`Cata`] and [`Ana`] compatibly can
+/// automatically implement [`Hylo`] as follows.
+///
+/// But of course this is not efficient, and types should implement in
+/// a more efficient manner, if available.
+///
+/// ```ignore
+/// Inter::ana(value, coalg).cata(alg)
+/// ```
+pub trait Hylo<T, S, U, F, G, H, A, C>: Cata<T, F, A> + Ana<U, H, C>
+where
+ F: Functor<T>,
+ G: Functor<S, Target<T> = F>,
+ H: Functor<U, Target<S> = G>,
+ A: Algebra<T, F>,
+ C: Coalgebra<U, H>,
+{
+ /// Expand from `value` to an intermediate recursive structure, by
+ /// means of a coalgebra, and then collapse into the result value,
+ /// by means of an algebra.
+ fn hylo(value: U, alg: A, coalg: C) -> T;
+}