in Code

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

Hi all! If you don’t already know, Advent of Code is in full swing this year! If you’re participating and using Haskell, you’re welcome to join us at 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. I also wrote a haskell library to the API, if you’re looking to streamline your process!

My daily reflections are online, where I talk about how I approach each problem and what insight purely typed Functional Programming gives us for each problem.

Every once in a while I’ll find a challenge that I think can be pulled out as a short blog post, so I’ll bring them onto the blog for a more long-term sort of longevity!¹

In this one, I’ll talk about using group theory to solve the Day 5 challenge. Spoilers for those who have not solved it yet!

Read more … Comments

Hi again! Welcome back; let’s jump right into the fourth and final part of our journey through the singleton design pattern and the great singletons library.

Please check out the first three parts of the series and make sure you are comfortable with them before reading on. I definitely also recommend trying out some or all of the exercises, since we are going to be building on the concepts in those posts in a pretty heavy way.

Today we’re going to jump straight into functional programming at the type level. Code in this post is built on GHC 8.6.1 with the nightly-2018-09-29 snapshot (so, singletons-2.5). However, unless noted, all of the code should still work with GHC 8.4 and singletons-2.4.

Read more … Comments

Welcome back! This article is part 3 of our journey through the singleton design pattern, and the great singletons library!

This post will be a continuation of Part 1 and Part 2, so if you haven’t read those first, now would be a good time to pause and do so (and also try to complete the exercises). Today we will be expanding on the ideas in those posts by working with more complex ways to restrict functions based on types. Like the previous posts, we will start by writing things “by hand”, and then jumping into the singletons library and seeing how the framework gives you tools to work with these ideas in a smoother way.

The first half of today’s post will introduce a new application and design pattern that the usage of singletons greatly enhances. The second part of today’s post deals directly with the lifting of functions to the type level, which is made practical by the usage of singletons and the singletons library.

Code in this post is built on GHC 8.6.1 with the nightly-2018-09-29 snapshot (so, singletons-2.5). However, unless noted, all of the code should still work with GHC 8.4 and singletons-2.4. Again, you can download the source for this file here, and, if stack is installed, you can drop into a ghci session with all of the bindings in scope executing it:

$ ./Door3.hs

Read more … Comments

I’ve written about a variety of topics on this blog, but one thing I haven’t touched in too much detail is the topic of lenses and optics. A big part of this is because there are already so many great resources on lenses.

This post won’t be a “lens tutorial”, but rather a dive into an perspective on lenses and prisms that I’ve heard repeated many times (usually credited to Edward Kmett, but shachaf has helped me trace the origins back to this paste by Reid Barton) but never quite expanded on in-depth. In particular, I’m going to talk about the perspective of lenses and prisms as embodying the essences of products and sums (respectively), the insights that perspective brings, how well it flows into the “profunctor optics” formulation, and how you can apply these observations to practical usage of lenses and prisms.

The “final code” in this post is available online as a “stack executable” that, when run, will pop you into a ghci session with all of the final definitions in scope, so you can play around with them :)

Read more … Comments

Short version: I’ve started a Patreon page for those who want to donate or help me sustain my writing in my post-doctoral life! :D

Long version: Hi all! Hope you can excuse the two non-technical and personal posts in a row :) To give some context on this announcement, here’s some news — I graduated*!

*Well, not exactly :) I haven’t finished my dissertation and defended my thesis yet (but expect to in the upcoming months); Chapman University was generous enough to allow me to walk in this past Spring’s ceremony.

I have a lot of excitement about my future after my defense and official commencement. However, with this excitement comes a lot of uncertainty.

As a student I have been able to devote time on-and-off again to this blog, which has become a passion of mine. I’ve even managed to find time to live-stream some coding projects occasionally! When I started this blog almost five years ago, I only wanted to write down what I was learning to help myself remember, and to help others going through the same thing as me. I never expected the warm reception from the Haskell and Programming community. Every once in a while I meet people who tell me personally that an article of mine had inspired them to get into functional programming, or had been the final straw to helping them get over a conceptual hurdle. It’s moments like these that really make everything worth it. And, as a researcher in a field dominated by imperative and dynamically typed programming, watching and encouraging the growth of functional programming has brought me a lot of joy.

Read more … Comments