在 Rust 的 impl 块中引用特征

Question

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

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

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

问题是，我想在 impl 块中为 Unifiable 使用这个辅助函数 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 中，特征除了任何通用参数外还有一个“特殊”参数： 特征实现的类型。 在这种情况下，术语类型 T 很自然就是该类型。
相关地，Haskell“功能依赖”t -> v 在 Rust 中使用 关联类型 而不是类型参数来表达，这同样在 Rust 中很重要，如 Haskell 有助于类型推断。

在一起，这意味着你的特征可以用 no 类型参数编写：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>>;
}

此外，由于特征方法之一 returns Self，我们需要在特征上绑定 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=debug&edition=2018&gist=73f3957a502e33d46092945ca564b588

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

在 Rust 的 impl 块中引用特征

Referring to a trait within an impl block in Rust

traits

rust