指Rust中impl块中的一个特性

Question

我正在将Haskell中的一个简单prolog实现翻译成Rust，以获得更多使用该语言的经验。

在Haskell中，我有一个类型类：

class Unifiable t v | t -> v where
variables :: t -> [v]
subs      :: Unifier v t -> t -> t
unify     :: t -> t -> (Maybe (Unifier v t))

我把它翻译成Rust中的以下特征：

pub type Unifier<V,T> = HashMap<V,T>;
pub trait Unifiable<T,V> {
fn variables(term: T) -> Vec<V>;
fn subs(unifier: Unifier<V,T>, term: T) -> T;
fn unify(firstTerm: T, secondTerm: T) -> Option<Unifier<V,T>>;

然后，我就有了一个实用函数的定义，只要Unifiable的实例可用，我就可以使用它。作为一个初步定义，我使用了这个：

pub fn compose<V: Hash + Eq, T, U: Unifiable<T,V>>(first: Unifier<V,T>, other: Unifier<V,T>) -> Unifier<V,T> {
let unifier: Unifier<V,T> = first.iter().map(|(&x,y)| (x, U::subs(other, *y))).collect();
unifier.extend(other);
return unifier;
}

我打算将其类似于Haskell类型的签名：

compose :: Unifiable v t => Unifier v t -> Unifier v t -> Unifier v t

问题是，我想在Unifiable的impl块中使用这个帮助函数compose，并且我不确定如何引用调用站点的Unifiable实例：

impl <T: Eq, V: Clone + Eq + Hash> Unifiable<Term<T,V>,V> for Term<T,V> {
...
fn unify(firstTerm: Term<T,V>, secondTerm: Term<T,V>) -> Option<Unifier<V,Term<T,V>>> {
....
return Some(compose<V,Term<T,V>,X>(u, us));
....
}
...
}

问题是，我不知道X用什么来引用我当前定义的impl块中的Unifiable实例，如果我去掉类型参数，我会得到一个"；无法推断类型参数"；错误这种带有特征的引用在Rust中可能吗？

Answer 1

以下是Haskell和Rust之间的差异，它们对正确翻译此代码非常重要：

• Haskell的类型类以一个未区分的类型参数集合开始，但在Rust中，一个trait除了任何泛型参数之外还有一个"特殊"参数：实现trait的类型。在这种情况下，术语类型T自然是该类型
• 与此相关的是，Haskell"；功能依赖性"；t -> v在Rust中使用关联类型而不是类型参数来表示，这在Rust和Haskell中对于帮助类型推理同样重要

这些加在一起意味着你的特质可以用没有类型参数来写：T变成Self，V声明为type V;并用作Self::V。

pub trait Unifiable {
type V;
fn variables(term: Self) -> Vec<Self::V>;
fn subs(unifier: Unifier<Self::V,Self>, term: Self) -> Self;
fn unify(firstTerm: Self, secondTerm: Self) -> Option<Unifier<Self::V,Self>>;
}

此外，因为其中一个trait方法返回Self，所以我们需要该trait上的绑定Self: Sized。

我一直在修改你的程序，直到它在Rust Playground中编译——希望这仍然符合你的意图(我没有根据我对统一算法的了解检查细节(。

注意：compose中的T: Clone绑定是因为subs取值为term: Self。如果subs的实现通常会在不破坏输入的情况下产生一个新值，那么参数类型应该改为term: &Self，这样就可以避免需要T: Clone(以及执行克隆(。你可能会想对你的程序进行另一次传递，并在每一点上考虑参数是应该通过移动还是通过引用传递，但这更多地取决于实现而不是特征结构，所以我不能在那里给你详细的建议。

use std::hash::Hash;
use std::collections::HashMap;
pub type Unifier<V,T> = HashMap<V,T>;
pub trait Unifiable where Self: Sized {
type V;
fn variables(term: Self) -> Vec<Self::V>;
fn subs(unifier: Unifier<Self::V,Self>, term: Self) -> Self;
fn unify(firstTerm: Self, secondTerm: Self) -> Option<Unifier<Self::V,Self>>;
}
pub fn compose<V: Hash + Eq + Clone, T: Unifiable<V = V> + Clone>(
first: Unifier<V, T>,
other: Unifier<V, T>,
) -> Unifier<V, T> {
let mut unifier: Unifier<V, T> = first
.into_iter()
.map(|(x, y)| (x, T::subs(other.clone(), y)))
.collect();
unifier.extend(other);
unifier
}
#[derive(Clone, Debug, Eq, PartialEq)]
struct Term<V: Sized> {
v: V,
}
impl <V: Clone + Eq + Hash> Unifiable for Term<V> {
type V = V;
fn variables(term: Self) -> Vec<V> {todo!();}
fn subs(unifier: Unifier<V,Self>, term: Self) -> Self {todo!();}
fn unify(firstTerm: Self, secondTerm: Self) -> Option<Unifier<V,Self>> {
return Some(compose::<V,Self>(todo!(), todo!()));
}
}

https://play.rust-lang.org/?version=stable&mode=调试&edition=2018&gist=73f3957a502e33d46092945ca564b588

(我没有编辑过这段代码的格式和样式，但请注意，使用lower_case_with_underscores名称而不是camelCase名称是惯用的。(