DEV Community: Derp

Parser combinators in typescript with parser-ts

Derp — Tue, 31 Jan 2023 15:32:03 +0000

Consider the following strings
"13:15"
"1:15pm"
"quarter past 1pm"

These may be just strings to a computer but to a human, we can see that they all represent a time. Furthermore, we see that there is some structure to these strings. So whereas “quarter past 1pm” makes sense as a time. “Foohoogablahblahl” does not.

Now our first instinct might be reach for regex to parse these strings and extract the data out of them, but I'd advise against it. We will solve this problem with parser combinators using the parser-ts library.

Let's begin with the first example "13:15" which is the time in 24 hour format. Upon closer examination, we see that it is comprised of three parts <hours> <:> <minutes> each with its own set of rules.

Taking a look at the <hours> component, we know that there are some rules. First, it must be a number and that number must be between 0 & 23. So to begin with, we reach for the int parser from the parser-ts/lib/string module.

import { run } from "parser-ts/lib/code-frame";
import * as S from "parser-ts/lib/string";

console.log(run(S.int, "14")); //[1] Right 14
console.log(run(S.int, "asdf4")); //[2] Left "Expected: an integer"
console.log(run(S.int, "14aaaaa")); //[3] Right 14

Let's break this down. On line [1], we ran the parser on the string "14" and we got back a Right instance containing the number 14. On line [2], we see that if the int parser is unable to extract out a number, we error out with a Left instance containing a helpful error message. On line [3], we see that we succeed in extracting out the number 14 and we abandon the rest of the string.

Phew, that was a lot, however we aren't done yet because if we try to do

console.log(run(S.int, "29")); // Right 29

We succeed with the number 29 which isn't what we want because there isn't a 29th hour in 24 hour format. To solve this, we reach for our first combinator filter. Filter allows us to pass in a predicate so that we can filter out our invalid values. After this, we finally have our 24 hours parser.

const isValid24Hour = (hours: number) => hours >= 0 && hours <= 23;

const hours24Parser = P.expected(
  pipe(S.int, P.filter(isValid24Hour)),
  "24 hour clock hours must be between 0 & 23"
);

console.log(run(hours24Parser, "14")); // Right 14
console.log(run(hours24Parser, "32")); // Left "24 hour clock hours must be between 0 & 23"

Nice! Next we need our colon parser which matches just the ":" character.

const colonParser = S.string(":");

Finally, we apply a similar approach to the hours24Parser for our minutes parser

const isValidMinute = (minutes: number) => minutes >= 0 && minutes <= 59;

const minutesParser = P.expected(
  pipe(S.int, P.filter(isValidMinute)),
  "Minutes must be between 0 & 59"
);

At this stage, we have our hours24Parser, our colonParserand our minutesParser. So the next challenge is to figure out a way to mash all three of these together. Now Parsers are monads which means that we can chain them together. To make life a bit simpler, we will be using the bind and bindTo convenience methods to store our extracted data.

const time24hoursParser = pipe(
  hours24Parser,
  P.bindTo("hours"), // store hours into an object with key 'hours'
  P.chainFirst(() => colonParser), // ignore and don't store the colon
  P.bind("minutes", () => minutesParser) //store minutes under the key 'minutes'

console.log(run(time24hoursParser, "00:24")); // Right { hours:0, minutes: 24}
);

Excellent! Let's give this hours, minutes data object a type and call it a TimeObj

type TimeObj = {
  hours: number;
  minutes: number;
};

Okay, let's take a breather now. Imagine you are an international amazing race participant and you have just woken up on a bus after three consecutive connecting flights. The bus is currently traveling in a tunnel and you have no idea what year it is let alone the month, day or time. Spying a fellow passenger with a wristwatch, you groggily come to and have the following conversation:

You: Hello fellow human. I appear to have regained consciousness after my intraplanetary travels. May I inquire the reading on your portal time tracking device?
Passenger: ooookay....
Passenger: <looks down at watch>
Passenger: uhhh, it is currently quarter past 1
You: May I ascertain the position of the sun relative to our position as well?
Passenger: huh? ohh
Passenger: quarter past 1...pm

So how do we parse the string "quarter past 1pm"? To do this, we will need to break down the structure of that string into a grammar.

<long-form-time> ::= <segment> <relative> <hours12><ampm>
<segment> ::= quarter | half
<relative> ::= past | to
<hours12> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
<ampm> ::= am | pm

Within our grammar, we allow sentences like "quarter past 1pm", "quarter to 5pm" and "half past 12pm".

So let's get into it. The first thing to tackle would be the string "quarter" and "half".

const quarterParser = pipe(
  S.string("quarter"),
  P.map(() => 15)
);
const halfParser = pipe(
  S.string("half"),
  P.map(() => 30)
);

const segmentParser = P.either(quarterParser, () => halfParser);

console.log(run(segmentParser, "half")); // Right 30

We have a quarterParser to match on the string "quarter" and return back the number 15. We have a halfParser to match on the string "half" and return back the number 30. We then use the either combinator to try one and then the other if the first one fails.

Next up will be tackling the <relative> segment of our grammar. This one requires a bit of thought. When we see the word "past" in the sentence "quarter past 1pm", what does it represent?

It represents that the notion that we should add 15 minutes to whatever the hours component is. The type signature of this notion might look like:

(minutes: number) => (hours:number) => TimeObj

So let's get to it

const minutesPast = (minutes: number) => (hours24: number): TimeObj => ({
    hours: hours24,
    minutes
});

const pastParser = pipe(
  S.string("past"),
  P.map(() => minutesPast)
);

Let's break this down. First we define a function minutesPast which takes in the minutes, then the hours in 24 hour format and returns back our 24 hour time object representation.
Next we define the pastParser, this parser matches on the string "past" and carries within it the minutesPast function.

Similarly, we do the same for the toParser

const minutesTo = (minutes: number) => (hours24: number): TimeObj => {
  if (hours24 === 0) {
    return {
      hours: 23,
      minutes: 60 - minutes
    };
  } else {
    return {
      hours: hours24 - 1,
      minutes: 60 - minutes
    };
  }
};

const toParser = pipe(
  S.string("to"),
  P.map(() => minutesTo)
);

We also need a way to parse our <hours12> segment and convert that into a 24 hour format

const isValid12Hour = (hours: number) => hours >= 1 && hours <= 12;
const num12Parser = P.expected(
  pipe(S.int, P.filter(isValid12Hour)),
  "12 hour clock hours must be between 1 & 12"
);

const amParser = pipe(
  S.string("am"),
  P.map(() => (hours12: number) => (hours12 === 12 ? 0 : hours12))
);

const pmParser = pipe(
  S.string("pm"),
  P.map(() => (hours12: number) => (hours12 === 12 ? 12 : hours12 + 12))
);

const amPmParser = P.either(amParser, () => pmParser);

const hours12Parser = P.seq(
  num12Parser,
  (hours12) =>
    pipe(
      amPmParser,
      P.map((f) => f(hours12))
    )
);

console.log(run(hours12Parser, "1am")) // Right 1
console.log(run(hours12Parser, "3pm")) // Right 15
console.log(run(hours12Parser, "14am")) // Left "12 hour clock hours must be between 1 & 12"

Let's break this down. Using a similar technique to the hours24Parser earlier in this article, we create the num12Parer to only allow numbers between 1 & 12.
The amParser and pmParser are Parsers that match on either am or pm and contains a function that converts 12 hour time to 24 hour time. We then join the amParser and pmParser together using the either combinator.

The hours12Parser takes the num12Parser and combines it using seq which is a combinator that passes results from the first Parser to the next Parser if it succeeds. If it succeeds, we pass the parsed hours12 number to the amPmParser, as that contains a function inside, we use P.map to apply our hours12 number to the contained function getting back a number representing the hours in 24 hour time.

Phew! We now have all the parsers for our individual segments. Time to glue them altogether.

const longFormParser = pipe(
  segmentParser, // [1]
  P.chainFirst(() => S.spaces1), // [2]
  P.chain((minutes) =>
    pipe(
      P.either(toParser, () => pastParser),
      P.map((f) => f(minutes)) // [3]
    )
  ),
  P.chainFirst(() => S.spaces1), //ignore 1 or more spaces
  P.chain((f) =>
    pipe(
      hours12Parser, // [4]
      P.map((hours12) => f(hours12)) // [5]
    )
  )
);

console.log(run(longFormParser, "quarter to 12am")); //Right {hours:23, minutes:45}
console.log(run(longFormParser, "half past 12am")); //Right {hours:0, minutes: 30}

Let's talk it out. [1] We start with our segmentParser to match on "quarter" or "half" and get back the number 15 or 30. [2] We then use chainFirst with S.spaces1 to ignore 1 or more whitespace characters. [3] We then use either our toParser or pastParser to get our function of the shape minutes -> hours -> TimeObj. Since we have our minutes already, we partially apply the minutes to our function [3]. After ignoring some more spaces, we use the hours12Parser to extract out the number of hours in 24 hour time [4]. Finally, we have the last argument for our function from [3] and we have the time represented in our TimeObj format.

With that, our alien friend now knows what time it is to help it win the amazing race!

To conclude, I leave you with a poem

A string is not only a string
Wherewith a data structure lies within
Regex don't you use
Use Parser combinators for the win!
~derp

Link to codesandbox:
https://codesandbox.io/s/time-parser-example-jwrwk3?file=/src/index.ts

Advanced parser combinators with parser-ts

Derp — Mon, 12 Dec 2022 04:08:00 +0000

In the last part, we used the power of parser combinators to systematically parse strings into dates. However a Parser is unbound in its return type and you can make it returning anything.

Today we will be using this ability and combining it with the state monad to draw things on a canvas in clean, modular way.

The problem we will be tackling today will be the turtle.

No not that turtle, this one:
https://docs.python.org/3/library/turtle.html

Python turtles are great, you can give them a list of instructions and these turtles will dutifully execute them to create fine art. As our turtle program will be simpler, we will give our turtle a short name. Meet Bob.

For simplicity, Bob will only understand a small subset of commands that python turtles can understand. Bob understands the following strings: forward X, left X, right X, penUp and penDown. These commands will respectively move, rotate and give Bob the ability to draw straight lines on a canvas.

To tackle this problem, we will be splitting it up into three parts

Teaching Bob how to understands strings
Teaching Bob how to store state
Teach Bob how to draw on the page

Once we have tackled these three sub problems, we will join them altogether and have our program.

Teaching Bob to understand strings

The first problem we will tackle is to teach Bob to understand strings. Building on the last article, we will use parser combinators. Let's teach Bob how to understand "forward 10".

const forwardStrParser: P.Parser<string, number> = pipe(
  S.string("forward"),
  P.chain(() => S.spaces1),
  P.chain(() => S.int)
);

Let's break this down. First (1) we match on the string "forward" with S.string("forward"), we then match on one or more spaces with P.chain(() => S.spaces1)) and finally we have P.chain(() => S.int). Note that we are ignoring the input from the string "forward" and the spaces and we only keep the number at the end.

In the end, we have a Parser that takes in a string and returns back a number. However as Parsers are functors, they have a method map which allows us to transform that number into any other type. We will get back to this point later in the article.

Teaching Bob to store state

Bob needs to know where he is on the canvas, which direction he is facing and whether or not he is currently drawing or not. Let's create a minimal representation of this state:

export const INITIAL = {
  dir: 0, // direction our turtle is facing in degrees
  pos: [0, 0], // our initial x,y position
  isDrawing: false // our way of putting the 'pen' up or down.
};

From the initial state above, we will need some sort of mechanism to transform that state and extract some sort of output from the new state. Thankfully, we can use the state monad to give this to us.

To summarise, the state monad has a type signature of:

State s a :: s -> (a,s)

What this says is that all our state monads are state transition functions that take in some initial state and returns back a pair of some output a and some new state s.

Let's ignore the output for now and see how we might write the state transition function to move Bob forward n.

export const forward = (n: number): St.State<State, ?> => (
  state: State
) => {
  const [x, y] = state.pos; // 1
  const dirRadians = degToRad(state.dir);
  const xComponent = Math.cos(dirRadians);
  const yComponent = Math.sin(dirRadians);

  const newState = { //2
    isDrawing: state.isDrawing,
    dir: state.dir,
    pos: [x + n * xComponent, y + n * yComponent]
  };
  return [?, newState]; // 3
};

Let's break this down. This is a function that takes in a number n spaces to move forward and returns back the state monad St.State<State,?>. Now state monads are functions that take in an initial state and return back some output and a new state.

In section 1, we are destructuring the x & y co-ordinate from the current position. We then do some trigonometry to calculate the x & y component based on the current direction of our turtle. Once we have all that, we start constructing our new state in section 2. As moving forward does not change the isDrawing or direction of our turtle, we pass those unchanged from our initial state. Our new co-ordinates are calculated by multiplying the n spaces that we are moving forward by the x & y components. Finally in section 3, we return back our pair of some output (?) and our new state.

Teaching Bob to draw on the page

In our example, we are using a canvas API to draw on the page. However, one important detail is that we don't want to immediately draw on the page, but instead create a function that will only draw on the page when executed.

To do this, we define a DrawFunction which has the type signature of

type DrawFunction = (context: CanvasRenderingContext2D) => void;

That is, this is a function that takes in the context as an argument so that when executed, we can perform side effects like context.stroke() drawing our lines on the canvas.

For example, our lineTo function will look like the below.

export const lineTo = (x: number, y: number): DrawFunction => (ctx) => {
  ctx.lineTo(x, y);
  ctx.stroke();
};

Let's break this down. We have a lineTo function that takes in the new x & y co-ordinate that we should move to from our previous x&Y co-ordinate stored in the internal canvas state. We then call lineTo which adds a new line to the current sub-path inside the canvas state. As this does not actually fill in the line, we will then need to call stroke to fill in the line causing the line to appear on the screen. As lineTo is a higher order function, the lines won't be drawn until both the (x,y) and (ctx) arguments are supplied.

Bringing it all together

In the previous section, we saw how to parse a string, transform state and draw onto a canvas individually. In this section, we will connect them all with the power of functional programming.

First, from our forward string parser, we ended up with a parser from strings to numbers. forwardStrParser : P.Parser<string, number>, however as alluded to earlier, Parsers a functors and we can map that number and pass it to our forward function that returns a state monad to get a parser that takes in a string and returns back a state transition.

// forwardStrParser :: P.Parser<string, number>
const forwardParser = pipe(forwardStrParser, P.map(forward));
// forward Parser :: P.Parser<string, S.State<State, ?>>

Now we have a parser that takes in a string and returns back state transition function.

From the state transition function, we glossed over the output of each step. What we can do is to return a DrawFunction for each step so as we go through our state transitions, we can build a corresponding DrawFunction.

export const forward = (n: number): St.State<State, DrawFunction> => (
  state: State
) => {
  // discussed in section 2
  const [x, y] = state.pos;
  const dirRadians = degToRad(state.dir);
  const xComponent = Math.cos(dirRadians);
  const yComponent = Math.sin(dirRadians);

  const newState = {
    isDrawing: state.isDrawing,
    dir: state.dir,
    pos: [x + n * xComponent, y + n * yComponent]
  };

  // **New** Look here below:
  const drawFunction: DrawFunction = state.isDrawing
    ? lineTo(newState.pos[0], newState.pos[1])
    : moveTo(newState.pos[0], newState.pos[1]);

  return [drawFunction, newState];
};

Let's break this down. Here we choose between two DrawFunctions depending on our current state. If isDrawing is true, we will choose the lineTo DrawFunction whereas if it is not, we will choose the moveTo DrawFunction. The moveTo function has not been shown above but can be seen in the codesandbox at the end.

Hence our forwardParser has the final type of P.Parser<string, S.State<State, DrawFunction>>.

Seeing it in action

import { pipe } from "fp-ts/function";
import { run } from "parser-ts/lib/code-frame";
import * as E from "fp-ts/lib/Either";

const initialState: State = {
  isDrawing: true,
  dir: 0,
  pos: [0, 0]
}; // 1

const c = <HTMLCanvasElement>document.getElementById("myCanvas");
let ctx = c.getContext("2d");
if (ctx == null) throw new Error("canvas not found"); 
ctx.lineWidth = 5;
ctx.moveTo(initialState.pos[0], initialState.pos[1]); // 2

const eitherState = run(forwardParser, "forward 100"); // 3
pipe(
  eitherState,
  E.fold(console.error, (state) => { // 4
    const [drawFn, _newState] = state(initialState); // 5
    drawFn(ctx); // 6
  })
);

Let's break this down. In (1), we set the initial state of Bob. Note that we are setting isDrawing to be true right off the bat as we want to draw a line instead of just moving Bob.

In (2), we need to get our reference in JS to our HTML canvas element. We then update the context to match our initial state.

In 3, we run the forward parser with our string "forward 100". This returns back either an error message if our string fails to parse or our state transition. If it is an error message, we log the error to the console, however if is our state monad (4), we run the state against the initial state in (5) to get a drawFunction and the updated state. As we are only interested in the drawFunction, we ignore the updated state and we execute the drawFunction by providing the last context argument in (6) causing our line to appear on the screen.

Understanding many commands

Currently Bob only understands how to draw lines forwards. We won't cover all the commands here however they all follow a similar pattern in that we create a Parser for every command that we want Bob to understand.

forwardParser :: P.Parser<State, DrawFunction>
leftParser :: P.Parser<State, DrawFunction>
rightParser :: P.Parser<State, DrawFunction>
penUpParser :: P.Parser<State, DrawFunction>
penDownParser :: P.Parser<State, DrawFunction>

Once we have our parsers, we can join them together with alt to create our overall turtleParser

export const turtleParser = pipe(
  forwardParser,
  P.alt(() => leftParser),
  P.alt(() => rightParser),
  P.alt(() => penUpParser),
  P.alt(() => penDownParser)
);

However, this is still a parser that takes in a single string and returns back a single state transition. Ie

turtleParser :: P.Parser<State, DrawFunction>

If we have many strings in an array, what we can do is run the turtleParser on every string in the array to get back an array of Either<string,St.State<State, DrawFunction> and use sequenceArray to convert that into an Either[]>.

Let's see that in action

const cmds: string[]= [
  "forward 100",
  "right 90",
  // ...other commands not shown
]; // 1

const parsed = cmds.map((cmd) => run(turtleParser, cmd)) // 2
// E.sequenceArray :: <E, A>(as: readonly Either<E, A>[]) => Either<E, readonly A[]> // 3
const maybeTransitions = E.sequenceArray(parsed); // 4

Let's break that down. In (1), we have our array of strings which we then map into an array of Parsers in (2). Now parsed has the type of parsed:: E.Either<string, St.State<State,DrawFunction>>[] however note that we have ended up with an array of Eithers which if we would then manually need to check on whether it was a Left or a Right and then only if it was a Right, would we want to progress. As this is a common task in functional programming, we reach for the utility function sequenceArray(3) which takes in an array of Eithers and runs through them sequentially and checks whether each element is a Left or a Right. If any element is Left, it will return back that result, however if all the elements in the array are Right, then it will collect them all into a single Array. In (4), we call this function on our array parsed to get back our maybeTransitions which is either an error or an array of State transitions.

if (E.isRight(maybeTransitions)) {
  const transitions = maybeTransitions.right;
  const [drawFns, finalState] = St.sequenceArray(transitions)(INITIAL); // 5

  drawFns.forEach((drawFn) => drawFn(ctx as CanvasRenderingContext2D)); //6
  drawTurtle(finalState.pos[0], finalState.pos[1], finalState.dir)(ctx); // 7
} else {
  console.error(maybeTransitions.left);
}

Once we have our array of state transitions in (5), we then call the State monad's version of sequenceArray to get back an array of drawFunctions and our final state. We then pass the final argument in all of our drawFunctions in (6) drawing our changes to the canvas. In (7), we draw Bob on our canvas with his position and direction based of our final state at the end of all our state transitions.

In conclusion, we have ended up with a program which neatly separates the concerns of parsing, state and side effects and joined them all with the power of functional programming. If you would like to have a play yourself, please feel free to check out the codesandbox link below:

https://codesandbox.io/s/parser-combinator-example-cjuh40

Abstracting away async with fp-ts

Derp — Tue, 22 Nov 2022 12:32:31 +0000

Business logic is usually quite simple. It is the plumbing that is hard. You can use ap to isolate your business logic from your plumbing

Consider the e-commerce store Widgi-tech:

The business logic for calculating the price of an order is usually quite simple. In the above example, our widgets are being sold for $3 each, we are buying three of them and we add shipping on top of that. The complexity usually comes from mixing our business logic with concerns like error handling and asynchronicity.

To begin, lets write our getTotal function.


 typescript
const getTotal = (price:number) => (qty:number) => (shipping:number) => price * qty + shipping;

Job done right? Well no, at Widgi-tech, each one of those arguments is the responsibility of a different team. The pricing team sets prices today based on the prices based on how many of an item you order. Oh and sometimes prices aren't available for a given SKU yet. Qty is controlled by the inventory team which tracks how many widgets they have in their warehouse and you can't order more of a widget than they have and shipping costs depend on the location and total weight of the order. Oh and you can't send items to addresses outside their delivery zone.

The problem then starts to look a bit more like this:



import * as E from "fp-ts/Either"

type SKU = string;
type Address = string;

type getPrice = (sku:SKU, qty:number) => E.Either<string, number>
//just ignore that we are representing money with a number type for now

type getQty = (sku:SKU, qty:number) => E.Either<string, number>

type getShipping = (sku:SKU, qty:number, address: Address) => E.Either<string, number>

Let's break this down.

We have a function signature for getPrice that takes in the SKU and the qty of an item and returns back either an error message (string) or the per unit price of the item (number).

We have a function signature for getQty that takes in the SKU and the quantity of items and returns back either an error message when they can't fulfill the item or just the quantity back.

We have a function signature for getShipping that takes in the SKU, the quantity of items and the address. We either get back an error message when they can't send the items there or we get back the shipping cost.

Now we are at a conundrum, we started with our beautiful and simple getTotal function but now we have to care about error messages and the ugliness of error messages and reality. How do we make the getTotal function fit?

The secret is that Either is an instance of an applicative functor. We can lift our simple getTotal function into an Either and then apply each of our arguments sequentially.


 typescript
/** We lift getTotal into E.Either and apply each argument sequentially */
const price: E.Either<string, number> = pipe(
  E.of(getTotal),
  E.ap(getPrice(sku, qty)),
  E.ap(getQty(sku, qty)),
  E.ap(getShipping(sku, qty, address))
);

https://codesandbox.io/s/practical-lewin-yqsthc?file=/src/index.ts

Let's take a closer look at how ap works by examining the type signature of different parts:

E.of(getTotal) This lifts our getTotal function into an Either and the type signature of this is E.Either<never, (price: number) => (qty: number) => (shipping: number) => number>
getPrice(sku, qty) This is an E.Either<string, number>
E.ap This is the Either ap function, in this case, it has a signature of <string, number>(fa: E.Either<string, number>) => <B>(fab: E.Either<string, (a: number) => B>) => E.Either<string, B>
pipe(E.of(getTotal), E.ap(getPrice(sku,qty)) This has a type signature of E.Either<string, (qty: number) => (shipping: number) => number> Notice the difference in this signature to the one of E.of(getTotal). We have partially applied our price in our getTotal function

Phew. That was a lot but let's take a step back and admire what we have just done. By using the power of applicative, we have isolated the business logic inside our getTotal function and deferred all the error handling to our Eithers.

So why is this isolation useful? Because business logic changes all the time. Let's say there's a promotion where orders get free shipping if the total order is over $100, what that look like?


 typescript
const getTotal = (price:number) => (qty:number) => (shipping:number) => {
  const exShipping = price * qty;
  const shippingFee = exShipping < 100 ? shipping : 0;
  return exShipping + shippingFee;
}

Notice the lack of any change to the plumbing code or any of the wiring. Think also about how easy it is to test this function in isolation.

Now at this point, you the reader will probably be thinking. Hang on Derp, our different departments would have APIs that are asynchronous. How do we handle that?

To answer that question, we'll need to reach for another applicative. Eithers encapsulate the concept of an error state, a Task encapsulates the concept of asynchronicity. The applicative we need is a TaskEither which encapsulates both.

So our changes are:



/** Note: all that chnages is going from E.Either to TE.TaskEither */
type GetPrice = (sku: SKU, qty: number) => TE.TaskEither<string, number>;
type GetQty = (sku: SKU, qty: number) => TE.TaskEither<string, number>;
type GetShipping = (sku: SKU, qty: number, address: Address) => TE.TaskEither<string, number>;



/** We lift getTotal into TE.TaskEither and apply each argument sequentially */
const total: TE.TaskEither<string, number> = pipe(
  TE.of(getTotal),
  TE.ap(getPrice(sku, qty)),
  TE.ap(getQty(sku, qty)),
  TE.ap(getShipping(sku, qty, address))
);

const totalP = pipe(
  total,
  TE.fold(
    (err) => () => Promise.reject(err),
    (total) => () => Promise.resolve(total)
  )
);

totalP().then((total) => console.log(`total is ${total}`), console.error);

Notice our simple, beautiful getTotal function has remained completely unchanged. It cares not for the messy, asynchronous and error prone state of the world. We have successfully abstracted all of this away from it with the power of fp-ts and functional programming.

https://codesandbox.io/s/dreamy-hofstadter-4vuzou?file=/src/index.ts

Promisifying CSS animation with timeout fallback

Derp — Thu, 10 Mar 2022 01:15:46 +0000

So I came across this interesting problem dealing with state updates and animations. I wanted to create a utility function that would execute a state update after an animation had finished but with a timeout fallback in case a developer forgot to animate the element.

This is useful for React applications where you want to wait for a slide-out animation for your popup to complete before updating your state, causing your popup to be removed from the DOM.

Let's start with the first two problems
1) We need an event listener to listen for the CSS tranistionend event that is fired from the animated element. When it is triggered, call some function fn.
2) We need a timeout function as a fallback. When the timeout triggers, call some function fn

// 1
const addTransitionEndListener = (element: Element) => (fn: () => void) => {
  element.addEventListener("transitionend", fn);
};

// 2
const addTimeOut = (duration: number) => (fn: () => void) => {
  setTimeout(fn, duration);
};

Next, we want to promisify these two functions inside Promise.race and apply our state update when either one of these two promises is settled. We will also add some convenience types.

// 1
type Effect = () => void;
type CallbackFn = (f: Effect) => void;

// 2
const promisify = (fn: CallbackFn) =>
  new Promise((resolve, reject) => {
    fn(() => {
      resolve(null);
    });
  });

// 3
const addTransitionEndListenerP = promisify(
  addTransitionEndListener(someElement)
);
const addTimeOutP = promisify(addTimeOut(someDuration));

// 4
Promise.race([addTransitionEndListenerP, addTimeOutP]).finally(() =>
  console.log("state update goes here")
);

There's a lot to digest here so let's go through it section by section.

Effect represents a function with no return value. CallbackFn expects an Effect function as an argument and does not return anything. Both addTransitionEndListener and addTimeOut are of type CallbackFn after the first argument.
The promisify function expects a CallbackFn and returns a Promise. We are passing in resolve(null) as the Effect fn as we do not care about returning anything from our Promise for now.
Using promisify, we turn addTransitionEndListener and addTimeOut into something that returns a Promise.
We use Promise.race and finally to perform our mock state update regardless of whether the transitionend event first first or someDuration passes first. someDuration and someElement are defined outside of here.

After wiring all this up, we now have another problem. How do we remove the event listener or clear the timeout once either event happens? Keep in mind that removeEventListenerrequires a reference to the same function that was passed in to addEventListener and clearTimeoutrequires the interval id which is only returned when setTimeout is called.

To solve this, let's change the type of CallbackFn to return a CleanupFn which is a type alias for Effect.

type CleanupFn = Effect;
type CallbackFn = (f: Effect) => CleanupFn;

Next we will need to change addTransitionEndListener and addTimeOut to return a CleanupFn.

const addTransitionEndListener = (element: Element) => (
  fn: () => void
): CleanupFn => {
  element.addEventListener("transitionend", fn);
  return () => {
    element.removeEventListener("transitionend", fn);
  };
};

const addTimeOut = (duration: number) => (fn: () => void): CleanupFn => {
  const timeoutID = setTimeout(fn, duration);
  return () => clearTimeout(timeoutID);
};

We will also need to change promisify to return a pair of a Promise and a Cleanup function. We will then need to provide another function that wraps Promise.race so that it calls all the cleanup functions in the finally block.

type PromiseCleanup = [Promise<unknown>, CleanupFn];

const promisify = (fn: CallbackFn) => {
  let cleanupFn: Effect | undefined;
  return [new Promise((resolve, reject) => {
    cleanupFn = fn(() => {
      resolve(null);
    });
  }), cleanupFn as Effect]
};

export const promisifyRace = (
  promiseCleanups: PromiseCleanup[]
): Promise<unknown> => {
  const promises = promiseCleanups.map(([promise, _]) => promise);
  const cleanups = promiseCleanups.map(([, cleanup]) => cleanup);

  return Promise.race(promises).finally(() => {
    cleanups.forEach((cleanup) => cleanup());
  });
};

Now we are free to use it like so:

 promisifyRace([transitionP(), durationP()])
    .finally(stateUpdate)

Github link: https://github.com/wibily/promisifyCleanup

Codesandbox link:
https://codesandbox.io/s/animationend-fiddle-o2scuh?file=/src/index.ts

Note: codesandbox link builds on top of the idea above by passing in both the resolve, reject Promise executor to the promisify function allowing the caller to choose whether they want to resolve or reject the Promise.

TLDR;

Convert your asynchronous side-effect functions to return a pair of a Promise and a cleanup function
As we don't have Promise.cancel, create your own Promise.race/any/all implementation that runs all the cleanup functions in the finally block

Aside:
TIL that there is a difference between animationend and transitionend. Thank you Jessica

State monad in fp-ts

Derp — Wed, 19 Jan 2022 12:52:46 +0000

Consider the gumball machine

It is in a unpaid or paid state and the output of it is either nothing or a gumball.

type State = Unpaid | Paid;
type Gumball = "Gumball";
type Output = O.Option<Gumball>;

Now let's consider the transitions. When we pay 50c into this gumball machine, it will put it into the Paid state. If the machine is in a paid state and we turn the handle, we get a gumball and the machine reverts back to an Unpaid state. All other transitions, we get nothing and the state remains the same.

To model these state transitions, let's use the fp-ts State type

// State s a :: s -> (a,s)
export interface State<S, A> {
  (s: S): [A, S]
}

which translated means give me an initial state s and I'll give you some output A and the new state. Now calling this interface State is a bit confusing as it is really more of a State processor whereas the actual state type is inside the generic parameter S.

Hence our pay and turn function looks like the following:

//state transition functions are of the type State -> (Output, State)
const pay = (amount: number): S.State<State, Output> => (state: State) => {
  switch (amount) {
    case 50:
      return [O.none, "Paid"];
    default:
      return [O.none, state];
  }
};

const turn: S.State<State, Output> = (state: State) => {
  switch (state) {
    case "Unpaid":
      return [O.none, state];
    case "Paid":
      return [O.some("Gumball"), "Unpaid"];
  }
};

//Single usage:
pay(50)("Unpaid"); // [O.none, "Paid"];
turn("Paid"); // [O.some("Gumball"), "Unpaid"]

Now here comes the tricky part, how do we combine these functions together to build up our state machine? The key is that State s is an instance of Monad and that we can use bind/chain to combine our different state transition functions into a single one. Switching to Haskell for a second,

// (>>=) :: (Monad m) => m a -> (a -> m b) -> m b
// instance Monad (State s)
// (>>=) :: (Monad (State s)) => State s a -> (a -> State s b) -> State s b

Let's unpack this. First we have the definition of bind (>>=) or chain as it is in known in fp-ts. Next we see that our instance of Monad is (State s) so we should substitute (State s) wherever we see m. Finally we are left with the definition of bind specialised to the State monad. which we will take a look at now in parts. Ie State s a, (a -> State s b) and State s b.

//State s a :: s -> (a,s)

We remember that State s a is a state transition function that takes a state s and returns back an output a and a new state. So we expand it out.

//a - > State s b :: a -> s -> (b, s)

Expanding out State s b to s -> (b,s), we see that the second part is a function that takes in some input of type a, some state of type s and returns back a new output of type b and a new state.

//State s b :: s -> (b, s)

The return value is a new state transition function of State s b.

// (>>=) :: (State s) => State s a -> (a -> State s b) -> State s b

Let's bring it altogether now.

Bind takes the first state transition function and gets the output and state from that to feed it to the second state transition function creating a new combined state transition function.

Switching back to fp-ts land and our gumball machine, how would we combine our pay(50) and turn functions? Keeping in mind that S.chain is a flipped version of bind, we use the following: Note that we use () => turn because our gumball machine transitions do not depend on the output of a previous state transition.

const combined = S.chain(() => turn)(pay(50));
combined('Unpaid') // [O.some("Gumball"), "Unpaid"]

Now that we know that monadic composition is available to us, we can use functions like S.sequeunceArray to combine an array of state transition functions into a single state transition function that returns a collected array of outputs as well as the final state.

const actions = [pay(5), turn, pay(50), turn, turn, pay(50), turn];
const [outputs, finalState] = S.sequenceArray(actions)('Unpaid');
const numGumballs = outputs.filter(O.isSome).length; //2

Sample code: https://codesandbox.io/s/ancient-firefly-3lgrg?file=/src/index.ts

Advent of code - day 6

Derp — Sat, 08 Jan 2022 06:47:41 +0000

This challenge is to create a state machine and find the end state after n iterations.

This seems like a perfect opportunity to dig deeper with the State Monad which i have been struggling with for a while. First, the interface which is

// newtype State s a = State { runState :: s -> (a, s) }
interface State<S, A> {
  (s: S): [A, S]
}

A more accurate name for this would be State processor. The type S represents the state whereas the A represents some sort of interesting output from the State processor.

First, I create my nextFishState function which has the signature:
nextFishState :: number -> [number]. Now in my nextState function which has the singature: nextState: S.State<number[], number>, I use chain to apply the nextFishState function to every element in my number[].

Finally, i replicate the nextState function 80 times so that i can pass it to sequeunce so that it'll fit the shape required by S.execute.

S.execute(initial)(A.sequence(S.Applicative)(A.replicate(80, nextState)))

This was okay with the small dataset however I suspect due to the eager evaluation of JS and the nature of A.sequence, my browser tab crashed on the input dataset. So, instead I'm going to use reduce instead:

pipe(A.replicate(80, nextState), A.reduce(initial, (state, f) => S.execute(state)(f))

Edit: I don't think the problem was due to using sequence or changing it to reduce. It may be something to do with console logging an array several hundred thousand long as the answer shows up before the tab crashes. Changing it to only print out the length of the array seems to work okay

Part 2:
Now we are assessing the number of fish after 256 days instead of 80, so only a simple change from 80 -> 256.

Edit 2: So it appears its not that simple as the brute force method is too slow and memory intensive. Instead, I am going to remodel my state to be an array where the index is the number of days left and the value is the number of fish with that index. The beauty of using the State monad pattern is that even though i have changed the representation of the State as well as the nextState transformation, the passing of one state to the next remained the same.

https://codesandbox.io/s/laughing-smoke-zehut?file=/src/index.ts

Advent of code 2021 - day 5

Derp — Thu, 06 Jan 2022 11:37:38 +0000

This challenge gives us a list of start & end co-ordinates and asks us to count the intersections. Looking at the input, it seems that all the co-ordinates are less than 1000. For part 1, we are ignoring co-ordinates which aren't horizontal or vertical.

My strategy is to map each start & end co-ordinate into a set of points. So (1,1) -> (1,3) gets transformed into list containing (1,1), (1,2), (1,3). I will then map that list of list of co-ordinates into a Map of co-ordinates and a count. In type signatures:

type Coord = [number, number]
type Line = [Coord, Coord]

toCoords:: Line -> List Coord
countIntersections:: List Coord -> Map (Coord, number)

Edit: I spent a lot of time trying to write a range function and went down a generator function rabbithole. I also goofed up trying to make the countIntersection function work with a Set instead of realising later that what i really needed was a Map.

Edit 2: So exploding out each line into an array of Coords is not good for the computer. Even though the above approach works for the example, the input is simply too large. My next approach is to fold over the input array so that the JS GC can get rid the exploded array for each line.

Edit 3: I suspect that the export declare const upsertAt: <K>(E: Eq<K>) => <A>(k: K, a: A) => (m: Map<K, A>) => Map<K, A> function is causing a bit of grief with performance. I think that the process of making this a pure function involves taking in a map, making an edit and then recreating the entire map which is causing a severe slow down.

Edit 4: I give up using a non-standard key requiring an Eq instance to figure out the difference between the keys. I'm going to stringify the coord and use that as the key.

-- Part 2
Part 2 asks us to take into account lines which aren't horizontal or vertical. This is a fairly easy addition.

https://codesandbox.io/s/quizzical-raman-lz0yx?file=/src/index.ts

Advent of code 2021 - day 4

Derp — Wed, 29 Dec 2021 04:15:59 +0000

Part 1:

We are playing simultaneous bingo where we have an array of numbers being called out as well as several matricies of bingo cards. We then need to identify which matrix has the bingo and sum up the remaining uncalled numbers.

So whenever a new number is called out, for each board, we Either get a Incomplete board or a Bingo Board. This translates to a function signature of number -> Incomplete Board -> Either (Bingo Board) (Incomplete Board). Using sequence we can turn our array of Eithers into Either a Bingo Board or an array of Incomplete Board. sequeunce:: Monad m => [m a] -> m [a]

There were two things that tripped me up in part 1 of this challenge though, the first was the parsing of the input. In previous challenges, I did it manually via search/replace and regex to turn it into arrays or what not. With this challenge, i accidentally chopped off a few digits in my example array causing the wrong answer to show up. Thankfully, I created a show function for debugging which enabled me to pick this error up quickly.

The second thing which tripped me up was the signature of fold
export declare const fold: <E, A, B>(onLeft: (e: E) => B, onRight: (a: A) => B) => (ma: Either<E, A>) => B. I had previously used identity as the onLeft function, however that sets the return type B and this caused a type error when i returned an Either for my onRight function. After realising my error, I returned an Either for my onLeft function.

E.fold( (complete) => E.left(complete), (incompletes) => play(rest)(incompletes) )

-- Part 2
Instead of returning the first bingo board, we want to return the last bingo board. We used sequence in part one which eagerly evaluates the first Left. Now in Part 1, sequence works because we stop immediately when we have found our winning bingo game so the return type of Either Complete Incomplete [] makes sense. However in part 2, it is not one or the other, we need both until we finish going through all the bingo numbers to find the last winning bingo board. Hence we need a return type of (Option<(number, Complete)>, Incomplete[]) representing the last winning bingo number and bingo board and the remaining list of incomplete boards. (This thought occurred to me several days later).

My strategy is to create a playLast function with the signature

  playLast:: number -> Incomplete[] -> (Option<(number,Complete)>, Incomplete[])

playLast also has the interesting situation where you might have several winning bingo games at the same time. To tackle this, I partitioned the partitionMap function which has as similar signature to partitionEithers:: [Either a b] -> ([a], [b]). I then return the head of the Completed games.

When reducing over my bingo numbers, I needed to figure out a way of joining my two Option<(number,Complete)> together such that the last Some won. To do this, I created a Monoid over Options

const getLastSome = O.getMonoid<any>(S.last());

Note the required to make it work as without it as without it, typescript substitutes never into there and it won't work with any Options.

Also sometimes the typescript compiler complains unless you use pipe.

https://codesandbox.io/s/jolly-flower-5o78i?file=/src/index.ts

Advent of code 2021 - day 3

Derp — Wed, 15 Dec 2021 12:37:10 +0000

https://adventofcode.com/2021/day/3

Day 3 wants us to calculate the most common bit for each index value in a list of strings. We will then turn that string into binary and do some mathematical operations with it. Ie

Will turn into 10110 which is 22 in decimal.

To tackle this, I am going to reduce the binary string array into a count of how many 1s for each position. So using the above example, that would reduce down to [7,5,8,7,5]. Since I also know the length of the array, if the count is larger than length/2 then I know that binary value for that index should be 1. From there I can work out the binary string and finally the decimal value.

Part 2 is a bit trickier. Instead of a single pass through the array, it requires us to recursively reduce the array by:
1) Start from the first position
2) If the array only has one element, this is the value
3) From the existing array, look at the most common bit in the current position
4) Filter the array to only include the elements that have that bit value in that index
5) Go back to 2) with the remaining array and increment the position by one.

This problem is well suited for a recursive function.

https://codesandbox.io/s/gracious-leaf-qjotm

Advent of Code 2021 - day 2

Derp — Mon, 13 Dec 2021 12:50:12 +0000

https://adventofcode.com/2021/day/2

Day 2 appears to be a parsing problem. So given

forward 5
down 5
forward 8
up 3
down 8
forward 2

We want to increment the X co-ordinate when going forwards and either increment the Y co-ordinate when going up or down.

To solve this, I am first going to map my strings into tuples representing the change in X or Y. So down 5 gets translated into (0, -5). I am also going to create a monoid under sum and fold over my tuple array to get my final change in X and Y.

-- Part 2
This introduces an aim concept. To solve this, I am re-using the tuple mapping from part 1 and I will need a reducing function that takes in a current [horizontal, depth, aim] and a [forward, updown] tuple and produces a new [horizontal', depth', aim'] tuple.

https://codesandbox.io/s/reverent-fast-ytbx3

Advent of Code 2021 - day 1

Derp — Sun, 12 Dec 2021 22:16:38 +0000

https://adventofcode.com/2021/day/1

Given a list of numbers, we are asked how many times the next number in the list is larger than the previous. Ie

199 (N/A - no previous measurement)
200 (increased)
208 (increased)
210 (increased)
200 (decreased)
207 (increased)
240 (increased)
269 (increased)
260 (decreased)
263 (increased)

This can be solved by reducing over the array returning back a pair of (lastNumber, count) in the reduction function. For the starting condition, I want to use Number.NaN to ensure that I do not increase the count for the first iteration.

-- Part 2
This time, instead of measuring the difference between individual measurements, we are now measuring a sliding window of three values. Ie in the first example, we measure whether [199, 200, 208] is larger than [200, 208, 210]. Since the only difference between these two frames are the numbers at the front and the end, I am going to use a comparison function that takes in four numbers and compares the first and last numbers which should tell me if there is an increase or not. I will then move my sliding window of four over the original list.

https://codesandbox.io/s/amazing-satoshi-zbcs7?file=/src/index.ts

Requirements engineering

Derp — Wed, 17 Nov 2021 00:37:06 +0000

Disclaimer: I am not a professional business analyst

I have been involved in a few projects and I have always followed a similar pattern into getting them to completion. I have broken down the process into different phases and although this may initially read like waterfall, in reality, it is a lot more collaborative as we try and find the hidden requirements through conversations rather than documentation.
This post is an effort to jot down a few notes and hopefully give readers a few things to think about.

Problem Discovery

· Understanding the constraints of the problem both technical and social
· Discovering the different stakeholder(s) requirements both explicit and contextual

We can't build the right thing if we do not understand the context in which the thing has to exist in. This can be both technical and social. Technical questions to ask:

Who's going to use this?
What other software are they familiar with?
If we build it, how will it be deployed?
Who will maintain it going forward?
What technology stacks are the future maintainers comfortable with?
Have the future maintainers been told that they will maintain it yet? Did they agree?

Social questions to ask:

Which organisation(s) are funding this?
Why are they funding this?
Who will be the primary decision maker(s)?
What are the main motivators for the primary decision makers(s)? Keep in mind that the motivations of the human decision makers are different to the broader motivations of an organisation.

Solution proposal

· Iteratively propose and refine solutions with the client usually with wireframes
· Arrive at a loose, shared conceptual agreement of what will be delivered

Hopefully after the problem discovery phase, you will have identified the primary decision maker(s). The goal of this stage is to reach a loose, shared conceptual agreement of what will be delivered and my favorite way of reaching that is through low fidelity wireframes using Pencil.

There are a few benefits to creating wireframes. Firstly, you can map it against your existing or hypothetical API to see whether or not your things is possible or not. Secondly, you can show them to clients and in seeing something visual, they can much more easily where you have missed key concepts and why it won't work for their use case. As it is easy to iterate on wireframes, you can incorporate their feedback to come up with new designs to meet their use cases. This has the very very important effect of making the client feel listened to which goes a long way to establishing trust. Furthermore, as the client sees their changes make their way onto the wireframes, they gain incrementally more ownership of it which may help increase the emotional attachment they have to the project.

After a few iterations, if there are no more major changes, then you can be fairly certain that you have reached the "loose, shared conceptual agreement" goal and the project can move onto the next phase.

Project delivery

· Set up architecture based on the skills/interests of the team
· Incrementally deliver and demonstrate developed functionality
· Negotiate and prioritise additional or changed client requirements as they are discovered

When choosing your technology stack, the most important thing to consider are the skills and interests of your team. I usually like to follow a very loose scrum process where we have standup to ensure that people aren't blocked for more than a day.

Post project

· Document lessons learnt
· Advise on possible futures for the delivered project seeding future collaboration opportunities

After the end of the project, it is important to hold a retrospective style meeting and to document the lessons learnt. By writing these down, it both increases your understanding of what went well or didn't go well and makes it available for other people to view thereby increasing the knowledge within your organisation.

It may also be helpful to have a more imaginative session with the team and the client where you muse on possible futures of your project. Although the money may not be available now, these seeds may fruit into future collaboration opportunities.