unification-fd icon indicating copy to clipboard operation
unification-fd copied to clipboard

Hindley Milner example?

Open Gabriella439 opened this issue 3 years ago • 7 comments

Is it possible to implement the Hindley Milner type inference algorithm using this package's API? The reason I ask is that I made an initial attempt to do so, but ran into difficult making polymorphic types Unifiable.

To illustrate this, usually the way the types are encoded in the HM algorithm is something like:

data Polytype = Polytype [TypeVariable] Monotype

data Monotype = Variable TypeVariable | FunctionType Monotype Monotype

Now, I can make Monotype implement Unifiable by doing this:

data MonotypeF x = Variable TypeVariable | FunctionType x x
    deriving (Foldable, Functor, Generic1, Traversable, Unifiable)

type Monotype = Fix MonotypeF

… but I can't make Polytype implement Unifiable (at least, not in a useful way, as far as I can tell). Is this a limitation of the unification-fd API or am I missing something?

Gabriella439 avatar Feb 28 '21 07:02 Gabriella439