Implemented generic substitution (tested) for use in inferring generics.

2 files changed, 45 insertions, 0 deletions

diff --git a/src/type/mod.rs b/src/type/mod.rs
index 6c4be97..37081a1 100644
--- a/src/type/mod.rs
+++ b/src/type/mod.rs
@@ -3,6 +3,7 @@
 pub mod util;
 pub mod display;
 pub mod check;
+pub mod subst;
 
 
 use crate::sexp::SExp;
diff --git a/src/type/subst.rs b/src/type/subst.rs
new file mode 100644
index 0000000..6e92584
--- /dev/null
+++ b/src/type/subst.rs
@@ -0,0 +1,44 @@
+
+use crate::r#type::{Type, Type::*, util::*};
+
+impl Type {
+    /// Performs substitution on the type.
+    ///
+    /// Replaces all free occurrences of generics
+    /// named `name` with the given type `value`
+    /// in the type.
+    /// ```rust
+    /// use melisp::r#type::{Type::*, util::*};
+    /// 
+    /// assert_eq!(
+    ///     List(vec![Integer, arr(Integer, VarType("A".to_string())), VarType("B".to_string())])
+    ///         .subst("A", &Integer),
+    ///     List(vec![Integer, arr(Integer, Integer), VarType("B".to_string())])
+    /// );
+    ///
+    /// assert_eq!(
+    ///     List(vec![Integer, arr(Integer, VarType("A".to_string())), VarType("B".to_string())])
+    ///         .subst("B", &arr(Integer, Integer)),
+    ///     List(vec![Integer, arr(Integer, VarType("A".to_string())), arr(Integer, Integer)])
+    /// );
+    /// ```
+    pub fn subst(self, name: &str, value: &Type) -> Type {
+        match self {
+
+            Arrow(a, b) => arr((*a).subst(name, value), (*b).subst(name, value)),
+
+            List(v) => List(
+                    v.into_iter()
+                     .map(|t| t.subst(name, value))
+                     .collect()
+                 ),
+
+            VarType(s) if s == name => value.clone(),
+
+            VarType(s) => VarType(s),
+
+            Integer => Integer,
+
+        }
+    }
+}