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

88

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

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

омар
источник
2
Многие функции Control.Monad используют более высокие типы, так что вы можете поискать там несколько примеров. В F # реализации придется повторять для каждого конкретного типа монады.
Ли
1
@Lee, но не могли бы вы просто создать интерфейс, IMonad<T>а затем вернуть его, например, IEnumerable<int>или IObservable<int>когда закончите? Все это только для того, чтобы избежать кастинга?
лобстеризм
4
Ну, приведение типов небезопасно, так что это отвечает на ваш вопрос о безопасности типов. Другая проблема заключается в том, как это returnбудет работать, поскольку это действительно относится к типу монады, а не к конкретному экземпляру, поэтому вы вообще не захотите помещать его в IMonadинтерфейс.
Ли
4
@ Ли, да, я просто подумал, что вам нужно привести окончательный результат после выражения, не важно, потому что вы только что создали выражение, чтобы вы знали тип. Но похоже, что вам также нужно будет использовать каждый имплант bindaka и SelectManyт. Д. Это означает, что кто-то может использовать API для bindan IObservableto an IEnumerableи предполагать, что он будет работать, что да, черт возьми, если это так и нет никакого способа обойти это. Просто не уверен на 100%, что другого пути нет.
лобстеризм
5
Отличный вопрос. Я еще не видел ни одного убедительного практического примера использования этой языковой функции IRL.
JD

Ответы:

78

Итак, тип типа - это его простой тип. Например, 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, но я думаю, вам придется покопаться в прологе типов или в литературе с зависимой типизацией, чтобы увидеть такой уровень сложности типов.

Дж. Абрахамсон
источник
3
Я проверю и отредактирую код через несколько минут, сейчас я на своем телефоне.
Дж. Абрахамсон
12
@ J.Abrahamson +1 за хороший ответ и наличие терпения набрать его на своем телефоне O_o
Daniel Gratzer
3
@lobsterism A TreeTree- это просто патология, но на практике это означает, что у вас есть два разных типа деревьев, переплетенных друг с другом - если продвигать эту идею немного дальше, вы можете получить очень мощные концепции безопасности типов, такие как статически безопасный красный / черные деревья и аккуратный статически сбалансированный тип FingerTree.
Дж. Абрахамсон
3
@JonHarrop Стандартный пример из реальной жизни - это абстрагирование над монадами, например, с помощью стеков эффектов в стиле mtl. Однако вы можете не согласиться с тем, что это ценно для реального мира. Я думаю, что в целом ясно, что языки могут успешно существовать без HKT, поэтому любой пример будет предоставлять некоторую абстракцию, более сложную, чем другие языки.
Дж. Абрахамсон
2
Вы можете иметь, например, подмножества разрешенных эффектов в различных монадах и абстрагироваться от любых монад, соответствующих этой спецификации. Например, монады, реализующие «телетайп», который позволяет читать и писать на уровне символов, могут включать как ввод-вывод, так и абстракцию канала. В качестве другого примера вы можете абстрагироваться от различных асинхронных реализаций. Без HKT вы ограничиваете любой тип, составленный из этой общей части.
Дж. Абрахамсон
64

Рассмотрим 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операции, которые производят другой тип результата, становится намного, намного сложнее давать такие гарантии.

Луис Касильяс
источник
Так что я заинтересован в вашем последнем бите, почему это полезно иметь fmapна Function aкогда он уже имеет .работу? Я понимаю, почему .имеет смысл быть определением fmapop, но я просто не понимаю, где вам когда-либо нужно было бы использовать fmapвместо .. Может быть, если бы вы могли привести пример, где это было бы полезно, это помогло бы мне понять.
лобстеризм
1
Ах, понятно: вы можете сделать fn doubleиз функтора, где double [1, 2, 3]дает [2, 4, 6]и double sinдает fn, что в два раза больше sin. Я могу понять, где, если вы начнете думать с таким мышлением, когда вы запускаете карту на массиве, вы ожидаете возврата массива, а не только seq, потому что, ну, мы работаем здесь с массивами.
лобстеризм
@lobsterism: существуют алгоритмы / методы, которые полагаются на возможность абстрагироваться Functorи позволять клиенту библиотеки выбирать его. Ответ Дж. Абрахамсона дает один пример: рекурсивные складки можно обобщить с помощью функторов. Другой пример - свободные монады; их можно рассматривать как своего рода библиотеку реализации универсального интерпретатора, в которой клиент предоставляет «набор инструкций» как произвольный Functor.
Луис Касильяс
3
Технически разумный ответ, но он заставляет меня задуматься, зачем кому-то это нужно на практике. Я не обнаружил, что обращаюсь к Haskell Functorили a SemiGroup. Где в реальных программах больше всего используется эта языковая функция?
JD
28

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

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

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

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

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

Бен
источник
9
Это ближе к полезному ответу, чем любой из других ответов, которые я читал до сих пор, но я все же хотел бы увидеть одно практическое приложение, в котором полезны более высокие типы.
JD
«На самом деле вам нужны эти абстракции, чтобы иметь код, который в общем работает с любым функтором / монадой». 13 лет назад F # получил монады в форме вычислительных выражений, изначально имевшие монады seq и async. Сегодня F # пользуется третьей монадой - запросом. С таким небольшим количеством монад, у которых так мало общего, зачем вам абстрагироваться от них?
JD
@JonHarrop Вы четко знаете, что другие люди писали код, используя огромное количество монад (и функторов, стрелок и т. Д.; HKT - это не только монады) на языках, которые действительно поддерживают HKT, и находят способы их абстрагирования. И, очевидно, вы не думаете, что какой-либо из этого кода имеет какое-либо практическое применение, и вам любопытно, почему другие люди потрудились его написать. Какого рода понимание вы надеетесь получить, вернувшись, чтобы начать обсуждение сообщения шестилетней давности, которое вы уже комментировали 5 лет назад?
Бен
«в надежде получить прибыль, вернувшись, чтобы начать обсуждение поста шестилетней давности». Ретроспектива. Оглядываясь назад, мы теперь знаем, что абстракции F # над монадами в основном остаются неиспользованными. Следовательно, способность абстрагироваться от трех совершенно разных вещей неудобна.
JD
@JonHarrop Суть моего ответа заключается в том, что отдельные монады (или функторы, и т. Д.) На самом деле не более полезны, чем аналогичные функции, выраженные без кочевого интерфейса, но это объединение множества разрозненных вещей. Я полагаюсь на ваш опыт работы с F #, но если вы говорите, что он имеет только 3 отдельных монады (вместо того, чтобы реализовывать монадический интерфейс для всех концепций, которые могут иметь один, таких как сбой, отслеживание состояния, синтаксический анализ и т. Д.), Тогда да, неудивительно, что вы не получите особой пользы от объединения этих трех вещей.
Бен
15

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

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

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

Дакс Фол
источник
2
Я дам вам +1 за то, что это единственный ответ, в котором упоминается что-то практическое, но я не думаю, что когда-либо использовал IObservablesв производственном коде.
JD
5
@JonHarrop Это кажется неправдой. В F # все события есть IObservable, и вы используете события в главе о WinForms в своей книге.
Дакс Фол
1
Microsoft заплатила мне за написание этой книги и потребовала, чтобы я осветил эту функцию. Я не помню, как использовал события в производственном коде, но посмотрю.
JD
Полагаю, возможно повторное использование IQueryable и IEnumerable
KolA
Четыре года спустя, и я закончил поиски: мы сняли Rx с производства.
JD
13

Наиболее часто используемый пример полиморфизма высших типов в 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добавляют больше, но они совместимы. Это означает, что они также работают с переменными типа с видом * -> *.

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

Карл
источник
4
Еще одно прекрасное техническое объяснение того, что такое высшие виды, заставляет меня задуматься, для чего они полезны. Где вы использовали это в реальном коде?
JD