Co to jest Scala o wyższym rodzaju?

275

W Internecie można znaleźć:

  1. Wyższy rodzaj == typ konstruktora?

    class AClass[T]{...} // For example, class List[T]

    Niektórzy twierdzą, że jest to typ bardziej uporządkowany, ponieważ streszcza typy, które byłyby zgodne z definicją.

    Wyższe typy pokrewne to typy, które pobierają inne typy i konstruują nowy typ

    Są one jednak znane również jako konstruktor typów . (Na przykład w Programowaniu w Scali ).

  2. Wyższy rodzaj == konstruktor typu, który bierze konstruktor typu jako parametr typu?

    W artykule Generics of a Highe Kind można przeczytać

    ... typy, które wyodrębniają ponad typy, które wyodrębniają ponad typy („typy lepiej dobrane”) ... ”

    co sugeruje to

    class XClass[M[T]]{...} // or
    
    trait YTrait[N[_]]{...} // e.g. trait Functor[F[_]]
    

    jest rodzajem wyższego rodzaju.

Mając to na uwadze, trudno jest rozróżnić konstruktor typu , typ o wyższym typie i konstruktor typu, który przyjmuje konstruktory typu jako parametr typu , a zatem pytanie powyżej.

Lutz
źródło
Dodano jako przykład Functor Landei.
Lutz

Odpowiedzi:

284

Pozwolę sobie nadrobić zaległości w tym zamieszaniu, wprowadzając z pewnym niedowierzaniem. Lubię używać analogii do poziomu wartości, aby to wyjaśnić, ponieważ ludzie są bardziej zaznajomieni z tym.

Konstruktor typu to typ, który można zastosować do argumentów typu w celu „skonstruowania” typu.

Konstruktor wartości to wartość, którą można zastosować do argumentów wartości w celu „skonstruowania” wartości.

Konstruktory wartości są zwykle nazywane „funkcjami” lub „metodami”. O tych „konstruktorach” mówi się również, że są „polimorficzne” (ponieważ można je stosować do konstruowania „elementów” o różnym „kształcie”) lub „abstrakcjach” (ponieważ abstrakcyjne są to, co różni się między różnymi instancjami polimorficznymi).

W kontekście abstrakcji / polimorfizmu pierwszeństwo odnosi się do „jednorazowego użycia” abstrakcji: raz abstraktujesz nad typem, ale sam ten typ nie może abstrakcji nad niczym. Generics Java 5 są pierwszego rzędu.

Interpretacja powyższych charakterystyk abstrakcji pierwszego rzędu to:

Konstruktor typów to typ, który można zastosować do argumentów odpowiedniego typu, aby „skonstruować” odpowiedni typ.

Konstruktor wartości to wartość, którą można zastosować do odpowiednich argumentów wartości w celu „skonstruowania” właściwej wartości.

Aby podkreślić, że nie ma w tym żadnej abstrakcji (myślę, że można to nazwać „zerowym porządkiem”, ale nigdzie go nie widziałem), na przykład wartość 1lub typ String, zwykle mówimy, że coś jest „właściwą” wartością lub typem.

Właściwa wartość jest „natychmiast użyteczna” w tym sensie, że nie czeka na argumenty (nie jest nad nimi abstrakcyjna). Pomyśl o nich jako o wartościach, które możesz łatwo wydrukować / sprawdzić (serializacja funkcji to oszustwo!).

Właściwy typ to typ, który klasyfikuje wartości (w tym konstruktory wartości), konstruktory typów nie klasyfikują żadnych wartości (najpierw należy je zastosować do argumentów odpowiedniego typu, aby uzyskać odpowiedni typ). Aby utworzyć instancję typu, konieczne (ale niewystarczające) jest, aby był on właściwym typem. (Może to być klasa abstrakcyjna lub klasa, do której nie masz dostępu).

„Nadrzędny porządek” jest po prostu ogólnym terminem, który oznacza wielokrotne stosowanie polimorfizmu / abstrakcji. Oznacza to to samo dla typów i wartości polimorficznych. Konkretnie, abstrakcja wyższego rzędu abstraktuje nad czymś, co abstraktuje nad czymś. W przypadku typów termin „bardziej uprzywilejowany” jest specjalną wersją bardziej ogólnego „wyższego rzędu”.

Tak więc wersja naszej charakteryzacji wyższego rzędu staje się:

Konstruktor typu to typ, który można zastosować do argumentów typu (odpowiednie typy lub konstruktory typu), aby „skonstruować” odpowiedni typ (konstruktor).

Konstruktor wartości to wartość, którą można zastosować do argumentów wartości (prawidłowe wartości lub konstruktory wartości), aby „skonstruować” odpowiednią wartość (konstruktor).

Zatem „wyższy porządek” oznacza po prostu, że kiedy mówisz „abstrakcja nad X”, naprawdę masz na myśli! To, Xco jest abstrakcyjne, nie traci własnych „praw do abstrakcji”: może abstrakcji wszystkiego, co chce. (Nawiasem mówiąc, używam tutaj czasownika „streszczenie”, aby pominąć coś, co nie jest niezbędne do zdefiniowania wartości lub typu, aby użytkownik mógł je zmienić / podać jako argument jako argument .)

Oto kilka przykładów (zainspirowanych pytaniami Lutza wysłanymi e-mailem) prawidłowych wartości i typów pierwszego i wyższego rzędu:

                   proper    first-order           higher-order

values             10        (x: Int) => x         (f: (Int => Int)) => f(10)
types (classes)    String    List                  Functor
types              String    ({type λ[x] = x})#λ   ({type λ[F[x]] = F[String]})#λ

Gdzie używane klasy zostały zdefiniowane jako:

class String
class List[T]
class Functor[F[_]]

Aby uniknąć pośrednictwa poprzez definiowanie klas, musisz w jakiś sposób wyrazić anonimowe funkcje typu, które nie są wyrażalne bezpośrednio w Scali, ale możesz używać typów strukturalnych bez nadmiernego nakładu składniowego ( styl jest spowodowany https://stackoverflow.com / users / 160378 / retronym afaik ):

W niektórych hipotetycznych przyszłych wersjach Scali, które obsługują anonimowe funkcje typu, możesz skrócić ten ostatni wiersz z przykładów do:

types (informally) String    [x] => x              [F[x]] => F[String]) // I repeat, this is not valid Scala, and might never be

(Osobiście żałuję, że kiedykolwiek mówiłem o „typach lepszych”, to w końcu są to tylko typy! Gdy absolutnie potrzebujesz ujednoznacznić, sugeruję powiedzenie takich rzeczy, jak „parametr konstruktora typu”, „członek konstruktora typu” lub „alias konstruktora typów”, aby podkreślić, że nie mówimy tylko o odpowiednich typach).

ps: Aby jeszcze bardziej skomplikować sprawy, „polimorficzny” jest niejednoznaczny w inny sposób, ponieważ typ polimorficzny oznacza czasami typ uniwersalnie skwantyfikowany, taki jak Forall T, T => T, który jest właściwym typem, ponieważ klasyfikuje wartości polimorficzne (w Scali ta wartość może być zapisane jako typ konstrukcyjny {def apply[T](x: T): T = x})

Adriaan Moors
źródło
1
patrz także: adriaanm.github.com/research/2010/10/06/…
Adriaan Moors
5
Artykuł Adriaana „Typ konstruktora polimorfizmu” teraz na adriaanm.github.com/research/2010/10/06/…
Steven Shaw
Ciągle czytam to jako wyższego pokrewnego i wyobrażam sobie pokrewnego ducha
Janac Meena
110

(Ta odpowiedź jest próbą udekorowania odpowiedzi Adriaan Maurów przez pewne informacje graficzne i historyczne.)

Wyższe rodzaje są częścią Scali od wersji 2.5.

  • Wcześniej Scala, tak jak dotychczas Java, nie pozwalała na użycie konstruktora typu („generics” w Javie) jako parametru typu dla konstruktora typu. na przykład

     trait Monad [M[_]]

    nie było możliwe.

    W Scali 2.5 system typów został rozszerzony o możliwość klasyfikowania typów na wyższym poziomie (znany jako polimorfizm konstruktora typów ). Te klasyfikacje są znane jako rodzaje.

    Rodzaj i rodzaj, ** pochodzący ** z „Generics of a Higher Kind” (Zdjęcie pochodzi z Generics of a Higher Kind )

    Konsekwencją jest to, że ten konstruktor typów (np. List) Może być używany tak samo, jak inne typy w pozycji parametrów typu konstruktorów typów, a więc stały się typami pierwszej klasy od Scali 2.5. (Podobne do funkcji, które są wartościami pierwszej klasy w Scali).

    W kontekście systemu typów obsługującego wyższe rodzaje, możemy odróżnić odpowiednie typy , typy podobne Intlub List[Int]od typów pierwszego rzędu, takie jak Listi typy wyższych rodzajów, takie jak Functorlub Monad(typy, które wyodrębniają się nad typami, które wyodrębniają ponad typy).

    System typów Java po drugiej stronie nie obsługuje rodzajów, a zatem nie ma typów „wyższego rodzaju”.

    Tak więc należy to rozpatrywać na tle systemu typów pomocniczych.

  • W przypadku Scali często widzisz przykłady takiego konstruktora typów

     trait Iterable[A, Container[_]]

    z nagłówkiem „Wyższe typy”, np. w Scali dla programistów ogólnych, sekcja 4.3

    To jest czasami missleading, ponieważ odnoszą się do wielu Containerjako wyższego typu kinded i nie Iterable, ale to, co jest bardziej precyzyjne jest

    zastosowanie tutaj Containerjako parametru konstruktora typu wyższego rodzaju (wyższego rzędu) Iterable.

Lutz
źródło
80

Rodzaj zwykłych typów, jak Inti Char, których przypadki są wartościami, jest *. Konstruktorzy typu jednoargumentowego jak Maybeto * -> *; konstruktory typu binarnego, takie jak Either( curry ) * -> * -> *, i tak dalej. Możesz przeglądać typy takie jak Maybei Eitherjako funkcje na poziomie typu: pobierają jeden lub więcej typów i zwracają typ.

Funkcja jest wyższego rzędu, jeśli ma rząd większy niż 1, gdzie porządek to (nieformalnie) głębokość zagnieżdżenia po lewej stronie strzałek funkcji:

  • Zamówienie 0: 1 :: Int
  • Zamówienie 1: chr :: Int -> Char
  • Zamówienie 2: fix :: (a -> a) -> a,map :: (a -> b) -> [a] -> [b]
  • Zamówienie 3: ((A -> B) -> C) -> D
  • Zamówienie 4: (((A -> B) -> C) -> D) -> E

Krótko mówiąc, wyższy rodzaj jest tylko funkcją wyższego rzędu na poziomie typu.

  • Zamówienie 0: Int :: *
  • Zamówienie 1: Maybe :: * -> *
  • Porządek 2: Functor :: (* -> *) -> Constraint—highher-kinded: konwertuje konstruktory typu jednoargumentowego na ograniczenia klasy
Jon Purdy
źródło
Ok, rozumiem, jakie byłyby wówczas przykłady w Scali dla (* ⇒ *) ⇒ * i (* ⇒ *) ⇒ (* ⇒ *)? Czy Functor Landei mieści się w pierwszej kategorii, czy raczej w drugiej?
Lutz
1
@lutz: Byłoby w pierwszej kategorii: Functortworzy odpowiedni typ (dobrze, cecha, ale ten sam pomysł) Functor[F[_]]z konstruktora typów F.
Jon Purdy,
1
@Jon: Bardzo wnikliwy post, dziękuję. Czy konwerter typów (* => *) => (* => *)można wyrazić w Scali? Jeśli nie, w innym języku?
Eugen Labun,
@JonPurdy Porównanie * ⇒ * ⇒ *z curry jest bardzo pomocne. Dzięki!
Lifu Huang,
(* ⇒ *) ⇒ (* ⇒ *)można również przeliterować (* ⇒ *) ⇒ * ⇒ *. Można to wyrazić jak Scala Foo[F[_], T]. Jest to rodzaj typu (w Haskell) newtype Twice f a = Twice (f (f a))(np. Twice Maybe IntMaybe (Maybe Int), Twice [] Char[[Char]]) lub coś bardziej interesującego jak wolna monada data Free f a = Pure a | Free (f (Free f a)).
Jon Purdy,
37

Powiedziałbym: abstrakty typu wyższego rodzaju nad konstruktorem typów. Np. Rozważ

trait Functor [F[_]] {
   def map[A,B] (fn: A=>B)(fa: F[A]): F[B]
}

Oto Functor„wyższy rodzaj rodzaju” (tak jak w artykule „Generics of a Higher Kind” ). Nie jest to konstruktor typu konkretnego („pierwszego rzędu”) List(który streszcza tylko odpowiednie typy). Abstrahuje od wszystkich konstruktorów typu jednoargumentowego („pierwszego rzędu”) (jak oznaczono za pomocą F[_]).

Innymi słowy: w Javie mamy wyraźne typy konstruktorów (np. List<T>), Ale nie mamy „typów o wyższych typach”, ponieważ nie możemy nad nimi streścić (np. Nie możemy napisać Functorinterfejsu zdefiniowanego powyżej - przynajmniej nie bezpośrednio ).

Termin „polimorfizm wyższego rzędu (konstruktor typu)” jest używany do opisania systemów, które obsługują „typy wyższego rzędu”.

Landei
źródło
Tak myślałem, ale wydaje się to zaprzeczać odpowiedzi Jona, gdzie „konstruktor typu konkretnego” jest już „typem wyższego rodzaju”.
Lutz
3
Tak. Zgodnie z odpowiedzią Jona (jak rozumiem) List<T>w Javie byłby to konstruktor jednoargumentowy, ponieważ ma wyraźnie taki rodzaj * -> *. W odpowiedzi Jona brakuje tego, że musisz umieć *streścić „całość” (a nie tylko drugą, jak w Javie), aby nazwać ją typem wyższego rodzaju.
Landei
@Landai: Papierowa Scala dla ogólnych programistów w sekcji 4.3 sugeruje, że cecha Iterable [A, Container [_]] jest lepszym typem (choć nie jest jasne, czy chodzi o Iterator lub Container), gdzie z drugiej strony vero690 w sekcja 2.3.1 używa terminu konstruktor typu wyższego rodzaju dla czegoś takiego jak (* -> *) -> * (operator typu sparametryzowany za pomocą konstruktora typu wyższego rzędu), który wygląda podobnie do Iteratora lub cechy Functora.
Lutz
1
To chyba prawda, ale myślę, że zaczynamy tutaj dzielić włosy. Ważną kwestią dotyczącą typów wyższych rodzajów jest to, że w grę wchodzą nie tylko konstruktory typu (polimorfizm konstruktora jednego typu), ale jesteśmy w stanie wyodrębnić konkretny typ konstruktorów tego typu (polimorfizm konstruktora typu wyższego rzędu). Mamy możliwość abstrakcji nad wszystkim, co chcemy bez ograniczeń (dotyczących typów i konstruktorów typów), co sprawia, że ​​nazwanie wszystkich możliwych wersji tej funkcji jest mniej interesujące. I to boli mój mózg.
Landei
2
Zasadniczo ważne jest tutaj rozróżnienie definicji i odniesień. Definicja def succ(x: Int) = x+1wprowadza „konstruktor wartości” (zobacz moją drugą odpowiedź na to, co mam na myśli) succ(nikt nie odniósłby się do tej wartości jako succ (x: Int)). Przez analogię Functorjest (rzeczywiście wyższy rodzaj) typ zdefiniowany w odpowiedzi. Znowu, nie należy odwoływać się do niego jak Functor[F[_]](co jest Fto, co jest? _Nie są one w zakres niestety, cukier syntaktyczny dla existentials muddies wody tutaj dokonując?! F[_]Skrót F[T forSome {type T}])
Adriaan Maurów
0

Scala REPL zapewnia :kindpolecenie, które

scala> :help kind

:kind [-v] <type>
Displays the kind of a given type.

Na przykład,

scala> trait Foo[A]
trait Foo

scala> trait Bar[F[_]]
trait Bar

scala> :kind -v Foo
Foo's kind is F[A]
* -> *
This is a type constructor: a 1st-order-kinded type.

scala> :kind -v Foo[Int]
Foo[Int]'s kind is A
*
This is a proper type.

scala> :kind -v Bar
Bar's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

scala> :kind -v Bar[Foo]
Bar[Foo]'s kind is A
*
This is a proper type.

:helpZapewnia jasne definicje więc myślę, że warto wpis go tutaj w całości (Scala 2.13.2)

scala> :help kind

:kind [-v] <type>
Displays the kind of a given type.

    -v      Displays verbose info.

"Kind" is a word used to classify types and type constructors
according to their level of abstractness.

Concrete, fully specified types such as `Int` and `Option[Int]`
are called "proper types" and denoted as `A` using Scala
notation, or with the `*` symbol.

    scala> :kind Option[Int]
    Option[Int]'s kind is A

In the above, `Option` is an example of a first-order type
constructor, which is denoted as `F[A]` using Scala notation, or
* -> * using the star notation. `:kind` also includes variance
information in its output, so if we ask for the kind of `Option`,
we actually see `F[+A]`:

    scala> :k -v Option
    Option's kind is F[+A]
    * -(+)-> *
    This is a type constructor: a 1st-order-kinded type.

When you have more complicated types, `:kind` can be used to find
out what you need to pass in.

    scala> trait ~>[-F1[_], +F2[_]] {}
    scala> :kind ~>
    ~>'s kind is X[-F1[A1],+F2[A2]]

This shows that `~>` accepts something of `F[A]` kind, such as
`List` or `Vector`. It's an example of a type constructor that
abstracts over type constructors, also known as a higher-order
type constructor or a higher-kinded type.
Mario Galic
źródło