# in Code

## Justin Le

Welcome! My name is Justin Le. I’m an Applied Math/Computational Science PhD with a background with physics, currently working at SimSpace doing Haskell for cyber-security platforms. This is just my weblog covering my various adventures in programming and explorations in the vast worlds of computation, physics, engineering, mathematics, and knowledge. Expect a healthy curiosity and an only slightly unhealthy obsession for finding new ways to marvel, wonder, and create. Join me if you wish!

Check out some of my most popular articles: First-Class Statements, “IO Monad” Considered Harmful, and Purely Functional Typed Models!

## Recent Entries

• ### Breaking a Degenerate Hyper-Dimensional Game of Life

tldr: Demonstrated with interactive visualizations and simulations — over the course of a month, we were able to discover successive new mathematical properties of a “degenerate” hyper-dimensional game of life" to take a “7 dimensions may just barely be possible on a commercial PC, could we ever reach 10 dimensions?” to “10 dimensions is easy enough to be run on any modern browser (jump to spoilers here), and 60 dimensions can be reached with a compiled language”.

This is a story about breaking a degenerate hyper-dimensional game of life via interactive exploratory visualizations and math!

T’was the night before Thursday, December 17, 2020, the release of “Conway Cubes”. It was Day 17 of Advent of Code 2020, a series of fun little themed coding puzzles building up to Christmas; I always enjoyed these puzzles because they are so self-contained and tidy that they are often open-ended in the interesting ways you can solve them or expand on them (which I’ve written many blog posts on).

On the surface, Day 17 seemed to be a straightforward extension of Conway’s Game Of Life (“GoL”). GoL is a simulation played out on a 2D grid, where cells are “on” and “off”, and at each step of the simulation the states spread and propagate in interesting ways based on the state of their neighbors (a 2D cellular automaton). The twist of the Advent of Code puzzle is it asks what would happen if we played out the rules of GoL in 3D instead, and then 4D.

I submitted my solution on my assigned puzzle input with a naive implementation (placing 66 and 66 on the leaderboards for that day), concluding the “competitive” part. Of course, the real fun always starts after. When discussing with some friends (on the subreddit and freenode’s ##adventofcode channel), we started talking about the trade-offs of different implementations and realized that the extra dimensionality was no joke: as you upped the number of dimensions, the number of points you have to consider grow exponentially, and so does the number of neighbors at each point to check. 4D can be solved naively, but anything higher is going to be strained. My naive solution on 6D took three minutes, and 7D in a reasonable amount of time (requiring as much as 612,220,032 points with 2,186 neighbors each) seemed impossible on commercial consumer hardware because of the sheer number of points in 7D space. But I thought…what if a breakthrough in optimization was possible? I set an (arbitrary) personal goal of reaching 10D (3,570,467,226,624 points with 59,048 neighbors each), not knowing if it would ever be possible.

And soon…a breakthrough did come! Someone brought up that if we look at the 3d version, we see there’s actually a mirror symmetry! Because everything starts off on the xy plane, with z=0, the resulting progression must be symmetrical on both sides (positive and negative z).

• ### Advent of Code 2020: Haskell Solution Reflections for all 25 Days

Merry Christmas and Happy New Years, to all!

Once again, every year I like to participate in Eric Wastl’s Advent of Code! It’s a series of 25 Christmas-themed puzzles that release every day at midnight — there’s a cute story motivating each one, usually revolving around saving Christmas. Every night my friends and I (including the good people of freenode’s ##advent-of-code channel) talk about the puzzle and creative ways to solve it (and also see how my bingo card is doing). The subreddit community is also pretty great as well! And an even nicer thing is that the puzzles are open-ended enough that there are often many ways of approaching them…including some approaches that can leverage math concepts in surprising ways, like group theory, galilean transformations and linear algebra, and more group theory. Many of the puzzles are often simple data transformations that Haskell is especially good at!

Speaking of Haskell, I usually do a write-up for every day I can get around to about unique insights that solving in Haskell can provide to each different puzzle. I did them in 2017, 2018, and 2019, but I never finished every day. But 2020 being what it is, I was able to finish! :D

You can find all of them here, but here are links to each individual one. Hopefully you can find them helpful. And if you haven’t yet, why not try Advent of Code yourself? :) And drop by the freenode ##advent-of-code channel, we’d love to say hi and chat, or help out! Thanks all for reading, and also thanks to Eric for a great event this year, as always!

• ### Roll your own Holly Jolly streaming combinators with Free

Hi! Welcome, if you’re joining us from the great Advent of Haskell 2020 event! Feel free to grab a hot chocolate and sit back by the fireplace. I’m honored to be able to be a part of the event this year; it’s a great initiative and harkens back to the age-old Haskell tradition of bite-sized Functional Programming “advent calendars”. I remember when I was first learning Haskell, Ollie Charles’ 24 Days of Hackage series was one of my favorite series that helped me really get into the exciting world of Haskell and the all the doors that functional programming can open.

All of the posts this year have been great — they range from insightful reflections on the nature of Haskell and programming in Haskell, or also on specific language features. This post is going to be one of the “project-based” ones, where we walk through and introduce a solidly intermediate Haskell technique as it applies to building a useful general toolset. I’m going to be exploring the “functor combinator style” where you identify the interface you want, associate it with a common Haskell typeclass, pick your primitives, and automatically get the ability to imbue your primitives with the structure you need. I’ve talked about this previously with:

and I wanted to share a recent application I have been able to use apply it with where just thinking about the primitives gave me almost all the functionality I needed for a type: composable streaming combinators. This specific application is also very applicable to integrate into any composable effects system, since it’s essentially a monadic interface.

In a way, this post could also be seen as capturing the spirit of the holidays by reminiscing about the days of yore — looking back at one of the more exciting times in modern Haskell’s development, where competing composable streaming libraries were at the forefront of practical innovation. The dust has settled on that a bit, but it every time I think about composable streaming combinators, I do get a bit nostalgic :)

This post is written for an intermediate Haskell audience, and will assume you have a familiarity with monads and monadic interfaces, and also a little bit of experience with monad transformers. Note — there are many ways to arrive at the same result, but this post is more of a demonstration of a certain style and approach that has benefited my greatly in the past.

• ### Shuffling things up: Applying Group Theory in Advent of Code

So it’s November, and Advent of Code season is in the air! It’s time for everyone’s favorite Santa-based light hearted learn-to-program-or-a-new-language holiday season programming challenge series. Every year a bunch of us gather around the fireplace, roast chestnuts, and brainstorm all of the interesting ways we can solve these cute themed puzzles every day. These puzzles are designed to accessible enough for most new programmers, but deep enough to provide entertainment for experienced ones. I’ve written many blog posts on some of the interesting insight some of the puzzles have yielded, and I also post my reflections on as many puzzles I can while solving them in Haskell. And if you’re solving things in Haskell, I also published an open-sourced rate-limited API library so you can fetch and submit answers from the comfort of your command line.

To kick off the season, I’ve decided to write about one of my favorite puzzles from Advent of Code 2019 – Day 22: Slam Shuffle. To me, it stands out because it’s a perfect example of how Haskell’s approach to mathematical abstraction nudges you into the direction of an efficient solution — in a way that other languages would obscure or make less obvious.

So, let’s dive in! In the end, hopefully this post can get you excited for this wonderful season, and maybe also shed some insight into what it means when we say that Haskell can help you leverage math to find good solutions to your real problems.

Of course, this post has spoilers for Advent of Code 2019 Day 22, if you are planning on trying to figure it out from yourself. If you haven’t tried it, I recommend you give it a shot and come back after! :D

• ### Enhancing Functor Structures Step-By-Step (Part 2)

Welcome to Part 2 of the “Enhancing Functor Structures” series! Here we are taking a base structure describing a data type schema and enhancing it step-by-step with new functory capabilities: first, covariant capabilities (to generate parsers), then contravariant capabilities (to generate serializers)…who knows what might be in store next?

Please do check out Part 1 if you haven’t already, since this post pretty much jumps straight into things!

• ### Enhancing Functor Structures Step-By-Step (Part 1)

A style of Haskell programming that I’ve been pretty excited about with over the past two years or so is something that I can maybe call a “functor structure” design pattern. In this post we’re going to be exploring the idea of enhancing normal data types with different types of functor structures step-by-step, by starting with a simple useful structure and enhancing it piece by piece in order to reap incremental benefits. This process reflects a lot of the way I personally work through these things — I normally don’t get the whole powerful structure all the way; instead I incrementally add things as I see how things fit together.

We’re going build the tools to describe a data type schema, which can represent algebraic data types — sums and products. We’ll start off just building things we can use to describe the schema (by printing out documentation), and by the end of the journey we’ll also be able to use our schema to generate parsers and serializers through json.

This interest in functor structures culminated in my Functor Combinatorpedia post last year and the functor-combinators library. But personally I had never really explored the less commonly used lowercase-f functor abstractions in Hask — contravariant functors and invariant functors until recently.

This series is designed for an intermediate Haskeller with familiarity in things like product/sum types, using Applicative/Alternative, and monadic parser combinators, and is written in sync with functor-combinators-0.3.6.0.

• ### Introducing the mutable library

mutable: documentation / reference / github

(Note: This post has been heavily revised to reflect mutable-0.2.0.0, as of July 2020. For reference, the original post is available on github.)

I’m excited to announce the release of the mutable library!

The library offers what I call beautiful mutable values1 — automatic, composable piecewise-mutable references for your data types. Sort of like an automatically generated MVector, but for all your ADTs.

My high-level goal was a composable and overhead-free solution for dealing with mutable values in Haskell in a type-safe and clean way. After all, why do imperative languages have to have all the fun? In Haskell, we can have the best of both worlds: efficient and clean mutable algorithms and type safety.

The official documentation and homepage is here, so it’s a good read if you want to be introduced to how to use the library and where it is most effective. But I’m going to use this blog post to talk about why I wrote the library, some of the neat things you can do with it, and the techniques that went into writing it.

1. Okay so I don’t actually think the library is beautiful, I just like the way that “beautiful mutable values” sounds when you say it out loud.↩︎

• ### Adjunctions in the wild: foldl

I recently made a few connections that linked some different concepts in Haskell that I hadn’t realized before. They deal with one of my favorite “practical” libraries in Haskell, and also one of the more “profound” category theory-inspired abstractions in Haskell. In the process, it made the library a bit more useful to me, and also made the concept a bit more concrete and understandable to me.

This post mainly goes through my thought process in finding this out — it’s very much a “how I think through this” sort of thing — in the end, the goal is to show how much this example made me further appreciate the conceptual idea of adjunctions and how they can pop up in interesting places in practical libraries. Unlike most of my other posts, it’s not about necessarily about how practically useful an abstraction is, but rather what insight it gives us to understanding its instances.

The audience of this post is Haskellers with an understanding/appreciation of abstractions like Applicative, but be aware that the final section is separately considered as a fun aside for those familiar with some of Haskell’s more esoteric types. The code samples used here (along with exercise solutions) are available on github.