Home > database >  Why is this type definition illegal?
Why is this type definition illegal?

Time:10-05

I'm writing an interpreter for a small programming language, and the AST looks something like this:

data Value a = IntVal a Int | FloatVal a Float
data Expr a = AddExpr a (Value a) (Value a) | MulExpr a (Value a) (Value a)

I use parameter a for storing the line number of each term. Some functions take terms with annotations, and some take empty terms (replacing a with unit), like this:

myFunction :: Value Int -> ...
myFunction = ...

myOtherFunction :: Value () -> ...
myOtherFunction = ...

However, I find this alternative a bit more clear:

type Annotated b = b Int
type Bare b = b ()

Then, I can rewrite the previous two functions like this:

myFunction :: Annotated Value -> ...
myFunction = ...

myOtherFunction :: Bare Value -> ...
myOtherFunction = ...

This works great, however I also need to define a synonym for a list type with the same characteristics:

type MyList a = [Value a]

Now, I want to define a function taking an annotated MyList like so:

myOtherOtherFunction :: Annotated MyList -> ...
myOtherOtherFunction = ...

However, this doesn't work. The error says The type synonym ‘MyList’ should have 1 argument, but has been given none. Why doesn't this work? Is there any better way to define these types? Maybe with some extension?

CodePudding user response:

Haskell is by default a bit pedantic that type synonyms must always be fully applied, i.e. you can't mention MyList without directly applying it to a concrete type parameter, thus you can't have Annotated MyList. The reason for this restriction is that partially applied type synonyms could be misused to form a Turing-complete language. Oops... that would be a pain for the compiler.

That said, clearly this is a bit silly for Annotated MyList, which is after resolved with two simple substitutions to the perfectly unspectacular [Value Int], so that should work, shouldn't it? And indeed it does, but you need to enable a syntactic extension:

{-# LANGUAGE LiberalTypeSynonyms #-}

myOtherOtherFunction :: Annotated MyList -> ...
myOtherOtherFunction = undefined
  • Related