in Code

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.

Read more … Comments

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 values¹ — 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.↩︎

Read more … Comments

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.

Read more … Comments

In my time I’ve written a lot of throwaway binary TCP/IP services (servers and services you can interact with over an internet connection, through command line interface or GUI). For me, this involves designing a protocol from scratch every time with varying levels of hand-rolled authentication and error detection (Send this byte for this command, this byte for this other command, etc.). Once I design the protocol, I then have to write both the command line client and the server — something I usually do from scratch over the raw TCP streams.

This process was fun (and informative) the first few times I did it, but spinning it up from scratch again every time discouraged me from doing it very often. However, thankfully, with the servant haskell library (and servant-cli, for command line clients), writing a TCP server/client pair for a TCP service (using HTTP under the hood) becomes dead-simple — the barrier for creating one fades away that designing/writing a service becomes a tool that I reach for immediately in a lot of cases without second thought.

servant is usually advertised as a tool for writing web servers, web applications, and REST APIs, but it’s easily adapted to write non-web things as well. Let’s dive in and write a simple TCP/IP service (a todo list manager) to see how straightforward the process is!

To goal of this article is to take service/program that you already have planned out, and easily provide it with a networked API that can be used over any TCP/IP connection (over the internet, or even locally). This won’t teach you how to write a todo app, but rather how to hook up a todo app over a TCP/IP connection quickly, with a command line client — and in such a simple way that you wouldn’t give a second thought based on complexity issues.

This post can also serve as a stepping-stone to a “microservices architecture”, if you intend to build towards one (this is explored deeper by k-bx)…but really it’s more focused for standalone user-facing applications. How you apply these techniques is up to you :)

All of the code in this article is available online, and the server and client are available as “stack executables”: if you download them all, and set the permissions properly (chmod u+x), you can directly run them to launch the server and client (if they are all download to the same directory).

Read more … Comments

functor-combinators: hackage / github

(Note: This post has been heavily revised to reflect the functor-combinators-0.2 refactoring, as of November 2019. For reference, the original post is available on github.)

(Note 2: The section on contravariant functor combinators was added following the release of functor-combinators-0.3 in August 2020, which added support for contravariant and invariant functor combinators.)

Recently I’ve been very productive what I have been calling the “Functor Combinator” design pattern. It is heavily influenced by ideas like Data types a la Carte and unified free monoidal functors, but the end goal is slightly different in spirit. The goal is to represent schemas, DSL’s, and computations (things like parsers, things to execute, things to consume or produce data) by assembling “self-evident” basic primitives and subjecting them to many different successive transformations and combiners (through combinators, free structures, tensors, and other options). The process of doing so:

1. Forces you to make explicit decisions about the structure of your computation type as an ADT.
2. Allows you to retain isolation of fundamental parts of your domain as separate types
3. Lets you manipulate the structure of your final computation type through normal Haskell techniques like pattern matching. The structure is available throughout the entire process, so you can replace individual components and values within your structure.
4. Allows you to fully reflect the structure of your final computation through pattern matching and folds, so you can inspect the structure and produce useful summaries.

Like “data types a la carte” and free monad/applicative/alternative designs, these techniques allow you to separate the assembly and inspection of your programs from the “running” of them.¹ However, the main difference is that here we focus not just on products and sums, but many different varied and multi-purpose combinators — a “zoo” of combinators. The fixed point is not the end goal. The actual ADT data types themselves are the goal.

---

1. On the surface, this functor combinator design pattern might look like it fills a similar space to effects systems and libraries like mtl, polysemy, freer-simple, or fused-effects. However, this design pattern actually exists on a different level.

   Functor combinator design patterns can be used to help build the structure of the data types and schemas that define your program/DSL. Once you build these nice structures, you then interpret them into some target context. This “target context” is the realm that libraries like mtl and polysemy can fill; functor combinators serve to help you define a structure for your program before you interpret it into whatever Applicative or Monad or effects system you end up using.↩︎

Read more … Comments

Today, we’re going to implement applicative regular expressions and parsers (in the style of the regex-applicative library) using free structures!

Free structures are some of my favorite tools in Haskell, and I’ve actually written a few posts about them before, including this one using free groups, this one on a free monad variation, and this one on a “free” applicative on a monoid.

Regular expressions (and parsers) are ubiquitous in computer science and programming, and I hope that demonstrating that they are pretty straightforward to implement using free structures will help you see the value in free structures without getting too bogged down in the details!

All of the code in this post is available online as a “stack executable”. When you run it (./regexp.hs), you’ll load up a ghci session with all of the definitions in scope, so you can play around with the functions and types :)

This post should be accessible to late beginner or early intermediate Haskell users, and requires some basic familiarity with pattern matching, algebraic data types, and abstractions like Monoid and Functor, and do notation.

Read more … Comments

Not too long ago, I was browsing the prequel memes subreddit — a community built around creative ways of remixing and re-contextualizing quotes from the cinematic corpus of the three Star Wars “prequel” movies — when I noticed that a fad was in progress constructing tries based on quotes as keys indexing stills from the movie corresponding to those quotes.

This inspired me to try playing around with some tries myself, and it gave me an excuse to play around with recursion-schemes (one of my favorite Haskell libraries). If you haven’t heard about it yet, recursion-schemes (and the similar library data-fix) abstracts over common recursive functions written on recursive data types. It exploits the fact that a lot of recursive functions for different recursive data types all really follow the same pattern and gives us powerful tools for writing cleaner and safer code, and also for seeing our data types in a different light. The library is a pathway to many viewpoints — some considered to be particularly natural.

Recursion schemes is a perfect example of those amazing accidents that happen throughout the Haskell ecosystem: an extremely “theoretically beautiful” abstraction that also happens to be extremely useful for writing industrially rigorous code.

Is it possible to learn this power? Yes! As a fun intermediate-level Haskell project, let’s build a trie data type in Haskell based on recursion-schemes to see what it has to offer!

Read more … Comments

(TL;DR: scroll down to the very bottom for a summary and the closed form solution)

Another short Advent of Code post! Advent of Code 2018 is in full swing; we’re 40% of the way through. Every once in a while, if I find a fun way to solve a problem, I’ll make a short post about it. You can check out my other ones here on the series page, and you can also find my daily reflections here, as well. And, again, if you’re following along in Haskell, why not hop on glguy’s semi-official Haskell Leaderboard (join code 43100-84040706)! There are also Haskellers on freenode ##adventofcode, and also #adventofcode on the Functional Programming slack. You might also find my advent of code api haskell bindings helpful too!

Today, we’re going to be using linear algebra, calculus, and galilian transformations to solve the Day 10 challenge. (That’s right, this isn’t just a Haskell blog, I do have math posts on occasion too :) )

Read more … Comments