Kiedy są przydatne typy wyższego rodzaju?

Od jakiegoś czasu zajmuję się programowaniem w języku F # i podoba mi się to. Jednak jedno słowo, które wiem, że nie istnieje w F #, to typy wyższego rodzaju. Przeczytałem materiały o typach wyższego rzędu i myślę, że rozumiem ich definicję. Po prostu nie jestem pewien, dlaczego są przydatne. Czy ktoś może podać przykłady tego, co typy wyższego rodzaju ułatwiają w Scala lub Haskell, które wymagają obejść w języku F #? Również w tych przykładach, jakie byłyby obejścia bez typów wyższego rodzaju (lub odwrotnie w F #)? Może jestem tak przyzwyczajony do pracy nad tym, że nie zauważam braku tej funkcji.

(Myślę) Rozumiem, że zamiast myList |> List.map flub myList |> Seq.map f |> Seq.toListwyższego rodzaju typy pozwalają po prostu napisać myList |> map fi zwróci List. To świetnie (zakładając, że to prawda), ale wydaje się trochę małostkowe? (I czy nie można tego zrobić po prostu zezwalając na przeciążanie funkcji?) Zwykle konwertuję na Seqi tak, a potem mogę konwertować na cokolwiek chcę. Znowu, może jestem po prostu zbyt przyzwyczajony do tego. Ale czy jest jakiś przykład, w którym typy wyższego rzędu naprawdę oszczędzają cię w przypadku naciśnięć klawiszy lub bezpieczeństwa typów?

Więc rodzaj typu jest jego prostym typem. Na przykład Intma rodzaj, *co oznacza, że ​​jest to typ podstawowy i można go utworzyć za pomocą wartości. Według pewnej luźnej definicji typu wyższego rodzaju (i nie jestem pewien, gdzie F # rysuje linię, więc po prostu ją uwzględnij) kontenery polimorficzne są doskonałym przykładem typu wyższego rodzaju.

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

Konstruktor typu Listma rodzaj, * -> *co oznacza, że ​​musi zostać przekazany konkretny typ, aby uzyskać konkretny typ: List Intmoże mieć mieszkańców takich jak, [1,2,3]ale Listsam nie może.

Zakładam, że zalety polimorficznych pojemników są oczywiste, ale istnieją bardziej przydatne * -> *typy niż tylko pojemniki. Na przykład relacje

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

lub parsery

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

obaj też są mili * -> *.

Możemy jednak pójść dalej w Haskell, mając typy z jeszcze wyższymi rodzajami. Na przykład moglibyśmy szukać typu z rodzajem (* -> *) -> *. Prostym przykładem może być Shapepróba napełnienia pojemnika * -> *.

data Shape f = Shape (f ())

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

Jest to przydatne na przykład do charakteryzowania Traversables w Haskellu, ponieważ zawsze można je podzielić według kształtu i zawartości.

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

Jako inny przykład rozważmy drzewo, które jest sparametryzowane na rodzaj gałęzi, które ma. Na przykład może nim być normalne drzewo

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

Ale widzimy, że typ gałęzi zawiera a Pairz Tree as, więc możemy wyodrębnić ten fragment z typu parametrycznie

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

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

Ten TreeGkonstruktor typu ma rodzaj (* -> *) -> * -> *. Możemy go użyć do tworzenia interesujących innych odmian, takich jak aRoseTree

type RoseTree a = TreeG [] a

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

Lub patologiczne, takie jak 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

Lub a TreeTree

type TreeTree a = TreeG Tree a

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

Innym miejscem, w którym się to pojawia, są „algebry funktorów”. Jeśli upuścimy kilka warstw abstrakcji, można to lepiej uznać za fałdę, na przykład sum :: [Int] -> Int. Algebry są parametryzowane względem funktora i nośnej . Funktor ma rodzaj * -> *i rodzaj nośnika *tak zupełnie

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

ma miły (* -> *) -> * -> *. Algużyteczne ze względu na związek z typami danych i schematami rekursji zbudowanymi na nich.

-- | 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)

Wreszcie, chociaż teoretycznie są one możliwe, nigdy nie widziałem konstruktora typu nawet wyższego rodzaju. Czasami widzimy funkcje tego typu, takie jak mask :: ((forall a. IO a -> IO a) -> IO b) -> IO b, ale myślę, że będziesz musiał zagłębić się w prolog typów lub literaturę zależnie wpisaną w typowanie, aby zobaczyć ten poziom złożoności typów.

Rozważmy Functorklasę typu w Haskell, gdzie fjest zmienną typu wyższego rzędu:

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

Ten podpis typu mówi, że fmap zmienia parametr typu z fod ado b, ale pozostawia ftaki, jaki był. Więc jeśli używasz fmaplisty, otrzymujesz listę, jeśli używasz jej przez parser, otrzymujesz parser i tak dalej. A są to statyczne gwarancje czasu kompilacji.

Nie znam Functorjęzyka F #, ale zastanówmy się, co się stanie, jeśli spróbujemy wyrazić abstrakcję w języku takim jak Java lub C #, z dziedziczeniem i rodzajami ogólnymi, ale bez typów ogólnych wyższego rzędu. Pierwsza próba:

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

Problem z tą pierwszą próbą polega na tym, że implementacja interfejsu może zwrócić dowolną klasę, która implementuje Functor. Ktoś mógłby napisać metodę, FunnyList<A> implements Functor<A>której mapmetoda zwraca inny rodzaj kolekcji lub nawet coś, co w ogóle nie jest kolekcją, ale nadal jest Functor. Ponadto, gdy używasz mapmetody, nie możesz wywołać żadnych metod specyficznych dla podtypu na wyniku, chyba że zmniejszysz go do typu, którego faktycznie oczekujesz. Mamy więc dwa problemy:

1. System typów nie pozwala nam wyrazić niezmiennej, że mapmetoda zawsze zwraca tę samą Functorpodklasę co odbiornik.
2. W związku z tym nie ma statycznego bezpiecznego sposobu wywoływania Functormetody innej niż wynik map.

Istnieją inne, bardziej skomplikowane sposoby, które możesz wypróbować, ale żaden z nich tak naprawdę nie działa. Na przykład możesz spróbować rozszerzyć pierwszą próbę, definiując podtypy, Functorktóre ograniczają typ wyniku:

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);
}

// …

Pomaga to zabronić implementatorom tych węższych interfejsów zwracania niewłaściwego typu Functorz mapmetody, ale ponieważ nie ma ograniczeń co do liczby Functormożliwych implementacji, nie ma ograniczeń co do liczby węższych interfejsów, których będziesz potrzebować.

( EDYCJA: Zauważ, że to działa tylko dlatego, że Functor<B>pojawia się jako typ wyniku, więc interfejsy potomne mogą go zawęzić. Więc AFAIK nie możemy zawęzić obu zastosowań Monad<B>w następującym interfejsie:

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

W Haskell, ze zmiennymi typu wyższego rzędu, jest to (>>=) :: Monad m => m a -> (a -> m b) -> m b.)

Jeszcze inną próbą jest użycie rekurencyjnych typów ogólnych w celu ograniczenia przez interfejs typu wyniku podtypu do samego podtypu. Przykład zabawki:

/**
 * 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);

}

Ale ten rodzaj techniki (który jest raczej tajemniczy dla twojego zwykłego programisty OOP, do cholery również dla twojego zwykłego programisty funkcjonalnego) nadal nie może wyrazić pożądanego Functorograniczenia:

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

Tutaj problemem jest to nie ogranicza FBsię mieć takie same Fjak FA-tak że kiedy zadeklarować typ List<A> implements Functor<List<A>, A>The mapmetoda może nadal zwracają NotAList<B> implements Functor<NotAList<B>, B>.

Ostatnia próba, w Javie, przy użyciu typów surowych (nieparametryzowanych kontenerów):

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

Tutaj Fzostanie utworzona instancja nieparametryzowanych typów, takich jak po prostu Listlub Map. Gwarantuje to, że a FunctorStrategy<List>może zwrócić tylko a List- ale zrezygnowałeś z używania zmiennych typu do śledzenia typów elementów list.

Sedno problemu polega na tym, że języki takie jak Java i C # nie pozwalają parametrom typu mieć parametrów. W Javie, jeśli Tjest zmienną typu, możesz pisać Ti List<T>, ale nie T<String>. Typy wyższego rzędu usuwają to ograniczenie, abyś mógł mieć coś takiego (nie do końca przemyślane):

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) {
        // ...
    }

}

W szczególności odnosząc się do tego fragmentu:

(Myślę) Rozumiem, że zamiast myList |> List.map flub myList |> Seq.map f |> Seq.toListwyższego rodzaju typy pozwalają po prostu napisać myList |> map fi zwróci List. To świetnie (zakładając, że to prawda), ale wydaje się trochę małostkowe? (I czy nie można tego zrobić po prostu zezwalając na przeciążanie funkcji?) Zwykle konwertuję na Seqi tak, a potem mogę konwertować na cokolwiek chcę.

Istnieje wiele języków, które uogólniają ideę mapfunkcji w ten sposób, modelując ją tak, jakby w istocie mapowanie dotyczyło sekwencji. Ta twoja uwaga jest w tym duchu: jeśli masz typ, który obsługuje konwersję do i z Seq, operację mapy otrzymasz „za darmo” przez ponowne użycie Seq.map.

Jednak u Haskella Functorklasa jest bardziej ogólna; nie jest związane z pojęciem sekwencji. Możesz zaimplementować fmapdla typów, które nie mają dobrego mapowania do sekwencji, takich jak IOakcje, kombinatory parsera, funkcje itp .:

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

Pojęcie „mapowania” tak naprawdę nie jest związane z sekwencjami. Najlepiej zrozumieć prawa funktora:

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

Bardzo nieformalnie:

1. Pierwsze prawo mówi, że mapowanie z funkcją tożsamości / noop jest tym samym, co nie robienie niczego.
2. Drugie prawo mówi, że każdy wynik, który można uzyskać poprzez mapowanie dwukrotnie, można również uzyskać przez mapowanie raz.

Dlatego chcesz fmapzachować ten typ - ponieważ gdy tylko otrzymasz mapoperacje, które dają inny typ wyniku, wykonanie takich gwarancji staje się dużo, dużo trudniejsze.

Nie chcę tu powtarzać informacji w niektórych doskonałych odpowiedziach, ale jest kluczowy punkt, który chciałbym dodać.

Zwykle nie potrzebujesz typów wyższego rzędu, aby zaimplementować jakąkolwiek konkretną monadę lub funktor (lub funktor aplikacyjny, strzałkę lub ...). Ale takie postępowanie w większości mija się z celem.

Generalnie odkryłem, że kiedy ludzie nie widzą użyteczności funktorów / monad / cokolwiek, często dzieje się tak dlatego, że myślą o tych rzeczach pojedynczo . Operacje Functor / monad / etc naprawdę nie dodają nic do żadnej instancji (zamiast wywoływać bind, fmap, itp., Mogę po prostu wywołać dowolne operacje, których użyłem do zaimplementowania bind, fmap itp.). To, czego naprawdę potrzebujesz, to abyś mógł mieć kod, który działa ogólnie z dowolnym funktorem / monadą / itp.

W kontekście, w którym taki ogólny kod jest szeroko stosowany, oznacza to, że za każdym razem, gdy piszesz nową instancję monady, twój typ natychmiast uzyskuje dostęp do dużej liczby użytecznych operacji, które zostały już dla ciebie napisane . O to właśnie chodzi, by wszędzie widzieć monady (i funktory i ...); nie po to, żebym mógł używać bindzamiast concati mapimplementować myFunkyListOperation(co samo w sobie nie daje mi nic), ale raczej po to, aby kiedy potrzebować myFunkyParserOperationi myFunkyIOOperationmóc ponownie użyć kodu, który pierwotnie widziałem w kategoriach list, ponieważ jest to faktycznie monada .

Ale aby abstrahować od sparametryzowanego typu, takiego jak monada z bezpieczeństwem typów , potrzebujesz typów wyższego rodzaju (jak również wyjaśniono w innych odpowiedziach tutaj).

Z perspektywy bardziej specyficznej dla platformy .NET, jakiś czas temu napisałem o tym wpis na blogu . Sedno tego polega na tym , że w przypadku typów wyższego rodzaju możesz potencjalnie ponownie użyć tych samych bloków LINQ między IEnumerablesi IObservables, ale bez typów wyższego rodzaju jest to niemożliwe.

Najbliższy można dostać (ja zorientowali się po zaksięgowaniu bloga) to zrobić własny IEnumerable<T>i IObservable<T>i rozszerzył je zarówno zIMonad<T> . To pozwala na ponowne użycie bloków LINQ, jeśli są one oznaczone IMonad<T>, ale wtedy to już nie typesafe ponieważ pozwala na mix-and-match IObservablesi IEnumerablesw tym samym bloku, który choć może to brzmieć intrygujące zezwala na to, że jesteś po prostu uzyskaj niezdefiniowane zachowanie.

Napisałem później post o tym, jak Haskell to ułatwia. (No-op, naprawdę - ograniczenie bloku do pewnego rodzaju monady wymaga kodu; opcja ponownego użycia jest domyślna).

Najczęściej używanym przykładem polimorfizmu typu wyższego rzędu w Haskell jest Monadinterfejs. Functori Applicativesą w ten sam sposób wyższego rodzaju, więc pokażę Functor, aby pokazać coś zwięzłego.

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

Teraz przyjrzyj się tej definicji, przyglądając się, jak fużywana jest zmienna typu . Zobaczysz, że fnie może to oznaczać typu, który ma wartość. Możesz zidentyfikować wartości w tym podpisie typu, ponieważ są one argumentami funkcji i wynikami. Więc zmienne typu ai bsą typami, które mogą mieć wartości. Podobnie jest z wyrażeniami typu f ai f b. Ale nie fsiebie. fjest przykładem zmiennej typu wyższego rzędu. Biorąc pod uwagę, że *jest to rodzaj typów, które mogą mieć wartości, fmuszą mieć ten rodzaj * -> *. Oznacza to, że przyjmuje typ, który może mieć wartości, ponieważ wiemy z poprzedniego badania, że ai bmusi mieć wartości. Wiemy też, że f aif b musi mieć wartości, więc zwraca typ, który musi mieć wartości.

To sprawia, że ​​jest fużywany w definicji Functorzmiennej typu wyższego rodzaju.

Te Applicativei Monadinterfejsy dodać więcej, ale są one kompatybilne. Oznacza to, że działają również na zmiennych typu z rodzajem * -> *.

Praca nad typami wyższego rzędu wprowadza dodatkowy poziom abstrakcji - nie jesteś ograniczony tylko do tworzenia abstrakcji na typach podstawowych. Możesz także tworzyć abstrakcje dla typów, które modyfikują inne typy.