Когда полезны высшие родственные типы?

Некоторое время я занимаюсь разработкой на F #, и мне это нравится. Однако одного модного слова, которого, как мне известно, не существует в F #, является высокодородные типы. Я читал материал о высокородных типах и думаю, что понимаю их определение. Я просто не знаю, почему они полезны. Может ли кто-нибудь привести несколько примеров того, какие типы более высокого порядка упрощают в Scala или Haskell, что требует обходных путей в F #? Также для этих примеров, какие обходные пути были бы без типов высшего порядка (или наоборот в F #)? Возможно, я просто так привык работать над этим, что не замечаю отсутствия этой функции.

(Я думаю) я понимаю, что вместо myList |> List.map fили myList |> Seq.map f |> Seq.toListболее высокодородных типов вы можете просто писать, myList |> map fи он вернет List. Это здорово (при условии, что это правильно), но кажется мелочным? (И нельзя ли это сделать, просто разрешив перегрузку функций?) Я обычно Seqвсе равно конвертирую, а потом могу конвертировать во все, что захочу. Опять же, возможно, я слишком привык работать над этим. Но есть ли какой-нибудь пример, когда высокоуровневые типы действительно спасают вас от нажатия клавиш или с точки зрения безопасности типов?

Итак, тип типа - это его простой тип. Например, Intимеет вид, *что означает, что это базовый тип и может быть создан по значениям. По некоторому вольному определению высокодородного типа (а я не уверен, где F # проводит черту, поэтому давайте просто включим его) полиморфные контейнеры являются отличным примером высокородного типа.

data List a = Cons a (List a) | Nil

Конструктор типа Listимеет вид, * -> *что означает, что ему необходимо передать конкретный тип, чтобы получить конкретный тип: List Intможет иметь жителей как, [1,2,3]но Listсам не может.

Я собираюсь предположить, что преимущества полиморфных контейнеров очевидны, но существуют более полезные * -> *типы типов, чем просто контейнеры. Например, отношения

data Rel a = Rel (a -> a -> Bool)

или парсеры

data Parser a = Parser (String -> [(a, String)])

у обоих тоже есть добрые * -> *.

Однако мы можем пойти дальше в Haskell, имея типы с видами еще более высокого порядка. Например, мы могли бы поискать тип с добром (* -> *) -> *. Простым примером этого может быть Shapeпопытка заполнить какой-либо контейнер * -> *.

data Shape f = Shape (f ())

[(), (), ()] :: Shape List

Это полезно Traversable, например, для характеристики s в Haskell, поскольку их всегда можно разделить по форме и содержимому.

split :: Traversable t => t a -> (Shape t, [a])

В качестве другого примера рассмотрим дерево, параметризованное по типу ветки. Например, нормальное дерево может быть

data Tree a = Branch (Tree a) a (Tree a) | Leaf

Но мы видим, что тип ветки содержит a Pairof Tree as, и поэтому мы можем извлечь эту часть из типа параметрически.

data TreeG f a = Branch a (f (TreeG f a)) | Leaf

data Pair a = Pair a a
type Tree a = TreeG Pair a

TreeGКонструктор этого типа имеет вид (* -> *) -> * -> *. Мы можем использовать его для создания других интересных вариаций, таких какRoseTree

type RoseTree a = TreeG [] a

rose :: RoseTree Int
rose = Branch 3 [Branch 2 [Leaf, Leaf], Leaf, Branch 4 [Branch 4 []]]

Или патологические, как MaybeTree

data Empty a = Empty
type MaybeTree a = TreeG Empty a

nothing :: MaybeTree a
nothing = Leaf

just :: a -> MaybeTree a
just a = Branch a Empty

Или TreeTree

type TreeTree a = TreeG Tree a

treetree :: TreeTree Int
treetree = Branch 3 (Branch Leaf (Pair Leaf Leaf))

Другое место, где это проявляется, - это «алгебры функторов». Если мы отбросим несколько уровней абстрактности, это лучше будет рассматривать как складку, например sum :: [Int] -> Int. Алгебры параметризованы над функтором и носителем . Функтор имеет вид * -> *и носитель вид *так вообще

data Alg f a = Alg (f a -> a)

имеет вид (* -> *) -> * -> *. Algполезен из-за его связи с типами данных и схемами рекурсии, построенными на них.

-- | The "single-layer of an expression" functor has kind `(* -> *)`
data ExpF x = Lit Int
            | Add x x
            | Sub x x
            | Mult x x

-- | The fixed point of a functor has kind `(* -> *) -> *`
data Fix f = Fix (f (Fix f))

type Exp = Fix ExpF

exp :: Exp
exp = Fix (Add (Fix (Lit 3)) (Fix (Lit 4))) -- 3 + 4

fold :: Functor f => Alg f a -> Fix f -> a
fold (Alg phi) (Fix f) = phi (fmap (fold (Alg phi)) f)

Наконец, хотя они теоретически возможны, я никогда не видел конструктора типа даже более высокого порядка. Иногда мы видим функции этого типа, например mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, но я думаю, вам придется покопаться в прологе типов или в литературе с зависимой типизацией, чтобы увидеть такой уровень сложности типов.

Рассмотрим Functorкласс типа в Haskell, где f- переменная типа более высокого порядка:

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

Сигнатура этого типа говорит о том, что fmap изменяет параметр типа fот aдо b, но оставляет без изменений f. Итак, если вы используете fmapсписок, вы получаете список, если вы используете его через синтаксический анализатор, вы получаете синтаксический анализатор и так далее. И это статические гарантии времени компиляции.

Я не знаю F #, но давайте посмотрим, что произойдет, если мы попытаемся выразить Functorабстракцию на таком языке, как Java или C #, с наследованием и дженериками, но без дженериков более высокого порядка. Первая попытка:

interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}

Проблема с этой первой попыткой заключается в том, что реализация интерфейса может возвращать любой класс, который реализует Functor. Кто-то может написать, FunnyList<A> implements Functor<A>чей mapметод возвращает коллекцию другого типа, или даже что-то еще, что вообще не является коллекцией, но все же остается Functor. Кроме того, когда вы используете этот mapметод, вы не можете вызывать какие-либо методы, зависящие от подтипа, для результата, если вы не преобразуете его в тот тип, который вы действительно ожидаете. Итак, у нас есть две проблемы:

1. Система типов не позволяет нам выразить инвариант, что mapметод всегда возвращает тот же Functorподкласс, что и получатель.
2. Следовательно, не существует статически безопасного способа вызова не- Functorметода для результата map.

Вы можете попробовать и другие, более сложные способы, но ни один из них не работает. Например, вы можете попробовать расширить первую попытку, определив подтипы, Functorкоторые ограничивают тип результата:

interface Collection<A> extends Functor<A> {
    Collection<B> map(Function<A, B> f);
}

interface List<A> extends Collection<A> {
    List<B> map(Function<A, B> f);
}

interface Set<A> extends Collection<A> {
    Set<B> map(Function<A, B> f);
}

interface Parser<A> extends Functor<A> {
    Parser<B> map(Function<A, B> f);
}

// …

Это помогает запретить разработчикам этих более узких интерфейсов возвращать Functorиз mapметода неправильный тип , но, поскольку нет ограничений на количество Functorреализаций, которые вы можете иметь, нет ограничений на то, сколько более узких интерфейсов вам понадобится.

( EDIT: и обратите внимание, что это работает только потому, что Functor<B>отображается как тип результата, и поэтому дочерние интерфейсы могут сузить его. Итак, AFAIK мы не можем сузить оба использования Monad<B>в следующем интерфейсе:

interface Monad<A> {
    <B> Monad<B> flatMap(Function<? super A, ? extends Monad<? extends B>> f);
}

В Haskell с переменными типа более высокого ранга это так (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Еще одна попытка - использовать рекурсивные универсальные шаблоны, чтобы попытаться ограничить интерфейс типом результата подтипа самим подтипом. Пример игрушки:

/**
 * A semigroup is a type with a binary associative operation.  Law:
 *
 * > x.append(y).append(z) = x.append(y.append(z))
 */
interface Semigroup<T extends Semigroup<T>> {
    T append(T arg);
}

class Foo implements Semigroup<Foo> {
    // Since this implements Semigroup<Foo>, now this method must accept 
    // a Foo argument and return a Foo result. 
    Foo append(Foo arg);
}

class Bar implements Semigroup<Bar> {
    // Any of these is a compilation error:

    Semigroup<Bar> append(Semigroup<Bar> arg);

    Semigroup<Foo> append(Bar arg);

    Semigroup append(Bar arg);

    Foo append(Bar arg);

}

Но этот вид техники (который довольно загадочен для вашего обычного разработчика ООП, черт возьми, также для вашего обычного функционального разработчика) все еще не может выразить желаемое Functorограничение:

interface Functor<FA extends Functor<FA, A>, A> {
    <FB extends Functor<FB, B>, B> FB map(Function<A, B> f);
}

Проблема здесь в том, что это не ограничивает FBиспользование того же, Fчто и FA- поэтому, когда вы объявляете тип List<A> implements Functor<List<A>, A>, mapметод все равно может возвращать NotAList<B> implements Functor<NotAList<B>, B>.

Последняя попытка в Java с использованием необработанных типов (непараметризованные контейнеры):

interface FunctorStrategy<F> {
    F map(Function f, F arg);
} 

Здесь Fбудут созданы экземпляры непараметризованных типов, таких как просто Listили Map. Это гарантирует, что a FunctorStrategy<List>может возвращать только a, Listно вы отказались от использования переменных типа для отслеживания типов элементов списков.

Суть проблемы здесь в том, что такие языки, как Java и C #, не позволяют параметрам типа иметь параметры. В Java, если Tэто переменная типа, вы можете написать Tи List<T>, но не T<String>. Высокородные типы снимают это ограничение, чтобы у вас могло быть что-то вроде этого (не до конца продуманное):

interface Functor<F, A> {
    <B> F<B> map(Function<A, B> f);
}

class List<A> implements Functor<List, A> {

    // Since F := List, F<B> := List<B>
    <B> List<B> map(Function<A, B> f) {
        // ...
    }

}

И, в частности, обращаясь к этому биту:

(Я думаю) я понимаю, что вместо myList |> List.map fили myList |> Seq.map f |> Seq.toListболее высокодородных типов вы можете просто писать, myList |> map fи он вернет List. Это здорово (при условии, что это правильно), но кажется мелочным? (И нельзя ли это сделать, просто разрешив перегрузку функций?) Я обычно Seqвсе равно конвертирую, а потом могу конвертировать во все, что захочу.

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

В Haskell, однако, этот Functorкласс является более общим; это не связано с понятием последовательностей. Вы можете реализовать fmapтипы, которые не имеют хорошего сопоставления с последовательностями, например IOдействия, комбинаторы синтаксического анализатора, функции и т. Д .:

instance Functor IO where
    fmap f action =
        do x <- action
           return (f x)

 -- This declaration is just to make things easier to read for non-Haskellers 
newtype Function a b = Function (a -> b)

instance Functor (Function a) where
    fmap f (Function g) = Function (f . g)  -- `.` is function composition

Концепция «отображения» на самом деле не привязана к последовательностям. Лучше всего понять законы функторов:

(1) fmap id xs == xs
(2) fmap f (fmap g xs) = fmap (f . g) xs

Очень неформально:

1. Первый закон гласит, что отображение с функцией identity / noop - это то же самое, что и бездействие.
2. Второй закон гласит, что любой результат, который вы можете получить, нанеся двойное отображение, вы также можете получить однократным отображением.

Вот почему вы хотите fmapсохранить тип - потому что, как только вы получаете mapоперации, которые производят другой тип результата, становится намного, намного сложнее давать такие гарантии.

Я не хочу повторять информацию в некоторых отличных ответах, которые уже здесь, но есть ключевой момент, который я хотел бы добавить.

Обычно вам не нужны высокодородные типы для реализации какой-либо конкретной монады или функтора (или аппликативного функтора, или стрелки, или ...). Но в большинстве случаев это упускает из виду суть.

В общем, я обнаружил, что когда люди не видят полезности функторов / монад / каких-либо функций, это часто происходит потому, что они думают об этих вещах по очереди . Операции Functor / monad / etc действительно ничего не добавляют к какому-либо одному экземпляру (вместо вызова bind, fmap и т.д. я мог бы просто вызвать любые операции, которые я использовал для реализации bind, fmap и т.д.). На самом деле вам нужны эти абстракции, чтобы иметь код, который в общем работает с любым функтором / монадой / и т. Д.

В контексте, где такой общий код широко используется, это означает, что каждый раз, когда вы пишете новый экземпляр монады, ваш тип немедленно получает доступ к большому количеству полезных операций , которые уже были написаны для вас . В этом смысл видеть монады (и функторы, и ...) повсюду; не так , что я могу использовать , bindа не concatи mapреализовать myFunkyListOperation(который не получает ничего мне сам по себе), а так , что , когда я пришел к необходимости myFunkyParserOperationи myFunkyIOOperationя могу повторно использовать код , который я изначально видел в терминах списков , потому что это на самом деле монады-родовой .

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

Для более специфической перспективы .NET я написал об этом в блоге некоторое время назад. Суть в том, что с высокодородными типами вы потенциально можете повторно использовать одни и те же блоки LINQ между IEnumerablesи IObservables, но без высокодородных типов это невозможно.

Ближайший вы могли бы получить (я понял, после размещения в блоге), чтобы сделать свой собственный IEnumerable<T>и IObservable<T>, упрочив их как с IMonad<T>. Это позволит вам повторно использовать LINQ блоки , если они обозначены IMonad<T>, но тогда это уже не типизированный , потому что она позволяет смешивать и матч , IObservablesи IEnumerablesв том же блоке, что в то время как это может показаться интригующим , чтобы включить это, вы бы в основном просто получить неопределенное поведение.

Позже я написал пост о том, как Haskell упрощает эту задачу. (На самом деле, без операции - ограничение блока определенным типом монады требует кода; включение повторного использования по умолчанию).

Наиболее часто используемый пример полиморфизма высших типов в Haskell - это Monadинтерфейс. Functorи так Applicativeже высокородны, поэтому я покажу Functor, чтобы показать что-нибудь лаконичное.

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

Теперь рассмотрим это определение, посмотрев, как используется переменная типа f. Вы увидите, что fэто не может означать тип, имеющий значение. Вы можете идентифицировать значения в этой сигнатуре типа, потому что они аргументы и результаты функции. Итак, переменные типа aи bявляются типами, которые могут иметь значения. Таковы выражения типов f aи f b. Но не fсам. fявляется примером переменной более высокого порядка. Учитывая, что *это тип типов, которые могут иметь значения, они fдолжны иметь вид * -> *. То есть он принимает тип, который может иметь значения, потому что из предыдущего исследования мы знаем, что aи bдолжны иметь значения. И мы тоже это знаем f aиf b должен иметь значения, поэтому он возвращает тип, который должен иметь значения.

Это позволяет fиспользовать в определении Functorпеременной более высокого типа.

Интерфейсы Applicativeи Monadдобавляют больше, но они совместимы. Это означает, что они также работают с переменными типа с видом * -> *.

Работа с высокодородными типами вводит дополнительный уровень абстракции - вы не ограничены только созданием абстракций над базовыми типами. Вы также можете создавать абстракции над типами, которые изменяют другие типы.