Forem: Giulio Canti

Getting started with fp-ts: Reader

Giulio Canti — Wed, 18 Dec 2019 10:29:30 +0000

The purpose of the Reader monad is to avoid threading arguments through multiple functions in order to only get them where they are needed.

One of the ideas presented here is to use the Reader monad for dependency injection.

The first thing you need to know is that the type Reader<R, A> represents a function (r: R) => A

interface Reader<R, A> {
  (r: R): A
}

where R represents an "environment" needed for the computation (we can "read" from it) and A is the result.

Example

Let's say we have the following piece of code

const f = (b: boolean): string => (b ? 'true' : 'false')

const g = (n: number): string => f(n > 2)

const h = (s: string): string => g(s.length + 1)

console.log(h('foo')) // 'true'

What if we want to internationalise f? Well, we could add an additional parameter

interface Dependencies {
  i18n: {
    true: string
    false: string
  }
}

const f = (b: boolean, deps: Dependencies): string => (b ? deps.i18n.true : deps.i18n.false)

Now we have a problem though, g doesn't compile anymore

const g = (n: number): string => f(n > 2) // error: An argument for 'deps' was not provided

We must add an additional parameter to g as well

const g = (n: number, deps: Dependencies): string => f(n > 2, deps) // ok

We haven't finished yet, now it's h that doesn't compile, we must add an additional parameter to h as well

const h = (s: string, deps: Dependencies): string => g(s.length + 1, deps)

finally we can run h by providing an actual instance of the Dependencies interface

const instance: Dependencies = {
  i18n: {
    true: 'vero',
    false: 'falso'
  }
}

console.log(h('foo', instance)) // 'vero'

As you can see, h and g must have knowledge about f dependencies despite not using them.

Can we improve this part? Yes we can, we can move Dependencies from the parameter list to the return type.

`Reader`

Let's start by rewriting our functions, putting the deps parameter alone

const f = (b: boolean): ((deps: Dependencies) => string) => deps => (b ? deps.i18n.true : deps.i18n.false)

const g = (n: number): ((deps: Dependencies) => string) => f(n > 2)

const h = (s: string): ((deps: Dependencies) => string) => g(s.length + 1)

Note that (deps: Dependencies) => string is just Reader<Dependencies, string>

import { Reader } from 'fp-ts/Reader'

const f = (b: boolean): Reader<Dependencies, string> => deps => (b ? deps.i18n.true : deps.i18n.false)

const g = (n: number): Reader<Dependencies, string> => f(n > 2)

const h = (s: string): Reader<Dependencies, string> => g(s.length + 1)

console.log(h('foo')(instance)) // 'vero'

`ask`

What if we want to also inject the lower bound (2 in our example) in g? Let's add a new field to Dependencies first

export interface Dependencies {
  i18n: {
    true: string
    false: string
  }
  lowerBound: number
}

const instance: Dependencies = {
  i18n: {
    true: 'vero',
    false: 'falso'
  },
  lowerBound: 2
}

Now we can read lowerBound from the environment using ask

import { pipe } from 'fp-ts/function'
import { ask, chain, Reader } from 'fp-ts/Reader'

const g = (n: number): Reader<Dependencies, string> =>
  pipe(
    ask<Dependencies>(),
    chain(deps => f(n > deps.lowerBound))
  )

console.log(h('foo')(instance)) // 'vero'
console.log(h('foo')({ ...instance, lowerBound: 4 })) // 'falso'

p.s.

As a curiosity, Reader's map is (the usual) function composition

import { flow, pipe } from 'fp-ts/function'
import { map } from 'fp-ts/Reader'

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

const composition = flow(len, double, gt2)
// equivalent to
const composition = pipe(len, map(double), map(gt2))

Type holes in TypeScript

Giulio Canti — Thu, 27 Jun 2019 16:27:21 +0000

Sandy Maguire recently wrote a nice article about type holes (Implement With Types, Not Your Brain!), this blog post is a porting to TypeScript.

What's a type hole?

The idea is to implement the tiny part of a function that you know how to do, and then ask the compiler for help on the rest of it. It's an iterative process. It's a discussion with the compiler. Each step of the way, you get a little closer to the right answer, and after enough iterations your function has written itself — even if you're not entirely sure how.

TypeScript doesn't support type holes but they can be kind of simulated.

A first example

Let's see the first example from the article

declare function jonk<A, B>(
  ab: (a: A) => B,
  ann: (an: (a: A) => number) => number
): (bn: (b: B) => number) => number

In order to simulate a type hole I'm going to use the following function declaration

declare function _<T>(): T

Let's put it into the jonk's body

function jonk<A, B>(
  ab: (a: A) => B,
  ann: (an: (a: A) => number) => number
): (bn: (b: B) => number) => number {
  return _()
}

If you move the mouse over the "type hole" _ you can see what TypeScript infers for its type parameter T

(bn: (b: B) => number) => number

So what is the type checker telling us? Two things

The expression we want to replace _() with must have type (bn: (b: B) => number) => number.
We have some local binds (ab, ann, jonk, and their types) that we can use to help with the implementation.

Since our hole has type (bn: (b: B) => number) => number we should bind the bn in a lambda (I'll just write the function body from now on)

return bn => _() // inferred type: number

What's the new inferred type? number. How can we produce a number? We can use ab, ann or bn. Since both ann and bn return a number let's choose ann as a guess

return bn => ann(_()) // inferred type: (a: A) => number

Our new hole has a function type, so let's introduce a lambda

return bn => ann(a => _()) // inferred type: number

We need to produce a number again, let's choose bn this time

return bn => ann(a => bn(_())) // inferred type: B

Now we need to produce a B. We have a function that can do that, ab: (a: A) => B

return bn => ann(a => bn(ab(_()))) // inferred type: A

Finally, we have a hole whose type is A. Since we have an A (the a parameter) let's just use that

function jonk<A, B>(
  ab: (a: A) => B,
  ann: (an: (a: A) => number) => number
): (bnn: (b: B) => number) => number {
  return bn => ann(a => bn(ab(a)))
}

Now we have a complete implementation, almost driven by the type checker.

The second example

Let's tackle the second example of the blog post: zoop

declare function zoop<A, B>(abb: (a: A) => (b: B) => B, b: B, as: Array<A>): B

We notice that as has type Array<A>, let's "pattern match" on that using foldLeft

import { foldLeft } from 'fp-ts/lib/Array'
import { pipe } from 'fp-ts/lib/pipeable'

function zoop<A, B>(abb: (a: A) => (b: B) => B, b: B, as: Array<A>): B {
  return pipe(
    as,
    foldLeft(
      () => _(), // inferred type: B
      (head, tail) => _() // inferred type: B
    )
  )
}

We need to produce a B for the "nil" case (i.e. when the array is empty). Since we have a B let's just use that (I'll just write the function body from now on)

return pipe(
  as,
  foldLeft(
    () => b,
    (head, tail) => _() // inferred type: B
  )
)

Again we want to produce a B for the other case and we want to call abb. Since it takes two arguments, let's give it two holes

return pipe(
  as,
  foldLeft(
    () => b,
    (head, tail) =>
      abb(
        _() // inferred type: A
      )(
        _() // inferred type: B
      )
  )
)

head has type A so let's use it

return pipe(
  as,
  foldLeft(
    () => b,
    (head, tail) =>
      abb(head)(
        _() // inferred type: B
      )
  )
)

Now we must to produce a B and we want to use tail which has type Array<A>. Our only option is using zoop itself

function zoop<A, B>(abb: (a: A) => (b: B) => B, b: B, as: Array<A>): B {
  return pipe(
    as,
    foldLeft(() => b, (head, tail) => abb(head)(zoop(abb, b, tail)))
  )
}

// p.s. `zoop` is `reduceRight`

The reason why this works is known as theorems for free, which roughly states that we can infer lots of facts about a type signature (assuming it's correct.)

Getting started with fp-ts: IO

Giulio Canti — Sun, 14 Apr 2019 06:31:21 +0000

In fp-ts a synchronous effectful computation is represented by the IO type, which is basically a thunk, i.e. a function with the following signature: () => A

interface IO<A> {
  (): A
}

Note that IO represents a computation that never fails.

Examples of such computations are:

read / write to localStorage
get the current time
write to the console
get a random number

Example (read / write to localStorage)

import { fromNullable, Option } from 'fp-ts/Option'

const getItem = (key: string): IO<Option<string>> => () =>
  fromNullable(localStorage.getItem(key))

const setItem = (key: string, value: string): IO<void> => () =>
  localStorage.setItem(key, value)

Example (get the current time)

const now: IO<number> = () => new Date().getTime()

Example (write to the console)

const log = (s: unknown): IO<void> => () => console.log(s)

Example (get a random number)

const random: IO<number> = () => Math.random()

The IO type admits a Monad instance, so you can map...

import { io } from 'fp-ts/IO'

/** get a random boolean */
const randomBool: IO<boolean> = io.map(random, n => n < 0.5)

...or chain computations

/** write to the `console` a random boolean */
const program: IO<void> = io.chain(randomBool, log)

program()

Note that nothing happens until you call program().

That's because program is a value which just represents an effectful computation, so in order to execute any side effect you must "run the IO action".

Since IO actions are just values you can use useful abstractions like Monoid to handle them...

Example (Dungeons and Dragons)

import { log } from 'fp-ts/Console'
import { getMonoid, IO, io } from 'fp-ts/IO'
import { fold, Monoid, monoidSum } from 'fp-ts/Monoid'
import { randomInt } from 'fp-ts/Random'

type Die = IO<number>

const monoidDie: Monoid<Die> = getMonoid(monoidSum)

/** returns the sum of the roll of the dice */
const roll: (dice: Array<Die>) => IO<number> = fold(monoidDie)

const D4: Die = randomInt(1, 4)
const D10: Die = randomInt(1, 10)
const D20: Die = randomInt(1, 20)

const dice = [D4, D10, D20]

io.chain(roll(dice), result => log(`Result is: ${result}`))()
/*
Result is: 11
*/

..or define useful combinators

/** Log any value to the console for debugging purposes */
const withLogging = <A>(action: IO<A>): IO<A> =>
  io.chain(action, a => io.map(log(`Value is: ${a}`), () => a))

io.chain(roll(dice.map(withLogging)), result => log(`Result is: ${result}`))()
/*
Value is: 4
Value is: 2
Value is: 13
Result is: 19
*/

Error handling

What if we want to represent a synchronous effectful computation that may fail?

We need two effects:

Type constructor	Effect (interpretation)
`IO<A>`	a synchronous effectful computation
`Either<E, A>`	a computation that may fail

The solution is to put Either inside IO, which leads to the IOEither type

interface IOEither<E, A> extends IO<Either<E, A>> {}

When we "run" a value of type IOEither<E, A>, if we get a Left it means that the computation failed with an error of type E, otherwise we get a Right which means that the computation succeeded with a value of type A.

Example (read a file)

Since fs.readFileSync may throw, I'm going to use the tryCatch helper

tryCatch: <E, A>(f: () => A) => IOEither<E, A>

where f is a thunk that either throws an error (which is automatically catched by tryCatch) or returns a value of type A.

import { toError } from 'fp-ts/Either'
import { IOEither, tryCatch } from 'fp-ts/IOEither'
import * as fs from 'fs'

const readFileSync = (path: string): IOEither<Error, string> =>
  tryCatch(() => fs.readFileSync(path, 'utf8'), toError)

readFileSync('foo')() // => left(Error: ENOENT: no such file or directory, open 'foo')
readFileSync(__filename)() // => right(...)

Lifting

The fp-ts/IOEither module provides other helpers which allow to create values of type IOEither, they are collectively called lifting functions.

Here's a summary

Start value	lifting function
`IO<E>`	`leftIO: <E, A>(ml: IO<E>) => IOEither<E, A>`
`E`	`left: <E, A>(e: E) => IOEither<E, A>`
`Either<E, A>`	`fromEither: <E, A>(ma: Either<E, A>) => IOEither<E, A>`
`A`	`right: <E, A>(a: A) => IOEither<E, A>`
`IO<A>`	`rightIO: <E, A>(ma: IO<A>) => IOEither<E, A>`

Example (loading a random file)

Let's say we want to randomly load the content of one of three files (1.txt, 2.txt, 3.txt).

The randomInt: (low: number, high: number) => IO<number> function returns a random integer uniformly distributed in the closed interval [low, high]

import { randomInt } from 'fp-ts/Random'

We can chain randomInt with the readFileSync function defined above

import { ioEither } from 'fp-ts/IOEither'

const randomFile = ioEither.chain(
  randomInt(1, 3), // static error
  n => readFileSync(`${__dirname}/${n}.txt`)
)

This doesn't type check though!

The types don't align: randomInt runs in the IO context while readFileSync runs in the IOEither context.

However we can lift randomInt to the IOEither context by using rightIO (see the summary above)

import { ioEither, rightIO } from 'fp-ts/IOEither'

const randomFile = ioEither.chain(rightIO(randomInt(1, 3)), n =>
  readFileSync(`${__dirname}/${n}.txt`)
)

Getting started with fp-ts: Monad

Giulio Canti — Tue, 09 Apr 2019 06:05:40 +0000

In the last post we saw that we can compose an effectful program f: (a: A) => M with a pure n-ary program g by lifting g, provided that M admits an applicative functor instance

Program f	Program g	Composition
pure	pure	`g ∘ f`
effectful	pure, `n`-ary	`liftAn(g) ∘ f`

where `liftA1 = lift`

However we must solve one last case: what if both programs are effectful?

f: (a: A) => M<B>
g: (b: B) => M<C>

What's the "composition" of such f and g?

In order to handle this last case we need something more powerful than Functor since it's quite easy to end up with nested contexts.

The problem: nested contexts

To better explain why we need something more, let's see some examples.

Example (M = Array)

Say we want to retrive the followers of the followers of a Twitter user:

interface User {
  followers: Array<User>
}

const getFollowers = (user: User): Array<User> => user.followers

declare const user: User

const followersOfFollowers: Array<Array<User>> = getFollowers(user).map(getFollowers)

There's something wrong here, followersOfFollowers has the type Array<Array<User>> but we want Array<User>.

We need to flatten the nested arrays.

The flatten: <A>(mma: Array<Array<A>>) => Array<A> function exported by fp-ts comes in handy

import { flatten } from 'fp-ts/Array'

const followersOfFollowers: Array<User> = flatten(getFollowers(user).map(getFollowers))

Nice! What about other data structures?

Example (M = Option)

Say we want to calculate the inverse of the head of a numeric list

import { Option, some, none, option } from 'fp-ts/Option'
import { head } from 'fp-ts/Array'

const inverse = (n: number): Option<number> => (n === 0 ? none : some(1 / n))

const inverseHead: Option<Option<number>> = option.map(head([1, 2, 3]), inverse)

Opss, I did it again, inverseHead has the type Option<Option<number>> but we want Option<number>.

We need to flatten the nested Options.

import { isNone } from 'fp-ts/Option'

const flatten = <A>(mma: Option<Option<A>>): Option<A> => (isNone(mma) ? none : mma.value)

const inverseHead: Option<number> = flatten(option.map(head([1, 2, 3]), inverse))

All those flatten functions... It's not a coincidence, there's a functional pattern under the hood.

Indeed all those type constructors (and many others) admit a monad instance and

flatten is the most peculiar operation of monads

So what's a monad?

This is how monads are often presented...

Definition

A monad is defined by three things:

(1) a type constructor M which admits a Functor instance

(2) a function of with the following signature

of: <A>(a: A) => HKT<M, A>

(3) a function flatMap with the following signature

flatMap: <A, B>(f: (a: A) => HKT<M, B>) => ((ma: HKT<M, A>) => HKT<M, B>)

Note: recall that the HKT type is the fp-ts way to represent a generic type constructor, so when you see HKT<M, X> you can think to the type constructor M applied to the type X (i.e. M<X>).

The functions of and flatMap are required to obey three laws:

flatMap(of) ∘ f = f (Left identity)
flatMap(f) ∘ of = f (Right identity)
flatMap(h) ∘ (flatMap(g) ∘ f) = flatMap((flatMap(h) ∘ g)) ∘ f (Associativity)

where f, g, h are all effectful functions and ∘ is the usual function composition.

Ok but... why?

Back in the day when I first saw such a definition my first reaction was bewilderment.

All these questions were spinning around in my head:

why those two particular operations and why they have those types?
why the name "flatMap"?
why the laws? What do they mean?
but above all, where's my flatten?

This post will try to answer each question.

Let's get back to our problem: what's the composition of two effectful functions (also called Kleisli arrows)?

(two Kleisli arrows, what's their composition?)

I don't even know what its type is.

Wait... we already encountered an abstraction that is all about composition. Do you remember what I said about categories?

Categories capture the essence of composition

We can turn our problem into a category problem: can we find a category that models the composition of Kleisli arrows?

The Kleisli category

Let's try to build a category K (named Kleisli category) which only contains effectful functions:

the objects are the same objects of the TS category, that is all the TypeScript types.
the morphisms are built like this: whenever there's a Kleisli arrow f: A ⟼ M in TS we draw an arrow f': A ⟼ B in K

(above the _TS_ category, below the _K_ construction)

So what would be the composition of f' and g' in K? That's the dashed arrow labeled h' in the image below

(above the composition in the _TS_ category, below the composition in the _K_ construction)

Since h' is an arrow that goes from A to C, there should be a corresponding function h from A to M<C> in TS.

So a good candidate for the composition of f and g in TS is still an effectful function with the following signature: (a: A) => M<C>.

How can we build such a function? Well, let's try!

In which we build the composition step by step

The point (1) of the monad defintion says the M admits a functor instance, so we can lift the function g: (b: B) => M<C> to a function lift(g): (mb: M) => M<M<C>> (here I'm using its synonym map)

(where `flatMap` comes from)

And now we are stuck: there's no legal operation on the functor instance which is able to flatten a value of type M<M<C>> to a value of type M<C>, we need an additional flatten operation.

If we can define such operation then we can obtain the composition we are looking for

h = flatten ∘ map(g) ∘ f

But wait, flatten ∘ map(g) is flatMap, that's where the name comes from!

h = flatMap(g) ∘ f

We can now update our "composition table"

Program f	Program g	Composition
pure	pure	`g ∘ f`
effectful	pure, `n`-ary	`liftAn(g) ∘ f`
effectful	effectful	`flatMap(g) ∘ f`

where `liftA1 = lift`

What about of? Well, of comes from the identity morphisms in K: for each identity morphism 1A in K there should be a corresponding function from A to M<A> (i.e. of: <A>(a: A) => M<A>).

(where `of` comes from)

The laws

Last question: where do the laws come from? They are just the category laws in K translated into TS:

Law	K	TS
Left identity	1B ∘ `f'` = `f'`	`flatMap(of) ∘ f = f`
Right identity	`f'` ∘ 1A = `f'`	`flatMap(f) ∘ of = f`
Associativity	`h' ∘ (g' ∘ f') = (h' ∘ g') ∘ f'`	`flatMap(h) ∘ (flatMap(g) ∘ f) = flatMap((flatMap(h) ∘ g)) ∘ f`

Monads in `fp-ts`

In fp-ts the flatMap function is modeled by a variant called chain, which is basically flatMap with the arguments rearranged

flatMap: <A, B>(f: (a: A) => HKT<M, B>) => ((ma: HKT<M, A>) => HKT<M, B>)
chain:   <A, B>(ma: HKT<M, A>, f: (a: A) => HKT<M, B>) => HKT<M, B>

Note that chain can be derived from flatMap (and viceversa).

Now if we get back to the examples showing the problem with nested contexts we can fix them by using chain

import { array, head } from 'fp-ts/Array'
import { Option, option } from 'fp-ts/Option'

const followersOfFollowers: Array<User> = array.chain(getFollowers(user), getFollowers)

const headInverse: Option<number> = option.chain(head([1, 2, 3]), inverse)

Conclusion

Functional programming provides universal ways to compose functions with effects: functors, applicative functors and monads are all abstractions that offer principled tools for composing different kind of programs.

TLDR: functional programming is really all about composition

Getting started with fp-ts: Either vs Validation

Giulio Canti — Wed, 03 Apr 2019 13:23:55 +0000

The problem

Say you must implement a web form to signup for an account. The form contains two field: username and password and the following validation rules must hold:

username must not be empty
username can't have dashes in it
password needs to have at least 6 characters
password needs to have at least one capital letter
password needs to have at least one number

Either

The Either<E, A> type represents a computation that might fail with an error of type E or succeed with a value of type A, so is a good candidate for implementing our validation rules.

For example let's encode each password rule

import { Either, left, right } from 'fp-ts/Either'

const minLength = (s: string): Either<string, string> =>
  s.length >= 6 ? right(s) : left('at least 6 characters')

const oneCapital = (s: string): Either<string, string> =>
  /[A-Z]/g.test(s) ? right(s) : left('at least one capital letter')

const oneNumber = (s: string): Either<string, string> =>
  /[0-9]/g.test(s) ? right(s) : left('at least one number')

We can chain all the rules using... chain

import { chain } from 'fp-ts/Either'
import { pipe } from 'fp-ts/function'

const validatePassword = (s: string): Either<string, string> =>
  pipe(
    minLength(s),
    chain(oneCapital),
    chain(oneNumber)
  )

Because we are using Either the checks are fail-fast. That is, any failed check shortcircuits subsequent checks so we will only ever get one error.

console.log(validatePassword('ab'))
// => left("at least 6 characters")

console.log(validatePassword('abcdef'))
// => left("at least one capital letter")

console.log(validatePassword('Abcdef'))
// => left("at least one number")

However this could lead to a bad UX, it would be nice to have all of these errors be reported simultaneously.

The Validation abstraction may help here.

Validation

Validations are much like Either<E, A>, they represent a computation that might fail with an error of type E or succeed with a value of type A, but as opposed to the usual computations involving Either, they are able to collect multiple failures.

In order to do that we must tell validations how to combine two values of type E.

That's what Semigroup is all about: combining two values of the same type.

For example we can pack the errors into a non empty array.

The 'fp-ts/Either' module provides a getValidation function that, given a semigroup, returns an alternative Applicative instance for Either

import { getSemigroup } from 'fp-ts/NonEmptyArray'
import { getValidation } from 'fp-ts/Either'

const applicativeValidation = getValidation(getSemigroup<string>())

However in order to use applicativeValidation we must first redefine all the rules so that they return a value of type Either<NonEmptyArray<string>, string>.

Instead of rewriting all the previous functions, which is cumbersome, let's define a combinator that converts a check outputting an Either<E, A> into a check outputting a Either<NonEmptyArray<E>, A>

import { NonEmptyArray } from 'fp-ts/NonEmptyArray'
import { mapLeft } from 'fp-ts/Either'

function lift<E, A>(check: (a: A) => Either<E, A>): (a: A) => Either<NonEmptyArray<E>, A> {
  return a =>
    pipe(
      check(a),
      mapLeft(a => [a])
    )
}

const minLengthV = lift(minLength)
const oneCapitalV = lift(oneCapital)
const oneNumberV = lift(oneNumber)

Let's put all together, I'm going to use the sequenceT helper which takes n actions and does them from left-to-right, returning the resulting tuple

import { sequenceT } from 'fp-ts/Apply'
import { map } from 'fp-ts/Either'

function validatePassword(s: string): Either<NonEmptyArray<string>, string> {
  return pipe(
    sequenceT(getValidation(getSemigroup<string>()))(
      minLengthV(s),
      oneCapitalV(s),
      oneNumberV(s)
    ),
    map(() => s)
  )
}
console.log(validatePassword('ab'))
// => left(["at least 6 characters", "at least one capital letter", "at least one number"])

Appendix

Note that the sequenceT helper is able to handle actions with different types:

interface Person {
  name: string
  age: number
}

// Person constructor
const toPerson = ([name, age]: [string, number]): Person => ({
  name,
  age
})

const validateName = (s: string): Either<NonEmptyArray<string>, string> =>
  s.length === 0 ? left(['Invalid name']) : right(s)

const validateAge = (s: string): Either<NonEmptyArray<string>, number> =>
  isNaN(+s) ? left(['Invalid age']) : right(+s)

function validatePerson(name: string, age: string): Either<NonEmptyArray<string>, Person> {
  return pipe(
    sequenceT(applicativeValidation)(validateName(name), validateAge(age)),
    map(toPerson)
  )
}

Getting started with fp-ts: Applicative

Giulio Canti — Thu, 28 Mar 2019 16:58:48 +0000

In the last post we saw that we can compose an effectful program f: (a: A) => F with a pure program g: (b: B) => C by lifting g to a function lift(g): (fb: F) => F<C> provided that F admits a functor instance

Program f	Program g	Composition
pure	pure	`g ∘ f`
effectful	pure (unary)	`lift(g) ∘ f`

However g must be unary, that is it must accept only one argument as input. What if g accepts two arguments? Can we still lift g by using only the functor instance? Well, let's try!

Currying

First of all we must model a function that accepts two arguments, let's say of type B and C (we can use a tuple) and returns a value of type D

g: (args: [B, C]) => D

We can rewrite g using a technique called currying.

Currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, a function that takes two arguments, one from B and one from C, and produces outputs in D, by currying is translated into a function that takes a single argument from C and produces as outputs functions from B to C.

(source: currying on wikipedia.org)

So we can rewrite g to

g: (b: B) => (c: C) => D

What we want is a lifting operation, let't call it liftA2 in order to distinguish it from our old lift, that outputs a function with the following signature

liftA2(g): (fb: F<B>) => (fc: F<C>) => F<D>

How can we get there? Since g is now unary, we can use the functor instance and our old lift

lift(g): (fb: F<B>) => F<(c: C) => D>

But now we are stuck: there's no legal operation on the functor instance which is able to unpack the value F<(c: C) => D> to a function (fc: F<C>) => F<D>.

Apply

So let's introduce a new abstraction Apply that owns such a unpacking operation (named ap)

interface Apply<F> extends Functor<F> {
  ap: <C, D>(fcd: HKT<F, (c: C) => D>, fc: HKT<F, C>) => HKT<F, D>
}

The ap function is basically unpack with the arguments rearranged

unpack: <C, D>(fcd: HKT<F, (c: C) => D>) => ((fc: HKT<F, C>) => HKT<F, D>)
ap:     <C, D>(fcd: HKT<F, (c: C) => D>, fc: HKT<F, C>) => HKT<F, D>

so ap can be derived from unpack (and viceversa).

Note: the HKT type is the fp-ts way to represent a generic type constructor (a technique proposed in the Lightweight higher-kinded polymorphism paper) so when you see HKT<F, X> you can think to the type constructor F applied to the type X (i.e. F<X>).

Applicative

Moreover it would be handy if there exists an operation which is able to lift a value of type A to a value of type F<A>. This way we could call the liftA2(g) function either by providing arguments of type F and F<C> or by lifting values of type B and C.

So let's introduce the Applicative abstraction which builds upon Apply and owns such operation (named of)

interface Applicative<F> extends Apply<F> {
  of: <A>(a: A) => HKT<F, A>
}

Let's see the Applicative instances for some common data types

Example (F = Array)

import { flatten } from 'fp-ts/Array'

const applicativeArray = {
  map: <A, B>(fa: Array<A>, f: (a: A) => B): Array<B> => fa.map(f),
  of: <A>(a: A): Array<A> => [a],
  ap: <A, B>(fab: Array<(a: A) => B>, fa: Array<A>): Array<B> =>
    flatten(fab.map(f => fa.map(f)))
}

Example (F = Option)

import { Option, some, none, isNone } from 'fp-ts/Option'

const applicativeOption = {
  map: <A, B>(fa: Option<A>, f: (a: A) => B): Option<B> =>
    isNone(fa) ? none : some(f(fa.value)),
  of: <A>(a: A): Option<A> => some(a),
  ap: <A, B>(fab: Option<(a: A) => B>, fa: Option<A>): Option<B> =>
    isNone(fab) ? none : applicativeOption.map(fa, fab.value)
}

Example (F = Task)

import { Task } from 'fp-ts/Task'

const applicativeTask = {
  map: <A, B>(fa: Task<A>, f: (a: A) => B): Task<B> => () => fa().then(f),
  of: <A>(a: A): Task<A> => () => Promise.resolve(a),
  ap: <A, B>(fab: Task<(a: A) => B>, fa: Task<A>): Task<B> => () =>
    Promise.all([fab(), fa()]).then(([f, a]) => f(a))
}

Lifting

So given an instance of Apply for F can we now write liftA2?

import { HKT } from 'fp-ts/HKT'
import { Apply } from 'fp-ts/Apply'

type Curried2<B, C, D> = (b: B) => (c: C) => D

function liftA2<F>(
  F: Apply<F>
): <B, C, D>(g: Curried2<B, C, D>) => Curried2<HKT<F, B>, HKT<F, C>, HKT<F, D>> {
  return g => fb => fc => F.ap(F.map(fb, g), fc)
}

Nice! But what about functions with three arguments? Do we need yet another abstraction?

The good news is that the answer is no, Apply is enough

type Curried3<B, C, D, E> = (b: B) => (c: C) => (d: D) => E

function liftA3<F>(
  F: Apply<F>
): <B, C, D, E>(
  g: Curried3<B, C, D, E>
) => Curried3<HKT<F, B>, HKT<F, C>, HKT<F, D>, HKT<F, E>> {
  return g => fb => fc => fd => F.ap(F.ap(F.map(fb, g), fc), fd)
}

Actually given an instance of Apply we can write a liftAn function, for each n.

Note. liftA1 is just lift, the Functor operation.

We can now update our "composition table"

Program f	Program g	Composition
pure	pure	`g ∘ f`
effectful	pure, `n`-ary	`liftAn(g) ∘ f`

where liftA1 = lift

Is the general problem solved?

Not yet. There's still an important case which is missing: what if both programs are effectful?

Again we need something more: in the next post I'll talk about one of the most important abstractions of functional programming: monads.

TLDR: functional programming is all about composition

Getting started with fp-ts: Functor

Giulio Canti — Fri, 22 Mar 2019 11:20:02 +0000

In the last post about categories I presented the TS category (the TypeScript category) and the central problem with function composition

How can we compose two generic functions f: (a: A) => B and g: (c: C) => D?

Why finding solutions to this problem is so important?

Because if categories can be used to model programmming languages, morphisms (i.e. functions in TS) can be used to model programs.

Therefore solving the problem also means to find how to compose programs in a general way. And this is pretty interesting for a developer, isn't it?

Functions as programs

We call pure program a function with the following signature

(a: A) => B

Such a signature models a program which accepts an input of type A and yields a result of type B, without any effect.

We call effectful program a function with the following signature

(a: A) => F<B>

Such a signature models a program which accepts an input of type A and yields a result of type B, along with an effect F, where F is some type constructor.

Recall that a type constructor is an n-ary type operator taking as argument zero or more types, and returning another type.

Example

Given the concrete type string, the Array type constructor returns the concrete type Array<string>

Here we are interested in n-ary type constructors with n >= 1, for example

Type constructor	Effect (interpretation)
`Array<A>`	a non deterministic computation
`Option<A>`	a computation that may fail
`Task<A>`	an asynchronous computation

Now back to our main problem

How can we compose two generic functions f: (a: A) => B and g: (c: C) => D?

Since the general problem is intractable, we need to put some constraint on B and C.

We already know that if B = C then the solution is the usual function composition

function compose<A, B, C>(g: (b: B) => C, f: (a: A) => B): (a: A) => C {
  return a => g(f(a))
}

What about the other cases?

In which the constraint `B = F<C>` leads to functors

Let's consider the following constraint: B = F<C> for some type constructor F, or in other words (and after some renaming)

f: (a: A) => F is an effectful program
g: (b: B) => C is a pure program

In order to compose f with g we could find a way to lift g from a function (b: B) => C to a function (fb: F) => F<C> so that we can use the usual function composition (the output type of f would be the same as the input type of the lifted function)

So we turned the original problem into another one: can we find such a lift function?

Let's see some examples

Example (F = Array)

function lift<B, C>(g: (b: B) => C): (fb: Array<B>) => Array<C> {
  return fb => fb.map(g)
}

Example (F = Option)

import { Option, isNone, none, some } from 'fp-ts/Option'

function lift<B, C>(g: (b: B) => C): (fb: Option<B>) => Option<C> {
  return fb => (isNone(fb) ? none : some(g(fb.value)))
}

Example (F = Task)

import { Task } from 'fp-ts/Task'

function lift<B, C>(g: (b: B) => C): (fb: Task<B>) => Task<C> {
  return fb => () => fb().then(g)
}

All those lift functions almost look the same. It's not a coincidence, there's a functional pattern under the hood.

Indeed all those type constructors (and many others) admit a functor instance.

Functors

Functors are mappings between categories that preserve the categorical structure, i.e. that preserve identity morphisms and composition.

Since categories are constituted of two things (objects and morphisms) a functor is constituted of two things as well:

a mapping between objects that associates to each object X in C an object in D
a mapping between morphisms that associates to each morphism in C a morphism in D

where C and D are two categories (aka two programming languages).

(source: [functor on ncatlab.org](https://ncatlab.org/nlab/show/functor))

Even if a mapping between two different programming languages is an intriguing idea, we are more interested in a mapping where C and D coincide (with TS). In this case we talk about endofunctors ("endo" means "within", "inside").

From now on when I write "functor" I actually mean an endofunctor in TS.

Definition

A functor is a pair (F, lift) where

F is a n-ary type constructor (n >= 1) which maps each type X to the type F<X> (mapping between objects)
lift is a function with the following signature

lift: <A, B>(f: (a: A) => B) => ((fa: F<A>) => F<B>)

which maps each function f: (a: A) => B to a function lift(f): (fa: F<A>) => F (mapping between morphisms).

The following properties must hold

lift(identityX) = identityF(X) (identities map to identities)
lift(g ∘ f) = lift(g) ∘ lift(f) (mapping a composition is the composition of the mappings)

The lift function is also known through a variant called map, which is basically lift with the arguments rearranged

lift: <A, B>(f: (a: A) => B) => ((fa: F<A>) => F<B>)
map:  <A, B>(fa: F<A>, f: (a: A) => B) => F<B>

Note that map can be derived from lift (and viceversa).

Functors in `fp-ts`

How can we define a functor instance in fp-ts? Let's see a practical example.

The following declaration defines a model for the response of an API call

interface Response<A> {
  url: string
  status: number
  headers: Record<string, string>
  body: A
}

Note that the body field is parametrized, this makes Response a good candidate for a functor instance since Response is a n-ary type constructors with n >= 1 (a necessary precondition).

In order to define a functor instance for Response we must define a map function (along with some technicalities required by fp-ts)

// `Response.ts` module

import { Functor1 } from 'fp-ts/Functor'

export const URI = 'Response'

export type URI = typeof URI

declare module 'fp-ts/HKT' {
  interface URItoKind<A> {
    Response: Response<A>
  }
}

export interface Response<A> {
  url: string
  status: number
  headers: Record<string, string>
  body: A
}

function map<A, B>(fa: Response<A>, f: (a: A) => B): Response<B> {
  return { ...fa, body: f(fa.body) }
}

// functor instance for `Response`
export const functorResponse: Functor1<URI> = {
  URI,
  map
}

Is the general problem solved?

Not at all. Functors allow us to compose an effectful program f with a pure program g, but g must be unary, that is it must accept only one argument as input. What if g accepts two arguments? Or three?

Program f	Program g	Composition
pure	pure	`g ∘ f`
effectful	pure (unary)	`lift(g) ∘ f`
effectful	pure (`n`-ary, `n > 1`)	?

In order to handle such circumstances we need something more: in the next post I'll talk about another remarkable abstraction of functional programming: applicative functors.

TLDR: functional programming is all about composition

Getting started with fp-ts: Category

Giulio Canti — Wed, 20 Mar 2019 14:17:11 +0000

In the last posts we saw some basic abstractions used in functional programming: Eq, Ord, Semigroup and Monoid.

In the next posts we will explore some advanced abstractions that make functional programming even more interesting.

Storically the first advanced abstraction contained in fp-ts is Functor, but before we can talk about functors we need to learn something about categories since functors are built upon them.

A corner stone of functional programming is composition. But what does that exactely mean? When we can say that two things compose? And when we can say that things compose well?

We need a formal definition of composition. That's what categories are all about.

Categories capture the essence of composition.

Functional design: Algebraic Data Types

Giulio Canti — Mon, 18 Mar 2019 09:49:52 +0000

A good first step while building a new application is to define its domain model. TypeScript offers many tools to help you in this task. Algebraic Data Types (ADT for short) are one of these tools.

What is an ADT?

In computer programming, especially functional programming and type theory, an algebraic data type is a kind of composite type, i.e., a type formed by combining other types.

Two common classes of algebraic types are:

product types
sum types

Product types

A product type is a collection of types Ti indexed by a set I.

Two common members of this family are n-tuples, where I is a non empty interval of natural numbers...

type Tuple1 = [string] // I = [0]
type Tuple2 = [string, number] // I = [0, 1]
type Tuple3 = [string, number, boolean] // I = [0, 1, 2]

// Accessing by index
type Fst = Tuple2[0] // string
type Snd = Tuple2[1] // number

...and structs, where I is a set of labels.

// I = {"name", "age"}
interface Person {
  name: string
  age: number
}

// Accessing by label
type Name = Person['name'] // string
type Age = Person['age'] // number

Why "product" types?

If we write C(A) for the number of inhabitants of the type A (aka its cardinality) then the following equality holds

C([A, B]) = C(A) * C(B)

the cardinality of the product is the product of cardinalities

Example

type Hour = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
type Period = 'AM' | 'PM'
type Clock = [Hour, Period]

The Clock type has 12 * 2 = 24 inhabitants.

When should I use a product type?

Whenever its components are independent.

type Clock = [Hour, Period]

Here Hour and Period are independent, i.e. the value of Hour doesn't affect the value of Period and vice versa, all pairs are legal and meaningful.

Sum types

A sum type is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which one is in use.

In the TypeScript documentation they are named tagged union types.

Example (redux actions)

type Action =
  | {
      type: 'ADD_TODO'
      text: string
    }
  | {
      type: 'UPDATE_TODO'
      id: number
      text: string
      completed: boolean
    }
  | {
      type: 'DELETE_TODO'
      id: number
    }

The type field is the tag and ensures that its members are disjoint.

Constructors

A sum type with n members requires n constructors, one for each member

const add = (text: string): Action => ({
  type: 'ADD_TODO',
  text
})

const update = (id: number, text: string, completed: boolean): Action => ({
  type: 'UPDATE_TODO',
  id,
  text,
  completed
})

const del = (id: number): Action => ({
  type: 'DELETE_TODO',
  id
})

Sum types can be polymorphic and/or recursive.

Example (linked lists)

//        ↓ type parameter
type List<A> = { type: 'Nil' } | { type: 'Cons'; head: A; tail: List<A> }
//                                                              ↑ recursion

Pattern matching

JavaScript doesn't have pattern matching (and so TypeScript) however we can define a "poor man" pattern matching by defining a fold function

const fold = <A, R>(
  fa: List<A>,
  onNil: () => R,
  onCons: (head: A, tail: List<A>) => R
): R => (fa.type === 'Nil' ? onNil() : onCons(fa.head, fa.tail))

Example (calculate the length of a List recursively)

const length = <A>(fa: List<A>): number =>
  fold(fa, () => 0, (_, tail) => 1 + length(tail))

Why "sum" types?

The following equality holds

C(A | B) = C(A) + C(B)

the cardinality of the sum is the sum of cardinalities

Example (the Option type)

type Option<A> =
  | { type: 'None' }
  | {
      type: 'Some'
      value: A
    }

From the general formula C(Option<A>) = 1 + C(A) we can derive for example the cardinality of Option<boolean>: 1 + 2 = 3 inhabitants.

When should I use a sum type?

When its components would be dependent if implemented as a product type.

Example (component props)

interface Props {
  editable: boolean
  onChange?: (text: string) => void
}

class Textbox extends React.Component<Props> {
  render() {
    if (this.props.editable) {
      // error: Cannot invoke an object which is possibly 'undefined' :(
      this.props.onChange(...)
    }
  }
}

The problem here is that Props is modelled as a product type but onChange depends on editable.

A sum type is a better choice

type Props =
  | {
      type: 'READONLY'
    }
  | {
      type: 'EDITABLE'
      onChange: (text: string) => void
    }

class Textbox extends React.Component<Props> {
  render() {
    switch (this.props.type) {
      case 'EDITABLE' :
        this.props.onChange(...) // :)
      ...
    }
  }
}

Example (node callbacks)

declare function readFile(
  path: string,
  //         ↓ ---------- ↓ CallbackArgs
  callback: (err?: Error, data?: string) => void
): void

The result is modelled as a product type

type CallbackArgs = [Error | undefined, string | undefined]

however, its components are dependent: you get either an error or a string

err	data	legal?
`Error`	`undefined`	✓
`undefined`	`string`	✓
`Error`	`string`	✘
`undefined`	`undefined`	✘

A sum type would be a better choice, but which one?

Functional error handling

Let's see how to deal with errors in a functional style.

The `Option` type

The Option type represents the effect of a computation that may fail or yield a value of type A

type Option<A> =
  | { type: 'None' } // represents a failure
  | { type: 'Some'; value: A } // represents a success

Constructors and pattern matching:

// a nullary constructor can be implemented as a constant
const none: Option<never> = { type: 'None' }

const some = <A>(value: A): Option<A> => ({ type: 'Some', value })

const fold = <A, R>(fa: Option<A>, onNone: () => R, onSome: (a: A) => R): R =>
  fa.type === 'None' ? onNone() : onSome(fa.value)

The Option type can be used to avoid throwing exceptions and/or to represent optional values, so we can go from...

//                this is a lie ↓
const head = <A>(as: Array<A>): A => {
  if (as.length === 0) {
    throw new Error('Empty array')
  }
  return as[0]
}

let s: string
try {
  s = String(head([]))
} catch (e) {
  s = e.message
}

...where the type system is unaware of possible failures, to...

//                              ↓ the type system "knows" that this computation may fail
const head = <A>(as: Array<A>): Option<A> => {
  return as.length === 0 ? none : some(as[0])
}

const s = fold(head([]), () => 'Empty array', a => String(a))

...where the possibility of failures is lifted to the type system.

The `Either` type

A common use of Either is as an alternative to Option for dealing with possible missing values. In this usage, None is replaced with a Left which can contain useful information. Right takes the place of Some. Convention dictates that Left is used for failure and Right is used for success.

type Either<L, A> =
  | { type: 'Left'; left: L } // represents a failure
  | { type: 'Right'; right: A } // represents a success

Constructors and pattern matching:

const left = <L, A>(left: L): Either<L, A> => ({ type: 'Left', left })

const right = <L, A>(right: A): Either<L, A> => ({ type: 'Right', right })

const fold = <L, A, R>(
  fa: Either<L, A>,
  onLeft: (left: L) => R,
  onRight: (right: A) => R
): R => (fa.type === 'Left' ? onLeft(fa.left) : onRight(fa.right))

Getting back to our callback example

declare function readFile(
  path: string,
  callback: (err?: Error, data?: string) => void
): void

readFile('./myfile', (err, data) => {
  let message: string
  if (err !== undefined) {
    message = `Error: ${err.message}`
  } else if (data !== undefined) {
    message = `Data: ${data.trim()}`
  } else {
    // should never happen
    message = 'The impossible happened'
  }
  console.log(message)
})

we can change its signature to

declare function readFile(
  path: string,
  callback: (result: Either<Error, string>) => void
): void

and then consume the API like this

readFile('./myfile', e => {
  const message = fold(e, err => `Error: ${err.message}`, data => `Data: ${data.trim()}`)
  console.log(message)
})

Conclusion

In this post we've seen product types and sum types, and how reasoning in terms of the number of states they represent can greatly affect the design of our domain models.

A common pitfall of many real-world APIs is to misuse product types that, in addition to all the legal states, also model many illegal ones.

Sum types are an incredibly useful and fundamental language feature, they are the key to design excellent domain models by allowing to make illegal states irrepresentable.

Functional design: TDD in TypeScript (aka abusing `declare`)

Giulio Canti — Mon, 18 Mar 2019 08:48:57 +0000

Type driven development (TDD) is a technique used to split a problem into a set of smaller problems, letting the type checker suggest the concrete implementation, or at least helping us getting there. Here's a practical example.

Say for instance that we like to reimplement the function Promise.all, we'll name it sequence. Let's start with its signature

// TODO
declare function sequence<T>(promises: Array<Promise<T>>): Promise<Array<T>>

Notice that a declared function, even if not implemented yet, is immediately available and can concur to type check the rest of our code. If we are running a build system though, we'll get an error because there's no such function at runtime, it only exists in the "world of types" for now.

However, the goal of this technique is working in the editor for as long as possible without the need to run our code. We'll rely entirely on the type checker making sure it doesn't raise any errors as we go through.

Back to our problem, we need to transform (or "reduce") an array of values of type A to a value of type B.

The transformation we're looking for is likely reduce, which in fact has the following signature

declare function reduce<A, B>(this: Array<A>, f: (acc: B, x: A) => B, init: B): B

We don't know how to implement neither f nor init yet, but we can skip the concrete implementation as we did before. For now it's enough to simply declare the missing bits and replace the type parameters A and B with the corresponding types we're working with:

A = Promise<T>

B = Promise<Array<T>>

This is what we get

// TODO
declare function pushPromise<T>(acc: Promise<Array<T>>, x: Promise<T>): Promise<Array<T>>

// TODO
function sequence<T>(promises: Array<Promise<T>>): Promise<Array<T>> {
  declare const init: Promise<Array<T>> // TypeScript error
  return promises.reduce(pushPromise, init)
}

Alas declare can't be used inside a function body so we need a temporary workaround

declare const TODO: any

// TODO
declare function pushPromise<T>(acc: Promise<Array<T>>, x: Promise<T>): Promise<Array<T>>

// partially implemented
function sequence<T>(promises: Array<Promise<T>>): Promise<Array<T>> {
  const init: Promise<Array<T>> = TODO
  return promises.reduce(pushPromise, init)
}

Now init is straightforward, we can put an empty array into the Promise "container"

const init: Promise<Array<T>> = Promise.resolve([])

Implementing pushPromise is more complicated, we know how to concat a value of type Array<T> with a value of type T to get another value of type Array<T>, let's name it push

declare function push<T>(x: Array<T>, y: T): Array<T>

but how do we concat acc and x in pushPromise given that they are both promises?

What we'd like to have is a procedure, let's name it liftA2, which can "lift" the function push producing a new function which can work on the values "inside" the promises. Again we just declare the expected result without any implementation

// TODO
declare function liftA2<A, B, C>(
  f: (a: A, b: B) => C
): (fa: Promise<A>, fb: Promise<B>) => Promise<C>

// TODO
declare function push<T>(x: Array<T>, y: T): Array<T>

// implemented
function pushPromise<T>(acc: Promise<Array<T>>, x: Promise<T>): Promise<Array<T>> {
  return liftA2<Array<T>, T, Array<T>>(push)(acc, x)
}

// implemented
function sequence<T>(promises: Array<Promise<T>>): Promise<Array<T>> {
  const init: Promise<Array<T>> = Promise.resolve([])
  return promises.reduce(pushPromise, init)
}

Now we only need to implement liftA2 and push

function liftA2<A, B, C>(
  f: (a: A, b: B) => C
): (fa: Promise<A>, fb: Promise<B>) => Promise<C> {
  return (a, b) => a.then(aa => b.then(bb => f(aa, bb)))
}

function push<T>(x: Array<T>, y: T): Array<T> {
  return x.concat([y])
}

function pushPromise<T>(acc: Promise<Array<T>>, x: Promise<T>): Promise<Array<T>> {
  return liftA2<Array<T>, T, Array<T>>(push)(acc, x)
}

function sequence<T>(promises: Array<Promise<T>>): Promise<Array<T>> {
  const init: Promise<Array<T>> = Promise.resolve([])
  return promises.reduce(pushPromise, init)
}

Let's try it out

sequence([]).then(x => console.log(x)) // []
sequence([Promise.resolve(1), Promise.resolve(2), Promise.resolve(3)]).then(x =>
  console.log(x)
) // [1, 2, 3]

As you can see a strong type system can not only prevent errors, but also guide you and provide feedback in your design process.

Introduction to property based testing

Giulio Canti — Sun, 17 Mar 2019 11:25:49 +0000

In the last posts about Eq, Ord, Semigroup and Monoid we saw that instances must comply with some laws.

So how can we ensure that our instances are lawful?

Property based testing

Property based testing is another way to test your code which is complementary to classical unit-test methods.

It tries to discover inputs causing a property to be falsy by testing it against multiple generated random entries. In case of failure, a property based testing framework provides both a counterexample and the seed causing the generation.

Let's apply property based testing to the Semigroup law:

Associativity : concat(concat(x, y), z) = concat(x, concat(y, z))

I'm going to use fast-check, a property based testing framework written in TypeScript.

Testing a `Semigroup` instance

We need three ingredients

a Semigroup<A> instance for the type A
a property that encodes the associativity law
a way to generate random values of type A

Instance

As instance I'm going to use the following

import { Semigroup } from 'fp-ts/Semigroup'

const S: Semigroup<string> = {
  concat: (x, y) => x + ' ' + y
}

Property

A property is just a predicate, i.e a function that returns a boolean. We say that the property holds if the predicate returns true.

So in our case we can define the associativity property as

const associativity = (x: string, y: string, z: string) =>
  S.concat(S.concat(x, y), z) === S.concat(x, S.concat(y, z))

`Arbitrary<A>`

An Arbitrary<A> is responsible to generate random values of type A. We need an Arbitrary<string>, fortunately fast-check provides many built-in arbitraries

import * as fc from 'fast-check'

const arb: fc.Arbitrary<string> = fc.string()

Let's wrap all together

it('my semigroup instance should be lawful', () => {
  fc.assert(fc.property(arb, arb, arb, associativity))
})

If fast-check doesn't raise any error we can be more confident that our instance is well defined.

Testing a `Monoid` instance

Let's see what happens when an instance is lawless!

As instance I'm going to use the following

import { Monoid } from 'fp-ts/Monoid'

const M: Monoid<string> = {
  ...S,
  empty: ''
}

We must encode the Monoid laws as properties:

Right identity : concat(x, empty) = x
Left identity : concat(empty, x) = x

const rightIdentity = (x: string) => M.concat(x, M.empty) === x

const leftIdentity = (x: string) => M.concat(M.empty, x) === x

and finally write a test

it('my monoid instance should be lawful', () => {
  fc.assert(fc.property(arb, rightIdentity))
  fc.assert(fc.property(arb, leftIdentity))
})

When we run the test we get

Error: Property failed after 1 tests
{ seed: -2056884750, path: "0:0", endOnFailure: true }
Counterexample: [""]

That's great, fast-check even gives us a counterexample: ""

M.concat('', M.empty) = ' ' // should be ''

Resources

For a library that makes easy to test type classes laws, check out fp-ts-laws

Getting started with fp-ts: Monoid

Giulio Canti — Sat, 16 Mar 2019 13:51:30 +0000

In the last post we saw that a Semigroup captures the concept of "merging" values (via concat). A Monoid is any Semigroup that happens to have a special value which is "neutral" with respect to concat.

Type class definition

As usual in fp-ts the type class Monoid, contained in the fp-ts/Monoid module, is implemented as a TypeScript interface, where the neutral value is named empty

import { Semigroup } from 'fp-ts/Semigroup'

interface Monoid<A> extends Semigroup<A> {
  readonly empty: A
}

The following laws must hold

Right identity: concat(x, empty) = x, for all x in A
Left identity: concat(empty, x) = x, for all x in A

Whichever side of concat we put the value empty, it must make no difference to the value.

Note. If an empty value exists then is unique.

Instances

Most of the semigroups we saw in the previous post are actually monoids

/** number `Monoid` under addition */
const monoidSum: Monoid<number> = {
  concat: (x, y) => x + y,
  empty: 0
}

/** number `Monoid` under multiplication */
const monoidProduct: Monoid<number> = {
  concat: (x, y) => x * y,
  empty: 1
}

const monoidString: Monoid<string> = {
  concat: (x, y) => x + y,
  empty: ''
}

/** boolean monoid under conjunction */
const monoidAll: Monoid<boolean> = {
  concat: (x, y) => x && y,
  empty: true
}

/** boolean monoid under disjunction */
const monoidAny: Monoid<boolean> = {
  concat: (x, y) => x || y,
  empty: false
}

You may wonder if all semigroups are also monoids. That's not the case, as a counterexample consider the following semigroup

const semigroupSpace: Semigroup<string> = {
  concat: (x, y) => x + ' ' + y
}

We can't find an empty value such that concat(x, empty) = x.

Let's write some Monoid instances for more complex types. We can build a Monoid instance for a struct like Point

type Point = {
  x: number
  y: number
}

if we can provide a Monoid instance for each field

import { getStructMonoid } from 'fp-ts/Monoid'

const monoidPoint: Monoid<Point> = getStructMonoid({
  x: monoidSum,
  y: monoidSum
})

We can go on and feed getStructMonoid with the instance just defined

type Vector = {
  from: Point
  to: Point
}

const monoidVector: Monoid<Vector> = getStructMonoid({
  from: monoidPoint,
  to: monoidPoint
})

Folding

When using a monoid instead of a semigroup, folding is even simpler: we don't need to explicitly provide an initial value (the implementation can use the monoid's empty value for that)

import { fold } from 'fp-ts/Monoid'

fold(monoidSum)([1, 2, 3, 4]) // 10
fold(monoidProduct)([1, 2, 3, 4]) // 24
fold(monoidString)(['a', 'b', 'c']) // 'abc'
fold(monoidAll)([true, false, true]) // false
fold(monoidAny)([true, false, true]) // true

Monoids for type constructors

We already know that given a semigroup instance for A we can derive a semigroup instance for Option<A>.

If we can find a monoid instance for A then we can derive a monoid instance for Option<A> (via getApplyMonoid) which works like this

x	y	concat(x, y)
none	none	none
some(a)	none	none
none	some(a)	none
some(a)	some(b)	some(concat(a, b))

import { getApplyMonoid, some, none } from 'fp-ts/Option'

const M = getApplyMonoid(monoidSum)

M.concat(some(1), none) // none
M.concat(some(1), some(2)) // some(3)
M.concat(some(1), M.empty) // some(1)

We can derive two other monoids for Option<A> (for all A)

1) getFirstMonoid...

Monoid returning the left-most non-None value

x	y	concat(x, y)
none	none	none
some(a)	none	some(a)
none	some(a)	some(a)
some(a)	some(b)	some(a)

import { getFirstMonoid, some, none } from 'fp-ts/Option'

const M = getFirstMonoid<number>()

M.concat(some(1), none) // some(1)
M.concat(some(1), some(2)) // some(1)

2) ...and its dual: getLastMonoid

Monoid returning the right-most non-None value

x	y	concat(x, y)
none	none	none
some(a)	none	some(a)
none	some(a)	some(a)
some(a)	some(b)	some(b)

import { getLastMonoid, some, none } from 'fp-ts/Option'

const M = getLastMonoid<number>()

M.concat(some(1), none) // some(1)
M.concat(some(1), some(2)) // some(2)

As an example, getLastMonoid can be useful for managing optional values

import { Monoid, getStructMonoid } from 'fp-ts/Monoid'
import { Option, some, none, getLastMonoid } from 'fp-ts/Option'

/** VSCode settings */
interface Settings {
  /** Controls the font family */
  fontFamily: Option<string>
  /** Controls the font size in pixels */
  fontSize: Option<number>
  /** Limit the width of the minimap to render at most a certain number of columns. */
  maxColumn: Option<number>
}

const monoidSettings: Monoid<Settings> = getStructMonoid({
  fontFamily: getLastMonoid<string>(),
  fontSize: getLastMonoid<number>(),
  maxColumn: getLastMonoid<number>()
})

const workspaceSettings: Settings = {
  fontFamily: some('Courier'),
  fontSize: none,
  maxColumn: some(80)
}

const userSettings: Settings = {
  fontFamily: some('Fira Code'),
  fontSize: some(12),
  maxColumn: none
}

/** userSettings overrides workspaceSettings */
monoidSettings.concat(workspaceSettings, userSettings)
/*
{ fontFamily: some("Fira Code"),
  fontSize: some(12),
  maxColumn: some(80) }
*/

Next post Introduction to property based testing

Forem: Giulio Canti

Getting started with fp-ts: Reader

Example

Reader

ask

Type holes in TypeScript

What's a type hole?

A first example

The second example

Getting started with fp-ts: IO

Error handling

Lifting

Getting started with fp-ts: Monad

The problem: nested contexts

Definition

Ok but... why?

The Kleisli category

In which we build the composition step by step

The laws

Monads in fp-ts

Conclusion

Getting started with fp-ts: Either vs Validation

The problem

Either

Validation

Appendix

Getting started with fp-ts: Applicative

Currying

Apply

Applicative

Lifting

Is the general problem solved?

Getting started with fp-ts: Functor

Functions as programs

In which the constraint B = F<C> leads to functors

Functors

Definition

Functors in fp-ts

Is the general problem solved?

Getting started with fp-ts: Category

Categories

Part I (Definition)

Part II (Composition)

Categories as programming languages

A category for TypeScript

The central problem with composition

Functional design: Algebraic Data Types

What is an ADT?

Product types

Why "product" types?

When should I use a product type?

Sum types

Constructors

Pattern matching

Why "sum" types?

When should I use a sum type?

Functional error handling

The Option type

The Either type

Conclusion

Functional design: TDD in TypeScript (aka abusing `declare`)

Introduction to property based testing

Property based testing

Testing a Semigroup instance

Instance

Property

Arbitrary<A>

Testing a Monoid instance

Resources

Getting started with fp-ts: Monoid

Type class definition

Instances

Folding

Monoids for type constructors

`Reader`

`ask`

Monads in `fp-ts`

In which the constraint `B = F<C>` leads to functors

Functors in `fp-ts`

The `Option` type

The `Either` type

Testing a `Semigroup` instance

`Arbitrary<A>`

Testing a `Monoid` instance