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),
);
Required methods
Get the shared prefix of two instances.
This must be commutative.
fn difference(a: &Self, b: &Self) -> Self
fn difference(a: &Self, b: &Self) -> Self
When b
is a prefix of a
, get the remaining suffix of a
that is not
shared with b
.