Trait peepmatic_automata::Output [−][src]
pub trait Output: Sized + Eq + Hash + Clone { fn empty() -> Self; fn prefix(a: &Self, b: &Self) -> Self; fn difference(a: &Self, b: &Self) -> Self; fn concat(a: &Self, b: &Self) -> Self; fn is_empty(&self) -> bool { ... } }
Expand description
An output type for a transducer automata.
Not every type can be the output of a transducer. For correctness (not memory safety) each type that implements this trait must satisfy the following laws:
-
concat(empty(), x) == x
– concatenating something with the empty instance produces that same something. -
prefix(a, b) == prefix(b, a)
– taking the prefix of two instances is commutative. -
prefix(empty(), x) == empty()
– the prefix of any value and the empty instance is the empty instance. -
difference(concat(a, b), a) == b
– concatenating a prefix value and then removing it is the identity function.
Example
Here is an example implementation for unsigned integers:
use peepmatic_automata::Output; #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] struct MyInt(u64); impl Output for MyInt { // The empty value is zero. fn empty() -> Self { MyInt(0) } // The prefix of two values is their min. fn prefix(a: &MyInt, b: &MyInt) -> Self { std::cmp::min(*a, *b) } // The difference is subtraction. fn difference(a: &MyInt, b: &MyInt) -> Self { MyInt(a.0 - b.0) } // Concatenation is addition. fn concat(a: &MyInt, b: &MyInt) -> Self { MyInt(a.0 + b.0) } } // Law 1 assert_eq!( MyInt::concat(&MyInt::empty(), &MyInt(5)), MyInt(5), ); // Law 2 assert_eq!( MyInt::prefix(&MyInt(3), &MyInt(5)), MyInt::prefix(&MyInt(5), &MyInt(3)) ); // Law 3 assert_eq!( MyInt::prefix(&MyInt::empty(), &MyInt(5)), MyInt::empty() ); // Law 4 assert_eq!( MyInt::difference(&MyInt::concat(&MyInt(2), &MyInt(3)), &MyInt(2)), MyInt(3), );