Generic Functional Programming with TypeScript

… or “FP to the Max with TypeScript”.

Inspired by amazing FP to the Max video by John A De Goes here I’m going to replicate the result John obtained using TypeScript and try get as close as possible to build a simple game application using generic functional programming style.

Challenges

First, there are some challenges to solve before we can start. Scala has a richer type system and in the example there are some parts of the puzzle missing in the TypeScript:

Generic higher kinded types: Ex[F[_]] (http://adriaanm.github.io/files/higher.pdf)
Implicits or Extension functions - which allows to enrich data types with new functionality from outside
for comprehension syntax

Generic higher kinded types

Unfortunately TypeScript doesn’t support higher kinded types natively yet, but meanwhile the community seems to converge to use it’s lightweight implementation:

For example a Functor type class will looks like this:

import { HK } from "funland"

export interface Functor<_URI> {
  map<A, B>(f: (a: A) => B, fa: HK<_URI, A>): HK<_URI, B>
}

HK<_URI, _> here is equivalent to F[_] in scala, where _URI type parameter is used to identify type F.

One drawback of this construct is that you can’t easily go back to concrete type when needed, but going concrete sounds like an implementation detail and will look how to workaround it later.

So let’s call challenge #1 - solved.

Implicits

Scalas implicits allows its users to achieve nicer syntax for their DSLs by adding extra functionality to existing data types (adhoc polymorphism), similar to extension methods from kotlin, swift, or you can bring dependent data (ex. type classes) into your local context without passing them explicitly.

For TypeScript I’m not aware of any functionality that can help us build similar functionality, so we will pass our type classes explicitly through function arguments.

`for` comprehension syntax

Not much here also so will use a helper function to chain operations sequence.

The App

Our goal is to build a game application. It will generate a random number then will ask user to guess it, user will enter his guess then program will say if that was the right number or not. When round ends - user may choose to continue the game or stop.

Full source code is here: lostintime/fp-to-the-max.

Domains and Languages

For the app specifications above - first we will split our app business domain into smaller ones and define basic languages for them.

A domain language will consist of:

Custom data types, if needed (language primitive types may be enough)
An interface defining language functions, using generic higher kinded types for non-domain data structures

Spoiler: The way we will define the DSLs is named Tagless Final, here are few links to read more:

Console

In order to interact with user we will use command line interface to read user’s input and write messages to user, so console domain language is defined as an interface with 2 functions:

export interface Console<F> {

  /**
   * Displays a message to user
   */
  writeLine(line: string): HK<F, void>

  /**
   * Reads a line from user's input
   */
  readLine(): HK<F, string>
}

src: console.ts

Random

App will need to generate random numbers for user to guess:

export interface Random<F> {

  /**
   * Generates a random integer number within given closed range
   */
  randomInt(min: number, max: number): HK<F, number>
}

src: random.ts

Strings and Numbers

So far we can read and write string lines from/to user and generate random numbers, but ito compare user guess with generated value we will have to parse an integer number from user’s string input (or transform generated integer number to a string):

export interface Numbers<F> {

  /**
   * Parse an integer from a string
   * NOTE: Failures will be encoded within HKT, for simplicity
   */
  parseInt(num: string): HK<F, number>
}

src: numbers.ts

Program

In order to be able to build more complex programs - we’re missing some glue, let’s put them together within new Program DSL:

export interface Program<F> {
  /**
   * Lift a constant A
   */
  pure<A>(a: A): HK<F, A>

  /**
   * Chain 2 operations
   */
  chain<A, B>(f: (a: A) => HK<F, B>, fa: HK<F, A>): HK<F, B>
}

pure function will wrap given value into our box type, chain - will apply a transformation over given boxed value A.

Game Time!

Now we’re ready to build our game application using the languages we defined above. It is defined as a function taking as argument a type with all the DSLs needed for it’s implementation.

Hello World

When game starts - we will show a “Welcome” message to the user:

/**
 * Game DSL is composed from all languages needed to build it
 * At this level we only need to print a message to console
 */
export type GameDSL<F> = Console<F>

/**
 * Game Application:
 *  1. Say Hello
 */
export const game = <F>(dsl: GameDSL<F>): HK<F, void> => {
  const { writeLine } = dsl

  return writeLine("Hello & welcome to our game (press CTRL/CMD+C to exit)")
}

Play npm start -s:

Game Round

After welcome message - a game round starts, we will define it as separate function (application) which:

Displays round rules message to user;
Generates a random number;
Asks user to guess and enter the number;
Compare the guess with generated number and show round results.

/**
 * The type composes all the languages neede to build a single round game application
 */
export type GameRoundDSL<F> = Program<F> & Console<F> & Numbers<F> & Random<F>

/**
 * Single round application
 */
const gameRound = <F>(dsl: GameRoundDSL<F>): HK<F, void> => {
  const { chain, readLine, writeLine, parseInt, randomInt } = dsl

  const intro = writeLine("Please enter a number from 1 to 5")

  const genInt = () => randomInt(1, 5)

  const readGuess = chain(parseInt, readLine())

  const checkGuess = (num: number) => (guess: number) =>
    guess === num
      ? writeLine("You Win!")
      : writeLine(`Wrong! The right number was ${num}`)

  return chain(
    num => chain(
      checkGuess(num),
      readGuess
    ),
    chain(genInt, intro)
  )
}

/**
 * Game Application:
 *  1. Say Hello
 *  2. Run game round
 */
export const game = <F>(dsl: GameDSL<F>): HK<F, void> => {
  const { chain, writeLine } = dsl

  return chain(
    () => gameRound(dsl),
    writeLine("Hello & welcome to our game (press CTRL/CMD+C to exit)")
  )
}

Play npm start -s:

Loop

And finally - we don’t want our game to exit after single round so will write game loop to continue with user’s confirmation:

/**
 * Recursive game loop: plays a round then asks user to continue
 */
const gameLoop = <F>(dsl: GameDSL<F>): HK<F, void> => {
  const { pure, chain, readLine, writeLine } = dsl

  const checkContinue = chain(
    answer => pure(
      answer.toLowerCase() === "y" || answer.trim() === "" ? true : false
    ),
    chain(
      readLine,
      writeLine("Do you want to play again? [Y/n]:")
    )
  )

  return chain(
    () => chain(
      // The recursive call is not stack safe!
      go => go ? gameLoop(dsl) : pure(undefined),
      checkContinue
    ),
    gameRound(dsl)
  )
}

/**
 * Game Application:
 *  1. Say Hello
 *  2. Run game loop
 *  3. Done
 */
export const game = <F>(dsl: GameDSL<F>): HK<F, void> => {
  const { chain, writeLine } = dsl
  const intro = writeLine("Hello & welcome to our game (press CTRL/CMD+C to exit)")

  return chain(
    () => writeLine("Done."),
    chain(
      () => gameLoop(dsl),
      intro
    )
  )
}

Play npm start -s:

Tada! We can you try your luck using our hand-made game, almost … you may ask a logical question here - where did I get the game screenshots? And the answer comes right from the future, future chapters, keep reading :).

One thing to mention is that we didn’t only use constructs from the languages we defined, like:

if branching: (condition) ? (true handler) : (false handler) - a disjunction type may be used here;
Equality checking: guess === num - it works fine in our example, but for more complex data structures - further abstraction is needed (see: Setoit).

Implementation

Finally, we have our application described in abstract terms - our DSLs, to make use of it we will also need an implementation.

At this moment we have to choose a concrete type for our HK<F, _>. In this example I’ll use IO from funfix-exec library.

Console

Define an object implementing our Console interface using concrete IO type:

import { Console } from "../dsl/console"
import { IO } from "funfix-effect"
import * as readline from "readline"
import { FutureMaker, Cancelable } from "funfix-exec"

export const ConsoleIO: Console<"funfix/io"> = {
  writeLine: (line: string) => IO.of(() => {
    console.log(line)
  }),

  readLine: (): IO<string> => IO.deferFuture(() => {
    const cl = Cancelable.empty()
    const ft = FutureMaker.empty<string>()

    const rl = readline.createInterface(process.stdin, process.stdout)

    rl.on("SIGINT", () => {
      rl.close()
      cl.cancel()
    })

    rl.question("> ", (answer) => {
      rl.close()
      ft.trySuccess(answer)
    })

    return ft.future(cl)
  })
}

src: console-io.ts

The readLine function supports cancellation on SIGINT process signal.

Random

import { Random } from "../dsl/random"
import { IO } from "funfix-effect"

export const RandomIO: Random<"funfix/io"> = {
  randomInt: (min: number, max: number): IO<number> => IO.of(() => {
    return Math.floor(Math.random() * (max - min + 1)) + min
  })
}

src: random-io.ts

Numbers

import { Numbers } from "../dsl/numbers"
import { IO } from "funfix-effect"

export const NumbersIO: Numbers<"funfix/io"> = {
  parseInt: (num: string): IO<number> =>
    IO.of(() => parseInt(num, 10))
      .flatMap(n => isFinite(n)
        ? IO.pure(n)
        : IO.raise(new Error(`Failed to parse integer number from "${num}:`))
      )
}

src: numbers-io.ts

Program

import { Program } from "../dsl/program"
import { IO } from "funfix-effect"

export const ProgramIO: Program<"funfix/io"> = {
  pure: <A>(a: A): IO<A> => IO.pure(a),

  chain: <A, B>(f: (a: A) => IO<B>, fa: IO<A>): IO<B> => fa.chain(f),
}

src: program-io.ts

Having all the languages implemented we can use them to compose our app language GameDSL:

export const GameDSL: GameDSL<"funfix/io"> = {
  ...ProgramIO,
  ...ConsoleIO,
  ...NumbersIO,
  ...RandomIO
}

export const gameIO = game(GameDSL)

The only remaining thing is to run the app, and luckily our IO type have the run method!

// The end of the world is here
gameIO.run()

Unfortunately this doesn’t work, as there are no HKTs support in the language so compiler cannot infer the concrete type to know there is a run method, so we will have to add one more small abstraction of this method, same way we did with other DSLs:

export interface App<F> {
  /**
   * Execute given application
   */
  run<A>(fa: HK<F, A>): void
}

src: app.ts

and the implementation:

export const AppIO: App<"funfix/io"> = {
  run: <A>(fa: IO<A>): void => {
    fa.run()
  }
}

src: app.ts

And Play! npm start -s:

AppIO.run(gameIO)

src: app.ts

Testing

A powerful type system already protects us from a lot of troubles which in dynamicaly typed languages, we have to deal with on runtime but in real life applications we ~~rarely~~ never shift app business logic to the type level completely, for various reasons, so there is still place for writing automated tests.

In order to test our game program we will need to write one more implementation which allows to provide test data and observes application side effects.

For this implementation we can use a simpler HK type implementation but it still must be lazy! to guarantee our declarative style program is evaluated in the right order!

Let’s call it Eval :)

export type Eval<A> = (() => A) & HK<"Eval", A>

export const Eval = <A>(a: () => A): Eval<A> => a as Eval<A>

And then just draw the rest of the Owl:

const ProgramEval: Program<"Eval"> = {
  pure: <A>(a: A): Eval<A> => Eval(() => a),

  chain: <A, B>(f: (a: A) => Eval<B>, fa: Eval<A>): Eval<B> => Eval(() => f(fa())())
}

const NumbersEval: Numbers<"Eval"> = {
  parseInt: (num: string): Eval<number> => Eval(() => parseInt(num, 10))
}

/**
 * This is a container for app state
 *  `readLines` property used to pass user inputs
 *  `writeLines` property used to collect messages wrote by the app
 *  `randoms` "random" numbers device
 */
class TestState {
  constructor(public readLines: string[],
              public writeLines: string[],
              public randoms: number[]) {}

  /**
   * Return input lines from a predefined list
   */
  readLine(): string {
    const head = this.readLines[0]
    this.readLines = this.readLines.slice(1)

    return head
  }

  /**
   * Collect all lines wrote
   */
  writeLine(line: string): void {
    this.writeLines.push(line)
  }

  /**
   * Issue "random" numbers
   */
  randomInt(min: number, max: number): number {
    const head = this.randoms[0]
    this.randoms = this.randoms.slice(1)

    return head
  }
}

function TestModule(state: TestState): GameDSL<"Eval"> {
  return {
    ...ProgramEval,
    writeLine: (line: string): Eval<void> => {
      return Eval(() => state.writeLine(line))
    },
    readLine(): Eval<string> {
      return Eval(() => state.readLine())
    },
    randomInt(min: number, max: number): Eval<number> {
      return Eval(() => state.randomInt(min, max))
    },
    ...NumbersEval
  }
}

const AppEval: App<"Eval"> = {
  run: <A>(fa: Eval<A>): void => {
    fa()
  }
}

TestState class represents our mutable world, providing us resources we need and accepting our output back.

Here is how test case will look like:

describe("game", () => {
  it("succeeds for right guess", () => {
    const state = new TestState(["1", "n"], [], [1])
    const testModule = TestModule(state)

    // Run the app and mutate the state
    AppEval.run(game(testModule))

    expect(state.readLines, "all lines read").is.empty
    expect(state.writeLines, "wrote the right output").deep.equals([
      "Hello & welcome to our game (press CTRL/CMD+C to exit)",
      "Please enter a number from 1 to 5",
      "You Win!",
      "Do you want to play again? [Y/n]:",
      "Done."
    ])
    expect(state.randoms, "all randoms consumed").is.empty
  })
})

src: game-app.test.ts

App will first receive the random number 1 we provided in TestState, then user will enter his guess "1", and will answer with "n" to not continue the game. All the app output will be also collected into state.writeLines and compared to expected messages list.

Note on Variance

Functions in TypeScript are contravariant on their arguments (with --strictFunctionTypes option On). For interface methods - bivariant first assignement is still permited and we will have to use bivariant definition when we have HKTs in contravariant positions (function arguments) so compiler can match lighweight HKTs to concrete type we used, ex:

import { HK } from "funland"
import { Eval } from "funfix-effect"

export interface Program<F> {
  // declared as a method
  pass<A>(fa: HK<F, A>): HK<F, A>
}

export const ProgramEval: Program<"funfix/eval"> = {
  pass: <A>(fa: Eval<A>): Eval<A> => fa
}

vs when declared as as a property:

import { HK } from "funland"
import { Eval } from "funfix-effect"

export interface Program<F> {
  // declared as a property
  pass: <A>(fa: HK<F, A>) => HK<F, A>
}

export const ProgramEval: Program<"funfix/eval"> = {
  pass: <A>(fa: Eval<A>): Eval<A> => fa
}

Issues an error:

test/bivariance.test.ts:36:3 - error TS2322: Type '<A>(fa: Eval<A>) => Eval<A>' is not assignable to type '<A>(fa: HK<"funfix/eval", A>) => HK<"funfix/eval", A>'.
  Types of parameters 'fa' and 'fa' are incompatible.
    Type 'HK<"funfix/eval", A>' is missing the following properties from type 'Eval<A>': get, map, flatMap, chain, and 5 more.

36   pass: <A>(fa: Eval<A>): Eval<A> => fa
     ~~~~

So, when you use HKTs as arguments to your DSL functions - declare them as interface methods, not as properties.

Conclusions

Overall the results looks pretty intriguing. We obtained an implementation agnostic, declarative style application, easy to compose and extend.

And I didn’t even use the scary M… word once so far! Did I? But the Monad, if you’re somehow familiar with it, probably came into your mind while looking at our Program<F> language as you may spot there some generic functionality which you will use with all of your programs.

However, there are still questions needs to be answered:

How can I introduce this approach gradually into my project?
How do I share my generic code?
- Should I provide a test kit for language laws?
- Should I provide a default implementation? if so - pack it into same package?
Does it scale?
- The final app should speak all the languages used inside, and composing it as an intersection type may lead to conflicts - how do I isolate/namespace my languages?
- How to set type bounds on domain data and/or languages? and how to bring those type classes in?
Do I really need to define all the languages myself?
- Here I invite you to join me digging deeper into commonly used type classes, starting with a really nice hierarchy visual representation: cats typeclasses;
How to handle errors or combine different arity kinds?

On all of these I’ll elaborate within my next posts - Follow Me and stay tuned!

PS: Lear more languages! Even if you won’t use them in production, it will definitely help you take a fresh look and make you better in your primary programming language.

Challenges

Generic higher kinded types

Implicits

for comprehension syntax

The App

Domains and Languages

Console

Random

Strings and Numbers

Program

Game Time!

Hello World

Game Round

Loop

Implementation

Console

Random

Numbers

Program

Testing

Note on Variance

Conclusions

`for` comprehension syntax