in Code

For many years now I’ve been using a mental model and intuition that has guided me well for understanding and teaching and using functors, applicatives, monads, and other related Haskell abstractions, as well as for approaching learning new ones. Sometimes when teaching Haskell I talk about this concept and assume everyone already has heard it, but I realize that it’s something universal yet easy to miss depending on how you’re learning it. So, here it is: how I understand the Functor and other related abstractions and free constructions in Haskell.

The crux is this: instead of thinking about what fmap changes, ask: what does fmap keep constant?

This isn’t a rigorous understanding and isn’t going to explain every aspect about every Functor, and will probably only be useful if you already know a little bit about Functors in Haskell. But it’s a nice intuition trick that has yet to majorly mislead me.

Read more … Comments

This is just a “personal life update” kind of post, but I recently found out a couple of cool things about my academic history that I thought were neat enough to write down so that I don’t forget them.

Read more … Comments

One thing I always appreciate about Haskell is that you can often choose the level of type-safety you want to work at. Haskell offers tools to be able to work at both extremes, whereas most languages only offer some limited part of the spectrum. Picking the right level often comes down to being consciously aware of the benefits/drawbacks/unique advantages to each.

So, here is a rundown of seven “levels” of type safety that you can operate at when working with the ubiquitous linked list data type, and how to use them! I genuinely believe all of these are useful (or useless) in their own different circumstances, even though the “extremes” at both ends are definitely pushing the limits of the language.

This post is written for an intermediate Haskeller, who is already familiar with ADTs and defining their own custom list type like data List a = Nil | Cons a (List a). But, be advised that most of the techniques discussed in this post (especially at both extremes) are considered esoteric at best and harmful at worst for most actual real-world applications. The point of this post is more to inspire the imagination and demonstrate principles that could be useful to apply in actual code, and not to present actual useful data structures.

All of the code here is available online here, and if you check out the repo and run nix develop you should be able to load them all in ghci as well:

$ cd code-samples/type-levels
$ nix develop
$ ghci
ghci> :load Level1.hs

Read more … Comments

AI is hot, so let’s talk about some “classical machine learning” in Haskell with k-means clustering! Let’s throw in some dependent types too.

There are a bazillion ways of implementing such a simple algorithm, but this is how I’d do it, as someone who develops almost exclusively in Haskell (or functional pure languages) in both personal projects and work. It’s not the “right” way or the “best” way, but it’s the way that brings me joy. Hopefully it can also break beyond the simple toy projects you’ll often see in conceptual tutorials. You’ll see how I integrate dependent types, type-driven development, mutable data structures, generating random data, and preparation for parallelism. I have been meaning to shift away from “conceptual” posts and instead post a bit more about small, practical snippets that demonstrate some useful Haskell techniques and principles drive how I approach coding in Haskell overall.

For reference, the intended audience is for people with knowledge of Haskell syntax and basic idioms (mapping, traversing, folding, applicatives). The source code is online here, and is structured as a nix flake script. If you have nix installed (and flakes enabled), you should be able to run the script as an executable (./kmeans.hs). You can also load it for editing with nix develop + ghci.

Read more … Comments

Happy new year! It’s been a while (almost three years) since my last post. But it’s a new year, a new me – and I just recently started working at a new job writing Haskell where everything is built and deployed using nix. Aside from the bliss that comes from being able to write Haskell as a day job, I also enjoyed the push to finally dive into the nix ecosystem for my general personal computing, which many of my friends have been subtly (or not so subtly) pushing me to look into for a long time. And I have to say, I’m hooked! I get a lot of similar joy using nix to organize my projects as I did when I was first learning Haskell. My path to re-organizing all of my personal projects to using nix has lead me back to one of my more “longer-running” pieces of legacy code – my 10 year old blog. So, this is a post from a naive new nix user on how I converted my blog deployment and building from a manual multi-stage build process into an automatic nix-with-cachix deploy – and some future things I would be hoping to investigate!

In this post I’ll also be explaining a bit of nix, so hopefully it’s accessible if you are curious like I was too. However, it’s not a tutorial — instead, it’s a high-level overview of the concepts that I put together to achieve the goal.

Read more … Comments

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).

Read more … Comments

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!

• Day 1 - Report Repair
• Day 2 - Passport Philosophy
• Day 3 - Toboggan Trajectory
• Day 4 - Passport Processing
• Day 5 - Binary Boarding
• Day 6 - Custom Customs
• Day 7 - Handy Haversacks
• Day 8 - Handheld Halting
• Day 9 - Encoding Error
• Day 10 - Adapter Array
• Day 11 - Seating System
• Day 12 - Rain Risk
• Day 13 - Shuttle Search
• Day 14 - Docking Data
• Day 15 - Rambunctious Recitations
• Day 16 - Ticket Translation
• Day 17 - Conway Cubes
• Day 18 - Operation Order
• Day 19 - Monster Messages
• Day 20 - Jurassic Jigsaw
• Day 21 - Allergen Assessment
• Day 22 - Crab Combat
• Day 23 - Crab Cups
• Day 24 - Lobby Layout
• Day 25 - Combo Breaker

Read more … Comments

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:

1. Applicative regular expressions
2. The functor combinatorpedia
3. Bidirectional serializers
4. Composable interpreters

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.

Read more … Comments