Posted on December 23, 2025 Working with grids in Haskell (or any purely functional language, I’m sure) can be pretty painful, but it doesn’t have to be. The reason it’s so painful is that we’re tempted to manipulate grids using indices. Now maybe if we’re using a nice array library such as vector , then index-based manipulations aren’t so gross, but in this article, I’ll show you a way to…
Posted on October 19, 2025 First imagine that the OCaml type int is infinite. Now what happens when you refunctionalize an infinite datatype? Let make a concrete program to work with. This will be a stateful generator that outputs the integers, starting at 0 , and ending at an exclusive limit n . type 'a gen = { next : unit -> 'a option } let range n = let r = ref 0 in { next = fun () -> let i =…
Posted on July 31, 2025 Short answer: hard, but not as hard as I thought. This is part 2 of a series of posts on the implementation of a dependently-typed lambda-calculus. In part 1, we discussed the need for normalization of terms, and used a powerful, extensible approach called Normalization by Evaluation to implement a normalization procedure. In this post, we’ll implement the typechecking…
Posted on May 23, 2025 Short answer: hard, but not as hard as I thought. Type systems in which the types (of functions, typically) may depend on terms are called dependently-typed. These systems exist on a spectrum, where restricted forms of dependent types exist in common functional programming languages such as OCaml, Haskell, and even TypeScript; the most complex forms of dependent types appear…
Posted on February 20, 2025 At long last I combine my two passions to form an unlikely duo: mathematical rigour and bodybuilding. For me, the biggest challenge in bodybuilding has always been to eat enough. The apps out there for tracking macros and meal planning always left me dissastisfied, so I even made my own called macro-traco. But in macro-traco, I made the same mistake that major apps like…
Posted on September 27, 2024 As I prepare for technical interviews, I’ve been grinding Leetcode to practice my data structures and algorithms. (And if you’re looking to hire in 2025, hit me up .) I want to share detailed explanations of three different, fairly short solutions to Problem 10 , “regular expression matching.” I especially find it interesting when a problem admits multiple, workable…
Posted on April 2, 2023 Some languages define a variant of return called yield . When a function returns normally, it’s finished, but when a function yields, the execution context of the function is saved, enabling us to re-enter the function to resume its execution. Such resumable functions are especially convenient for defining lazily generated sequences. Such functions that generate sequences…
Posted on March 25, 2023 Once upon a time, some seven years ago, I wrote a post about a Python trick for accessing the first element of any kind of sequence. The gist of that article is that just using indexing isn’t general enough: if the sequence is lazily computed by a generator, then indexing won’t work. What does work, however, is to iterate over the sequence using a for loop. But since we…
Posted on February 12, 2023 Originally developed as a technique for implementing compilers for (higher-order) functional languages, defunctionalization (d17n) is a program transformation that eliminates higher-order functions. It is based on the following observation: although there might be infinitely many possible functions one might pass to a higher-order function, there are only finitely many…
Posted on January 22, 2023 (This article was originally drafted in February 2022. The topic is very much related to the previous article’s, Implementing environment-based evaluation of recursive functions in OCaml , but they can very much be read independently.) Whew, that’s a title that takes some unpacking! Asynchronous recursion is a concept in JavaScript, and presumably in other languages with…