Referring to a trait within an impl block in Rust

Question

I am working on translating a simple prolog implementation in Haskell to Rust for fun, and to get some more experience using the language.

In Haskell, I have a type class:

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

Which I translated into the following trait in 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>>;

I then have the definition of a utility function that I would like to be able to use whenever an instance of Unifiable is available. As a preliminary definition, I used this:

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;
}

which I am intending on being analogous to the Haskell type signature:

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

The problem is, I would like to use this helper function compose in an impl block for Unifiable, and I am not sure how to refer to to the Unifiable instance at the call site:

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));
        ....
    }
    ...
}

The issue being, I don't know what to use for X to refer to the Unifiable instance in the impl block I'm currently defining, and if I leave out the type parameters, I get a "cannot infer type parameter" error. Is this sort of reference with traits possible in Rust?

What types are u and us? It would help if you gave an example with working code (except for the type error, that is) that we could run in the Rust Playground. — Aplet123

Kevin Reid Kevin Reid · Accepted Answer · 2020-12-15T16:21:30

Here are the differences between Haskell and Rust that are important to translating this code correctly:

Haskell's type classes start with an undifferentiated collection of type parameters, but in Rust, a trait has one “special” parameter in addition to any generic parameters: the type the trait is implemented on. In this case, it's natural for the term type T to be that type.
Relatedly, the Haskell "functional dependency" t -> v is expressed in Rust using an associated type instead of a type parameter, and this is equally important in Rust as in Haskell for aiding type inference.

Together, these mean that your trait can be written with no type parameters: T becomes Self, and V becomes declared as type V; and used as 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>>;
}

Also, because one of the trait methods returns Self, we'll need the bound Self: Sized on the trait.

I've tinkered with your program until it compiles in the Rust Playground — hopefully this still matches your intent (I didn't check the details against my knowledge of unification algorithms).

Note: The T: Clone bound in compose arises because subs takes term: Self by value. If implementations of subs will typically produce a new value without destroying the input, then the parameter type should be term: &Self instead and you can avoid needing T: Clone (and performing the clones) that way. You will probably want to make another pass over your program and consider at each point whether parameters should be passed by-move or by-reference, but that is more informed by the implementation than the trait structure, so I can't give you detailed advice there.

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

(I have not edited this code for formatting and style, but note that it is idiomatic to use lower_case_with_underscores names instead of camelCase names.)

Referring to a trait within an impl block in Rust

1 Answers