Typy wyższego rzędu (Higher-kinded types) - które języki to mają?

3

Próbuję zebrać listę wszystkich języków które mają HKT:

  • Na pewno Scala i Haskell, to sprawdzałem. Za to Kotlin nie ma :(
  • PureScript? Piszą że też, ale już Elm nie ma
  • Idris? Jeśli PureScript jest oparty na kompilatorze Idris to chyba też ma?
  • Rust nie ma, ale chce mieć
  • OCaml? Tylko czemu by pisali że OCaml nie ma monad? Po co komu HKT jak nie można sobie monady napisać?
  • Za to F# jest niedorobionym OCamlem i nie ma.
  • Ciekawe czy ReasonML/ReScript ma?

Jeszcze jakieś?
Ktoś pomoże?
Ktoś coś wie?

Z góry dziękuję za odpowiedzi

2

Rust nie ma, ale chce mieć

Technicznie już są! (nightly; większość rzeczy już działa, afair) :-)

0

@Patryk27: to jak wyglądają? Np. pokaż jakiegoś monad transformera.

0

RFC samo w sobie już wspomina:

This does not add all of the features people want when they talk about higher- kinded types. For example, it does not enable traits like Monad.

:-P

Co nie oznacza, że feature jest bezużyteczny - dzięki HKT możliwe będzie np. tworzenie struktur generycznych nad typem kontenera (np. Arc / Rc https://rust-lang.github.io/rfcs/1598-generic_associated_types.html#associated-type-constructors-of-type-arguments.).

0

To HKT-które-nie-jest-HKT (?) w Ruście to mi przypomina type members ze Scali: https://docs.scala-lang.org/tour/abstract-type-members.html

1

Scala'owe ATM:

abstract class SeqBuffer extends Buffer {
  type U
  type T <: Seq[U]
  def length = element.length
}

... w Rust są, o ile dobrze rozumiem, zwyczajnymi traitami:

trait SeqBuffer {
  type U;
  type T: Seq<Self::U>;
}

(w rustowej terminologii U oraz T są nazwane associated type.)

To, co jest teraz implementowane dodatkowo, to możliwość stworzenia generic associated type:

trait SeqBuffer {
  type T<U>: Seq<U>;
}

// SeqBuffer::T = type constructor

Taki pozornie prosty ficzer umożliwia np. zbudowanie traitu pozwalającego na wybór między rodzajem smart-wskaźnika:

trait PointerFamily {
    type Pointer<T>: Deref<Target = T>;
}

// Arc = reference counted, z obsługą wielowątkowości
struct ArcFamily;

impl PointerFamily for ArcFamily {
    type Pointer<T> = Arc<T>;
}

// Rc = reference counted, bez obsługi wielowątkowości
struct RcFamily;

impl PointerFamily for RcFamily {
    type Pointer<T> = Rc<T>;
}

// Struktura jest generyczna nad typem wskaźnika - użytkownik może wybrać między `ArcFamily` albo `RcFamily`, i
// otrzymać odpowiednio `Arc<HashMap<...>>` lub `Rc<HashMap<...>>`
struct ConcurrentMap<P: PointerFamily> {
  map: P::Pointer<HashMap<String, String>>,
}
3

Scalowe ATM mogą być generyczne:
https://scastie.scala-lang.org/d5xK4pqOQCqTTR47wuj5uA (Scala 2.13.x)

abstract class Abc {
  type A
  type B[_]
  type C[_] <: B[_]
  type D[E] <: B[E]
}

class MyAbc extends Abc {
  class A // implement type directly, type A = A is not needed
  
  type B[X] = MyB[X]
  class MyB[X]
  
  type C[X] = MyC[X]
  class MyC[X] extends MyB[Int]
  
  type D[X] = MyD[X]
  class MyD[X] extends MyB[X]
}

println(new MyAbc)
0

Z tego co rozumiem o HKT, to TypeScript oraz C++ (szablony) powinny się łapać?

A Idris to już na pewno, ma typy zależne, i w ogóle typy wyższych rzędów niż #0 i #1.

0
enedil napisał(a):

Z tego co rozumiem o HKT, to TypeScript oraz C++ (szablony) powinny się łapać?

Podaj przykład bo HKT to coś więcej niż szablony/generyki. Szablony/generyki pozwalają pisać kod niezależny od typu elementu kolekcji. HKT pozwala pisać kod niezależny od typu kolekcji (monady, kontekstu) bez definiowania typu elementu. HKT i TypeClasami razem zestępują interfejsy (klasy abstrakcyjne). Przykłąd Scali:

trait Collection[T[_]] {
  def wrap[A](a: A): T[A]
  def first[B](b: T[B]): B
}

T to typ kolekcji. A i B to typy elementów

1

@KamilAdam: chodzi o coś takiego?
https://godbolt.org/z/8T79rn8fY

2

@enedil: wydaje mi się, że nie do końca - imo brakuje tutaj tego higher-kinded :-)

Rozważmy taki kod (Rust):

// Wektor, generyczny nad T
struct Vec<T> {
  /* ... */ 
}

// Optional, generyczny nad T
enum Maybe<T> {
  /* ... */
}

impl<T> Vec<T> {
  // Dokonuje konwersji `Vec<T>` na `Vec<U>`
  // (przykład: konwersja `Vec<Liczba>` na `Vec<CiągZnaków>`)
  pub fn map<U>(self, mapper: ...) -> Vec<U> {
    /* ... */
  }
}

impl<T> Maybe<T> {
  // Dokonuje konwersji `Maybe<T>` na `Maybe<U>`
  pub fn map<U>(self, mapper: ...) -> Maybe<U> {
    /* ... */
  }
}

Jak widać, obydwa typy zawierają bardzo podobną funkcję o nazwie map - i trik polega na tym, aby tę funkcję uogólnić; w pseudo-Rust, szukamy czegoś w stylu:

trait Map<T> {
  fn map<U>(self, ...) -> T<U>;
  // -------------------- ^
  // | `T` jest `higher-kinded`, ponieważ w założeniu odnosi się
  // | do type-constructor (np. `Vec`), a nie konkretnego typu
  // | (np. `Vec<String>`)
  // ---
}

// po polskiemu: clue polega na tym, aby zdefiniować funkcję, której definicja mówi:
// "zmieniam *wnętrze* kontenera, lecz nie zmieniam *rodzaju* kontenera"
// (Vec<T> => Vec<U>; Option<T> => Option<U>; Something<T> => Something<U> etc.)

(monady ftw.)

1 użytkowników online, w tym zalogowanych: 0, gości: 1