Skip to content

Instantly share code, notes, and snippets.

Revisions

  1. CMCDragonkai revised this gist Jun 30, 2015. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions higher_kinded_types_in_rust_and_haskell.md
    Original file line number Diff line number Diff line change
    @@ -87,11 +87,11 @@ class citizen. It is however on the roadmap.

    Just a note about syntax:

    * `trait` <-> Type Classes
    * `impl` <-> Type Class Instances
    * `enum`/`struct` <-> ADTs
    * `trait <-> class`
    * `impl <-> instance`
    * `enum/struct <-> data`

    However there is an interesting resources for working around this:
    However there are interesting resources for working around this:

    * [Using a macro to get HKT!](https://gist.github.com/14427/af90a21b917d2892eace)
    * [Using iterators instead!](http://stackoverflow.com/q/18374612/582917)
  2. CMCDragonkai revised this gist Jun 30, 2015. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions higher_kinded_types_in_rust_and_haskell.md
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    Rust/Haskell: Higher-Kinded Types
    =================================
    Rust/Haskell: Higher-Kinded Types (HKT)
    =======================================

    A higher kinded type is a concept that reifies a type constructor as an
    actual type.
  3. CMCDragonkai revised this gist Jun 30, 2015. 1 changed file with 3 additions and 1 deletion.
    4 changes: 3 additions & 1 deletion higher_kinded_types_in_rust_and_haskell.md
    Original file line number Diff line number Diff line change
    @@ -97,5 +97,7 @@ However there is an interesting resources for working around this:
    * [Using iterators instead!](http://stackoverflow.com/q/18374612/582917)

    Other reading:
    -------------

    * https://en.wikipedia.org/wiki/Lambda_cube
    * https://en.wikipedia.org/wiki/Lambda_cube
    * https://www.academia.edu/11975482/Second-order_logic_explained_in_plain_English_
  4. CMCDragonkai created this gist Jun 30, 2015.
    101 changes: 101 additions & 0 deletions higher_kinded_types_in_rust_and_haskell.md
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,101 @@
    Rust/Haskell: Higher-Kinded Types
    =================================

    A higher kinded type is a concept that reifies a type constructor as an
    actual type.

    A type constructor can be thought of in these analogies:

    * like a function in the type universe
    * as a type with a "hole" in it
    * as a container containing type(s)
    * as a generic type, parameterised over other types
    * as an endofunctor in the category of types

    To be able to use them in places where concrete "proper" types are usually
    expected, a language must support the concept of higher kinded types.

    There are 3 keywords in "higher kinded types":

    1. Higher
    2. Kinded
    3. Types

    **Higher**:

    The "higher" prefix is derived from the phrase "higher order". In terms of
    programming, it usually refers to a function that can at least take other
    functions as input, or return functions as output. However I think in this case,
    the prefix has become more general, and refers to a form of recursive
    containment. Basically it's the idea that a type could contain other types.
    See concepts like "higher order messages". This makes sense, and seems to define
    they very concept of type constructors and/or recursive data structures. Here we
    use the word "contain" to mean parameterisation of things related to itself,
    and/or returning of things related to itself. Refer to 1st order and 2nd order
    logic literature for more:

    * https://www.academia.edu/11975482/Second-order_logic_explained_in_plain_English_
    * http://math.stackexchange.com/questions/1052118/what-are-some-examples-of-third-fourth-or-fifth-order-logic-sentences
    * http://programmers.stackexchange.com/questions/186035/who-first-coined-the-term-higher-order-function-and-or-first-class-citizen

    **Kinded**:

    Kinds are the types of types. Most "proper" types have a kind signature of `*`.
    But higher order types, or type constructors could have a kind signature of
    `* -> *`. The ability of having higher kinds defines a type constructor.

    **Types**:

    Finally of course I believe this term signifies a reification of our type
    constructors as a first class type that can be manipulated using the same
    tools that we manipulate normal `*` "proper" types.

    Haskell
    -------

    Haskell has good support for higher kinded types. Every type constructor such as
    they `[]` can be used as a "first class type".

    This is specifically relevant to typeclasses such as the `Functor` typeclass.

    ```hs
    > :info Functor
    class Functor (f :: * -> *) where
    fmap :: (a -> b) -> f a -> f b
    (GHC.Base.<$) :: a -> f b -> f a
    -- Defined in ‘GHC.Base’
    instance Functor Maybe -- Defined in ‘Data.Maybe’
    instance Functor (Either a) -- Defined in ‘Data.Either’
    instance Functor [] -- Defined in ‘GHC.Base’
    instance Functor IO -- Defined in ‘GHC.Base’
    instance Functor ((->) r) -- Defined in ‘GHC.Base’
    instance Functor ((,) a) -- Defined in ‘GHC.Base’
    ```

    Each of those instances are implementations of the Functor class for a
    particular higher kinded type. For example, we see `[]`, which we know is a type
    constructor but it is also a higher kinded type, since we can use it like a
    "first class type".

    Rust
    ----

    Rust 1.0 currently lacks support for higher kinded types. This doesn't mean it
    doesn't have container types or type constructors. It certainly does. It just
    hasn't reified them into a higher kinded type that can be used like a first
    class citizen. It is however on the roadmap.

    Just a note about syntax:

    * `trait` <-> Type Classes
    * `impl` <-> Type Class Instances
    * `enum`/`struct` <-> ADTs

    However there is an interesting resources for working around this:

    * [Using a macro to get HKT!](https://gist.github.com/14427/af90a21b917d2892eace)
    * [Using iterators instead!](http://stackoverflow.com/q/18374612/582917)

    Other reading:

    * https://en.wikipedia.org/wiki/Lambda_cube