Forem: Yuriy Bogomolov

#MonadicMonday compilation: July

Yuriy Bogomolov — Mon, 15 Jul 2019 06:36:00 +0000

Recently I started a small activity in Twitter called #monadicmonday – each Monday I post a thread about some FP stuff which is useful and is easy to start using right away. Each month I will be doing a compilation for those who prefer to read long articles.

Episode 12: Futures

Welcome to twelfth episode of #monadicmonday! Today I want to talk about a Future – a concept of asynchronous lazy task, which is a far better replacement for an eager Promise. Due to their laziness, futures support cancellation, racing, parallelism and resource safety out of the box. The best library I've seen and used for Futures is fluture-js.

Fun fact: in Scala world Future is not a monad, but something akin to JS's Promise – i.e., eager referentially non-transparent construct. Instead, it's far better to use IO (cats), Task (monix & scalaz) or ZIO (zio) to achieve the described benefits of today's topic.

In fp-ts & StaticLand terminology, Future could be described as Task>. But there's much more to it than my simplification implies. So let's dive in!

You have quite a bunch of ways to create a Future. For full list of method go see https://github.com/fluture-js/Fluture/tree/11.x#creating-futures
Please note that due to TS's way of type inference I have to provide type arguments manually:

import * as F from 'fluture';

const f1 = F.of<Error, number>(42);
const f2 = F.node<Error, Buffer>((done) => fs.readFile('./foo.txt', done));
const f3 = F.attempt<Error, void>(() => fs.writeFileSync('./bar.txt', 'Hello!'));
const f4 = F.tryP<Error, string>(async () => {
  const file = await fs.promises.readFile('./foo.txt');
  const text = file.toString();
  await fetch('https://example.com', { method: 'POST', body: text });
  return text;
});
const f5 = F.after<Error, number>(500, 42);

Why Future is bright and cool? Well, first of all, it is a pure value – i.e., the Future will not be running until you call fork or promise methods:

const f3 = F.attempt(() => fs.writeFileSync('./bar.txt', 'Hello!')); // will not create a file...
f3.promise(); // ...up until this time!
f3.fork(console.error, console.log); // ...or this time :)

Second, Futures support cancellation, making timing out requests a breeze:

const fetchF = F.encaseP(fetch); // convert `fetch` into a Future-returning function

const getUserLogin = fetchF('https://api.github.com/users/YBogomolov')
  .chain((res) => F.tryP(() => res.json()))
  .map<string>((user) => user.login);

getUserLogin
  // all we need to do for introducing a timeout:
  .race(F.rejectAfter<Error, string>(1000)(new Error('timeout')))
  .fork(console.error, console.log);

Third, Futures are stack-safe:

const add100000 = function self(x: number): F.FutureInstance<never, number> {
  const mx = F.of<never, number>(x + 1);
  return x < 100000 ? mx.chain(self) : mx;
};

add100000(1).fork(console.error, console.log); // => 100001

Fourth, Futures are monads, bifunctors and alternatives, so you can use all the machinery you've used to:

getUserLogin // let's pretend we get a login somehow...
  .alt(F.of('admin')) // ...or fall back to 'admin'
  // then let's search for that user:
  .chain((login) => fetchF(`https://api.github.com/search/users?q=${login}`).chain((res) => F.tryP(() => res.json())))
  .chain((users) => users.total_count > 0 ? F.of(users.items[0]) : F.reject(new Error('not found')))
  // ...and get his/her repositories:
  .chain((user) => fetchF(user.repos_url).chain((res) => F.tryP(() => res.json())))
  // ...and simplify our container, throwing away redundant info:
  .bimap((reason: Error) => reason.toString(), (repos) => repos.length)
  .fork(console.error, console.log); // => 30

Finally, fluture has a nice touch – so kind of imitation for Haskell's do notation, available by names do and go. As a side note, I must admit that attempts to write types for its results are quite cumbersome, but TS can infer them flawlessly:

const calc200002 = F.go(function*() {
  const res: number = yield add100000(1);
  const res2: number = yield add100000(1);
  return res + res2;
});

calc200002.fork(console.error, console.log);

So as you can see, Futures are a very powerful functional concept, and working with them is really easy thanks to the awesome fluture-js! I encourage you to read its documentation and examples, and try it in your projects – it's battle-tested and highly performant: https://github.com/fluture-js/Fluture/tree/11.x

This concludes my short introduction to programming with Futures. As usual, all code examples are available at https://github.com/YBogomolov/monadic-mondays

Episode 13: Property-based testing

Welcome to thirteenth episode of #monadicmonday! Today we'll talk a bit about property-based testing using the awesome library fast-check.

When you write a unit test, you'd normally do something like this:

import { expect } from 'chai';
import { left, right } from 'fp-ts/lib/Either';

import f from './function-to-test';

it('should return a Right<string> for given number', () => {
  const mockInput = 42;
  const mockOutput = 'foobar';

  expect(f(mockInput)).to.deep.equal(right(mockOutput));
});

it('should return a Left<Error> if input is not a number', () => {
  const mockInput = 'aaaa';
  f(mockInput).fold(
    (e) => expect(e)
      .to.be.an.instanceOf(Error)
      .and
      .to.have.property('message').include(mockInput),
    () => expect.fail('should not be Right'),
  );
});

However, this barely tests the logic of your module. You have to write a lot of unit tests to cover all boundaries, handle possible type errors and so on. For example, how many of English-speaking programmers test their string-accepting functions for Cyrillic or kanji inputs?

And if you wrote some tests, you know how difficult it is to prepare good test set for your mocks. Usually you end up with custome mock generators or a set of giant JSONs which contain pre-generated data. And still there's a chance that you've missed something.

So property-based testing to the rescue. Its idea is rather simple: we assert that some property of the tested algorithm holds, and the testing framework generates sample random data to prove or disprove this assertion.

For TypeScript & JavaScript there's a nice library called fast-check: https://github.com/dubzzz/fast-check. It integrates well with mocha, jest, ava, tape and jasmine. Let's see how we can write property-based tests.

We start with rather simple test: "check that any string contains itself". Something akin to Identity for strings:

import * as fc from 'fast-check';

describe('Identity laws for string', () => {
  it('any Unicode string should contain itself', () => {
  //runner:   property:   arbitrary:              actual assertion:
    fc.assert(fc.property(fc.fullUnicodeString(), (str) => str.includes(str)));
  });

  // this one has faulty logic, so it should fail and provide you with a counterexample:
  it('should fail with counterexample', () => {
    fc.assert(fc.property(fc.fullUnicodeString(), (str) => str.trim().includes(str)));
  });
});

Running these tests will give you a counterexample for the faulty logic, so you can use it to debug the test subject and fix the bug:

> jest ./src/episode-13

 FAIL  src/episode-13/fc.test.ts
  ● Property tests › Identity laws for string › should fail with counterexample

    Property failed after 17 tests
    { seed: -976548053, path: "16", endOnFailure: true }
    Counterexample: [" "]
    Shrunk 0 time(s)
    Got error: Property failed by returning false

    Hint: Enable verbose mode in order to have the list of all failing values encountered during the run

       9 | 
      10 |     it('should fail with counterexample', () => {
    > 11 |       fc.assert(fc.property(fc.fullUnicodeString(), (str) => str.trim().includes(str)));
         |          ^
      12 |     });
      13 |   });
      14 |

I would not include the fast-check library in Monadic Monday episode if it didn't had some monads up its sleeves :)
Arbitraries are acutally monads, so you can use their sequential properties to chain several arbitraries and build a composite object.

Let's build a property test for this program: "if two users are older than 18 and have some common likes, pair them. Otherwise, report found errors".
The implementation will be as simple as:

type Like = 'cars' | 'cats' | 'football';

interface User {
  login: string;
  age: number;
  email: string;
  likes: Like[];
}

const validate = (user: User): Either<Error, User> =>
  user.age < 18 ? left(new Error(`User ${user.login} must be over 18`)) : right(user);

const match = (user1: User, user2: User): Either<Error, [User, User]> => {
  // if both users have at least something in common:
  if (user1.likes.some((like) => user2.likes.includes(like))) {
    return right([user1, user2]);
  }

  return left(new Error(`No common likes for ${user1.login} and ${user2.login}`));
};

Let's start with writing a test for validation. First, we need a custom Arbitrary – generator for the User type:

const userArbitrary = fc.unicodeString().chain(
  // any Unicode login:
  (login) => fc.integer().chain(
    // any age – from -2^32 to 2^32, you'll see why in a moment:
    (age) => fc.emailAddress().chain(
      // any email address:
      (email) => fc.subarray<Like>(['cars', 'cats', 'football']).map<User>(
        // and `likes` could only contain `Like` type:
        (likes) => ({ login, age, email, likes }),
      ),
    ),
  ),
);

Now we can check that validate function passes through only valid users, and reports age errors for invalid:

it('should validate a user', () => {
  fc.assert(fc.property(userArbitrary, (user) => validate(user).fold(
    (e) => {
      expect(e).to.be.an.instanceOf(Error).and.to.have.property('message').include(user.login);
    },
    (validatedUser) => {
      expect(validatedUser).to.deep.equal(user);
    },
  )));
});

Note that due to userArbitrary is able to generate users of any integer age, we can test validate on the full range of possible values.
Now we can write a test for match function, using precondition to filter the arbitraries:

it('should match two valid users', () => {
  fc.assert(fc.property(userArbitrary, userArbitrary, (user1, user2) => {
    fc.pre(user1.age >= 18 && user2.age >= 18);

    array.sequence(either)([validate(user1), validate(user2)]).fold(
      (vErr) => {
        expect(vErr.message.includes(user1.login) || vErr.message.includes(user2.login)).to.be.true;
      },
      ([u1, u2]) => match(u1, u2).fold(
        (pairError) => {
          expect(pairError.message.includes(user1.login) || pairError.message.includes(user2.login)).to.be.true;
        },
        (pair) => {
          expect(pair[0]).to.deep.equal(u1).and.deep.equal(user1);
          expect(pair[1]).to.deep.equal(u2).and.deep.equal(user2);
        },
      ),
    );
  }));
});

The real spot where property-based testing shines is when you need to check that your algorithm holds up to algebraic laws – like laws for Functor or Monad.
Say, we want to ensure that Either holds functorial laws. Note that I generate two random functions and verify that their composition is preserved:

import * as fc from 'fast-check';
import { left, right } from 'fp-ts/lib/Either';
import { compose, identity } from 'fp-ts/lib/function';

describe('Either', () => {
  describe('Functor laws', () => {
    it('should preserve identity morphism', () => {
      // for any `x`, `either(x) map id` is isomorphic to `either(x)`:
      fc.assert(fc.property(fc.anything(), (x) => {
        expect(right(x).map(identity)).toEqual(right(x));
        expect(left(x).map(identity)).toEqual(left(x));
      }));
    });

    // for any `x`, `either(x) map f map g` is isomorphic to `either(x) map (g ∘ f)`:
    it('should preserve composition of morphisms', () => {
      fc.assert(fc.property(fc.anything(), fc.func(fc.anything()), fc.func(fc.anything()), (x, f, g) => {
        const g_o_f = compose(g, f);

        expect(right(x).map(f).map(g)).toEqual(right(x).map(g_o_f));
        expect(left(x).map(f).map(g)).toEqual(left(x).map(g_o_f));
      }));
    });
  });
});

So there you have it, a bried introduction to property-based testing using fast-check (https://github.com/dubzzz/fast-check). I encourage you to read its documentation, which is thorough and nicely written.

This concludes my short introduction to property-based testing. As usual, all code examples are available at https://github.com/YBogomolov/monadic-mondays

Episode 14: Final

Welcome to fourteenth episode of #monadicmonday! Today's episode will be very short, as I decided to finish the series for now.

First of all, I would like to thank all my readers and followers – your feedback and support was great, and I'm really astonished how many people had supported my efforts with likes & retweets.

I wanted Monadic Mondays to be a bite-sized pragmatic stories about useful monad-ish structures, tips and tricks which you can use in your day-to-day coding. These intentions meant that I needed to focus on quite simple things. On the other hand, I didn't want to start from the ground up and describe what a Monad is, or what an Applicative is, or what does it mean to "fold" something… And finally I was limited by TypeScript's type system, which was seriously nerfed down in v3 comparing to v2.

So basically up to now I covered almost all topics I wanted and I could express in TypeScript. I got into a writer's block, and need some time to recover. I plan to occasionally write an article or two, but most likely they will be published separately from this hashtag.

I want to express my sincere gratitude to people who inspired me and provided feedback about the episodes. This means a lot, and fills my heart with happiness.

See you around! :)

Typesafe Frontend Development

Yuriy Bogomolov — Sun, 07 Jul 2019 14:02:39 +0000

This is a transfer of my article originally posted on Medium.

Preface

Tony Hoare at QCon'09 apologized for creating the most disasterous invention in computer science – null reference exception:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. {...} This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

My daily job involves working with the language which has not one, but two places of possible null refs – null and undefined. I'm talking about JavaScript. Although I do love this pet project of Brendan Eich for its sloping learning curve, expressiveness and rich tooling, I cannot allow myself or my colleagues to use it in its 'pure' form. The price of dealing with errors like undefined is not a function, cannot call method 'foo' of null and so on is just too high. I cannot risk my customer's money and suggest developing a product with such support costs.

As I am diving deeper and deeper into computer science, category theory and homotopy type theory, I want my code:

to be reasonable about,
to execute with runtime safety,
to have good performance,
and to be easy to refactor and support.

Toxicity warning! However, on the other hand, there exists free market and obvious lack of qualified specialists. I might be a little bit biased here, but, unfortunately, most programmers are not engineers and not even closely mathematicians. Still, I need to have a way of achieving my mission and spreading my vision via creation of qualified resources from the market's raw material. I want programming world to be a better place.

Given those presuppositions, I have chosen strict functional programming as my preferred approach and TypeScript as my main language. It has best of the both worlds: it's quite popular (just read success stories from companies like Facebook), and has enough perks to satisfy my demands. At least, for now.

What is type safety?

Speaking from a formal point of view, type safety is determined by two properties of the semantics of the programming language:

(Type-)preservation – "Well typedness" of programs remains invariant under the transition rules of the language.
Progress – A well typed (typable) program never gets into an undefined state where no further transitions are possible.

If translated from academic language, type safety is making use of information about our data in the compile time to prevent errors in runtime.

And the last point.

– Snake, why are we still here? Just to suffer?..

Kazuhira Miller, Metal Gear Solid V

I am convinced that the developer who follows The Rules Of Type Safety should feel comfortable and use compiler as his best friend & main tool. But if the developer wants to write non-safe code, he must suffer. His "wrong" code should not compile, or his library design should not be easy to use with the rest of the system – which inevitably will lead to complaints from his colleagues, and then to heavy refactoring.

Jokes aside, I really do want to achieve the state where incorrect programs could not be expressed at all. This involves usage of several techniques and patterns.

Typesafe Patterns

N.B. As I am using the incredible fp-ts package from Giulio Canti, I would stick to using its terminology.

Use `const` to allow easy reasoning

As you probably know, nowadays JavaScript has three ways of declaring a variable: var, let and const. The former demanded from a programmer to keep in his head all hoisting rules, so in ES6 TC39 committee introduced let and const keywords, which – what a surprize! – don't hoist. From those two only const allows us to reason about our code with confidence. Let me explain with a quick example:

// Line 48:
let user = await getUser();
// somewhere around line 74:
user = await getAdmin();
// Line 153:
return user; // Oops! We think that we return a user here, but it's actually an admin

Can someone with enough confidence say that user variable wasn't reassigned between lines 48 and 153, without looking at those lines and following all method calls? Consider this instead:

// ...
// Line 48:
const user = await getUser();
// Line 74:
user = await getAdmin(); // TS2588: Cannot assign to 'user' because it is a constant.
// Line 153:
return user; // No way this will compile

Much better.

Rule of thumb: always use const.

Avoid `null` and `undefined`

I started this article with a Tony Hoare's quote not just for the sake of appearing literate. I really, really hate working with nulls in JS and TS. Thankfully, functional programming has given us an awesome tool just for this case – an Option monad (also known as Maybe).

A quick example:

// Bad:
function bad(registry: Registry<Module>): TransformedModule[] | null {
  const modules = getModules(registry); // => null | Module[]

  if (modules.length === 0) { return null; }

  return modules.map(doStuffWithModules);
}

// Good:
function good(registry: Registry<Modules>): Option<TransformedModule[]> {
  const modulesO = getModulesO(registry); // => Option<Module[]>
  return modulesO.map((modules: Module[]) => modules.map(doStuffWithModules));
}

So a rule of thumb #2: if you need to introduce an entity which value can be absent in any time of program's execution, use Option to encode this idea.

Avoid throwing exceptions and side effects

You know what's worse than returning a null? Throwing an exception. There's no way in 'traditional' JS/TS to mark a method with a warning that it may blow up. In plain ol' Java we have the throws keyword, but it leads to another set of issues and (in my opinion) should be banned in any production code as well.

So what do we do instead? Use an another tool from our bag of monads – Either monad and its successors, of course! It encodes a computation which may yield a business result or fail with a recoverable error. I cannot stress enough how this is important. If you are familiar with Scala ecosystem (and even if you're not), – go see an incredible article by John De Goes about bifunctor IO in ScalaZ. John describes motivation for this approach very well.

On the frontend side it's painful to introduce an IO monad, as the most of the frameworks/libraries like React/Angular/Vue are written in traditionalistic OOP-esque approach, and require quite a lot of boilerplate to introduce this concept. However, using an Either in any part of the code is completely unintrusive and requires no changes to the code of the framework or library.

By the way, I would like to recommend a great module called remote-data-ts, which encodes the state of a network request. I've built an entire rendering system for my current customer using this approach, and developers are happy with it. Go check it out!

To be honest, I've created my own subtype of RemoteData called ApiData, which encodes six states instead of just four, but this is a specific case of my customer and easily could be a topic for another full article.

Compute as much as possible in compile time

This is one of my favorite topics in functional programming – typelevel coding! It means we encode our data types in such way that they represent only valid states of the program, and incorrect program just won't compile!

I often say that I use TDD – Type-Driven Development. It is obviously a joke, but it's only a half-joke. Typelevel programming forces you to think of values and types in the same way, and your coding starts with designing a flow of types – and when it's done, your program literally writes itself, as you just need to ensure that types match. Using this approach, you will no longer see the difference between a function operating on values and a generic type operating on type parameters, which makes your reasoning even more clear and expressive.

Using this technique requires quite a lot from the type system of the chosen language. I still dream about times when I can write production code in dependently-typed languages like Agda or Coq. But TypeScript still has some aces up its sleeve – due to its structural type system we can express types like NonEmptyList:

type NonEmptyList<T> = T[] & { 0: T };

Of course, this doesn't make TypeScript a dependently-typed language, but it is something :)

So, let me share an example – it may be more clear than any description:

// Conditional: if `T` extends `U`, then returns `True` type, otherwise `False` type
type If<T, U, True, False> = [T] extends [U] ? True : False;

// If `T` is defined (not `never`), then resulting type is equivalent to `Yep`, otherwise to `Nope`.
type IfDef<T, Yep, Nope> = If<T, never, Nope, Yep>;

// Makes keys `K` required:
type With<T, K extends keyof T> = Pick<T, Exclude<keyof T, K>> & { [P in K]-?: T[P] };

// For typelevel tests:
const assertType = <T>(expect: IfDef<T, T, never>): T => expect;

/*
 * Actual usage
 */

// Our tested type which makes its parts optional or required, depending on passed parameters:
type ComponentProps<Routes extends string, Permissions extends string> =
  IfDef<Routes, { routes: Record<Routes, Lazy<string>>; }, { routes?: never }> &
  IfDef<Permissions, { permissions: Record<Permissions, Lazy<boolean>>; }, { permissions?: never }>;

// Code of the test using `jest`:
type Routes = 'goHere' | 'orHere';
type Permissions = 'permissionToDo' | 'permissionToBe';
type Props1 = ComponentProps<Routes, Permissions>;
type Props2 = { foo: 'bar' | 'baz';  routes: Routes; permissions: Permissions };

type Assertion1 = If<Props2, Props1, true, never>;
expect(assertType<Assertion1>(true)).toBeTruthy();

Finally Tagless, Partially Evaluated

This is just a design pattern, but its importance is incredibly high. Using tagless final encoding, the developer creates a custom eDSL, in which incorrect program states are impossible to express. If you want to dive deep in the math & original design, please refer to the initial paper by Oleg Kiselyov et al..

I created a sample gist of implementing TF in TypeScript, so go check it out for the details!

BTW, some people suggested to call 2017 a year of Final Tagless, and this means a lot. However, every buzz thing sooner or later comes to its end. On 25th of February John De Goes will postulate his vision of the next big thing in FP in Scala. I'm quite excited to see the results.

Conclusion

I hope my article gets you interested in a topic of functional programming and typelevel approach. It really broadens the horizons of any programmer, as well as enables businesses to have a reliable, performant, supportable software. I hope to see this approach being spread even further when WebAssembly becomes widely available, and we as frontend engineers will have more awesome tools at our disposal. Who knows, maybe, even dependently-typed languages :)

Please ping me back at @ybogomolov in Telegram, @YuriyBogomolov in Twitter or via yuriy.bogomolov@gmail.com.

#MonadicMonday compilation: June

Yuriy Bogomolov — Sun, 07 Jul 2019 13:15:01 +0000

Episode 10: Reasons to choose FP

Welcome to tenth episode of #monadicmonday! I would like to make today's episode lite and codeless, and talk about reasons to chose FP, and how to show its viability to the customers.

When you make decisions as an engineer or architect, you have to consider a lot of things when chosing programming paradigm. It's not a big secret that functional approach is far less popular than imperative style, and when you choose it, you have to deal with consequences.

What these consequences might be?

First of all, increased complexity of on-boarding for developers. Unless you hide all functional stuff somewhere under the hood, your developers have to learn what a functor, a monad, an applicative, etc. are and how they are used. And even that isn't a guarantee that your code base will follow best functional practices. It is still possible to write imperatively using monads&stuff, and think that you're "doing FP".
Second, if you bid on hiring already familiar with FP devs from the market, be ready to close your open positions for months, unless your primary language is (semi)pure functional one like Haskell/PureScript/etc. And if you expose the hardcore bits (say, like recursion schemes or freer monads) to the surface, chances to find quickly an individual who truly understands such topics are very little.
Third, amount of pratical materials about FP is far lesser than about any other approach. Yes, we have a lot of yet-another-monad-tutorial, but there's little to none materials about functional design patterns, mental models and problem decomposition examples. Nowadays the situation is slowly changing, and I hope to stand among those who finally change it for good.

But what benefits are we gaining when we make a decision to write in a functional paradigm?

Equational reasoning. When we program with pure functions, monads, algebraic data types, we gain tremendous power of equational reasoning – ability to substitute equals by equals in all contexts. This allows ut to check the correctness of our programs "in mind compiler", and be confident about our understanding of the code. I must admit, this requires additional efforts and in many cases support from the language as well.
Modularity and composability. This could be achieved in other styles, as well, – say, in traditional OOP. Low coupling & high cohesion require your code to be modular and isolated, which often leads to good composability. However, only in functional style these characteristics of code are a cornerstone to the whole approach.
Testability. Naturally follows from p.2. If your code is modular, it's very easy to mock parts of it and test them independently. Please check out fifth episode about Tagless Final and the example of testing the program in that style: https://twitter.com/YuriyBogomolov/status/1124244215620341760
Robustness. I mean robustness in mathematical sense – if your code follows mathematical laws like associativity, transitivity, idempotence, totality, it's far less likely that it contains errors. This doesn't mean you don't need tests or you're allowed to write sloppy, but when a compiler backs you up, it's a good feeling.
Proofs of correctness. I'm looking over a horison here, but using math apparatus of type theory and its successors (like HoTT) it is possible to build automatic proofs of correctness of the system you're building. Using dependently-typed languages like Coq and Agda it is possible not only to express the logic logic of your application, but also prove that it doesn't contain flaws and mistakes. Dep-types languages still have a long road ahead of them to be truly useful (and usabe) in production, but it's only the beginning.

So how might you communicate to a customer when you're defending your decision to use FP? First of all, you have to answer the simple question: what is the main pain this customer is facing? Is his/her code is tightly coupled and poorly testable? Is it not highly reusable? Does it have a lot of runtime errors like NPE or 'undefined is not a function'? Rank those pain points and build your statements around the solutions to those. Also, be fair to yourself and don't bring FP only for sake of brining FP :) Always consider the people you'll be working with, the overall situation with the codebase and the environment you'll be working in. Talking about FP and migration to Scala with a customer who uses JavaEE in all solutions for 20+ years is not a very bright idea. However, if you're building a frontend app, you can ops to chose TypeScript – and convince the customer that it's a viable decision by showing that is leads to lesser number of bugs per line, more development convenience and ease of transition for pure JS developers. Almost in any language it is possible to use bits of FP, and it's up to you to find the fine balance of FP and non-FP stuff in your solution.

Join the discussion! I would love to hear about your experience with "selling" FP to the customer, lessons learned and transition approaches.

Episode 11: Kleisli arrows

Welcome to eleventh episode of #monadicmonday! Today we'll talk about Kleisli arrows, and I'll introduce my small project called "kleisli-ts".

Function composition is a cornerstone of functional programming. Having f :: A -> B and g :: B -> C, we compose g . f and obtain h :: A -> C. This works well when we are speaking about total pure functions. But when we interact with the real world, problems appear. Real World™ is asynchronous, impure and seems to be a total opposite of what we want it to be.

The usual approach involves monads in all their glory – IO, Task, Reader, with an apex in form of bifunctorial ZIO (see https://twitter.com/YuriyBogomolov/status/1125403292530507776). Probably, you know the main problem with monads – they don't compose, at least in generic way: https://www.slideshare.net/pjschwarz/monads-do-not-compose

However, there's another way of writing effectful functions that compose well, and this way involves Kleisli arrows.

Kleisli arrows are named after Swiss mathematicial Heinrich Kleisli, who worked in a field of category theory and homotopy theory. These arrows are functions in form f :: A -> F B, having F as a context of our computation. In TypeScript we can write them down as a type with three parameters, using fp-ts notation for HKTs:

// should be interpreted as: (a: A) => F<B>
type Kleisli<F extends URIS, A, B> = (a: A) => Type<F, B>;

Having functions of such form, we can compose them if we have a monad for the F kind (or even narrower: if we have a Chain):

const composeK = <F extends URIS>(F: Chain1<F>) =>
  <A, B, C>(f: Kleisli<F, A, B>, g: Kleisli<F, B, C>): Kleisli<F, A, C> => 
    (a: A) => F.chain(f(a), g);

We can defined some useful combinators, such as zipWith for zipping two Kleisli arrows, or ifThenElse to organize the conditional flow:

const zipWith = <F extends URIS>(M: Chain1<F>) =>
  <A, B, C, D>(l: Kleisli<F, A, B>, r: Kleisli<F, A, C>) =>
    (f: (t: [B, C]) => D): Kleisli<F, A, D> =>
      (a) => M.chain(l(a), (b) => M.map(r(a), (c) => f([b, c])));

const ifThenElse = <F extends URIS>(M: Chain1<F>) =>
  <A, B>(cond: Kleisli<F, A, boolean>) =>
    (then: Kleisli<F, A, B>) => (else_: Kleisli<F, A, B>): Kleisli<F, A, B> =>
      (a) => M.chain(cond(a), (t) => t ? then(a) : else_(a));

This may look like a tongue-in-cheek replacement – after all, we are still using monadic chaining for passing the values around, – but in reality this approach allows you to think about your code in a different way, and what's more important, Kleisli arrows allow some optimizations to be done, mitigating allocation overhead of monadic wrappers.

I would like to give credits to awesome talk at LambdaConf'18 by @jdegoes about KleisliIO: https://www.youtube.com/watch?v=L8AEj6IRNEE. You can find benchmarks and some implementation details there. I went a bit further, and with John's approval ported KleisliIO to TypeScript with some minor enhancements like Bifunctor instance: https://github.com/YBogomolov/kleisli-ts

I should admit that after some time of using bifunctor IO (IOEither, TaskEither in fp-ts, ZIO in Scala) I find it's expressiveness much bigger than plain ol' IO. That's why kleisli-ts uses it as a main typeclass.

Let's look at the example. If you recall fifth and sixth episodes, we wrote a random generation app using Tagless Final and ZIO/TIO. Now we can write it using one more approach – with KleisliIO.

We start by obtaining an instance of KleisliIO API for the given monad, in this case – TaskEither:

import { taskEither, tryCatch, URI } from 'fp-ts/lib/TaskEither';
import { getInstancesFor, KleisliIO } from 'kleisli-ts/lib';

const K = getInstancesFor(taskEither);

The distinctive part here is that we describe our computation by composing functions as whole, not by looking at their input and output separately:

// Note usage of `ifThenElse` combinator here:
export const parse: KleisliIO<URI, Error, string, number> =
  K.ifThenElse<Error, string, number>
    (K.liftK((s: string) => {
      const i = +s;
      return isNaN(i) || i % 1 !== 0;
    }))
    (K.identity<Error, string>().chain((s) => K.fail(new Error(s + ' is not a number'))))
    (K.liftK(Number));

// We usually lift impure functions into Kleisli arrows via `liftK` or `impure`/`impureVoid`:
export const generateRandom: KleisliIO<URI, never, number, number> =
  K.impureVoid((lowerBound) => Math.floor(Math.random() * lowerBound + 1));

export const print: KleisliIO<URI, never, string, void> =
  K.impureVoid((message: string) => console.log(message));

As we have to deal with async I/O here, we can utilize convenient pure method, which works with pure monadic computations:

import { createInterface } from 'readline';

export const read: KleisliIO<URI, Error, void, string> =
  K.pure(
    () => tryCatch(() => new Promise<string>((resolve) => {
      const rl = createInterface({
        input: process.stdin,
        output: process.stdout,
      });
      rl.question('> ', (answer) => {
        rl.close();
        resolve(answer);
      });
    }), (e) => new Error(String(e))),
  );

Now interesting part: we can use chaining combinators like andThen or chain to stitch our functions together. Compare with combining pure total functions with compose!

export const getUpperStr: KleisliIO<URI, Error, void, string> =
  K.of<Error, void, string>('Enter random upper bound:')
    .andThen(print)
    .andThen(read);

export const checkContinue: KleisliIO<URI, Error, void, boolean> =
  K.of<Error, void, string>('Do you want to continue?')
    .andThen(print)
    .andThen(read)
    .chain((answer) => {
      switch (answer.toLowerCase()) {
        case 'y':
          return K.of(true);
        case 'n':
          return K.of(false);
        default:
          return checkContinue;
      }
    });

And finally we can write and run our main program:

import { unsafeRunTE } from 'kleisli-ts/lib/unsafe';

export const main: KleisliIO<URI, Error, void, void> =
  getUpperStr
    .andThen(parse)
    .andThen(generateRandom)
    .chain((rnd) => K.of<Error, void, string>(`Your random is: ${rnd}`).andThen(print))
    .andThen(checkContinue)
    .chain((answer) => answer ? main : K.of<Error, void, string>('Good-bye').andThen(print));

unsafeRunTE(main.run());

This concludes my introduction of Kleisli arrows.

That's all, folks. Hope you liked this episode! And stay tuned for July's compilation and next episodes ;)
As usual, all code examples are available at https://github.com/YBogomolov/monadic-mondays

#MonadicMonday compilation: May

Yuriy Bogomolov — Mon, 27 May 2019 11:21:44 +0000

Episode 5: Tagless Final

Welcome to the fifth episode of #monadicmonday! Today we'll look at the famous Tagless Final pattern and its implementation in TypeScript.

If you haven't heard of Tagless Final style (also called "Finally Tagless Interpreters"), here's a brief recap.

Originally this pattern was introduced by Oleg Kiselyov et al. in his paper "Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages": http://okmij.org/ftp/tagless-final/JFP.pdf

TF style is a general method of embedding domain-specific languages (DSL) in a typed functional language. It effectively separates eDSL statements from their interpreters, allowing building a robust extensible applications.

One of the most notable features of TF – it allows building different interpreters for the same eSDL, so you can run your production code on optimizing cache-enabled interpreter, while your tests could be ran using simple Identity interpreter.

Also note that one of functional Scala influencers @jdegoes deprecate TF style in favor of slightly different approach using horizontal effect rotation: https://skillsmatter.com/skillscasts/13247-scala-matters

IMO, TF style is a valid choice for many functional languages like TypeScript. So let's build a small program in this style!

Our program will do the simple thing: it will as a user about random upper bound and return a random number in range [0, bound).

In TypeScript we don't have proper support for higher-kinded types, so we need to use some hacks. So we start with defining an "HKT" synonym which will adhere to Functor and Monad interfaces:

import { Type, URIS } from 'fp-ts/lib/HKT';

export interface ProgramSyntax<F extends URIS, A> {
  map: <B>(f: (a: A) => B) => _<F, B>;
  chain: <B>(f: (a: A) => _<F, B>) => _<F, B>;
}

export type _<F extends URIS, A> = Type<F, A> & ProgramSyntax<F, A>;

Next we'll define a few algebras – sets of operations of type A => F A, which will be building blocks of our eDSL – i.e., expressions we can use to build the final program.

export interface Program<F extends URIS> {
  // Exit the program with some message or code
  terminate: <A>(a: A) => _<F, A>;
}

export interface Console<F extends URIS> {
  // Print a line on some kind of console:
  print: (message: string) => _<F, void>;
  // Read a line from console:
  read: _<F, string>;
}

export interface Random<F extends URIS> {
  // Get next number in [0, upper) bounds:
  nextInt: (upper: number) => _<F, number>;
}

export type Main<F extends URIS> = Program<F> & Console<F> & Random<F>;

Now, when we have these expressive powers, we can express our program. I think of the following logic flow:

App asks for a upper bound
App reads user input
If the input is not a number:
1. App prints a warning
2. App asks if the user wants to continue:
  1. If 'y' -> start over
  2. If 'n' -> print 'Good-bye' and terminate
If the input is a number:
1. App generates a random int
2. App prints this number
3. App asks if the user wants to continue:
  1. If 'y' -> start over
  2. If 'n' -> print 'Good-bye' and terminate

I would like to split the program's logic in small functions to show the core idea of TF style: you can "summon" only those parts of functionality you really use!

const generateRandom = <F extends URIS>(F: Program<F> & Random<F>) =>
  (upper: number): _<F, number> => F.nextInt(upper);

const getUpperStr = <F extends URIS>(F: Program<F> & Console<F>): _<F, string> =>
  F.print('Enter random upper bound:')
    .chain(() => F.read);

const checkContinue = <F extends URIS>(F: Program<F> & Console<F>): _<F, boolean> =>
  F.print(`Do you want to continue?`)
    .chain(() => F.read)
    .chain((answer) => {
      switch (answer.toLowerCase()) {
        case 'y':
          return F.terminate(true);
        case 'n':
          return F.terminate(false);
        default:
          return checkContinue(F);
      }
    });

You may have noticed some "burden" of passing F instance over and over to various functions. This is a price we have to pay in TypeScript. In other languages like Scala such instances are passed implicitly, resulting in a much cleaner code.

With these building blocks we can finally express our main program:

const main = <F extends URIS>(F: Main<F>): _<F, void> =>
  getUpperStr(F).chain(
    (upper) => parse(upper).foldL(
      () => F.print(`"${upper}" is not an integer`),
      (upperN) => generateRandom(F)(upperN).chain(
        (rand) => F.print(`Your random is: ${rand}`),
      ),
    ).chain(() => checkContinue(F).chain(
      (answer) => answer ?
        main(F) :
        F.print('Good-bye').chain(
          () => F.terminate(undefined),
        ),
    )),
  );

// Helper: a pure function to parse a string to number
const parse = (s: string): Option<number> => {
  const i = Number(s);
  return isNaN(i) || i % 1 !== 0 ? none : some(i);
};

However, if you try to run this code, you'll get… nothing. Why? Because our main is just an expression – it's data needed to be interpreted! And here come the second half of TF style: interpreters.

As we are building a console application, let's use Task typeclass for expressing asynchronous operations. Here are instances of out algebras using Tasks:

import { log } from 'fp-ts/lib/Console';
import { randomInt } from 'fp-ts/lib/Random';
import { fromIO, Task, task, URI as TaskURI } from 'fp-ts/lib/Task';
import { createInterface } from 'readline';

const programTask: Program<TaskURI> = {
  terminate: task.of,
};

const randomTask: Random<TaskURI> = {
  nextInt: (upper) => fromIO(randomInt(0, upper)),
};

const consoleTask: Console<TaskURI> = {
  read: new Task(
    () => new Promise((resolve) => {
      const rl = createInterface({
        input: process.stdin,
        output: process.stdout,
      });
      rl.question('> ', (answer) => {
        rl.close();
        resolve(answer);
      });
    }),
  ),
  print: (message: string): Task<void> => fromIO(log(message)),
};

Finally, we can obtain our mainTask and run it:

const mainTask = main({
  ...programTask,
  ...randomTask,
  ...consoleTask,
});

mainTask.run();

Here's an example of program session:

 yuriy@MBP  ts-node ./src/monday/tagless.ts
Enter random upper bound:
> aaaa
"aaaa" is not an integer
Do you want to continue?
> y
Enter random upper bound:
> 23
Your random is: 4
Do you want to continue?
> n
Good-bye

However, our journey is not over yet. We can define a set of interpreters for Identity type which just do nothing and use hard-coded values – but allow us to debug the logic of our program on a fixed set of values:

import { identity, URI as IdURI } from 'fp-ts/lib/Identity';
const programId: Program<IdURI> = {
  terminate: identity.of,
};

const randomId: Random<IdURI> = {
  nextInt: (upper) => identity.of(upper),
};

const consoleId: Console<IdURI> = {
  print: (_message) => identity.of(undefined),
  read: identity.of('42'),
};

console.log(
  generateRandom({ ...programId, ...randomId })(
    +getUpperStr({ ...programId, ...consoleId }).fold((x) => x),
  ).toString(),
); // => new Identity(42)

Or we can use a State monad with a tuple of inputs, outputs and randoms – and use it for creating fully synchronous tests! Or we can, for example, define yet another set of algebra instances which "render" output as HTML and read input from dialog windows. Or we can introduce some kind of network interaction – say, log our data not onto terminal, but put it in LogStash. Or in Kafka. Or in any database.

This concludes my short intro to Tagless Final.

Episode 6: ZIO in TypeScript

Welcome to the sixth episode of #monadicmonday! Today I will answer to the question from one of my followers: “Could you share an example of ZIO in Typescript?”.

For those of you who are not familiar what a ZIO is, let me explain it briefly.
ZIO is a trifunctor (i.e., it takes 3 type parameters and can map over them), and it encapsulates the following idea:
ZIO[-R, +E, +A] describes a computation which can read from an enviroment typed by R, can fail with error of type E or succeed with a value of type A.

Concuptually, ZIO is identical to a Reader[R, Task[Either[E, A]]], but it bakes all effects in a single high-performant container – opposed to the way of using monadic transformers, familiar to most Haskell developers. You may read a bit more about such design decision in @jdegoes blog post: http://degoes.net/articles/rotating-effects

You may wonder why ZIO incorporates a Reader and not a State, and how to implement a mutable environment using it. I sugges reading great article by @snoyberg: https://www.fpcomplete.com/blog/2017/06/readert-design-pattern. It is written in Haskell, but let's be honest: Haskell is nowadays a "de-facto" FP language, so you should be familiar with it simple syntax.
In short, Reader lets you write concurrent programs and guarantees runtime immutability of a shared resource, which is a cornerstone of concurrent programming, while State/Writer have no such guarantees.

Let's switch to a more familiar to my readers TypeScript syntax and try to replicate ZIO in it. I will call my execise TIO (T stands for TypeScript, obviously) to avoid name collisions.

We start with a typeclass definition:

declare module 'fp-ts/lib/HKT' {
  interface URI2HKT3<U, L, A> {
    // We need to have our R, E, A parameters 
    // called U, L, A in order for this HKT pattern to work.
    // It is required that all interface augmentations 
    // have the same parameters:
    TIO: TIO<U, L, A>;
  }
}

export const URI = 'TIO';
export type URI = typeof URI;

Next, we'll have to define our base class, TIO. In order for it to work fast, I should have written the implementation of Reader<R, Task<Either<E, A>>> manually. This is quite a tedious work, so I'll still use monad transformers to achieve the same interface:

import { Either } from 'fp-ts/lib/Either';
import * as readerT from 'fp-ts/lib/ReaderT';
import * as taskEither from 'fp-ts/lib/TaskEither';

import TaskEither = taskEither.TaskEither;

const readerTTaskEither = readerT.getReaderT2v(taskEither.taskEither);

export class TIO<R, E, A> {
  readonly _R!: R;
  readonly _E!: E;
  readonly _A!: A;
  readonly _URI!: URI;

  constructor(readonly value: (e: R) => TaskEither<E, A>) { }

  run(e: R): Promise<Either<E, A>> {
    return this.value(e).run();
  }

  chain<R1 extends R, E1, B>(f: (a: A) => TIO<R1, E1, B>): TIO<R1, E1, B>;
  chain<E1, B>(f: (a: A) => TIO<R, E1, B>): TIO<R, E1, B>;
  chain<B>(f: (a: A) => TIO<R, E, B>): TIO<R, E, B> {
    return new TIO(readerTTaskEither.chain(this.value, (a) => f(a).value));
  }

  // Some methods are skipped for readability
}

export const of = <R, E, A>(value: (e: R) => TaskEither<E, A>) => new TIO(value);
export const fromIO = <R, E, A>(a: io.IO<A>) => new TIO<R, E, A>(() => taskEither.fromIO(a));

export const tio = {
  of,
};

Finally, here are some synonims ZIO defines at its core:

export type UIO<A> = TIO<any, never, A>;
export type Task<A> = TIO<any, Error, A>;
export type IO<E, A> = TIO<any, E, A>;

Now we can express the same program I've used as a demo in the previous installment of MonadicMonday – a program which asks the user for upper bound for random generation, prints the resulting random number and asks if the user wants to continue. In order to show the power of ZIO as a pattern, I will change the logic by the slightliest bit: RNG will read the lower bound from the environment instead of using hard-coded "1":

export interface MainEnvironment {
  lowerBound: number;
}

export const parse = (s: string): Option<number> => {
  const i = Number(s);
  return isNaN(i) || i % 1 !== 0 ? none : some(i);
};

// Take a note: `ask` just returns it's environment, 
// so we can `chain` it and gain access to the runtime value:
export const generateRandom = (upper: number): TIO<MainEnvironment, never, number> =>
  ask().chain(({ lowerBound }) => fromIO(randomInt(lowerBound, upper)));

Today the expressiveness of this program will be greater, as we don't have to carry around first parameter which determines runtime implementation of our program's interpreter. We still keep one of the main benefits of FP-styled program – algorythm as data – but we lose the ability to test the effects with an ease of Tagless Final approach.

import { ask, fromIO, Task, TIO, tio } from './tio';

export const terminate = tio.of;
export const print = (message: string): Task<void> => fromIO(log(message));
export const getUpperStr: Task<string> = print('Enter random upper bound:').chain(() => read);
export const checkContinue: Task<boolean> = print(`Do you want to continue?`)
  .chain(() => read)
  .chain((answer) => {
    switch (answer.toLowerCase()) {
      case 'y':
        return terminate(true);
      case 'n':
        return terminate(false);
      default:
        return checkContinue;
    }
  });

export const main: TIO<MainEnvironment, never, void> = getUpperStr.chain(
  (upper) => parse(upper).foldL(
    () => print(`"${upper}" is not an integer`),
    (upperN) => generateRandom(upperN).chain(
      (rand) => print(`Your random is: ${rand}`),
    ),
  ).chain(() => checkContinue.chain(
    (answer) => answer ? main : print('Good-bye').chain(() => terminate(undefined)),
  )),
);

We can run our program by supplying it with a correct environment:

import { main } from './main';

main.run({ lowerBound: 33 });

Scala's ZIO can be tested: http://degoes.net/articles/testable-zio. But in my opinion, testing programs in TF style is much simpler. In either approach you need to pass the mock object, but with TF you pass it (and carry around) to each method, and with ZIO you need to write your programs with explicit access to the environmental effects via ZIO.access/ZIO.accessM.

In this episode I won't be showing the testing approach to the ZIO style. John @jdegoes described this very well, so please go check out his article.

As a summary, let's briefly compare the TF and ZIO:

Tagless Final
Pros:

Explicit abstracting over effects;
Higher performance compared to MTL/Free monads style;
Good composability;
Ease of testing;
Is a pattern, rather a final implementation – so it is possible to write in TF style in many languages; Cons:
Very steep learning curve;
Every bit of program needs to be in TF style;
Effect stack my be VERY big in real apps;

ZIO
Pros:

High performance (see John's blog for details);
More approachable to the new developers (more shallow learning curve);
Quite good composability; Cons:
Harder to test (effects must be baked in the Reader's environment);
Still is more an end-to-end implementation rather than a pattern, exclusive for Scala;

I guess it's better to compare TF with a ReaderTaskEither pattern (achievable via MTL style). There's a lot of talks and articles around this topics, so I won't be duplicating them here. Instead I would like to show you a good talk comparing TF vs. MTL vs. Bifunctor IO: https://www.youtube.com/watch?v=QM86Ab3lL20

As usual, you can find the code example for this episode on my GitHub: https://github.com/YBogomolov/monadic-mondays

Episode 7: Functional optics

Welcome to the seventh episode of #monadicmonday! Today we'll talk a bit about functional optics: lenses, prisms, folds and traversals.

History of lenses started in 2009 with "The Essence of the Iterator Pattern" paper, which started a whole lot of cascading publications, leading to current lens package for Haskell and various implementations in different languages. I will use an awesome monocle-ts package from @GiulioCanti for this episode, but you may use any optics library you find suitable. The concepts are the same.

You can find more historical references at https://github.com/ekmett/lens/wiki/History-of-Lenses

It's a common practice that we work with immutable data structures when writing in functional style. It gives us incredible guarantees about our code, but also comes with a drawback: it's hard to update (rebuild) the deeply-nested data structure. So optics to the resque!

Functional optics gives you a way of working with a complicated immutable data structures (deeply nested, recursive, etc) without explicit need to maintain the structure by hand. Current generation of optics libraries heavily rely on profunctor encoding, but we will be using a much simpler encoding.

Consider an example in imperative style:

// We have an organizational data structure like this:
interface Organization {
  title: string;
  employees: Array< {
    name: string;
    age: number;
    car?: {
      model: string;
      plateNum: string;
    };
    partner?: {
      name: string;
      age: number;
    };
    projects: Array<{
      title: string;
      code: string;
      start: Date;
      end: Date;
    }>
  }>
}

// Say, you're changing internal project codes from lowercase to uppercase + prefix. 
// How would you do this imperatively?
function changeCodes(o: Organization): Organization {
  const newOrg: Organization = {
    ...o,
    employees: o.employees.map((emp) => ({
      ...emp,
      // Note: we need to preserve absense of `projects`, 
      // if it was absent in the first place:
      ...(emp.projects ? {
        projects: emp.projects.map((p) => ({
          ...p,
          code: 'MY-' + p.code.toLocaleUpperCase(),
        })),
      } : {}),
    })),
  };

  return newOrg;
}

I should say that this way is error-prone (for example, it's easy to make a mistake and forcefully create projects field for all employees – even if they hadn't had it), tedious and not composable. However, there's a way to solve this problem with ease.

N.B. Bonus points are going to those who remembered the third episode and said that you can use a recursion scheme named "catamorphism" here (or simply fold). But today we take a look through optics at this problem.

The intuition behind optics comes straight from physics: each optic entity allows you to "focus" on some part(s) of your data structure and provide interface to interact with them.

Let's start with an Iso. "Iso" stands for "isomorphism", and is generally could be thought of as a pair of functions to "get" and "rebuild" the values (reverse the "get"). Please note that in general isomorphisms between any two types are not guaranteed:

interface Iso<S, A> {
  get: (s: S) => A;
  reverseGet: (a: A) => S;
}

One example I can think of is a pair of two "1/x" functions. Given an y value, "get" applies x -> 1/x and leaves you with 1/y, and "reverseGet" rebuilds y from 1/y applying x -> 1/x function again.
The other example may be a pair of "toLocaleLowerCase" and "toLocaleUpperCase" functions in JS – but if and only if we agree that an input to Iso must already be in uppercase. Law for Iso is the following:

reverseGet . get ≅ id

Iso as it is may seem to be pretty useless, because in general from any A you cannot obtain any B. But it gives a raise to the next optics – Lens.

Lens<S, A> is a pair of functions to "get" and "set" values in the structure. Please note that unlike Iso, Lens implies the structure itself is already defined, so you cannot "set" a deeply nested level if intermediate levels are missing. Lenses are great for working with product types (tuples & objects).

interface Lens<S, A> {
  get: (s: S) => A;
  set: (a: A) => (s: S) => S;
}

Consider an example:

interface Foo {
  bar: string;
  baz: {
    quux: number;
    fizz: {
      buzz: boolean;
    };
  };
}

const aFoo: Foo = { bar: 'bar', baz: { quux: 1, fizz: { buzz: true } } };

const buzzLens = Lens.fromPath<Foo>()(['baz', 'fizz', 'buzz']);

buzzLens.get(aFoo); // => true
buzzLens.set(false)(aFoo); // => { bar: 'bar', baz: { quux: 1, fizz: { buzz: false } } }

If you need to work with fields that may be missing, you'll need to use a Prism or Optional. They both are used for working with sum types: arrays, Options, Eithers, etc, and they are defined using a pair of functions:

interface Prism<S, A> {
  getOption: (s: S) => Option<A>;
  reverseGet: (a: A) => S;
}

interface Optional<S, A> {
  getOption: (s: S) => Option<A>;
  set: (a: A) => (s: S) => S;
}

If you are coming from an imperative programming background, you can think of Lens, Optional & Prism as of ways of overloading property accessors.

Another useful type of optics – Fold. It allows, given a Monoid instance for the data type M, to fold (reduce) its value into type M:

interface Fold<S, A> {
  foldMap: <M>(M: Monoid<M>) => 
    (f: (a: A) => M) => (s: S) => M;
}

Traversal is an optics which can traverse (what a surprise!) data structure and perform the following operations:

interface Traversal<S, A> {
  modifyF: <F>(F: Applicative<F>): (f: (a: A) => HKT<F, A>) => (s: S) => HKT<F, S>;
  modify(f: (a: A) => A): (s: S) => S;
  set(a: A): (s: S) => S;
  // `filter` allows narrowing a Traversal:
  filter(predicate: Predicate<A>): Traversal<S, A>;
}

Consider an example:

import { Tree, tree } from 'fp-ts/lib/Tree';

interface User {
  name: string;
  age: number;
}

const hierarchy = new Tree<User>({ name: 'Boss', age: 42 }, [
  new Tree({ name: 'Manager1', age: 35 }, [
    tree.of({ name: 'Emp1', age: 45 }),
    tree.of({ name: 'Emp2', age: 64 }),
  ]),
  new Tree({ name: 'Manager2', age: 52 }, [
    tree.of({ name: 'Emp3', age: 27 }),
    tree.of({ name: 'Emp4', age: 32 }),
    tree.of({ name: 'Emp5', age: 39 }),
  ]),
]);

const hierarchyTraversal = fromTraversable(tree)<User>();
console.dir(hierarchyTraversal.modify(
  (u) => ({ ...u, name: u.name.toLocaleUpperCase() }),
)(hierarchy), { depth: null }); // =>
// Tree {
//   value: { name: 'BOSS', age: 42 },
//   forest:
//    [ Tree {
//        value: { name: 'MANAGER1', age: 35 },
//        forest:
//         [ Tree { value: { name: 'EMP1', age: 45 }, forest: [] },
//           Tree { value: { name: 'EMP2', age: 64 }, forest: [] } ] },
//      Tree {
//        value: { name: 'MANAGER2', age: 52 },
//        forest:
//         [ Tree { value: { name: 'EMP3', age: 27 }, forest: [] },
//           Tree { value: { name: 'EMP4', age: 32 }, forest: [] },
//           Tree { value: { name: 'EMP5', age: 39 }, forest: [] } ] } ] }

The best thing about optics is that it is easily composed with each other. You can start with a Lens, compose it with a Prism to zoom deeper, then compose with a Traversal to walk the inner structure, and so on.

Let's take a look at another example: given an organizational structure, calculate average age of its members.

We start with or data type definition and example dataset:

import { Tree, tree } from 'fp-ts/lib/Tree';

interface User {
  name: string;
  age: number;
}

const hierarchy = new Tree<User>({ name: 'Boss', age: 42 }, [
  new Tree({ name: 'Manager1', age: 35 }, [
    tree.of({ name: 'Emp1', age: 45 }),
    tree.of({ name: 'Emp2', age: 64 }),
  ]),
  new Tree({ name: 'Manager2', age: 52 }, [
    tree.of({ name: 'Emp3', age: 27 }),
    tree.of({ name: 'Emp4', age: 32 }),
    tree.of({ name: 'Emp5', age: 39 }),
  ]),
]);

Now we can write the solution:

import { identity } from 'fp-ts/lib/function';
import { getTupleMonoid, monoidSum } from 'fp-ts/lib/Monoid';
import { fromFoldable, Lens } from 'monocle-ts';

const ageTupleLens = new Lens<User, [number, number]>(
  (u) => [u.age, 1],
  ([age]) => (u) => ({ ...u, age }),
);

const hierarchyFold = fromFoldable(tree)<User>().composeLens(ageTupleLens);

const tupleMonoid = getTupleMonoid(monoidSum, monoidSum);

// Note that we get an answer in a single traverse of the tree:
const [agesSum, agesCount] = hierarchyFold.foldMap(tupleMonoid)(identity)(hierarchy);
console.log(agesSum / agesCount); // => 42

If you want to dive into categorical view on the optics, you should read excellent article by @BartoszMilewski: https://bartoszmilewski.com/2017/07/07/profunctor-optics-the-categorical-view/
However, it's not an entry-level work, so be prepared for complicated categorical topics like profunctor, adjoints and Tambara modules.

Episode 8: Free Monads

Welcome to the eighth episode of #monadicmonday! Today we'll talk about the topic you've requested: free monads.

Free monads is a way of describing eDSL and building expressions trees & interpreters for them. This may sound a lot like Tagless Final we've discussed in ep.5, but free monads have their own twist.

First of all, why this name – "free" monad? "Free" means "free of evaluation", like in "freedom" and not in "free beer".
A free monad is a construction which allows you to build a monad from any functor. What's more important for us programmers, it also allows us to run it in a stack-safe way.

Categorically speaking, free monad is a left adjoint to a forgetful functor. A forgetful functor takes a monad and "forgets" its of and chain parts, keeping only map. It's left adjoint has its arrows reversed, so free monad is a construction which:
– take a functor;

adds the pointed part (of);
adds the monadic behavior (chain).

Using free monads we represend our computations as AST, with some expressions being terminal commands, and the others having sub-expressions as next part.

As usual, I will illustrate today's topic with a small example. Let's write a simple program which reads 2 lines from a text file and puts them onto console.

Programs written using free monads are just descriptions of computations, not the computations themselves. Our programs are values, and we need to interpret them to get things actually done.

Our domain model will be just File with a handle and isOpen attribute:

import fs from 'fs';

// Data structure we'll be working with:
interface File {
  handle: fs.promises.FileHandle;
  isOpen: boolean;
}

We start with a HKT OpsF<A>, which will be our free construction. It allows us to build our expression tree for our domain:

// Some boilerplate for higher-kinded types:
const OpsFURI = 'Ops';
type OpsFURI = typeof OpsFURI;

declare module 'fp-ts/lib/HKT' {
  interface URI2HKT<A> {
    Ops: OpsF<A>;
  }
}

// Our eDSL – building blocks of our small application:
type OpsF<A> = OpenFile<A> | ReadLine<A> | Log<A> | CloseFile<A>;

class OpenFile<A> {
  readonly _tag: 'OpenFile' = 'OpenFile';
  readonly _A!: A;
  readonly _URI!: OpsFURI;
  constructor(readonly name: string, readonly next: (file: File) => A) { }
}

class ReadLine<A> {
  readonly _tag: 'ReadLine' = 'ReadLine';
  readonly _A!: A;
  readonly _URI!: OpsFURI;
  constructor(readonly file: File, readonly next: (a: [string, File]) => A) { }
}

class Log<A> {
  readonly _tag: 'Log' = 'Log';
  readonly _A!: A;
  readonly _URI!: OpsFURI;
  constructor(readonly message: string, readonly next: () => A) { }
}

class CloseFile<A> {
  readonly _tag: 'CloseFile' = 'CloseFile';
  readonly _A!: A;
  readonly _URI!: OpsFURI;
  constructor(readonly file: File, readonly next: (file: File) => A) { }
}

Next, we want to have a way to use those building blocks, preferably enhanced with monadic interface. So we need to "lift" our pure data of type OpsF into a free monad world. Luckily, we have a function just for that – liftF:

import { liftF } from 'fp-ts/lib/Free';

// Helpers for building eDSL expressions.
// Note that in general we have a possibility to fiddle with values
// as they are getting returned in `next` part:
const open = (name: string) => liftF(new OpenFile(name, identity));
const readLine = (file: File) => liftF(new ReadLine(file, identity));
const log = (message: string) => liftF(new Log(message, () => void 0));
const closeFile = (file: File) => liftF(new CloseFile(file, identity));

Finally, we can build the program which expresses the logic of our domain:

// This is our program – just a value, nothing REALLY happens here,
// we just declare our intentions:
const program = open('./src/episode-8/file.csv')
  .chain((file) => log(`File is open: ${file.isOpen}`).chain(() => readLine(file)))
  .chain(([line, file]) => log(line).chain(() => readLine(file)))
  .chain(([line, file]) => log(line).chain(() => closeFile(file)))
  .chain((file) => log(`File is open: ${file.isOpen}`));
// => program :: Free<"Ops", void>

Seems really close to Tagless Final style – we've created an embedded DSL and expressed our intentions using its statements. We have our program as data, and during the next step we'll build some interpreters to run the actual code.

However, as I said earlier, there's a twist. Tagless Final is spinning around final algebras (i.e., set of operations of type A => F<A>), while Free Monads approach builds up expression trees using recursive data type Free<F<A>>, which serve as initial algebras.

You may read a bit more specialized categorical description of a free monads here: https://www.paolocapriotti.com/blog/2013/11/20/free-monads-part-1 (parts 2 and 3 are also available).

And, of course, I cannot recommend enough an awesome blog post by @BartoszMilewski: https://bartoszmilewski.com/2018/08/20/recursion-schemes-for-higher-algebras/. Must read!

Anyway, let's proceed with defining the interpreters for our program. As usual, I will define two of them: one for Identity monad, and the other – for Task:

import { Identity, identity as id } from 'fp-ts/lib/Identity';

const exaustive = (x: never): never => x;

// For sake of brevity I will use a "global state" here instead of `State` monad:
let position = 0;
const lines = ['first line', 'second line'];

const identityInterpreter = <A>(fa: OpsF<A>): Identity<A> => {
  switch (fa._tag) {
    case 'OpenFile':
      // I'm stubbing the `handle` with null here, as my Identity interpreter won't be using it:
      return id.of(fa.next({ isOpen: true, handle: null as unknown as fs.promises.FileHandle }));

    case 'ReadLine':
      return id.of(fa.next([lines[position++], fa.file]));

    case 'Log':
      return id.of(fa.next());

    case 'CloseFile':
      return id.of(fa.next({ isOpen: false, handle: null as unknown as fs.promises.FileHandle }));
  }

  // A little trick: if you add a call to `exaustive`,
  // the compiler will force you to use all possible `_tag` values in switch!
  return exaustive(fa);
};

Interpreter for Task will do some actual work using Node's filesystem API:

import { delay, Task, task } from 'fp-ts/lib/Task';
import fs from 'fs';

const taskInterpreter = <A>(fa: OpsF<A>): Task<A> => {
  switch (fa._tag) {
    case 'OpenFile':
      return new Task(
        () => fs.promises.open(fa.name, 'r')
          .then((handle) => fa.next({ isOpen: true, handle })),
      );

    case 'ReadLine':
      console.timeLog('TASK', 'Read line');
      return new Task(
        () => fa.file.handle.read(Buffer.from(new ArrayBuffer(24), 0, 24), 0, 24)
          .then(({ buffer }) => buffer.toString()),
      ).chain((line) => task.of(fa.next([line, fa.file])));

    case 'Log':
      console.log('>>>>>', fa.message);
      // Let's pretend that we're logging to DB here, hence the
      return delay(500, undefined).chain(() => {
        console.timeLog('TASK', 'Log');
        return task.of(fa.next());
      });

    case 'CloseFile':
      return new Task(() => fa.file.handle.close()).chain(() => {
        console.timeLog('TASK', 'Close file');
        return task.of(fa.next({ ...fa.file, isOpen: false }));
      });
  }

  return exaustive(fa);
};

When we run our interpreters using foldFree function, we'll see the following output (I've added some instrumentation so you could see actual duration):

console.log('Id interpreter');
const resId = foldFree(id)(identityInterpreter, program); // => Identity<void>
console.log(resId.value);

console.log('\nTask interpreter');
const resTask = foldFree(task)(taskInterpreter, program); // => Task<void>
console.time('TASK');
resTask.run().then(() => console.timeEnd('TASK'));

/*
> ts-node ./src/episode-8/free.ts

Id interpreter
undefined

Task interpreter
>>>>> File is open: true
TASK: 506.466ms Log
TASK: 506.756ms Read line
>>>>> this is our first line!

TASK: 1013.263ms Log
TASK: 1013.459ms Read line
>>>>> this is the second line

TASK: 1518.309ms Log
TASK: 1518.753ms Close file
>>>>> File is open: false
TASK: 2021.198ms Log
TASK: 2021.623ms
*/

Now let's speak a bit about stack safety I've mentioned earlier. When you're writing interpreters for free monads, it's very simple to cause stack overflow, as you are (de)composing possibly infinite recursive data structure. To help with solving this issue, a common technique called "trampoline" is used.
Basically, trampolining means executing recursive calls in a loop – i.e., doing tail-call optimization for the compiler. A general definition of trampolining function is such:

// Enter Trampoline!
type Trampoline<T> = T | (() => Trampoline<T>);

function trampoline<T>(firstResult: Trampoline<T>) {
  let result = firstResult;
  while (result instanceof Function) {
    result = result();
  }
  return result;
}

So let's take a look at another example. Let's hand-write simple IO monad and express with it infinite recursive loop:

// Free IO monad – representing generic computations:
const IOFURI = 'StackOps';
type IOFURI = typeof IOFURI;

type IO<A> = Return<A> | Suspend<A> | FlatMap<A>;

class Return<A> {
  readonly _tag: 'Return' = 'Return';
  readonly _A!: A;
  readonly _URI!: IOFURI;
  constructor(readonly a: A) { }
}

class Suspend<A> {
  readonly _tag: 'Suspend' = 'Suspend';
  readonly _A!: A;
  readonly _URI!: IOFURI;
  constructor(readonly resume: () => A) { }
}

class FlatMap<A> {
  readonly _tag: 'FlatMap' = 'FlatMap';
  readonly _A!: A;
  readonly _URI!: IOFURI;
  constructor(readonly fa: IO<A>, readonly f: (a: A) => IO<A>) { }
}

// Runs given `IO` forever:
const forever = <A>(a: IO<A>): IO<A> => new FlatMap(a, () => forever(a));

// Should log current timestamp infinitely:
const program = forever(new Suspend(() => console.log(Date.now())));

We can create a naïve implementation of run interpreter like this:

const run = <A>(fa: IO<A>): A => {
  switch (fa._tag) {
    case 'Return':
      return fa.a;
    case 'Suspend':
      return fa.resume();
    case 'FlatMap': {
      const x = fa.fa;
      const f = fa.f;
      switch (x._tag) {
        case 'Return':
          return run(f(x.a));
        case 'Suspend':
          return run(f(x.resume()));
        default:
        case 'FlatMap':
          const y = x.fa;
          const g = x.f;
          return run(new FlatMap(y, (a) => new FlatMap(g(a), f)));
      }
    }
  }

  return exaustive(fa);
};

However, when you try to run this example, it'll fail with:


RangeError: Maximum call stack size exceeded
    at RegExp.test (<anonymous>)
    at WriteStream.getColorDepth (internal/tty.js:128:22)
    at Console.(anonymous function) (console.js:183:16)
    at Console.(anonymous function) (console.js:190:40)
    at Console.log (console.js:202:31)
    at Suspend [as resume] (/Users/yuriy/Projects/monadic-mondays/src/episode-8/stack.ts:95:51)
    at run (/Users/yuriy/Projects/monadic-mondays/src/episode-8/stack.ts:80:27)
    at run (/Users/yuriy/Projects/monadic-mondays/src/episode-8/stack.ts:80:18)
    at run (/Users/yuriy/Projects/monadic-mondays/src/episode-8/stack.ts:80:18)
    at run (/Users/yuriy/Projects/monadic-mondays/src/episode-8/stack.ts:80:18)

So we need to use trampolining for this recursion Uroboros to unfold safely. We change run signature just a bit and return recursive calls as thunks:

const run = <A>(fa: IO<A>): Trampoline<A> => {
  switch (fa._tag) {
    case 'Return':
      return fa.a;
    case 'Suspend':
      return fa.resume();
    case 'FlatMap': {
      const x = fa.fa;
      const f = fa.f;
      switch (x._tag) {
        case 'Return':
          return () => run(f(x.a));
        case 'Suspend':
          return () => run(f(x.resume()));
        default:
        case 'FlatMap':
          const y = x.fa;
          const g = x.f;
          return () => run(new FlatMap(y, (a) => new FlatMap(g(a), f)));
      }
    }
  }

  return exaustive(fa);
};

// Now this won't fall and provide an infinite stream of Unix timestamps:
trampoline(run(program));

If you want to dive deeper into trampolining, I recommend reading these two great papers:
http://functorial.com/stack-safety-for-free/index.pdf
http://blog.higher-order.com/assets/trampolines.pdf

As you've probably guessed, our hand-written IO is just a specialization of a Free IO a monad. I leave re-writing this example using Free from fp-ts to a curious reader.

I should admit that free monads in general are considered harmful due to heavy allocation on the stack. If you examine code more closely, you'll notice that Free regularly re-constructs its data structure, leading to overwhelming amount of allocations.
You can find more details in an article by Mark Karpov: https://markkarpov.com/post/free-monad-considered-harmful.html
So in general, IMO, it's better to use other stack-sparing techniques like ZIO (if you are writing Scala) and Tagless Final (otherwise).

This concludes my explanation of Free Monads and free constructions in general. As usual, all code examples are available at https://github.com/YBogomolov/monadic-mondays

Episode 9: Type-Level Programming

Welcome to ninth episode of #monadicmonday! Today I would like to return to the roots of this series and provide you with a few "take and go" recepies for type-level programming in TypeScript.

Let's start with the basics. Type-level programming means that we express statements using types, and ask compiler to check them. In TypeScript, we use conditional types to infer our statements to be either never (bottom type) or some meaningful type.

The first useful operation is type-level If operator, which can be expressed like so:

type If<T, U, True, False> = [T] extends [U] ? True : False;

Let's write some tests for it! First of all, we need a way to run type-level assertions. We can use a specialized tool, dtslint, from Microsoft, but its setup is a bit painful, so let's stick with something simple like jest.

We start with an assertType function, which will compile only if its parameter is not never:

// Type-level assertions which is possible to compile 
// only if parameter is inferred to a non-bottom type:
const assertType = <T>(expect: [T] extends [never] ? never : T): T => expect;

Our test for If will look like this:

it('If<T, Eq, True, False>', () => {
  //                If<  A,       B,      T,    F  >;
  type Assertion1 = If<string, boolean, never, true>;
  expect(assertType<Assertion1>(true)).toBeTruthy();

  type Assertion2 = If<string, string, true, never>;
  expect(assertType<Assertion2>(true)).toBeTruthy();
});

Practically, I find myself mostly using checks against never, so let's define IfDef type operator and write tests for it:

type IfDef<T, True, False> = If<T, never, False, True>;

it('IfDef<T, True, False>', () => {
  type Assertion1 = IfDef<string, true, never>;
  expect(assertType<Assertion1>(true)).toBeTruthy();

  type Assertion2 = IfDef<string | never, true, never>; // a + 0 = a
  expect(assertType<Assertion2>(true)).toBeTruthy();

  type Assertion3 = IfDef<string & never, never, true>; // a * 0 = 0
  expect(assertType<Assertion3>(true)).toBeTruthy();
});

Another useful type operation is OrElse, which falls back to its second argument if the first is never:

type OrElse<MaybeNever, Fallback> = IfDef<MaybeNever, MaybeNever, Fallback>;

it('OrElse<A, B>', () => {
  type Assertion1 = OrElse<string, true>;
  expect(assertType<Assertion1>('some string')).toEqual('some string');

  type Assertion2 = OrElse<never, true>;
  expect(assertType<Assertion2>(true)).toBeTruthy();
});

Now let's define something more interesting. Say, let's check if two types intersect each other:

type Intersect<A extends {}, B extends {}> =
  Pick<A, Exclude<keyof A, Exclude<keyof A, keyof B>>> extends { [x: string]: never } & { [x: number]: never } ?
  never :
  Pick<A, Exclude<keyof A, Exclude<keyof A, keyof B>>>;

it('Intersect<A, B>', () => {
  interface A { foo: string; }
  interface B { bar: number; }
  interface C { foo: string; baz: boolean; }

  type AnB = Intersect<A, B>;
  type Assertion1 = IfDef<AnB, never, true>;
  expect(assertType<Assertion1>(true)).toBeTruthy();

  type AnC = Intersect<A, C>;
  type Assertion2 = If<AnC, { foo: string }, true, never>;
  expect(assertType<Assertion2>(true)).toBeTruthy();
});

Another great type operation I often use is AtLeastOne. It transforms a partial type into a union of types with one required field from the whole set:

type AtLeastOne<T, Keys extends keyof T = keyof T> = Partial<T> & { [K in Keys]: Required<Pick<T, K>> }[Keys];

it('AtLeastOne<T>', () => {
  interface T {
    foo?: string;
    bar?: number;
    baz?: boolean;
  }

  type ALOT = AtLeastOne<T>;
  type Assertion1 = If<ALOT, { foo: string } | { bar: number } | { baz: boolean }, true, never>;
  expect(assertType<Assertion1>(true)).toBeTruthy();
});

Finally, let's prohibit type from being widened:

type Exact<S extends {}, T extends S> = S & Record<Exclude<keyof T, keyof S>, never>;

it('Exact<S, T>', () => {
  interface A { foo: string; }
  interface B { foo: string; baz: boolean; }

  type Assertion1 = If<Exact<A, B>, A, true, never>;
  type Assertion2 = If<Exact<A, B>['baz'], never, true, never>;

  expect(assertType<Assertion1>(true)).toBeTruthy();
  expect(assertType<Assertion2>(true)).toBeTruthy();
});

Now I would like to show you how to use these type-level operations in your code. For example, you're writing a function which requires its arguments to never intersect:

const neverIntersect = <
  A extends {},
  B extends {},
  // Typelevel law: A and B should not intersect
  NeverIntersect = IfDef<Intersect<A, B>, never, {}>
>(a: A & NeverIntersect, b: B & NeverIntersect): A & B & NeverIntersect => ({ ...a, ...b });

it('neverIntersect', () => {
  interface A { foo: string; }
  interface B { bar: number; }

  const a1: A = { foo: 'foo' };
  const b1: B = { bar: 42 };

  const c1 = neverIntersect<A, B>(a1, b1);
  expect(c1).toStrictEqual({ foo: 'foo', bar: 42 });
  // Won't compile with: 
  // Argument of type 'A' is not assignable to parameter of type 'never'.ts(2345)
  // const c2 = neverIntersect<A, A>(a1, a1); 
});

And now let's have some type-level fun! As you (probably) know, TypeScript's type system is close to be Turing-complete:
https://github.com/Microsoft/TypeScript/issues/14833
So we can play a bit with it and see where it may lead us :)

Since TS@2.0 a lot happened to its inference engine, so it's hard to express recursive types. However, we still can, for example, describe a type-level list and reverse it. Or define a type-level Peano numbers. Let's dive in!

First of all, we need some Boolean values on type level – they are bread and butter of type-level checks:

type False = 'f';
type True = 't';
type Bool = False | True;

Next, let's write a definition of a heterogeneous list, which is either empty or consists of a head and a tail:

type HNil = { isNil: True; };
// I will be using `any` for head type, because making 
// HCons generic makes code really messy and cumbersome to read:
type HCons = { isNil: False; head: any; tail: HList; };
type HList = HNil | HCons;

Next, we'll need some "functions" to create and manipulate our lists:

type Cons<Head, Tail extends HList> = { isNil: False, head: Head, tail: Tail };
type Head<Xs extends HCons> = Xs['head'];
type Tail<Xs extends HCons> = Xs['tail'];
type IsNil<Xs extends HList> = Xs['isNil'];

Having these, we can finally write the Reverse type. To reverse a list, we take its head and append it to a reversed tail:

type Reverse<Xs extends HList> = Rev<Xs, HNil>;
type Rev<Xs extends HList, T extends HList> = {
  f: Xs extends HCons ? Rev<Tail<Xs>, Cons<Head<Xs>, T>> : HNil;
  t: T;
}[IsNil<Xs>];

type ABC = Cons<'a', Cons<'b', Cons<'c', HNil>>>;
type CBA = Reverse<ABC>; // => HCons<'c', HCons<'b', HCons<'a', HNil>>>

Using the exact same technique, you can define type-level Peano numbers:

type Zero = { isZero: True };
type Nat = Zero | { isZero: False, pred: Nat };

type Succ<N extends Nat> = { isZero: False, pred: N };
type Pred<N extends Succ<Nat>> = N['pred'];
type IsZero<N extends Nat> = N['isZero'];

type _0 = Zero;
type _1 = Succ<_0>;
type _2 = Succ<_1>;
type _3 = Succ<_2>;

And even combine these two types:

type UpTo3 = Cons<_0, Cons<_1, Cons<_2, Cons<_3, HNil>>>>;
type From3 = Reverse<UpTo3>; // => HCons<_3, HCons<_2, HCons<_1, HCons<_0, HNil>>>>

Curious reader may find familiar patterns – for example, Nat definition is almost the same we used in the third episode about recursion schemes: https://twitter.com/YuriyBogomolov/status/1117723946005213185

// Compare:
type Zero = { isZero: True };
type Nat = Zero | { isZero: False, pred: Nat };

// From ep.3:
export class Zero<A> {
  public value: never;
  readonly _tag: 'Zero' = 'Zero';
  readonly '_A': A;
  readonly '_URI': URI;
  private constructor() { }
}

export class Succ<A> {
  readonly _tag: 'Succ' = 'Succ';
  readonly '_A': A;
  readonly '_URI': URI;
  constructor(public value: A) { }
}

export type NatF<A> = Zero<A> | Succ<A>;

If we had proper recursive types in TypeScript, we could define recursion schemes on the type level. However, I see little to none practical day-to-day usage of such possiblity.

As a final note, I would like to reference a module with some neat (and practically useful!) type-level operations from @GiulioCanti: https://github.com/gcanti/typelevel-ts

Another great resource I've used during preparation of this episode is the following blog post in Japanese from @ryotakameoka:
https://ryota-ka.hatenablog.com/entry/2017/12/21/000000

As usual, all code examples are available at https://github.com/YBogomolov/monadic-mondays

#MonadicMonday compilation: April

Yuriy Bogomolov — Sun, 28 Apr 2019 08:26:40 +0000

Episode 1: These/Ior monad

Welcome to #monadicmonday! Let's start with a These/Ior monad.

These is a monad which expresses "inclusive-OR" relation:

These(A, B) = A + B + A * B.

These represents a simple idea: it can hold either value of type A, value of type B or both of them simultaneously.

It may be present in FP libraries under it's literal name "These" (Haskell, TypeScript), or under "Ior" name (like in Scala's cats package).

Take a look at the following function in TypeScript using These monad from fp-ts package by @GiulioCanti:

import { both, that, These, this_ } from 'fp-ts/lib/These';

// May warn if user is under 18, or panic if user has negative age
const greet = (name: string, age: number): These<Error, string> => {
  if (age <= 0) {
    return this_(new Error(`You age cannot be less than zero! You've entered: ${age}`));
  }

  const greeting = `Hello, ${name}!`;
  if (age < 18) {
    return both(new Error('You cannot use our service at that age!'), greeting);
  }

  return that(greeting);
};

Now let's look at the examples. Note that we need to provide all possible "handlers" to fold function, so the monad could be reduced to a single value.

// Ex. 1: Alice is 14 years old:
const howIsAlice = greet('Alice', 14);

// Ex.2: Bob is hAx0r who tries to pen-test us:
const howIsBob = greet('Bob', -42);

// Ex. 3: Charlie is just a normie:
const howIsCharlie = greet('Charlie', 25);

Now let's transform this code to a full example:

import { array } from 'fp-ts/lib/Array';
import { error, log, warn } from 'fp-ts/lib/Console';
import { io } from 'fp-ts/lib/IO';

array.sequence(io)([howIsAlice, howIsBob, howIsCharlie]
  .map((person) => person.fold(
    (err) => error(err.message),
    (greeting) => log(greeting),
    (err, greeting) => warn(err.message).chain(() => log(greeting)),
  ))).run();

Finally, let's run our example!

You cannot use our service at that age!
Hello, Alice!
You age cannot be less than zero! You've entered: -42
Hello, Charlie!

Episode 2: rings

Welcome to the second episode of #monadicmonday! Today we'll talk about algebraic data types, and more specifically – about semirings and rings.

First of all, let's recap what a semiring is. Semiring is a set equipped with two binary operations, called "addition" and "multiplication". The intuition that works here is such of natural numbers – you can define a semiring for Nat with addition as "+" and multiplication as "*"

A ring extends a semiring with an additional "inverse" operation (or, strictly speaking, ring implies that for each 'a' there exists '-a'). Rings and semirings must also have "zero" and "one" elements, and multiplication should distribute over addition.

The other important characteristic is that rings and semirings form a monoid under multiplication.
Recap: monoid is defined using two operations:

combine :: A×A → A, which merges two monoids together,
empty :: A, which defines an entity for "one".

Let's define a ring instance for Option (Maybe) data type. We can define it in several possible ways, and it depends on how we treat "None" value. I've called those instances "safe ring" and "strict ring".

import { none, Option, some } from 'fp-ts/lib/Option';
import { getTupleRing, Ring } from 'fp-ts/lib/Ring';

const safeOptionRing: Ring<Option<number>> = {
  zero: none,
  one: some(1),
  add: (x, y) => x.fold(y, (_x) => y.fold(x, (_y) => some(_x + _y))),
  sub: (x, y) => x.fold(y, (_x) => y.fold(x, (_y) => some(_x - _y))),
  mul: (x, y) => x.fold(y, (_x) => y.fold(x, (_y) => some(_x * _y))),
};

const strictOptionRing: Ring<Option<number>> = {
  zero: none,
  one: some(1),
  add: (x, y) => x.fold(none, (_x) => y.fold(none, (_y) => some(_x + _y))),
  sub: (x, y) => x.fold(none, (_x) => y.fold(none, (_y) => some(_x - _y))),
  mul: (x, y) => x.fold(none, (_x) => y.fold(none, (_y) => some(_x * _y))),
};

Given a few different Option instances, we can observe different behavior of our rings:

const a: Option<number> = some(42);
const b: Option<number> = none;
const c: Option<number> = some(21);

// safe only:
const R1 = getTupleRing(safeOptionRing, safeOptionRing, safeOptionRing);

console.log(R1.add([a, b, c], [b, a, c])); // => [ some(42), some(42), some(42) ]
console.log(R1.add([a, b, c], R1.one)); // => [ some(43), some(1), some(22) ]
console.log(R1.sub([a, b, c], R1.zero)); // => [ some(42), none, some(21) ]
console.log(R1.mul([a, b, c], [a, b, c])); // => [ some(1764), none, some(441) ]

Strict rings:

// strict only:
const R2 = getTupleRing(strictOptionRing, strictOptionRing, strictOptionRing);

console.log(R2.add([a, b, c], [b, a, c])); // => [ none, none, some(42) ]
console.log(R2.add([a, b, c], R2.one)); // => [ some(43), none, some(22) ]
console.log(R2.sub([a, b, c], R2.zero)); // => [ none, none, none ]
console.log(R2.mul([a, b, c], [a, b, c])); // => [ some(1764), none, some(441) ]

Or we can mix&match a bit:

// mix&match:
const R3 = getTupleRing(strictOptionRing, safeOptionRing, strictOptionRing);

console.log(R3.add([a, b, c], [b, a, c])); // => [ none, some(42), some(42) ]
console.log(R3.add([a, b, c], R3.one)); // => [ some(43), some(1), some(22) ]
console.log(R3.sub([a, b, c], R3.zero)); // => [ none, none, none ]
console.log(R3.mul([a, b, c], [a, b, c])); // => [ some(1764), none, some(441) ]

If you can identify a structure as a (semi)ring, you can use its properties with confidence. For example:

set of languages form a semiring with product as string concatenation and addition as set union;
boolean logic naturally forms a semiring: (Boolean, &&, ||, true, false).

Fun fact: semiring is sometimes called "rig", because a riNg without Negative is just a "rig" ¯\_(ツ)_/¯

Semiring is sometimes defined as a monoid on + and a semigroup on *, i.e. 0 is mandatory but 1 is not. Then, Rig adds 1 only, Rng adds negation only, and Ring has both.

via λoλcat

I would like to give credit to @LukaJacobowitz for his awesome article "A Tale on Semirings", which I recommend for reading: https://lukajcb.github.io/blog/functional/2018/11/02/a-tale-of-semirings.html

Episode 3: Recursion schemes

In this episode we'll talk about quite complicated topic – recursion schemes. Hold tight, as the ride won't be easy.

First of all, I would like to stress that I'm still grokking this topic, so if you spot a mistake, please ping me back!

Recursion schemes were popularized by a classical paper by Mejer, Fokkinga and Petterson called "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire": https://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf

Recursion schemes are powerful way to generalize various recursion algorithms and make them composable and easy to reason about. Importance of recursion schemes for FP is of the same scale as importance of design patterns for OOP. I would like to give credit to @importantshock for his magnificent work on blog "Adventures in Uncertainty", which is the most thorough and detailed intro to recursion schemes I know: https://blog.sumtypeofway.com

There is a plethora of recursion schemes, to name a few:

catamorphism tears down a structure layer by layer – you may think of it as a general fold operation;
anamorphism builds up a (recursive) structure layer by layer – you probably know it under unfold name;
para- and apomorphisms fold and unfold a structure while preserving the information about original strcuture. This is achieved by passing along the recursive calls not only the computed value itself, but also the original term;
histo- and futumorphisms are dual morphisms which give you an access to previous (histo-) and future (futu-) results of the recursive computations. They are tremendously useful for solving dynamic programming problems, as we will see later;
and many more: chrono-, dyna-, prepro-, postpro-, and so on, even the almighty zygohistomorphic prepromorphism, which has become a semi-joke in the functional programmer community.

As usual, I will illustrate my examples in Haskell-esque type definitions and TypeScript with fp-ts library for the solution itself.
Let's solve a problem: given a desired amount N, and an infinite supply S = { S1, S2, .. , Sm} of coins, how many ways can we make the change?
BTW, this problem is described in great details in various tutorial blogs (like (link: https://www.geeksforgeeks.org/coin-change-dp-7/) geeksforgeeks.org/coin-change-dp…), so I won't be describing the solution approach here. Instead I will show you how to implement it using a histomorphism.

Let's recall histomorphism type:

histo :: Functor f => CVAlgebra f a -> Fix f -> a,

where

CVAlgebra f a = f (Cofree f a) -> a - a course-of-value algebra,

Cofree f a = Cofree { attribute :: a, hole :: f (Cofree f a) } - cofree comonad

and

Fix f = f (Fix f) - fixpoint of functor f

Well, I guess these parts require some additional explanation.
Course-of-value algebra allows us to access the additional payload (attribute) of current recursive term, as well as fall deeper into it's hole.

Cofree comonad is a good topic for another Monadic Monday, so today I will just say that it's a way to "mark" a recursive term with an additional marker of type a.

A Fix is an Y-combinator (fixpoint combinator) on the type-level, so it just represents an infinite sequence of type application:

type Fix t = t (t (t (t (t ...))))

For example, a singly-linked list can be described like so:

type List a = Fix (L a)
data L a b = Nil | Cons a b

You can think about list as a math isomorphism https://twitter.com/xgrommx/status/880560506385252353
1) Understanding via abstraction (build a new abstraction)
2) Math isomorphisms
3) Category theory (Category of F-algebras)

via Denis Stoyanov

To begin solving our coin change problem, let's define our auxillary types in TypeScript. We will need:

Fix type;
Nat type to represent Peano numbers;
Cofree type for our comonad;
instance NatC for Cofree;
CVAlgebra;
and match for pattern-matching:

import { Lazy } from 'fp-ts/lib/function';
import { HKT, Type, URIS } from 'fp-ts/lib/HKT';

export class Fix<F> {
  constructor(public readonly value: HKT<F, Fix<F>>) { }
}

export function fix<F>(value: HKT<F, Fix<F>>): Fix<F> {
  return new Fix(value);
}

export function unfix<F>(term: Fix<F>): HKT<F, Fix<F>> {
  return term.value;
}

export class Cofree<F, A> {
  constructor(readonly attribute: A, readonly hole: HKT<F, Cofree<F, A>>) { }
}

export const cofree = <F, A>(a: A, h: HKT<F, Cofree<F, A>>) => new Cofree(a, h);
export const attribute = <F, A>(c: Cofree<F, A>): A => c.attribute;

export function hole<F extends URIS, A>(c: Cofree<F, A>): Type<F, Cofree<F, A>>;
export function hole<F, A>(c: Cofree<F, A>): HKT<F, Cofree<F, A>> { return c.hole; }

export type Algebra<F, A> = (fa: HKT<F, A>) => A;
export type CVAlgebra<F, A> = (fa: HKT<F, Cofree<F, A>>) => A;

export const match = <T extends string>(toMatch: T) => <B>(ops: Record<T, Lazy<B>>) => ops[toMatch]();

Definition of Nat type requires some boilerplate in TypeScript, compared to terse Haskell counterpart:

data Nat a = Zero | Succ a
  deriving Functor

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

import { Fix, fix } from './Fix';

declare module 'fp-ts/lib/HKT' {
  interface URI2HKT<A> {
    Nat: NatF<A>;
  }
}

export const URI = 'Nat';
export type URI = typeof URI;

export class Zero<A> {
  static value = new Zero<any>();
  public value: never;
  readonly _tag: 'Zero' = 'Zero';
  readonly '_A': A;
  readonly '_URI': URI;
  private constructor() { }
  map<B>(_f: (a: A) => B): NatF<B> {
    return this as any;
  }
}

export class Succ<A> {
  readonly _tag: 'Succ' = 'Succ';
  readonly '_A': A;
  readonly '_URI': URI;
  constructor(public value: A) { }
  map<B>(f: (a: A) => B): NatF<B> {
    return new Succ(f(this.value));
  }
}

export type NatF<A> = Zero<A> | Succ<A>;
export type Nat = Fix<URI>;

export const zero = fix(Zero.value);
export const succ = (n: Nat): Nat => fix(new Succ(n));

export const functorNat: Functor1<URI> = {
  URI,
  map<A, B>(nat: NatF<A>, f: (a: A) => B): NatF<B> {
    return nat.map(f);
  },
};

The implementation of histo itself is identical to it's Haskell original from https://blog.sumtypeofway.com/recursion-schemes-part-iv-time-is-of-the-essence/:

export function histo<F extends URIS>(F: Functor1<F>): <A>(h: (fa: Type<F, Cofree<F, A>>) => A) => (term: Fix<F>) => A;
export function histo<F>(F: Functor<F>): <A>(h: CVAlgebra<F, A>) => (term: Fix<F>) => A {
  return <A>(h: CVAlgebra<F, A>) => {
    return function self(term): A {
      const worker = (t: Fix<F>): Cofree<F, A> => {
        const calc = F.map(unfix(t), worker);
        return cofree(h(calc), calc);
      };
      return attribute(worker(term));
    };
  };
}

To begin with the solution, we'll need to define two helper which convert a common JavaScript number into Nat and vice versa:

// NatC – cofree wrapper around our target solution type - list of "ways of change",
// i.e. all possible combinations of change for the given amount:
export type NatC = Cofree<URI, number[][]>;

// Convert plain JavaScript `number` into Peano number:
const expand = (amt: number): Nat => amt === 0 ? zero : succ(expand(amt - 1));

// Convert Peano number back to `number`:
const compress = (n: NatF<NatC>): number => match(n._tag)({
  Zero: constant(0),
  Succ: () => 1 + compress(hole(n.value)),
});

Finally, let's define change function, which differs from the one @importantshock described in his article. My implementation stores not just a number of ways given amount can be exchanged – this information is insufficient for the correct solution. Instead, I store the exact solutions for each amount. This gives me an additional bonus: I can print not only a number of ways, but the ways themselves! That's why my NatC instance for Cofree was holding not just a number, but an array of number arrays.

const lookup = <A>(cache: Cofree<URI, A>, n: number): A =>
  n === 0 ? attribute(cache) : lookup(hole(cache).value, n - 1);

const COINS = [1, 5, 10, 25, 50];

const change = (amt: number): number[][] => {
  const go = (curr: NatF<NatC>) => match(curr._tag)({
    Zero: constant([[]]),
    Succ: () => {
      const given: number = compress(curr);
      const validCoins = COINS.filter((c) => c <= given);
      // This is what differs: we store not only the sum of ways, but the exact solution itself:
      const remaining: Array<[number, number]> = validCoins.map((c) => ([c, given - c]));
      const { right: zeroes, left: toProcess } = partition(remaining, (a) => a[1] === 0);
      const results: number[][][] = toProcess.map(
        ([coin, remainder]) => lookup(curr.value, given - 1 - remainder).reduce<number[][]>(
          (arr, coins) => (coins.every((c) => c <= coin) && arr.push([coin, ...coins]), arr),
          [],
        ),
      );
      return zeroes.map(([c]) => [c]).concat(...results);
    },
  });

  return histo(functorNat)(go)(expand(amt));
};

And here's the result of running change for amounts of 15, 20 and 42 cents. We get not only valid sum, but all possible ways of change, too:

Episode 4: Either and co.

In this episode we'll talk about specialized variants of Either monad.

The first one I'd like to show is awesome RemoteData from @devexperts: https://github.com/devex-web-frontend/remote-data-ts

This monad encapsulates four states of network request:

request not started yet;
request is running;
request failed;
request succeeded.

This allows a developer to always handle erroneous and pending states of a network request – which, obviously, is a common thing among web devs.

Using RemoteData, I usually build my Redux store in the following way:

any data that is coming from the net is wrapped in RD;
in redux-saga I yield pending as a first operation, and then – either failure or success when the request is finished;
in reducers I just pass RD as is without any folding;
in my components I fold RD as late as possible – usually when I need to render it's data as a JSX.

It looks something like this:

Saga:

function* getDataSaga() {
  yield put({ type: 'GET_DATA_START', payload: pending });

  const result: RemoteData<Error, Data> = yield call(API().getData());

  yield put({ type: 'GET_DATA_FINISH', payload: result });
}

Reducer:

const getDataReducer =
  (state = initial, { type, payload }: AnyActionWithPayload<Data>) => {
    switch (type) {
      case 'GET_DATA_START':
      case 'GET_DATA_FINISH': {
        return payload;
      }
      default: {
        return state;
      }
    }
  };

Component

const mapDispatchToProps = (dispatch: Dispatch<ApplicationState>) => ({
  load: dispatch({ type: 'GET_DATA_INIT' }),
});

const MyComponent: React.FunctionComponent<MyComponentProps> = ({ dataRD, load }) => {
  const doLoad = () => {
    load();
  };

  return (
    <>
      {dataRD.foldL(
        () => <Button onClick={doLoad}>Load!</Button>,
        () => <CircularProgress variant='indeterminate' />,
        (error) => <Typography variant='h1'>{error.message}</Typography>,
        (data) => <User model={data.user} />,
      )}
    </>
  );
}

One positive consequence of RemoteData lies outside of code. My co-developers are "forced" to think about pendings (=loading) and failures (=errors), so they ask designers to provide explanation of system's behavior in all situation, so system can never be in inconsistent state.

The other useful ADT I would like to expose is Validation. It looks and behaves similar to Either, with one defference: it's not a monad, but an applicative functor. I recommend reading great article by @GiulioCanti: https://dev.to/gcanti/getting-started-with-fp-ts-either-vs-validation-5eja

Another useful monad, These, was described in the first episode: https://twitter.com/YuriyBogomolov/status/1112712151062458370. It's not an extension of Either like RemoteData, but carries similar to Either business semantics.

Conclusion

These were the topics covered during April's Monadic Mondays. Please let me know what do you think of it! I would be happy to get your feedback, so please ping me back at @ybogomolov in Telegram, @YuriyBogomolov in Twitter or via yuriy.bogomolov@gmail.com.

Forem: Yuriy Bogomolov

#MonadicMonday compilation: July

Episode 12: Futures

Episode 13: Property-based testing

Episode 14: Final

Typesafe Frontend Development

Preface

What is type safety?

Typesafe Patterns

Use const to allow easy reasoning

Avoid null and undefined

Avoid throwing exceptions and side effects

Compute as much as possible in compile time

Finally Tagless, Partially Evaluated

Conclusion

#MonadicMonday compilation: June

Episode 10: Reasons to choose FP

Episode 11: Kleisli arrows

#MonadicMonday compilation: May

Episode 5: Tagless Final

Episode 6: ZIO in TypeScript

Episode 7: Functional optics

Episode 8: Free Monads

Episode 9: Type-Level Programming

#MonadicMonday compilation: April

Episode 1: These/Ior monad

Episode 2: rings

Episode 3: Recursion schemes

Episode 4: Either and co.

Conclusion

Use `const` to allow easy reasoning

Avoid `null` and `undefined`