From 8116a4989a7f9664ff2b4d07c705937f1aae1915 Mon Sep 17 00:00:00 2001
From: Tomas Musil <tomik.musil@gmail.com>
Date: Tue, 30 Dec 2014 17:45:05 +0100
Subject: [PATCH 1/1] start work on alg W

---
 src/Lambda/Type.hs | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 52 insertions(+)
 create mode 100644 src/Lambda/Type.hs

diff --git a/src/Lambda/Type.hs b/src/Lambda/Type.hs
new file mode 100644
index 0000000..9ffdae7
--- /dev/null
+++ b/src/Lambda/Type.hs
@@ -0,0 +1,52 @@
+-- |
+-- Module      :  Lambda.Type
+-- Copyright   :  Tomáš Musil 2014
+-- License     :  BSD-3
+--
+-- Maintainer  :  tomik.musil@gmail.com
+-- Stability   :  experimental
+--
+-- Data types for Hindley-Milner types.
+
+
+module Lambda.Type
+  ( -- * Types
+    Type(..)
+  ) where
+
+import Lambda.Term
+
+type TypeVarName = String
+type TypeName = String
+
+data Type = Primitive TypeName | TypeVar TypeVarName | TypeFunction Type Type deriving (Show)
+data TypeScheme = TScheme Type | TSForAll TypeVarName TypeScheme deriving (Show)
+
+data HMTerm = HMTerm Term TypeScheme | HMLet VarName HMTerm HMTerm TypeScheme 
+
+fresh :: TypeVarName
+fresh = undefined
+
+substitute :: TypeScheme -> TypeVarName -> TypeScheme -> TypeScheme
+substitute = undefined
+
+unify :: TypeScheme -> TypeScheme -> Either String TypeScheme
+unify = undefined
+
+algW :: HMTerm -> Either String TypeScheme
+algW (HMTerm (Var _) t) = Right t
+algW (HMTerm (Lambda x t) (TScheme p)) = do
+  let v = TScheme (TypeVar fresh)
+  np <- substitute v x t
+  return $ unify p np
+algW (HMTerm (App u v) t) = do
+  tu <- algW u
+  tv <- algW v
+  case tu of
+    (TScheme (TypeFunction a b)) -> do
+      unify a tv
+      return b
+    _ -> Left $ "cannot apply " ++ show tu ++ " to " ++ show tv
+  
+
+
-- 
2.4.2