Pattern matching / catamorphism (unions)

[gcanti]

import * as t from 'io-ts'

type Match<RT extends t.Any, R> = (value: t.TypeOf<RT>) => R
type Clause<RT extends t.Any, R> = [RT, Match<RT, R>]

export function match<A extends t.Any, B extends t.Any, R>(value: t.TypeOf<A> | t.TypeOf<B>, clauses: [Clause<A, R>, Clause<B, R>]): R
export function match<A extends t.Any, B extends t.Any, C extends t.Any, R>(value: t.TypeOf<A> | t.TypeOf<B> | t.TypeOf<C>, clauses: [Clause<A, R>, Clause<B, R>, Clause<C, R>]): R
// more overloadings here...
export function match<R>(value: any, clauses: Array<Clause<t.Any, R>>): R {
  for (let i = 0, len = clauses.length; i < len; i++) {
    const [type, match]: [t.Any, Match<t.Any, R>] = clauses[i]
    if (type.is(value)) {
      return match(value)
    }
  }
  throw new Error('No match')
}

// arguments types are inferred correctly
const x = match('hello', [ // value: string | number
  [t.string, s => s.length], // s: string
  [t.number, n => n] // n: number
])

const y = match(2, [
  [t.string, s => s.length],
  [t.number, n => n]
])

console.log(x) // => 5
console.log(y) // => 2

const z = match(true, [ // <= error Argument of type 'true' is not assignable to parameter of type 'string | number'
  [t.string, s => s.length],
  [t.number, n => n]
])

[pelotom]

This is a great idea! Some initial thoughts:

• You could consider currying match so that you can define a function in one place:

  const f = match([
  [t.string, s => s.length],
  [t.number, n => n]
  ])

  and then use it separately:

  f(2)

  I'm not even sure I like this idea, I think it would be very common to want to use it the way you have in your examples, but I'm curious what you think.

• You could also consider getting rid of the need to wrap the variants in a list:

  match(2,
  [t.string, s => s.length],
  [t.number, n => n]
  )

  and even the Clause tuples could be done away with in the interest of prettifying the syntax:

  match(2,
  t.string, s => s.length,
  t.number, n => n
  )

  Again, I'm not sure this would actually be an improvement; for one thing it seems likely to give worse error messages if you're missing half of a clause.

• There's some overlap here with the notion of unions. It looks like io-ts currently doesn't have differentiated subtypes of Type<A>, but if I was adding this to runtypes I'd probably add a variant of match to the UnionN interfaces, so that you could say:

  const StringOrNumber = Union(string, number)
  StringOrNumber.match(2,
  s => s.length,
  n => n
  )

  Now this is putting me in mind of catamorphisms, and I wonder if it would be useful for every runtime type to have a fold() method that lets you define a (possibly recursive) function over it! But now I'm wandering far afield, so I'll stop :)

[gcanti]

Hi, thanks for chime in!

I'm not even sure I like this idea, I think it would be very common to want to use it the way you have in your examples, but I'm curious what you think

Yeah, I thought about currying too though every example I ever seen in other languages are like this

// scala
match x {
  case ... => ...
  case ... => ...
}

You could also consider getting rid of the need to wrap the variants in a list

Good suggestion, here's an amended version

type Match<RT extends t.Any, R> = (value: t.TypeOf<RT>) => R
type Clause<RT extends t.Any, R> = [RT, Match<RT, R>]

export function match<A extends t.Any, B extends t.Any, R>(value: t.TypeOf<A> | t.TypeOf<B>, c1: Clause<A, R>, c2: Clause<B, R>): R
export function match<A extends t.Any, B extends t.Any, C extends t.Any, R>(value: t.TypeOf<A> | t.TypeOf<B> | t.TypeOf<C>, c1: Clause<A, R>, c2: Clause<B, R>, c3: Clause<C, R>): R
// more overloadings here...
export function match<R>(value: any, ...clauses: Array<Clause<t.Any, R>>): R {
  for (let i = 0, len = clauses.length; i < len; i++) {
    const [type, match]: [t.Any, Match<t.Any, R>] = clauses[i]
    if (type.is(value)) {
      return match(value)
    }
  }
  throw new Error('No match')
}

// arguments types are inferred correctly
const x = match('hello',  // value: string | number
  [t.string, s => s.length], // s: string
  [t.number, n => n] // n: number
)

const y = match(2,
  [t.string, s => s.length],
  [t.number, n => n]
)

console.log(x) // => 5
console.log(y) // => 2

const z = match(true,  // <= error Argument of type 'true' is not assignable to parameter of type 'string | number'
  [t.string, s => s.length],
  [t.number, n => n]
)

and even the Clause tuples could be done away with in the interest of prettifying the syntax

Again nice suggestion

type Match<RT extends t.Any, R> = (value: t.TypeOf<RT>) => R

export function match<A extends t.Any, B extends t.Any, R>(value: t.TypeOf<A> | t.TypeOf<B>, t1: A, m1: Match<A, R>, t2: B, m2: Match<B, R>): R
export function match<A extends t.Any, B extends t.Any, C extends t.Any, R>(value: t.TypeOf<A> | t.TypeOf<B>, t1: A, m1: Match<A, R>, t2: B, m2: Match<B, R>, t3: C, m3: Match<C, R>): R
// more overloadings here...
export function match<R>(value: any, ...clauses: Array<any>): R {
  for (let i = 0, len = clauses.length; i < len; i = i + 2) {
    const type: t.Any = clauses[i]
    const match: Match<t.Any, R> = clauses[i + 1]
    if (type.is(value)) {
      return match(value)
    }
  }
  throw new Error('No match')
}

// arguments types are inferred correctly
const x = match('hello',  // value: string | number
  t.string, s => s.length, // s: string
  t.number, n => n // n: number
)

const y = match(2,
  t.string, s => s.length,
  t.number, n => n
)

console.log(x) // => 5
console.log(y) // => 2

const z = match(true,  // <= error Argument of type 'true' is not assignable to parameter of type 'string | number'
  t.string, s => s.length,
  t.number, n => n
)

though you are right

it seems likely to give worse error messages if you're missing half of a clause

Missing a portion of a clause gives the obtuse message "Supplied parameters do not match any signature of call target"

Now this is putting me in mind of catamorphisms

Ahh.. another great idea :)

export type Match<RT extends Any, R> = (a: TypeOf<RT>) => R

export class UnionType<RTS extends Array<Any>, U> extends Type<U> {
  constructor(name: string, validate: Validate<U>, public readonly types: RTS) {
    super(name, validate)
  }
  // more overloadings here...
  fold<R>(value: U, m1: Match<RTS[0], R>, m2: Match<RTS[1], R>): R
  fold<R>(value: U, m1: Match<RTS[0], R>, m2: Match<RTS[1], R>, m3: Match<RTS[2], R>): R
Match<RTS[2], R>) => R): R
  fold<R>(value: U, ...matches: Array<Function>): R {
    for (let i = 0, len = matches.length; i < len; i++) {
      const type = this.types[i]
      const match = matches[i]
      if (type.is(value)) {
        return match(value)
      }
    }
    throw new Error('No match')
  }
}

console.log(t.union([t.string, t.number]).fold('hello', s => s.length, n => n)) // => 5
console.log(t.union([t.string, t.number]).fold(true, s => s.length, n => n)) // => error Argument of type 'true' is not assignable to parameter of type 'string | number'

[pelotom]

Looks good!

[pelotom]

WRT currying, I think it might come in handy a lot when using higher-order functions, e.g.

const stringOrNum = t.union(t.string, t.number)
[3, 'foo', 42, 'hello'].map(stringOrNum.fold(s => s.length, n => n)) // [3, 3, 42, 5]

[gcanti]

WRT currying, I think it might come in handy a lot when using higher-order functions

Yep, is handy. Amended version of fold

export type Match<RT extends Any, R> = (a: TypeOf<RT>) => R

export class UnionType<RTS extends Array<Any>, U> extends Type<U> {
  constructor(name: string, validate: Validate<U>, public readonly types: RTS) {
    super(name, validate)
  }
  // more overloadings here...
  fold<R>(m1: Match<RTS[0], R>, m2: Match<RTS[1], R>): (value: U) => R
  fold<R>(m1: Match<RTS[0], R>, m2: Match<RTS[1], R>, m3: Match<RTS[2], R>): (value: U) => R
  fold<R>(...matches: Array<Function>): (value: U) => R {
    return value => {
      for (let i = 0, len = matches.length; i < len; i++) {
        const type = this.types[i]
        const match = matches[i]
        if (type.is(value)) {
          return match(value)
        }
      }
      throw new Error('No match')
    }
  }
}

const stringOrNum = t.union([t.string, t.number])

// inferred number
const n = stringOrNum
  .fold(
    s => s.length,
    n => n
  )('hello')

// inferred Array<number>
const arr = [3, 'foo', 42, 'hello'].map(stringOrNum.fold(s => s.length, n => n)) // [3, 3, 42, 5]

[gcanti]

Better example

// inferred (value: string | number) => number
const f = t.union([t.string, t.number])
  .fold(
    s => s.length,
    n => n
  )

// inferred number
const n = f('hello') // 5

// inferred Array<number>
const arr = [3, 'foo', 42, 'hello'].map(f) // [3, 3, 42, 5]

[Xananax]

I don't know if you've heard of https://github.com/paldepind/union-type, but might be interesting to check, as it attempts to solve the same problem space.

[gcanti]

I don't know if you've heard of https://github.com/paldepind/union-type

Yes, thanks @Xananax (union-type is untyped though)

[Xananax]

Indeed! I was actually referring to the API choices, which I think are really hard, since there isn't an idiomatic JS way. There's always the hard choice of making it simple, making it closer to haskell/idiomatic fp, or making it look like "regular" js. As well as dealing with performance considerations, keeping it flexible enough yet not too much, etc.

I personally always find this a very hard part and it eats most of my time, and it is always a relief to find other people having already tackled this, if only to be certain I don't like how they're doing it. Might be just me though :)

[gcanti]

I personally always find this a very hard part and it eats most of my time

I agree, I just wanted to point out that with a typed language API choices are sometimes driven by different concerns: for example personally I'm inclined to sacrifice ergonomics in favour of type safety (if I am "into a corner").

Another example: with a good API and a typed language some issues are just absent (see 51 and 52 in union-type)

Anyway issues are a great source of suggestions and considerations, so thanks again for pointing out

[gcanti]

https://github.com/gcanti/io-ts/pull/30

[mmkal]

@gcanti might the match function make it into io-ts?

[gcanti]

@mmkal see the discussion here https://github.com/gcanti/io-ts/pull/183