Unification in Rust: A Type Inference Challenge

Unification is a core concept in type inference systems, used to determine the most general type that satisfies a set of constraints. This challenge asks you to implement a simplified unification algorithm in Rust, focusing on variable and type equality. Successfully completing this challenge will give you a deeper understanding of how type systems work and how they resolve type conflicts.

Problem Description

You are tasked with implementing a unification function that takes two terms (representing types) and attempts to unify them. Terms can be either a concrete type (represented as a String) or a type variable (represented as a char). The unification process should determine if the two terms are equivalent. If they are, the function should return Ok(()). If they are not, and one of the terms is a type variable, the function should attempt to substitute the other term for that variable. If both terms are type variables and they are different, the unification fails. If both terms are type variables and they are the same, unification succeeds. If one term is a type variable and the other is a concrete type, unification fails.

Key Requirements:

• Type Variables: Represented by single lowercase characters (e.g., 'a', 'b', 'c').
• Concrete Types: Represented by Strings (e.g., "int", "string", "bool").
• Unification Rules:
  • If t1 and t2 are the same concrete type, unification succeeds.
  • If t1 is a type variable and t2 is a concrete type, unification fails.
  • If t2 is a type variable and t1 is a concrete type, unification fails.
  • If t1 and t2 are both type variables and are the same, unification succeeds.
  • If t1 and t2 are both type variables and are different, unification fails.

Expected Behavior:

The function should return Ok(()) if unification succeeds. If unification fails, it should return Err(String) with a descriptive error message.

Edge Cases to Consider:

• Empty strings for concrete types.
• Type variables that are not single lowercase characters.
• Cases where the same type variable appears multiple times in the input. (This challenge does not require handling this, but it's good to be aware of.)

Examples

Example 1:

Input: ('a', "int")
Output: Err("Cannot unify 'a' with 'int'")
Explanation: 'a' is a type variable and "int" is a concrete type, which is a unification failure.

Example 2:

Input: ("int", "int")
Output: Ok(())
Explanation: Both terms are the same concrete type, so unification succeeds.

Example 3:

Input: ('a', 'b')
Output: Err("Type variables 'a' and 'b' are different")
Explanation: Both terms are type variables, but they are different, so unification fails.

Example 4:

Input: ('a', 'a')
Output: Ok(())
Explanation: Both terms are the same type variable, so unification succeeds.

Example 5:

Input: ("string", "int")
Output: Err("Cannot unify 'string' with 'int'")
Explanation: Both terms are concrete types, but they are different, so unification fails.

Constraints

• Type variables must be single lowercase characters.
• Concrete types must be represented as Strings.
• The function must handle all valid inputs gracefully and return appropriate error messages.
• Performance is not a primary concern for this challenge. Focus on correctness and clarity.

Notes

• You can use a simple match statement to handle the different cases.
• Consider the order of operations when comparing terms.
• This is a simplified unification algorithm. Real-world type inference systems are much more complex.
• Think about how to represent the "substitution" process if you were to extend this to a more complete type inference system. For this problem, you only need to detect unification success or failure.