Patterns may coincide with functions at the type level, but not at the value level, why is this difference?

Question

This SPJ document, on pages 3 and 4, says:

class Mutation m where type Ref m :: * -> * newRef :: a -> m (Ref ma) readRef :: Ref ma -> ma writeRef :: Ref ma -> a -> m () instance Mutation IO where type Ref IO = IORef newRef = newIORef readRef = readIORef writeRef = writeIORef instance Mutation (ST s) where type Ref (ST s) = STRef s newRef = newSTRef readRef = readSTRef writeRef = writeSTRef 

and

The class declaration now introduces a function of type Ref (with a specific look) along with the usual value functions, such as newRef (each with a specified type). Similarly, each instance declaration makes a proposal defining a type function in the instance type along with a witness for each value function.

We say that Ref is a type of family or a related type of class Mutation. It behaves like a level , so we also call the Ref type function. Applying a type function uses the same syntax as applying a constructor type: Ref ma above means applying a function of type Ref to m, then apply a resulting constructor of type k.

So, in other words,

Ref :: (*->*)->*->*

that is, Ref takes a type level function as an argument, such as Maybe or IO or [] , and creates another type level function, such as IORef , using pattern matching , i.e. Ref determined by matching patterns .

So, how is it possible that patterns can be mapped to functions at the type level, but not at the value level?

For example,

 fun2int:: (Int->Int)->Int fun2int (+)=2 fun2int (*)=3 

It is impossible to write, because equality in functions is undecidable .

1) So, how is it possible that at the type level this does not cause problems?

2) Is it because functions at the type level have a very limited look? Thus, no function at the level level can be an argument for Ref , but only a few selected ones, namely those that are declared by the programmer, and not functions such as (+) that are more general than those that were declared by the programmer ? Is this the reason that there are no problems when matching patterns of type level functions?

3) The answer to this question is related to this part of the GHC specification?

Answer 1

In short, there is no pattern matching on type values ​​at the level, but only on their name.

In Haskell, as in many other languages, types are stored separately by name, even if their representation is identical.

 data A x = A Int x data B x = B Int x 

Above, A and B are two different types of constructors, even if they describe the same level-level function: roughly in the pseudocode \x -> (Int, x) . In a sense, these two identical type level functions have a different name / identifier.

It is different from

 type C x = (Int, x) type D x = (Int, x) 

which describe the same level level function as described above, but do not introduce two new types. The above are simply synonyms: they denote a function, but do not have their own identity.

That's why you can add an instance of a class for A x or B x , but not for C x or D x : trying to do the latter will add the instance to the type (Int, x) instead, linking the instance instead of the type names (,) , Int .

At the value level, the situation is not so different. In fact, there are value constructors that are special functions with a name / identifier and regular functions without an actual identity. We can match a template with a template built from constructors, but not against anything else

 case expOfTypeA of A nt -> ... -- ok case someFunction of succ -> ... -- no 

Note that at the type level, we cannot easily match patterns. Haskell allows you to do this only using type classes. This is done to preserve some theoretical properties (parametricity), as well as for effective implementation (by allowing type erasure - we should not mark each value with its type at run time). These functions go beyond restricting type pattern matching to class classes — this puts a certain burden on the programmer, but the advantages outweigh the disadvantages.

Answer 2

 {-# LANGUAGE TypeFamilies, DataKinds, PolyKinds #-} import GHC.TypeLits 

Make several parallels between the type and level value in Haskell.

First , we have unlimited functions both in type and in value. At the type level, you can express almost everything using type families. You cannot match correspondence to arbitrary functions either by type or by value. For example. you cannot say

 type family F (a :: *) :: * type family IsF (f :: * -> *) :: Bool where IsF F = True IsF notF = False -- Illegal type synonym family application in instance: F -- In the equations for closed type family 'IsF' -- In the type family declaration for 'IsF' 

Second , we have fully implemented data and type constructors, such as Just 5 :: Maybe Integer at the value level or Just 5 :: Maybe Nat at the level level.

On them, you can match the correspondence:

 isJust5 :: Maybe Integer -> Bool isJust5 (Just 5) = True isJust5 _ = False type family IsJust5 (x :: Maybe Nat) :: Bool where IsJust5 (Just 5) = True IsJust5 x = False 

Note the difference between arbitrary functions and type / data constructors. The property of constructors is sometimes called generation. For two different functions f and g it is quite possible that fx = gx for some x . On the other hand, for the constructors fx = gx it follows f = g . This difference makes the first case (pattern matching on arbitrary functions) unsolvable, and the second case (pattern matching on fully applicable constructors) is decidable and accessible.

So far, we have seen consistency in type and value.

Finally , we partially applied (including not applicable) constructors. At the type level, they include Maybe , IO and [] (unapplied), as well as Either String and (,) Int (partially applied). At the value level, we do not use Just and Left and partially apply (,) 5 and (:) True .

The generativity condition does not care if the application is full or not; therefore, there is nothing to exclude matching patterns for partially used constructors. This is what you see at the type level; and we could have it at the level of values.

 type family IsLeft (x :: k -> k1) :: Bool where IsLeft Left = True IsLeft x = False isLeft :: (a -> Either ab) -> Bool isLeft Left = True isLeft _ = False -- Constructor 'Left' should have 1 argument, but has been given none -- In the pattern: Left -- In an equation for 'isLeft': isLeft Left = True 

The reason this is not supported is efficiency. Type level calculations are performed at compile time in interpreted mode; therefore, we can allow ourselves to transfer a lot of metadata about the types and types of functions to match the template according to them.

Value-level calculations are compiled and should be as fast as possible. Saving enough metadata to support pattern matching application designers will complicate the compiler and slow down the program at run time; it's too much to pay for such an exotic feature.