In this post we will implement a data compression program in about 150 lines of Haskell.It will use Huffman coding and handle arbitrary binary files using constant memory for encoding and decoding.The plan is:We briefly cover what Huffman codes are and how they can be used for data compression.We write a coder capable of compressing text.In the last step we use this coder to compress any file at all.We will leverage laziness to keep our memory footprint constant while the code remains modular. A good example of Why Functional Programming Matters.The full code is available here.Crash course on Huffman codesThe idea is straightforward:Map each character to a unique sequence of bits.Choose the bit sequences such that common characters map to shorter bit sequences and rare characters map to longer ones.Compression is achieved by the most common characters using fewer bits than their uncompressed representation.I say characters here, but we could really map anything to bits; like whole word

In this post I’ll walk through the full implementation of a Virtual DOM in a bit over 200 lines of JavaScript.The result is a full-featured and sufficiently performant virtual DOM library (demos).It’s available on NPM as the smvc package.The main goal is to illustrate the fundamental technique behind tools like React.React, Vue and the Elm language all simplify the creation of interactive webpages by allowing you to describe how you’d like the page to look like, and notworry about adding/removing elements to get there.They do that through a Virtual DOM.The goal of a virtual DOMIt’s not about performance.A Virtual DOM is an abstraction to simplify the act of modifying a UI.You describe how you would like your page to look like and the library takes care of taking the DOMfrom its current state, to the state you want it to be in.The key ideaThe library will take over a single DOM element and operate inside of it.This element should be initially empty, and we operate under the assumption t

The Haskell ecosystem has great facilities for searching and navigating package documentation using the browser. haskell-docs-cli allows you to do that much faster without leaving the terminal.Jump to demoThe problemSwitching focus from the editor to the browser when searching for something on Hoogle or reading a piece of documentation on Hackage is not an ideal workflow. Even having Hoogle as a custom search engine on Chrome and using Vimium to avoid the mouse, the path to the module documentation page requires too many key presses.Here is an example. Imagine I’m using the Prettyprinter module (from the prettyprinter package) and want to find out what function will concatenate documents vertically. The best way to do that is to open up the module documentation page and search for the word ‘vertical’.Here is the how to do that in the browser. I’m assuming that a browser window is already open:Cmd+Tab - Switch to browser windowCmd+T - New tabh Prettyprint - Search Hoogle using a custom

TL;DR: There is no Nix-native way of doing that. In this post I describe the process that led to the creation of Nix Package Versions, the tool that provides this functionality.The problemThe Nix package manager allows one to easily install and remove different versions of the same package. With nix-shell one can even start a shell environment with a different version of a package that is already installed.This is extremely useful and one of Nix’s killer features.Some time ago I noticed that my version of Neovim had a bug. This seemed like an easy fix, I just needed to install a previous version of the same package.Searching locally with nix-env -qa neovim revealed that my revision had only one version of the package, which was the same as the one available at https://search.nixos.org/packages. After some more research I discovered that there is currently no Nix-native way to search through previous revisions for older versions of a package. In fact there is a very long discussion span

In his post about a Telegram botJoachim Breitner mentions compiling his program into a static binary to have it run in Amazon’s version ofLinux without needing to build it inside a container. I was interested in experimenting withAmazon Lambda and having statically linked Haskell programs sounded like a great idea too, so thisis a write-up of what it took to get those things working.In the end we will have a Haskell program compiling to a statically linked binary, being builtquickly by making use of Nix and Cachix and automatically deployed to Amazon Lambda using GitHubActions.The code for this post can be found at lazamar/lambda-haskell.In Lambda we need a special wrapping layer to run Haskell code. I’m usingaws-lambda-haskell-runtimefor that. I wanted to see what data from the request Amazon was making available, so theprogram will simply get a request as a JSON, prettify it and return that. This is Main.hs,the only Haskell file.{-# LANGUAGE DeriveGeneric #-}{-# LANGUAGE DeriveAnyCla

Often I need to download many images from a web page and end up trying and adjusting far too many snippets from Stack Overflow.Here is a snippet that works. Give it two strings to download an image.async function download(url, name) { const res = await fetch(url); const blob = await res.blob(); const blobUrl = URL.createObjectURL(blob); const a = document.createElement("a"); a.href = blobUrl a.download = name; document.body.appendChild(a); a.click(); document.body.removeChild(a);}The browser doesn’t handle downloading many images at once very well. I find that adding a timeout is enough to make things work.function downloadWithTimeout(url, index) { const f = () => download(url, `image-${index}.jpg`); setTimeout(f, index * 500);}// Use like thismyUrls.forEach(downloadWithTimeout)

Imagine you want to write a parser to match any of a set of strings that you know beforehand.In Elm’s standard parsing library you would use Parser.oneOf. Like this:import Parser exposing (Parser, oneOf, backtrackable, token, getChompedString)friendName : Parser StringfriendName =oneOf[ backtrackable <| token "joe", backtrackable <| token "joey", backtrackable <| token "john"]|> getChompedStringNow we can parse the name of our friends. However this parser has a few problems:It is inefficientIf the string we are matching against is "lisa", for example, this parser will perform the following steps:Look at the first three characters in our parsed string and check whether they are equal to "joe". They aren’t.Look at the first four characters in our parsed string and check whether they are equal to "joey". They aren’tLook at the first four characters in our parsed string and check whether they are equal to "john". They aren’tFailOohf, that’s not very good. From the first time we looked at t

In functional programming languages you may find yourself overflowing the stack. This post describes techniques to achieve unbounded recursion without fear of the stack.TL;DRThe name of the game is staying tail recursiveEnable tail recursion by passing down computed valuesStick to one recursive call at a time by passing down a list of recursions to be doneIf we reach a stack overflow it is because we are not taking advantage of tail recursion. The fix is: use tail recursion. How to do that, however, is not always very clear.Tail recursionQuick recapitulation: If the very last thing our function does is to return the recursive call, it qualifies for tail call optimisation. This optimisation makes the recursive call take the place of the invoking function in the stack, allowing us to recurse without growing the stack size. This eliminates the risk of a stack overflow.This function is tail recursive (examples are in Elm):-- Pauses execution for n loops of the runtimesleep n =if n > 0 then

At the current state of web technologies, having our application be unavailable during every upgrade is not acceptable anymore. And if you are updating your application often, which you should, being available during updates is even more important. In this post I will walk you through hot-swapping docker containers without letting any request drop with just one command.Blue-Green deployment is the technique we will use. It involves running your new and old server versions in parallel and having a proxy redirect new requests to the new version. Once the old version is finished answering all its remaining requests it can be shut down safely. There you go, version swap with no downtime.It’s easier said than done, though. Even though everyone seems to be able to explain it very well it was hard to find someone actually showing how to do it.The setup is not complicated, but can be tricky to get right. We will use a small tool to do the heavy-lifting. I will do the explanation first and the

Haskell’s laziness can cause problems with recursive functions if they are not handled properly. In some cases this can be dealt with by using an accumulating parameter. Haskell’s wiki page on the subject does a great job in explaining how that works. Here I register some benchmarks on the wiki’s examples so we can see how much that matters.I won’t go into details as to why one implementation performs better than the other as the wiki’s article is already very clear and concise. I will stick to showing the code and the benchmarks.The task in our hands is to calculate the length of a list. To make sure this is working we will print the length of a really long one.main = print $ len [1..1000000000] -- 1 BillionVery lazy implementationThis is our first and very naive implementation.len :: [a] -> Intlen [] = 0len (x:xs) = len xs + 1In this implementation memory usage grew very quickly and we also hit a stack overflow in less than 10 seconds.Tail recursive implementationIn this implementati