Ответ 1

Некоторая терминология:

• Вид * иногда называют землей. Вы можете думать о нем как о порядке.
• Любой вид формы * → * ->... → * с хотя бы одной стрелкой - это первый порядок.
• Тип более высокого порядка - это "вложенная стрелка слева", например, (* → *) → *.

Порядок состоит в том, что глубина левого вложения стрелок, например, (* → *) → * является вторым порядком, ((* → *) → *) → * является третьим порядком и т.д.. (FWIW, то же понятие относится и к самим типам: функция второго порядка - это тип, тип которого имеет, например, форму (A → B) → C)

Типы неземного вида (порядок> 0) также называются конструкторами типов (а в некоторой литературе относятся только типы наземного типа как "типы"). Более высокий тип (конструктор) - это тип, который имеет более высокий порядок (порядок> 1).

Следовательно, тип более высокого рода - это тот, который принимает аргумент неземного вида. Для этого потребуются переменные типа неземного типа, которые не поддерживаются на многих языках. Примеры в Haskell:

type Ground = Int
type FirstOrder a = Maybe a  -- a is ground
type SecondOrder c = c Int   -- c is a first-order constructor
type ThirdOrder c = c Maybe  -- c is second-order

Последние два являются более высокопоставленными.

Аналогично, более высокоподобный полиморфизм описывает наличие (параметрически) полиморфных значений, которые абстрагируются от типов, которые не измельчены. Опять же, несколько языков поддерживают это. Пример:

f : forall c. c Int -> c Int  -- c is a constructor

Утверждение о том, что Rust поддерживает параметрический полиморфизм "вместо" более высоких типов, не имеет смысла. Оба являются разными параметрами параметризации, которые дополняют друг друга. И когда вы совмещаете оба, у вас более высокий тип полиморфизма.

Ответ 2

Простой пример того, что Rust не может сделать, это нечто вроде класса Haskell Functor.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

-- a couple examples:
instance Functor Maybe where
    -- fmap :: (a -> b) -> Maybe a -> Maybe b
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

instance Functor [] where
    -- fmap :: (a -> b) -> [a] -> [b]
    fmap _ []     = []
    fmap f (x:xs) = f x : fmap f xs

Обратите внимание, что экземпляры определены в конструкторе типа, Maybe или [], вместо полностью примененного типа Maybe a or [a].

Это не просто салонный трюк. Он имеет сильное взаимодействие с параметрическим полиморфизмом. Поскольку переменные типа a и b в типе fmap не ограничены определением класса, экземпляры Functor не могут изменить свое поведение на их основе. Это невероятно сильное свойство в рассуждении о коде с типами и где многие из тех, из которых исходит сила системы типа Haskell.

У него есть еще одно свойство - вы можете написать код, абстрактный в более высоких типах переменных. Вот несколько примеров:

focusFirst :: Functor f => (a -> f b) -> (a, c) -> f (b, c)
focusFirst f (a, c) = fmap (\x -> (x, c)) (f a)

focusSecond :: Functor f => (a -> f b) -> (c, a) -> f (c, b)
focusSecond f (c, a) = fmap (\x -> (c, x)) (f a)

Я признаю, что эти типы начинают выглядеть абстрактной глупостью. Но они оказываются действительно практичными, когда у вас есть пара помощников, которые используют преимущества более высокого рода абстракции.

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    -- fmap :: (a -> b) -> Identity a -> Identity b
    fmap f (Identity x) = Identity (f x)

newtype Const c b = Const { getConst :: c }

instance Functor (Const c) where
    -- fmap :: (a -> b) -> Const c a -> Const c b
    fmap _ (Const c) = Const c

set :: ((a -> Identity b) -> s -> Identity t) -> b -> s -> t
set f b s = runIdentity (f (\_ -> Identity b) s)

get :: ((a -> Const a b) -> s -> Const a t) -> s -> a
get f s = getConst (f (\x -> Const x) s)

(Если бы я допустил какие-либо ошибки там, может кто-то их исправить? Я переопределяю основную отправную точку lens из памяти без компилятора.)

Функции focusFirst и focusSecond могут быть переданы в качестве первого аргумента либо для get либо для set, поскольку переменная типа f в своих типах может быть унифицирована с более конкретными типами в get и set. Возможность абстрагироваться от переменной более высокого типа f позволяет использовать функции определенной формы как в качестве сеттеров, так и для геттеров в произвольных типах данных. Это одно из двух основных понятий, которые привели к lens библиотеки lens. Он не мог существовать без такой абстракции.

(Для того, что стоит, другое ключевое понимание заключается в том, что определение линз как функции подобно тому, что композиция линз является простой составной функцией.)

Так что нет, там больше, чем просто возможность принять переменную типа. Важной частью является возможность использования переменных типа, которые соответствуют конструкторам типа, а не конкретному (если неизвестно) типу.

Ответ 3

Параметрический полиморфизм просто ссылается на свойство, которое функция не может использовать в своем определении какую-либо конкретную особенность типа (или вида); это полный черный ящик. Стандартный пример - length :: [a] → Int, который работает только со структурой списка, а не с конкретными значениями, хранящимися в списке.

Стандартным примером HKT является класс Functor, где fmap :: (a → b) → fa → fb. В отличие от length, где a имеет вид *, f имеет вид * → *. fmap также показывает параметрический полиморфизм, поскольку fmap не может использовать какое-либо свойство a или b в его определении.

fmap демонстрирует специальный полиморфизм, поскольку определение может быть адаптировано к конкретному конструктору типа f для которого он определен. То есть существуют отдельные определения fmap для f ~ [], f ~ Maybe и т.д. Разница заключается в том, что f объявляется как часть определения typeclass, а не просто является частью определения fmap. (Действительно, для поддержки некоторой степени ad hoc-полиморфизма добавлены стили классов. Без классов типов существует только параметрический полиморфизм. Вы можете написать функцию, которая поддерживает один конкретный тип или любой конкретный тип, но не меньшую коллекцию между ними.)

Ответ 4

Я собираюсь возобновить его: тип более высокого типа - это только функция более высокого порядка на уровне уровня.

Но минута:

Рассмотрим monad трансформаторы:

newtype StateT s m a :: * -> (* -> *) -> * -> *

Вот,

- s is the desired type of the state
- m is a functor, another monad that StateT will wrap
- a is the return type of an expression of type StateT s m

Что такое более высокий тип?

m :: (* -> *)

Потому что принимает тип вида * и возвращает вид типа *.

Это как функция для типов, т.е. Конструктор типа

* -> *

В таких языках, как Java, вы не можете

class ClassExample<T, a> {
    T<a> function()
}

В Haskell T будет иметь вид *->*, но тип Java (т.е. класс) не может иметь параметр типа такого типа, более высокий тип.

Кроме того, если вы не знаете, в базовом Haskell выражение должно иметь тип, который имеет вид *, то есть "конкретный тип". Любой другой тип, например * → *.

Например, вы не можете создать выражение типа Maybe. Это должны быть типы, применяемые к аргументу, подобному Maybe Int, Maybe String и т.д. Другими словами, полностью применяемые конструкторы типов.