Skip to content

Instantly share code, notes, and snippets.

@zheeeng

zheeeng/fp-ts-technical-overview.md

Forked from gcanti/fp-ts-technical-overview.md
Created June 21, 2020 04:30
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save zheeeng/112e6d82ccf30fa778dec7325fe27d99 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save zheeeng/112e6d82ccf30fa778dec7325fe27d99 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @gcanti gcanti revised this gist Jun 21, 2018. 1 changed file with 150 additions and 186 deletions.
    336 changes: 150 additions & 186 deletions fp-ts-technical-overview.md
    View file
    Original file line number Diff line number Diff line change
    @@ -2,34 +2,34 @@

    ## A basic `Option` type

    File: Option.ts

    ```ts
    // Option.ts

    // definition
    type None = {
    __tag: 'None'
    export class None {
    readonly tag: 'None' = 'None'
    }

    type Some<A> = {
    __tag: 'Some',
    value: A
    export class Some<A> {
    readonly tag: 'Some' = 'Some'
    constructor(readonly value: A) {}
    }

    type Option<A> = None | Some<A>
    export type Option<A> = None | Some<A>

    // helpers
    const none: None = { __tag: 'None' }
    export const none: Option<never> = new None()

    function some<A>(a: A): Option<A> {
    return { __tag: 'Some', value: a }
    export const some = <A>(a: A): Option<A> => {
    return new Some(a)
    }

    // a specialised map for Option
    function map<A, B>(f: (a: A) => B, fa: Option<A>): Option<B> {
    switch (fa.__tag) {
    case 'None' :
    const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
    switch (fa.tag) {
    case 'None':
    return fa
    case 'Some' :
    case 'Some':
    return some(f(fa.value))
    }
    }
    @@ -39,288 +39,252 @@ Usage

    ```ts
    const double = (n: number): number => n * 2
    const length = (s: string): number => s.length
    const len = (s: string): number => s.length

    console.log(map(double, some(1))) // { __tag: 'Some', value: 2 }
    console.log(map(double, none)) // { __tag: 'None' }
    console.log(map(length, some(2))) // <= error
    console.log(map(double, some(1))) // { tag: 'Some', value: 2 }
    console.log(map(double, none)) // { tag: 'None' }
    console.log(map(len, some(2))) // <= static error: Type 'number' is not assignable to type 'string'
    ```

    ## Adding static land support

    TypeScript doesn't support higher kinded types

    ```ts
    interface StaticFunctor {
    map<A, B>(f: (a: A) => B, fa: ?): ?
    interface Functor {
    map: <A, B>(f: (a: A) => B, fa: ?) => ?
    }
    ```

    but we can fake them with an interface

    ```ts
    interface HKT<F, A> {
    __hkt: F
    __hkta: A
    // HKT.ts

    export interface HKT<F, A> {
    _URI: F
    _A: A
    }
    ```

    where `F` is a unique identifier representing the type constructor and `A` its type parameter.

    Now we can define a generic `StaticFunctor` interface
    Now we can define a generic `Functor` interface

    ```ts
    interface StaticFunctor<F> {
    map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B>
    // Functor.ts

    import { HKT } from './HKT'

    export interface Functor<F> {
    map: <A, B>(f: (a: A) => B, fa: HKT<F, A>) => HKT<F, B>
    }
    ```

    and a new `Option` type
    and redefine the `Option` type

    ```ts
    // Option.ts

    // unique identifier
    type URI = 'Option'
    export const URI = 'Option'

    type None = {
    __tag: 'None'
    __hkt: URI
    __hkta: any
    export type URI = typeof URI

    export class None {
    readonly _URI!: URI
    readonly _A!: never
    readonly tag: 'None' = 'None'
    }

    type Some<A> = {
    __tag: 'Some',
    __hkt: URI
    __hkta: A
    value: A
    export class Some<A> {
    readonly _URI!: URI
    readonly _A!: A
    readonly tag: 'Some' = 'Some'
    constructor(readonly value: A) {}
    }

    type Option<A> = None | Some<A>
    export type Option<A> = None | Some<A>

    const none: None = {
    __tag: 'None',
    __hkt: 'Option',
    __hkta: undefined as any
    }
    export const none: Option<never> = new None()

    function some<A>(a: A): Option<A> {
    return {
    __tag: 'Some',
    __hkt: 'Option',
    __hkta: a,
    value: a
    }
    export const some = <A>(a: A): Option<A> => {
    return new Some(a)
    }

    function map<A, B>(f: (a: A) => B, fa: Option<A>): Option<B> {
    switch (fa.__tag) {
    case 'None' :
    const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
    switch (fa.tag) {
    case 'None':
    return fa
    case 'Some' :
    case 'Some':
    return some(f(fa.value))
    }
    }
    ```

    Let's check the implementation
    Let's define an instance of `Functor` for `Option`

    ```ts
    // if this type-checks the signature is likely correct
    ;({ map } as StaticFunctor<URI>)
    // static land Functor instance
    export const option: Functor<URI> = {
    map
    }
    ```

    Usage
    There's a problem though, this code doesn't type-check with the following error

    ```ts
    console.log(map(double, some(1))) // { __tag: 'Some', __hkt: 'Option', __hkta: 2, value: 2 }
    console.log(map(double, none)) // { __tag: 'None', __hkt: 'Option', __hkta: undefined }
    console.log(map(length, some(2))) // <= error
    ```

    Exports can be directly used as a static land dictionary

    ```ts
    import * as option from './Option' // option contains map
    Type 'HKT<"Option", A>' is not assignable to type 'Option<A>'
    ```

    There's a problem though. Let's define a generic `lift` function based on the `StaticFunctor` interface
    Every `Option<A>` is a `HKT<"Option", A>` but the converse is not true. In order to fix this (we **know** that `Option<A> = HKT<"Option", A>`) functions like `map` should accept the more general version `HKT<"Option", A>` and return the more specific version `Option<A>`

    ```ts
    class FunctorOps {
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B> {
    return fa => functor.map(f, fa)
    const map = <A, B>(f: (a: A) => B, hfa: HKT<URI, A>): Option<B> => {
    const fa = hfa as Option<A>
    switch (fa.tag) {
    case 'None':
    return fa
    case 'Some':
    return some(f(fa.value))
    }
    }

    const ops = new FunctorOps()
    export const option: Functor<URI> = {
    map // no error
    }
    ```

    If we try to use `lift` and `map` together TypeScript raises an error
    There's another issue though: when trying to use the instance we don't get an `Option` as a result

    ```ts
    const maybeLength = ops.lift({ map }, length)

    map(double, maybeLength(some('hello')))
    /*
    Argument of type 'HKT<"Option", number>' is not assignable to parameter of type 'Option<number>'.
    Type 'HKT<"Option", number>' is not assignable to type 'Some<number>'.
    Property '__tag' is missing in type 'HKT<"Option", number>'
    */
    // x: HKT<"Option", number>
    const x = option.map(double, some(1))
    ```

    Every `Option<A>` is a `HKT<"Option", A>` but the converse is not true. In order to fix this (we **know** that `Option<A> = HKT<"Option", A>`) functions like `map` should accept the more general version `HKT<"Option", A>` and return the more specific version `Option<A>`
    we get an `HKT<"Option", number>`.

    ```ts
    type HKTOption<A> = HKT<URI, A>

    function map<A, B>(f: (a: A) => B, fa: HKTOption<A>): Option<B> {
    const option = fa as Option<A>
    switch (option.__tag) {
    case 'None' :
    return option
    case 'Some' :
    return some(f(option.value))
    }
    }
    We must somehow teach TypeScript that `HKT<"Option", number>` is really `Option<number>`, or more generally that
    `HKT<"Option", A>` is `Option<A>` for all `A`.

    map(double, maybeLength(some('hello'))) // ok
    ```
    We'll use a feature called [Module Augmentation](https://www.typescriptlang.org/docs/handbook/declaration-merging.html) for that.

    We can do even better. Note that `maybeLength` has the following signature
    Let's move the `HKT` definition to its own file and add a type-level map named `URI2HKT`

    ```ts
    (fa: HKT<"Option", string>) => HKT<"Option", number>
    ```

    We'd like to have `(fa: Option<string>) => Option<number>` instead.
    // HKT.ts

    We'll use a feature called [Module Augmentation](https://www.typescriptlang.org/docs/handbook/declaration-merging.html) for that
    export interface HKT<F, A> {
    _URI: F
    _A: A
    }

    Let's move the `Functor` definition to its own file
    // type-level map, maps a URI to its corresponding type
    export interface URI2HKT<A> {}
    ```

    File: Functor.ts
    Let's add some helpers types

    ```ts
    export interface StaticFunctor<F> {
    map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B>
    }

    export class FunctorOps {
    // base signature
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B>
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B> {
    return fa => functor.map(f, fa)
    }
    }
    // all URIs
    export type URIS = keyof URI2HKT<any>

    export const ops = new FunctorOps()
    // given a URI and a type, extracts the corresponding type
    export type Type<URI extends URIS, A> = URI2HKT<A>[URI]
    ```
    File: Option.ts
    Adding an entry to the type-level map `URI2HKT` means to leverage the module augmentation feature
    ```ts
    declare module './Functor' {
    interface FunctorOps {
    // specialized signature for Option
    lift<A, B>(functor: StaticFunctor<URI>, f: (a: A) => B): (fa: Option<A>) => Option<B>
    // Option.ts

    declare module './HKT' {
    interface URI2HKT<A> {
    Option: Option<A> // maps the type literal "Option" to the type `Option`
    }
    }
    ```

    That means that `lift` is truly polimophic and may have a specialized signature for any higher kinded type.
    Now we can redefine `Functor` in order to leverage this type-level machinery

    ## Adding fantasy land support
    ```ts
    // Functor.ts

    We can define a generic `FantasyFunctor` interface
    import { URIS, Type } from './HKT'

    ```ts
    interface FantasyFunctor<F, A> extends HKT<F, A> {
    map<B>(f: (a: A) => B): FantasyFunctor<F, B>
    export interface Functor1<F extends URIS> {
    map: <A, B>(f: (a: A) => B, fa: Type<F, A>) => Type<F, B>
    }
    ```

    And now let's change the implementation of `None` and `Some`
    and fix the instance definition

    ```ts
    type URI = 'Option'
    // Option.ts

    class None<A> implements FantasyFunctor<URI, A> {
    __tag: 'None'
    __hkt: URI
    __hkta: any
    map<B>(f: (a: A) => B): Option<B> {
    return none
    }
    }
    import { Functor1 } from './Functor'

    class Some<A> implements FantasyFunctor<URI, A> {
    __tag: 'Some'
    __hkt: URI
    __hkta: A
    constructor(public value: A) { }
    map<B>(f: (a: A) => B): Option<B> {
    return some(f(this.value))
    const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
    switch (fa.tag) {
    case 'None':
    return fa
    case 'Some':
    return some(f(fa.value))
    }
    }

    type Option<A> = None<A> | Some<A>

    const none = new None<any>()

    function some<A>(a: A): Option<A> {
    return new Some(a)
    export const option: Functor1<URI> = {
    map
    }
    ```

    Note that `None` has a type parameter, because the signature of `map` (the method) must be the same for both `None` and `Some` otherwise TypeScript will complain.

    The implementation of `map` (the static function) is now trivial.

    ```ts
    function map<A, B>(f: (a: A) => B, fa: HKTOption<A>): Option<B> {
    return (fa as Option<A>).map(f)
    }
    // x: Option<number>
    const x = option.map(double, some(1))
    ```

    ## Faking Haskell's type classes
    ## Adding fantasy land support

    Let's add to `FunctorOps` a polimorphic `map` function
    Let's add a `map` method to `None` and `Some`

    ```ts
    export class FunctorOps {
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B>
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B> {
    return fa => functor.map(f, fa)
    // Option.ts

    export class None<A> {
    readonly _URI!: URI
    readonly _A!: never
    readonly tag: 'None' = 'None'
    map<B>(f: (a: A) => B): Option<B> {
    return none
    }
    }

    map<F, A, B>(f: (a: A) => B, fa: FantasyFunctor<F, A>): FantasyFunctor<F, B>
    map<F, A, B>(f: (a: A) => B, fa: FantasyFunctor<F, A>): FantasyFunctor<F, B> {
    return fa.map(f)
    export class Some<A> {
    readonly _URI!: URI
    readonly _A!: A
    readonly tag: 'Some' = 'Some'
    constructor(readonly value: A) {}
    map<B>(f: (a: A) => B): Option<B> {
    return some(f(this.value))
    }
    }

    export type Option<A> = None<A> | Some<A>
    ```
    And the corresponding module augmentation in the `Option.ts` file
    Note that `None` has a type parameter now, because the signature of `map` (the method) must be the same for both `None` and `Some` otherwise TypeScript will complain.
    The implementation of `map` (the static function) is now trivial.
    ```ts
    declare module './Functor' {
    interface FunctorOps {
    lift<A, B>(functor: StaticFunctor<URI>, f: (a: A) => B): (fa: Option<A>) => Option<B>
    map<A, B>(f: (a: A) => B, fa: HKTOption<A>): Option<B>
    }
    const map = <A, B>(f: (a: A) => B, fa: Option<A>) => {
    return fa.map(f)
    }
    ```

    > Roughly speaking the `map` definition in `FunctorOps` corresponds to a type class definition, while the module augmentation part corresponds to declaring an instance
    Now `map` is a truly polimorphic function with prefect type inference
    We can now use a nice chainable API (a kind of do notation)

    ```ts
    import * as option from 'fp-ts/lib/Option'
    import * as io from 'fp-ts/lib/IO'
    const length = (s: string): number => s.length

    // x :: Option<number>
    const x = map(length, option.of('hello'))
    // y :: IO<number>
    const y = map(length, io.of('hello'))
    // x: Option<number>
    const x = some('foo')
    .map(len)
    .map(double)
    ```
  2. @gcanti gcanti created this gist Mar 17, 2017.
    326 changes: 326 additions & 0 deletions fp-ts-technical-overview.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,326 @@
    # Technical overview

    ## A basic `Option` type

    File: Option.ts

    ```ts
    // definition
    type None = {
    __tag: 'None'
    }

    type Some<A> = {
    __tag: 'Some',
    value: A
    }

    type Option<A> = None | Some<A>

    // helpers
    const none: None = { __tag: 'None' }

    function some<A>(a: A): Option<A> {
    return { __tag: 'Some', value: a }
    }

    // a specialised map for Option
    function map<A, B>(f: (a: A) => B, fa: Option<A>): Option<B> {
    switch (fa.__tag) {
    case 'None' :
    return fa
    case 'Some' :
    return some(f(fa.value))
    }
    }
    ```

    Usage

    ```ts
    const double = (n: number): number => n * 2
    const length = (s: string): number => s.length

    console.log(map(double, some(1))) // { __tag: 'Some', value: 2 }
    console.log(map(double, none)) // { __tag: 'None' }
    console.log(map(length, some(2))) // <= error
    ```

    ## Adding static land support

    TypeScript doesn't support higher kinded types

    ```ts
    interface StaticFunctor {
    map<A, B>(f: (a: A) => B, fa: ?): ?
    }
    ```

    but we can fake them with an interface

    ```ts
    interface HKT<F, A> {
    __hkt: F
    __hkta: A
    }
    ```

    where `F` is a unique identifier representing the type constructor and `A` its type parameter.

    Now we can define a generic `StaticFunctor` interface

    ```ts
    interface StaticFunctor<F> {
    map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B>
    }
    ```

    and a new `Option` type

    ```ts
    // unique identifier
    type URI = 'Option'

    type None = {
    __tag: 'None'
    __hkt: URI
    __hkta: any
    }

    type Some<A> = {
    __tag: 'Some',
    __hkt: URI
    __hkta: A
    value: A
    }

    type Option<A> = None | Some<A>

    const none: None = {
    __tag: 'None',
    __hkt: 'Option',
    __hkta: undefined as any
    }

    function some<A>(a: A): Option<A> {
    return {
    __tag: 'Some',
    __hkt: 'Option',
    __hkta: a,
    value: a
    }
    }

    function map<A, B>(f: (a: A) => B, fa: Option<A>): Option<B> {
    switch (fa.__tag) {
    case 'None' :
    return fa
    case 'Some' :
    return some(f(fa.value))
    }
    }
    ```

    Let's check the implementation

    ```ts
    // if this type-checks the signature is likely correct
    ;({ map } as StaticFunctor<URI>)
    ```

    Usage

    ```ts
    console.log(map(double, some(1))) // { __tag: 'Some', __hkt: 'Option', __hkta: 2, value: 2 }
    console.log(map(double, none)) // { __tag: 'None', __hkt: 'Option', __hkta: undefined }
    console.log(map(length, some(2))) // <= error
    ```

    Exports can be directly used as a static land dictionary

    ```ts
    import * as option from './Option' // option contains map
    ```
    There's a problem though. Let's define a generic `lift` function based on the `StaticFunctor` interface
    ```ts
    class FunctorOps {
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B> {
    return fa => functor.map(f, fa)
    }
    }

    const ops = new FunctorOps()
    ```

    If we try to use `lift` and `map` together TypeScript raises an error

    ```ts
    const maybeLength = ops.lift({ map }, length)

    map(double, maybeLength(some('hello')))
    /*
    Argument of type 'HKT<"Option", number>' is not assignable to parameter of type 'Option<number>'.
    Type 'HKT<"Option", number>' is not assignable to type 'Some<number>'.
    Property '__tag' is missing in type 'HKT<"Option", number>'
    */
    ```

    Every `Option<A>` is a `HKT<"Option", A>` but the converse is not true. In order to fix this (we **know** that `Option<A> = HKT<"Option", A>`) functions like `map` should accept the more general version `HKT<"Option", A>` and return the more specific version `Option<A>`

    ```ts
    type HKTOption<A> = HKT<URI, A>

    function map<A, B>(f: (a: A) => B, fa: HKTOption<A>): Option<B> {
    const option = fa as Option<A>
    switch (option.__tag) {
    case 'None' :
    return option
    case 'Some' :
    return some(f(option.value))
    }
    }

    map(double, maybeLength(some('hello'))) // ok
    ```

    We can do even better. Note that `maybeLength` has the following signature

    ```ts
    (fa: HKT<"Option", string>) => HKT<"Option", number>
    ```

    We'd like to have `(fa: Option<string>) => Option<number>` instead.

    We'll use a feature called [Module Augmentation](https://www.typescriptlang.org/docs/handbook/declaration-merging.html) for that

    Let's move the `Functor` definition to its own file

    File: Functor.ts

    ```ts
    export interface StaticFunctor<F> {
    map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B>
    }

    export class FunctorOps {
    // base signature
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B>
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B> {
    return fa => functor.map(f, fa)
    }
    }

    export const ops = new FunctorOps()
    ```

    File: Option.ts

    ```ts
    declare module './Functor' {
    interface FunctorOps {
    // specialized signature for Option
    lift<A, B>(functor: StaticFunctor<URI>, f: (a: A) => B): (fa: Option<A>) => Option<B>
    }
    }
    ```

    That means that `lift` is truly polimophic and may have a specialized signature for any higher kinded type.

    ## Adding fantasy land support

    We can define a generic `FantasyFunctor` interface

    ```ts
    interface FantasyFunctor<F, A> extends HKT<F, A> {
    map<B>(f: (a: A) => B): FantasyFunctor<F, B>
    }
    ```

    And now let's change the implementation of `None` and `Some`

    ```ts
    type URI = 'Option'

    class None<A> implements FantasyFunctor<URI, A> {
    __tag: 'None'
    __hkt: URI
    __hkta: any
    map<B>(f: (a: A) => B): Option<B> {
    return none
    }
    }

    class Some<A> implements FantasyFunctor<URI, A> {
    __tag: 'Some'
    __hkt: URI
    __hkta: A
    constructor(public value: A) { }
    map<B>(f: (a: A) => B): Option<B> {
    return some(f(this.value))
    }
    }

    type Option<A> = None<A> | Some<A>

    const none = new None<any>()

    function some<A>(a: A): Option<A> {
    return new Some(a)
    }
    ```

    Note that `None` has a type parameter, because the signature of `map` (the method) must be the same for both `None` and `Some` otherwise TypeScript will complain.

    The implementation of `map` (the static function) is now trivial.

    ```ts
    function map<A, B>(f: (a: A) => B, fa: HKTOption<A>): Option<B> {
    return (fa as Option<A>).map(f)
    }
    ```

    ## Faking Haskell's type classes

    Let's add to `FunctorOps` a polimorphic `map` function

    ```ts
    export class FunctorOps {
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B>
    lift<F, A, B>(functor: StaticFunctor<F>, f: (a: A) => B): (fa: HKT<F, A>) => HKT<F, B> {
    return fa => functor.map(f, fa)
    }

    map<F, A, B>(f: (a: A) => B, fa: FantasyFunctor<F, A>): FantasyFunctor<F, B>
    map<F, A, B>(f: (a: A) => B, fa: FantasyFunctor<F, A>): FantasyFunctor<F, B> {
    return fa.map(f)
    }
    }
    ```

    And the corresponding module augmentation in the `Option.ts` file

    ```ts
    declare module './Functor' {
    interface FunctorOps {
    lift<A, B>(functor: StaticFunctor<URI>, f: (a: A) => B): (fa: Option<A>) => Option<B>
    map<A, B>(f: (a: A) => B, fa: HKTOption<A>): Option<B>
    }
    }
    ```

    > Roughly speaking the `map` definition in `FunctorOps` corresponds to a type class definition, while the module augmentation part corresponds to declaring an instance
    Now `map` is a truly polimorphic function with prefect type inference

    ```ts
    import * as option from 'fp-ts/lib/Option'
    import * as io from 'fp-ts/lib/IO'
    const length = (s: string): number => s.length

    // x :: Option<number>
    const x = map(length, option.of('hello'))
    // y :: IO<number>
    const y = map(length, io.of('hello'))
    ```