Is Typescript capable of doing simple function composition?

Question

Is Typescript capable of doing simple function composition? I wrote out the following basic implementations for compose, map, and filter to test.

The types and functions are set up below and then the implementation after.

The javascript seems to be fine, but typescript is showing false positives when compose is used. Specifically, it seems to understand what the first function is going to return, but then it does not transfer that information to the input of the second function. Explained further below after set up.

import { curry } from './curry'

type f1<a, b> = (a: a) => b
type f2_2<a, b, c> = (a: a, b: b) => c
type f2_1<a, b, c> = (a: a) => (b: b) => c
type f2<a, b, c> = f2_2<a, b, c> & f2_1<a, b, c>
type p<a> = (a: a) => boolean

//====[compose]================================
type b3 = <a, b, c>(f: f1<b, c>, g: f1<a, b>, a: a) => c
type b2 = <a, b, c>(f: f1<b, c>, g: f1<a, b>) => f1<a, c>
type b1 = <a, b, c>(f: f1<b, c>) => f2<f1<a, b>, a, c>
type b = b1 & b2 & b3

// bluebird :: (b -> c) -> (a -> b) -> a -> c
const compose: b = curry((f, g, a) => f(g(a)))

//====[filter]=================================
type fil2 = <a>(p: p<a>, xs: a[]) => a[]
type fil1 = <a>(p: p<a>) => f1<a[], a[]>
type fil = fil1 & fil2

// filter :: (a -> Boolean) -> [a] -> [a]
const filter: fil = curry((p, xs) => {
  const len = xs.length
  const r = Array()

  for (let [i, j] = [0, 0]; i < len; i++) {
    const v = xs[i]

    if (p(v)) {
      r[j++] = v
    }
  }

  return r
})

//====[mapArr]=================================
type m2 = <a, b>(f1: f1<a, b>, xs: a[]) => b[]
type m1 = <a, b>(f: f1<a, b>) => f1<a[], b[]>
type m = m2 & m1

// map :: (a -> b) -> [a] -> [b]
const mapArr: m = curry((fn, xs) => {
  const len = xs.length
  const r = Array(len)

  for (let i = 0; i < len; i++) {
    r[i] = fn(xs[i])
  }

  return r
})

//====[prop]===================================
type z2 = <o, k extends keyof o>(propName: k, source: o) => o[k]
type z1 = <o, k extends keyof o>(propName: k) => f1<o, o[k]>
type z = z2 & z1

// prop :: String -> a -> b
// prop :: Number -> a -> b
// prop :: Symbol -> a -> b
const prop: z = curry((propName, obj) => obj[propName])

When I hover over the filter function from the composition below, TS understands that it will return data[]; however, if I hover over the mappArr function, TS is showing that the input is unknown[] and so it throws a false positive for the id field. What am I doing wrong?

//====[typescript test]===================================
interface data {
  relationId: string
  id: string
}

type isMine = p<data>
// isMine :: a -> Boolean
const isMine: isMine = x => x.relationId === '1'

type t = f1<data[], string[]>
const testFn: t = compose(
  // @ts-ignore
  mapArr(prop('id')),
  //=>       ^^^^^
  // error TS2345: Argument of type '"id"' is not assignable to
  // parameter of type 'never'.
  filter(isMine)
)

//====[javascript test]================================
const r = testFn([
  { id: '3', relationId: '1' },
  { id: '5', relationId: '3' },
  { id: '8', relationId: '1' },
])

test('javascript is correct', () => {
  expect(r).toEqual(['3', '8'])
})

Typescript's false positives get worse when I call compose with the arguments curried.

const testFn: t = compose (mapArr(prop('id')))
                          (filter(isMine))
//=>                      ^^^^^^^^^^^^^^^
// error TS2322: Type 'unknown[]' is not assignable to type 'f1<data[], string[]>'.
// Type 'unknown[]' provides no match for the signature '(a: data[]): string[]'.

//=====================================================================

@shanonjackson wanted to see the curry function. I'm almost positive that it could not be the source of any issue as the types for each of the above functions are applied to the result of the curry function as opposed to having them passed through, which seems impossible.

Again, it should not be necessary to review the following, which is just a standard implementation of curry:

function isFunction (fn) {
  return typeof fn === 'function'
}

const CURRY_SYMB = '@@curried'

function applyCurry (fn, arg) {
  if (!isFunction(fn)) {
    return fn
  }

  return fn.length > 1
    ? fn.bind(null, arg)
    : fn.call(null, arg)
}

export function curry (fn) {
  if (fn[CURRY_SYMB]) {
    return fn
  }

  function curried (...xs) {
    const args = xs.length
      ? xs
      : [undefined]

    if (args.length < fn.length) {
      return curry(Function.bind.apply(fn, [null].concat(args)))
    }

    const val =
      args.length === fn.length
        ? fn.apply(null, args)
        : args.reduce(applyCurry, fn)

    if (isFunction(val)) {
      return curry(val)
    }

    return val
  }

  Object.defineProperty(curried, CURRY_SYMB, {
    enumerable: false,
    writable: false,
    value: true,
  })

  return curried
}

Answer 1

No matter how much I might wish it were otherwise, TypeScript isn't Haskell (or insert-your-favorite-typed-language-here). Its type system has a lot of holes, and its type inference algorithms aren't guaranteed to yield sound results. It's not meant to be provably correct (enabling idiomatic JavaScript is more important). To be fair to TypeScript, Haskell doesn't have subtyping, and type inference in the face of subtyping is more difficult. Anyway, the short answer here is:

• Don't try to rely on contextual typing (inferring types from function outputs)
• Try to rely on forward type inference (inferring types from function inputs)
• When type inference fails, annotate and specify types.

---

Since TypeScript isn't Haskell the first thing I'm going to do is use TypeScript naming conventions. Also, because the implementations of compose() and the rest aren't the issue, I will just declare those functions and leave the implementation out.

Let's take a look:

type Predicate<A> = (a: A) => boolean;

//====[compose]===============================
declare function compose<B, C>(
  f: (x: B) => C
): (<A>(g: (a: A) => B) => (a: A) => C) & (<A>(g: (a: A) => B, a: A) => C); //altered
declare function compose<A, B, C>(f: (b: B) => C, g: (a: A) => B): (a: A) => C;
declare function compose<A, B, C>(f: (b: B) => C, g: (a: A) => B, a: A): C;

//====[filter]=================================
declare function filter<A>(p: Predicate<A>, xs: A[]): A[];
declare function filter<A>(p: Predicate<A>): (xs: A[]) => A[];

//====[mapArr]=================================
declare function mapArr<A, B>(f1: (a: A) => B): (xs: A[]) => B[];
declare function mapArr<A, B>(f1: (a: A) => B, xs: A[]): B[];

//====[prop]===================================
declare function prop<K extends keyof any>(
  propName: K
): <O extends Record<K, any>>(source: O) => O[K]; // altered
declare function prop<K extends keyof O, O>(propName: K, source: O): O[K];

---

Most of that is just a straight rewriting, but I'd like to draw your attention to two substantive alterations I've made. The first overload signature to compose() has been changed from

declare function compose<A, B, C>(
  f: (x: B) => C
): ((g: (a: A) => B) => (a: A) => C) & ((g: (a: A) => B, a: A) => C);

to

declare function compose<B, C>(
  f: (x: B) => C
): (<A>(g: (a: A) => B) => (a: A) => C) & (<A>(g: (a: A) => B, a: A) => C); 

That is, instead of compose() being generic in A, B, and C, it is only generic in B and C and returns a function generic in A. I've done this because in TypeScript, inference of generic function type parameters usually happens based on the types of the passed-in arguments to a function, and not to the expected return type of the function. Yes, there is contextual typing that can infer input types from required output types, but it's not as reliable as the normal "forward-in-time" inference.

What is likely to happen when you call a function generic in A when none of its parameters serve as inference sites for A? (e.g., when it only has one parameter of type (x: B) => C) The compiler will infer unknown (as of TS3.5) for A, and you will be unhappy later. By deferring the generic parameter specification until the returned function is called, we have a better chance of inferring A the way you intend.

---

Similarly, I've changed the first overload of prop() from

declare function prop<K extends keyof O, O>(
  propName: K, 
): (source: O) => O[K];

to

declare function prop<K extends keyof any>(
  propName: K
): <O extends Record<K, any>>(source: O) => O[K];

This has the same issue... the call to something like prop("id") would cause K to be inferred as "id", and O will likely be inferred as unknown, and then since "id" is not known to be part of keyof unknown (which is never), you will get an error. This is likely what happened to cause the error you're seeing.

Anyway, I've deferred the specification of O to when the returned function is called. This means I needed to reverse the generic constraints from K extends keyof O to O extends Record<K, any>... saying similar things but from opposite directions.

---

Fine, so what happens if we try your compose() test?

//====[typescript test]===================================
interface Data {
  relationId: string;
  id: string;
}
type isMine = Predicate<Data>;
const isMine: isMine = x => x.relationId === "1";

const testFnWithFaultyContextualTyping: (a: Data[]) => string[] = compose(
  mapArr(prop("id")), // error!
  filter(isMine)
);
// Argument of type '<O extends Record<"id", any>>(source: O) => O["id"]' 
// is not assignable to parameter of type '(a: unknown) => any'.

Oops, there's still an error there. It's a different error, but the issue here is that by annotating your return value as (a: Data[]) => string[], it has triggered some contextual typing that peters out before prop("id") is inferred properly. In this case my instinct is to try not to rely on contextual typing and instead see if regular type inference works:

const testFn = compose(
  mapArr(prop("id")),
  filter(isMine)
); // okay
// const testFn: (a: Data[]) => string[]

So that works. The forward-in-time inference behaves as intended, and testFn is the type you expect it to be.

---

If we try your curried version:

const testFnCurriedWithFaultyContextualTyping = compose(mapArr(prop("id")))( // error!
  filter(isMine)
); 
// Argument of type '<O extends Record<"id", any>>(xs: O[]) => O["id"][]' 
// is not assignable to parameter of type '(x: unknown) => any[]'.

Yes, we still get an error. This is again a problem with trying to do contextual typing... the compiler just does not really know how to infer the types for the argument to compose() given how you intend to call its returned function. In this case there's no way to fix it with moving generic types around. Inference just can't happen here. Instead, we can fall back on explicitly specifying the generic type parameters in the compose() function call:

const testFnCurried = compose<Data[], string[]>(mapArr(prop("id")))(
  filter(isMine)
); // okay

That works.

---

Anyway, I hope that gives you some ideas how to proceed, despite possibly being disappointing. Whenever I feel sad about the unsoundness and limited type inference capabilities of TypeScript, I remind myself about all its type system's neat features that make up for it, at least in my opinion.

Anyway, good luck!

Link to code