Когда полезны более качественные типы?

Ответ 1

Таким образом, тип типа - его простой тип. Например, 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 в Haskell, например, поскольку их всегда можно разделить на их форму и содержимое.

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

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

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

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

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 []]]

Или такие патологические, как a 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

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

Ответ 2

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

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

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

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

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

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

• Система типов не позволяет нам выразить инвариант, что метод map всегда возвращает тот же подкласс Functor, что и приемник.
• Поэтому нет статически безопасного типа для вызова метода 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, которые вы можете иметь, нет ограничений на сколько узких интерфейсов вам понадобится.

( РЕДАКТИРОВАТЬ: И обратите внимание, что это работает только потому, что в качестве типа результата появляется 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 может еще вернуть a NotAList<B> implements Functor<NotAList<B>, B>.

Заключительная попытка на Java использовать необработанные типы (непараметризированные контейнеры):

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

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

В основе проблемы лежит то, что такие языки, как Java и С#, не позволяют параметрам типа иметь параметры. В 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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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