A blog about functional programming and stuff
A lazy take on a classic game theory algorithm. Sip a caffè latte while thinking about lattices Haskell extensions and imports used in this post {-# LANGUAGE DataKinds, DeriveGeneric, DeriveTraversable, DerivingStrategies, GeneralizedNewtypeDeriving, RankNTypes, ScopedTypeVariables, StandaloneDeriving, TypeFamilies #-} import Data.Ord ( Down ( Down , getDown )) import Data.List.NonEmpty ( NonEmpty…
Twelve years of Haskell Twentyseven is a Rubik’s cube solver and one of my earliest projects in Haskell. The first commit dates from January 2014, and version 0.0.0 was uploaded on Hackage in March 2016. I first heard of Haskell in a course on lambda calculus in 2013. A programming language with lazy evaluation sounded like a crazy idea, so I gave it a try. Since then, I have kept writing in…
To visit a tree or graph in breadth-first order, there are two main implementation approaches: queue-based or level-based. Our goal here is to develop a level-based approach where the levels of the breadth-first walk are constructed compositionally and dynamically . Compositionality means that for every node, its descendants—the other nodes reachable from it—are defined by composing the…
An old French meme On my feed aggregator haskell.pl-a.net , I occasionally saw posts with broken titles like this ( from ezyang’s blog ): What’s different this time? LLM edition Yesterday I decided to do something about it. Locating the problem Tracing back where it came from, that title was sent already broken by Planet Haskell , which is itself a feed aggregator for blogs . The blog originally…
“Algebraic data types” is a beloved feature of programming languages with such a mysterious name. Where does this name come from? There are two main episodes in this saga: Hope and Miranda. The primary conclusion is that the name comes from universal algebra, whereas another common interpretation of “algebraic” as a reference to “sums of products” is not historically accurate. We drive the point…
Everybody knows that regular expressions are not Turing-complete. That won’t stop me from doing this. In a Turing machine, there is a tape and there is a program. What is the program in a Turing machine? drumroll 🥁… It is a finite-state machine, which is equivalent to a regular expression! Just for a silly pun, I’m going to introduce this programming language in an absurd allegory about T-rexes…
I’ve been reading The Joy of Abstraction, by Eugenia Cheng. Very accessible. Would recommend. It’s doing good stuff to my mind. Abstraction, food for thought Two apples are the same as two apples. Two apples are not the same as two oranges. Two ripe apples are not the same as two rotten apples, even though they are both two apples and two apples. Two fruits are the same as two fruits, even though…
The upcoming version of GHC will feature primitives for delimited continuations . Let’s put them to use and build a bare bones algebraic effect system. Algebraic effects In Haskell, different sorts of effectful computations can be expressed using monads. Monads for individual effects are fairly well understood. The challenge now is to combine many different effects. Applications manage many kinds…
My favorite Haskell trick is how to use quantified constraints with type families. Kudos to Iceland_jack for coming up with it. Quantified constraints and type families QuantifiedConstraints is an extension from GHC 8.6 that lets us use forall in constraints. It lets us express constraints for instances of higher-kinded types like Fix : newtype Fix f = Fix ( f ( Fix f )) deriving instance ( forall…
Combinatorics studies mathematical structures by counting. Counting may seem like a benign activity, but the same rigor necessary to prevent double- or under-counting mistakes arguably underpins all of mathematics. 1 Combining my two favorite topics, I’ve always wanted to mechanize combinatorics in Coq. 2 An immediate challenge is to formalize the idea of “set”. 3 We have to be able to define the…