Ziyang Liu's Haskell Blog

There are two versions of StateT in the transformers package: lazy and strict. And each version comes with two functions for updating the state: the lazy modify and the strict modify'. As long as, one might contemplate, I stick to the strict StateT and the strict modify', it should be safe and I’d need to worry no more about space leaks, right? Wrong.

Generally speaking, GHC’s error messages are fairly helpful and intelligible (so long as you don’t go wild with type-level programming). But there are definitely a few common but relatively less clear ones. Some of the GHC type error messages that can potentially lead to bewilderment are discussed in this post. The GHC version I used is 8.10.2.

Side effects break referential transparency. If you have a function f which has a pure type but performs side effects behind closed doors (e.g., f x = unsafePerformIO ...), you’d have to be careful when refactoring the code. You may want to, for instance, avoid changing f x + f x into let y = f x in y + y.

This blog post summarizes, with bite-size bullet points, some knowledge on Haskell string types that I think is important to recognize when writing Haskell. The intended audience include inexperienced Haskell programmers, and experienced Haskell programmers who feel like refreshing their memory. The bullet list hopefully makes things reasonably easy to digest, and helps you eat Haskell string types for breakfast.

Today I’m going to discuss a solution which I implemented in Haskell to a problem in ACM-ICPC World Finals 2019, titled “First of Her Name”. The solution makes use of a sorting technique called “prefix doubling” as seen in suffix array algorithms, as well as radix sort.

Haskell is a great, if not the best language for embedding DSLs in. Thanks to Haskell’s modern type system and elegant syntax, devising embedded domain-specific languages (EDSL) that are both low friction and type safe is often fairly achievable. Let’s take a simple EDSL as a running example, and evolve it in a series of steps to make it more user-friendly and safer. The main machineries involved are the indexed state monad (IxState) and some moderate type-level programming.

This is yet another CPS introduction post, with a focus on the use cases of CPS. This is where I find some other CPS articles to be insufficient in, for example, when I first read the CPS entry on Wikibooks, I got what CPS is but it wasn’t quite clear to me what the different ways are in which CPS can profitably be used in practice. Besides, CPS is a fairly obscure, convoluted and counter-intuitive thing, so I reckon another post that explains it is always beneficial.

The codebase I regularly work with uses in many places integer types that are not Int, including Integer, Natural, Word32, Word64, etc. A number of functions in Data.List, however, only works with Int, such as length, and so there’s a lot of fromIntegrals floating around, which isn’t pretty. I was once tempted to get rid of all these fromIntegrals by using genericLength, and a coworker reviewing the PR pointed out that the doc of genericLength mentions the following:

I’ve been playing with fixed points of Haskell functors lately and thought it would be useful to write down some of my thoughts, both to solidify my understanding and for future reference. If it happens to be helpful for someone else, then all the better. I guess I’ll start with Haskell’s category.

Beautiful Bridges is one of the eleven problems in ACM ICPC World Finals 2019. The problem set can be found here. In this post, we are going to solve this problem in two different ways, both of which involve specifying the problem as a relational hylomorphism, and extracting, via algebraic reasoning, an efficient functional program that conforms to the specification.