Understanding 'newtype' keyword

Question

For a uni assignment, we have been given a line of Haskell code which shows:

newtype TC a = TC ([Id] -> Either TypeError ([Id], a))

Firstly, TypeError is something which needs to be implemented by us for the assignment so I can't post the data declaration here, but my question is this. How do I read the code above? What is the a right after the newtype TC? I also don't understand how TC is being reused to the right of the equals sign.

I think a here is a type variable since newtype works similarly to data. I don't know how knowing this will help my understanding.

Answer 1

What is the a right after the newtype TC?

The a in the newtype declaration

newtype TC a = ...

expresses much the same as the x in a function declaration

f x = ...

a is a type parameter. So you'll be able to use TC as, for example, TC Int or TC Bool, similar to how you're able to use f like f 1 or f "bla bla" (depending on its type).

The case TC Int is equivalent to the following alternative:

newtype TCInt = TCInt ([Id] -> Either TypeError ([Id], Int))

I also don't understand how TC is being reused to the right of the equals sign.

That is a bit of a confusing quirk in Haskell. Actually TC is not reused, rather you're declaring two separate entities which are both called TC. You could also call them differently:

newtype TC_T a = TC_V ([Id] -> Either TypeError ([Id], a))

• TC_T is a type constructor. This is the thing that will appear in type signatures, i.e. TC_T Int or TC_T Bool.
• TC_V is a value constructor. You use this when, well, generating values of type TC_T Int or TC_T Bool.

So for example, you might write these:

tci :: TC_T Int
tci = TC_V (\ids -> Right (ids, 37))

tcb :: TC_T Bool
tcb = TC_V (\ids -> Right (reverse ids, False))

With your original version it looks like this:

tci :: TC Int
tci = TC (\ids -> Right (ids, 37))

tcb :: TC Bool
tcb = TC (\ids -> Right (reverse ids, False))

...but it's still two separate things both called TV here. Most newtypes in Haskell call the type- and value constructors the same, but often only the type constructor is exported from a module and the value constructor left as an implementation detail.

Most of this is the same for data as for newtype. You could as well have

data TC a = TC ([Id] -> Either TypeError ([Id], a))

... the only difference to the newtype version is a subtle indirection: if it's data, then the compiler inserts an indirection which allows a bit more lazyness, but in this case there's hardly a point to doing that.

In practice, you generally use data only when you need multiple constructors and/or a constructor with multiple fields, which newtype does not support.

Answer 2

The benefit of newtype over data is that you can derive via the type that underlies it:

{-# Language DerivingVia              #-}
{-# Language StandaloneKindSignatures #-}

import Control.Applicative   (Alternative)
import Control.Monad         (MonadPlus)
import Control.Monad.Except  (ExceptT(..), Except)
import Control.Monad.Fix     (MonadFix)
import Control.Monad.State   (StateT(..), MonadState)
import Data.Functor.Identity (Identity(..))
import Data.Kind             (Type)

type    TC :: Type -> Type
newtype TC a = MkTC ([Id] -> Either TypeError (a, [Id]))
  deriving
    ( Functor, Applicative, Alterantive
    , Monad, MonadPlus, MonadState [Id], MonadFix
    )
  via StateT [Id] (Except TypeError)

-- Alternative and MonadPlus rely on these
instance Semigroup TypeError ..
instance Monoid    TypeError ..

I had to swap the tuple but this works because of three newtypes: TC a, StateT s m a and ExceptT. The compiler generates an instance for each newtype witnessing that it has the same runtime representation as the underlying type.

This is called representational equality and is witnessed by Coercible.

-- instance Coercible (StateT s m a) (s -> m (a, s))
type    StateT :: Type -> (Type -> Type) -> (Type -> Type)
newtype StateT s m a = MkStateT (s -> m (a, s))

-- instance Coercible (ExceptT e m a) (m (Either e a))
type    ExceptT :: Type -> (Type -> Type) -> (Type -> Type)
newtype ExceptT e m a = MkExceptT (m (Either e a))

This entails that TC a is coercible to StateT [Id] (Except TypeError) a and thus we can use coerce-based deriving strategies to carry instances between them (like GeneralizedNewtypeDeriving or DerivingVia).

  TC a
={Coercible}
  [Id] -> Either TypeError (a, [Id])
={Coercible}
  [Id] -> ExceptT TypeError Identity (a, [Id])
={Except e = ExceptT e Identity} 
  [Id] -> Except TypeError (a, [Id])
={Coercible}
  StateT [Id] (Except TypeError) a

GeneralizedNewtypeDeriving only works on newtypes but this does not mean that DerivingVia only works on newtypes. You can dervive many instances for data, for example by Applicative lifting methods over TC (Ap TC a).

Making it a newtype does simplify things, the Applicative can be derived through the state transformer so we don't need to write any instance by hand.

data TC a = MkTC ..
  ..

  deriving (Semigroup, Monoid, Num, Bounded)
  via Ap TC a

---

The TC name serves two purposes in your code ('punning'). I separate them into two different names, for TC and the transformers.

The left-hand side is the type constructor:

>> :k TC
TC :: Type -> Type
>> :k StateT
StateT :: Type -> (Type -> Type) -> (Type -> Type)
>> :k ExceptT
ExceptT :: Type -> (Type -> Type) -> (Type -> Type)

and the right-hand side is the value constructor, which I added a Mk for disambiguation:

>> :t MkTC
MkTC :: ([Id] -> Either TypeError (a, [Id])) -> TC a
>> :t MkStateT
MkStateT :: (s -> m (a, s)) -> StateT s m a
>> :t MkExceptT
MkExceptT :: m (Either e a) -> ExceptT e m a

The a :: Type is an argument to the type constructor:

TC   :: Type -> Type
TC a :: Type

Without a type argument none of those instaces would kind-check because all of those instances require an "unary type constructor" (Type -> Type) as an argument. That is to say, a type parameterised by a type:

Functor         :: (Type -> Type) -> Constraint
Applicative     :: (Type -> Type) -> Constraint
Alternative     :: (Type -> Type) -> Constraint
Monad           :: (Type -> Type) -> Constraint
MonadPlus       :: (Type -> Type) -> Constraint
MonadState [Id] :: (Type -> Type) -> Constraint
MonadFix        :: (Type -> Type) -> Constraint