Синонимы типов haskell

A type synonym is a new name for an existing type.
Values of different synonyms of the same type are entirely compatible.
In Haskell you can define a type synonym using type:

type MyChar = Char

In C you define a type synonym using typedef.

В функциональном языке программирования Haskell синонимом типа называется определение, записанное при помощи ключевого слова type. Такое определение формирует краткое (или мнемоническое) наименование некоторого типа, которое используется исключительно в качестве сокращения и является полностью тождественным самому типу. При определении синонимов типов можно использовать полиморфизм.

Основное назначение синонимов — создание единственного места, где определяется некоторый сложный тип данных, не связанный с конструированием объектов в памяти. Это единственное место (собственно, определение синонима) используется для того, чтобы в нужный момент заменить определение типа в одном месте, чтобы оно автоматически поменялось во всём исходном коде, где только используется.

Примеры:

type IntList = [Int]

type Field a = [[a]]

type Function a b = a -> b

Синонимы типов могут использоваться везде, где могут использоваться сами типы, за исключением одного места — определения экземпляров классов.

This corresponds to existential quantification. In pseudo-Haskell,

type NumberList = exists a . Num a => [a]

I say «pseudo» because GHC doesn’t allow introducing existential quantifiers on the fly — you need to create a separate datatype for that.

Now, most of the type you’d use NumberList to the left of the arrow, where «exists» effectively changes its meaning to «forall».

That is, instead of writing

isIncreasing :: NumberList -> Bool

which is the same as

isIncreasing :: (exists a . Num a => [a]) -> Bool

you can write

isIncreasing :: forall a . Num a => [a] -> Bool

or simply

isIncreasing :: Num a => [a] -> Bool

Of course, having a type synonym seems like less code, but it has disadvantages as well.
These disadvantages, by the way, are typical for object-oriented programming, which is based on the existential approach.

For example, you want to concatenate two lists. Ordinarily you would write

(++) :: forall a . [a] -> [a] -> [a]

(where again forall is unnecessary and added for clarity). Since a is the same across the entire signature, that ensures that you are concatenating lists of the same type.

How do we concatenate two numeric lists? A signature

(++) :: NumberList -> NumberList -> NumberList

wouldn’t work, since one list may contain Ints and the other may contain Doubles. And the resulting NumberList has to contain values of a single type.

Or, say, you want to find the sum of the list elements.

Usually you write

sum :: Num a => [a] -> a

Notice that the result type is the same as the type of list elements. Alas, we cannot do the same for NumberList!

sum :: NumberList -> ???

What is the result type? We could apply existential quantification there as well.

sum :: NumberList -> (exists a . Num a => a)

But now the connection between the original list type and the sum type is lost — at least for Haskell’s type system. If you then decide to write a function like

multiplySum :: Integer -> [Integer] -> Integer
multiplySum x ys = x * sum ys

then you’ll get a type error, because sum ys may be of any type, not necessarily of type Integer.

It would work if you pushed everything to extreme and made every type existentially-quantified — but then you’d end up essentially with another object-oriented-like language with all their problems.

(That said, there are some good use cases for existential quantification, of course.)

Cactus has already brilliantly addressed any questions you might have had about the implementation of the actAsig function, however, I feel that the questions in the title of the post have been left unaddressed.

First of all, Haskell has both a value level language (Object Language) and a type level language (Metalanguage). They are both powerful but not normally equally powerful, at least not for the same things. However, some things work on both sides, such as constants, variables and functions.

A type level constant is:

type Name = String

— this is normally called a «type alias»: it means Name is made in (almost) all respects equivalent to String. This doesn’t introduce a new type, only a new name for an existing type. This is useful for making the intent in your code more readable if you don’t want to introduce an actual new type with data or newtype, in which case you’d be introducing a new set of values that need to be mapped from and to existing sets of values (i.e. types). Therefore, type is just a thing of convenience, if you will, not a measure of safety, which is instead what data and newtype are for.

However, the Haskell type level language also supports functions, i.e. mappings from 1 or more types to some existing type. You could consider this to be parametric aliasing, so to speak.

type Assignation a = Name -> a

This creates a type function called Assignation with a parameter a. Given a type a, it returns some type, in this case the type Name -> a. So Assignation Int returns Name -> Int; Assignation Person returns Name -> Person and so on. Note that sometimes type functions don’t make use of one or more of their parameters, just like value level functions:

type Empty a = ()

If we combine this new knowledge, we can start thinking in terms of type level evaluation/reduction, i.e. evaluation that only takes places within the borders of type signatures, type functions, type class constraint computations etc.

Let’s apply this to the type signature of actAsig, step by step:

Assignation a -> Name   -> a -> Assignation a
Assignation a -> String -> a -> Assignation a
(Name -> a)   -> String -> a -> (Name -> a)
(String -> a) -> String -> a -> (String -> a)

So the higher order function type you are seeing on the last line above, is the actual type of actAsig, all abstractions eliminated/reduced away.

In human language terms, the signature descirbes a function that

1. takes a function f that maps strings to values of some type a.
2. takes a string
3. takes a value of that type a
4. returns a new function of the same type as f.

So in a way, actAsig processes functions: it takes functions and returns new, possibly modified functions.

Furthermore, Haskell also has (somewhat basic) means of fuzzying the line between typelevel and value-level, by making computations in the type realm involve references (dependencies) into the value level, but that’s outside of the scope of this post, and would lead us into the world of Dependent Types and Dependent Type Theory.

Example

Type synonym families are just type-level functions: they associate parameter types with result types. These come in three different varieties.

Closed type-synonym families

These work much like ordinary value-level Haskell functions: you specify some clauses, mapping certain types to others:

{-# LANGUAGE TypeFamilies #-}
type family Vanquisher a where
    Vanquisher Rock = Paper
    Vanquisher Paper = Scissors
    Vanquisher Scissors = Rock

data Rock=Rock; data Paper=Paper; data Scissors=Scissors

Open type-synonym families

These work more like typeclass instances: anybody can add more clauses in other modules.

type family DoubledSize w

type instance DoubledSize Word16 = Word32
type instance DoubledSize Word32 = Word64
-- Other instances might appear in other modules, but two instances cannot overlap
-- in a way that would produce different results.

Class-associated type synonyms

An open type family can also be combined with an actual class. This is usually done when, like with associated data families, some class method needs additional helper objects, and these helper objects can be different for different instances but may possibly also shared. A good example is VectorSpace class:

class VectorSpace v where
  type Scalar v :: *
  (*^) :: Scalar v -> v -> v

instance VectorSpace Double where
  type Scalar Double = Double
  μ *^ n = μ * n

instance VectorSpace (Double,Double) where
  type Scalar (Double,Double) = Double
  μ *^ (n,m) = (μ*n, μ*m)
  
instance VectorSpace (Complex Double) where
  type Scalar (Complex Double) = Complex Double
  μ *^ n = μ*n

Note how in the first two instances, the implementation of Scalar is the same. This would not be possible with an associated data family: data families are injective, type-synonym families aren’t.

While non-injectivity opens up some possibilities like the above, it also makes type inference more difficult. For instance, the following will not typecheck:

class Foo a where
  type Bar a :: *
  bar :: a -> Bar a
instance Foo Int where
  type Bar Int = String
  bar = show
instance Foo Double where
  type Bar Double = Bool
  bar = (>0)

main = putStrLn (bar 1)

In this case, the compiler can’t know what instance to use, because the argument to bar is itself just a polymorphic Num literal. And the type function Bar can’t be resolved in “inverse direction”, precisely because it’s not injective^† and hence not invertible (there could be more than one type with Bar a = String).

^†_{With only these two instances, it is actually injective, but the compiler can’t know somebody won’t add more instances later on and thereby break the behaviour.}

Типовые синонимы

Семейство синонимов типов — это только функции на уровне шрифта: они связывают типы параметров с типами результатов. Они представлены в трех разных вариантах.

Закрытые семейства синонимов

Они работают так же, как обычные функции Haskell на уровне значений: вы указываете некоторые предложения, сопоставляя некоторые типы с другими:

{-# LANGUAGE TypeFamilies #-}
type family Vanquisher a where
    Vanquisher Rock = Paper
    Vanquisher Paper = Scissors
    Vanquisher Scissors = Rock

data Rock=Rock; data Paper=Paper; data Scissors=Scissors

Открытые семейства синонимов типа

Они больше похожи на экземпляры typeclass: каждый может добавлять дополнительные предложения в другие модули.

type family DoubledSize w

type instance DoubledSize Word16 = Word32
type instance DoubledSize Word32 = Word64
-- Other instances might appear in other modules, but two instances cannot overlap
-- in a way that would produce different results.

Синонимы, связанные с классом

Семейство открытого типа также можно комбинировать с фактическим классом. Обычно это делается, когда, как и в случае связанных семейств данных , некоторый метод класса нуждается в дополнительных вспомогательных объектах, и эти вспомогательные объекты могут быть разными для разных экземпляров, но могут также совместно использоваться. Хорошим примером является класс VectorSpace :

class VectorSpace v where
  type Scalar v :: *
  (*^) :: Scalar v -> v -> v

instance VectorSpace Double where
  type Scalar Double = Double
  μ *^ n = μ * n

instance VectorSpace (Double,Double) where
  type Scalar (Double,Double) = Double
  μ *^ (n,m) = (μ*n, μ*m)
  
instance VectorSpace (Complex Double) where
  type Scalar (Complex Double) = Complex Double
  μ *^ n = μ*n

Обратите внимание, что в первых двух случаях реализация Scalar одинакова. Это было бы невозможно с ассоциированным семейством данных: семейства данных инъективны , семейства синонимов типа нет.

Хотя неинъективность открывает некоторые возможности, подобные описанным выше, это также затрудняет определение типа. Например, следующее правило не будет выглядеть:

class Foo a where
  type Bar a :: *
  bar :: a -> Bar a
instance Foo Int where
  type Bar Int = String
  bar = show
instance Foo Double where
  type Bar Double = Bool
  bar = (>0)

main = putStrLn (bar 1)

В этом случае компилятор не может знать, какой экземпляр использовать, потому что аргумент bar является собственно полиморфным литералом Num . И Bar функции типа не может быть разрешен в «обратном направлении», именно потому, что он не является инъективным ^† и, следовательно, не обратим (может быть более одного типа с Bar a = String ).

^† _{Только с этими двумя экземплярами он фактически является инъективным, но компилятор не может знать, что кто-то не добавит больше экземпляров позже и тем самым нарушит поведение.}

Типы данных

Семейства данных могут использоваться для создания типов данных, которые имеют разные реализации на основе их аргументов типа.

Автономные семейства данных

{-# LANGUAGE TypeFamilies #-}
data family List a
data instance List Char = Nil | Cons Char (List Char)
data instance List () = UnitList Int

В приведенной выше декларации Nil :: List Char и UnitList :: Int -> List ()

Связанные семейства данных

Семейства данных также могут быть связаны с классами. Это часто полезно для типов с «вспомогательными объектами», которые требуются для универсальных методов класса, но должны содержать различную информацию в зависимости от конкретного экземпляра. Например, для индексирования местоположений в списке требуется только одно число, тогда как в дереве вам нужно число, указывающее путь на каждом узле:

class Container f where
  data Location f
  get :: Location f -> f a -> Maybe a

instance Container [] where
  data Location [] = ListLoc Int
  get (ListLoc i) xs
    | i < length xs  = Just $ xs!!i
    | otherwise      = Nothing

instance Container Tree where
  data Location Tree = ThisNode | NodePath Int (Location Tree)
  get ThisNode (Node x _) = Just x
  get (NodePath i path) (Node _ sfo) = get path =<< get i sfo

приемистости

Тип Семьи не обязательно инъективны. Поэтому мы не можем вывести параметр из приложения. Например, в servant , заданном Server a типа Server a мы не можем вывести тип a . Чтобы решить эту проблему, мы можем использовать Proxy . Например, в servant функция serve имеет тип ... Proxy a -> Server a -> ... Мы можем сделать вывод , из a Proxy a потому , что Proxy определяются data , которые инъективны.

LiberalTypeSynonyms

Расслабьтесь многие из правил Хаскелла 98 по определению синонимов типов.

Синонимы типов похожи на макросы на уровне типов, но Haskell 98 налагает множество правил на объявления отдельных синонимов. С расширением LiberalTypeSynonyms GHC выполняет проверку достоверности типов только после раскрытия синонимов типов . Это означает, что GHC может быть более либеральным в отношении синонимов типов, чем Haskell 98.

• Вы можете применить синоним типа к типу forall:

  type Foo a = a -> a -> Bool
  
  f :: Foo (forall b. b->b)
  

  После раскрытия синонима f имеет допустимый (в GHC) тип:

  f :: (forall b. b->b) -> (forall b. b->b) -> Bool
  

• К частично применяемому синониму типа можно применить синоним типа:

  type Generic i o = forall x. i x -> o x
  type Id x = x
  
  foo :: Generic Id []
  

  После раскрытия синонима foo имеет допустимый (в GHC) тип:

  foo :: forall x. x -> [x]
  

GHC выполняет проверку перед расширением синонимов.

После расширения синонимов типов GHC выполняет проверку типов на валидность,и ищет следующие пороки,которые не обнаруживаются простой проверкой вида:

• Конструктор типа, применяемый к типу, включающему для всех (если ImpredicativeTypes выключен)
• Частично применяемый синоним типа.

Так,например,это будет отклонено:

type Pr = forall a. a

h :: [Pr]
h = ...

потому что GHC не позволяет использовать конструкторы типов для всех типов.