I love recursion. As I’ve blogged about before , recursive implementations are usually the most maintainable way to solve inherently-recursive problems. That said, I do most of my programming in node.js and TypeScript, and I also love it when my code doesn’t overflow the stack. These things are sometimes in conflict. This post is about a technique for manually converting elegant, maintainable…
Continuation-passing style (CPS) is an occasionally very useful technique which is fairly niche for developers outside of functional programming languages. Many JavaScript developers are familiar with a similar technique in which callbacks are used to handle asynchronous operations in pre-promise-era node.js code, but CPS itself is more general. This post will introduce CPS and show how it can…
It seems to be common knowledge that any recursive function can be transformed into an iterative function. This post is an argument as to why you may not want to do that. Tree traversal One factor I consider when evaluating the quality of a solution is the degree to which its approach magnifies perturbations in requirements. As an example, consider a function which converts a binary tree to a…
I’ve had three different things on my mind recently: I read the excellent blog post “ Hyper-Typing ”. I watched a proponent of dynamically typed languages claim that state machines can’t be represented in statically typed languages. I’ve noticed a trend of posts on the r/typescript subreddit, in which posters make heavy usage of advanced TypeScript features in order to enforce invariants which…
We say that code is “extensible” when it can be augmented with additional behavior without requiring modifications to existing code. Extensibility is a valuable property because it allows systems to grow over time without unnecessary rework. Under traditional idiomatic development most systems have undesirable limits on their extensibility: systems based on object-oriented programming (using…
JavaScript and TypeScript developers often look down on the original Gang of Four design patterns as irrelevant. Some (though not all) are rendered unnecessary due to the flexibility that JS provides over C++, and TS preserves most of the relevant flexibility. This post focuses on one of the patterns which remains relevant: the Visitor pattern. The Visitor pattern enables a beneficial mixing of…
Previously I wrote about the Church encoding of non-recursive algebraic data types . In this post I’ll cover the Church encoding of recursive data types, as well as the related Scott encoding. This post uses TypeScript, and will use the abbreviation “ADT” to mean “algebraic data type”, not “abstract data type”. This post is longer than I’d prefer, but I’ve chosen to err on the side of…
When first learning about the lambda calculus, students are frequently introduced to Church numerals and Church-encoded booleans. These enable the expression of simple data types as pure functions. When I was first learning about them these encodings felt arbitrary, because I did not understand that they were expressions of a more general underlying principle. This post explores this more general…
In my last post I said that there were three fundamental approaches to representing data: abstract data types, objects, and algebraic data types. I introduced abstract data types and objects (using a strict definition of “object” based on autognosis) and showed the tradeoffs of implementing data structures in these two styles. In this post I’ll introduce the third way to represent data, the…
There are three main methods of representing data which developers are likely to encounter: abstract data types, algebraic data types, and objects. Abstract data types (frequently abbreviated “ADTs”) are likely familiar to developers with a computer science background, and algebraic data types (unfortunately also abbreviated “ADTs”) are likely familiar to developers with a functional programming…
I previously did my blogging on Medium. I plan to convert my old blog posts from JavaScript+Flow to TypeScript, and move them here. In the meantime, though, here are links to most of my older posts: On functors: (prelude to inevitable monad tutorial) A Short Introduction to Functors An Introduction to Applicative Functors Functional Side Effects with Applicatives, parts One , Two , and Three On…
I worry about using terms which have heavily overloaded meanings. In software discourse, “simple” and “complex” may be the most pernicious, and using them without referencing a specific definition is virtually guaranteed to cause misunderstanding and strife. In the same vein, I’ve recently developed an aversion to the term “overengineering”. It can equally be applied to adding excessive layers to…