# Announcing the 'debug' package

Haskell is a great language, but debugging Haskell is undoubtedly a weak spot. To help with that problem, I've just released the debug library. This library is intended to be simple and easy to use for a common class of debugging tasks, without solving everything. As an example, let's take a function we are interested in debugging, e.g.:

module QuickSort(quicksort) whereimport Data.Listquicksort :: Ord a => [a] -> [a]quicksort [] = []quicksort (x:xs) = quicksort lt ++ [x] ++ quicksort gt    where (lt, gt) = partition (<= x) xs

Turn on the TemplateHaskell and ViewPatterns extensions, import Debug, indent your code and place it under a call to debug, e.g.:

{-# LANGUAGE TemplateHaskell, ViewPatterns #-}module QuickSort(quicksort) whereimport Data.Listimport Debugdebug [d|   quicksort :: Ord a => [a] -> [a]   quicksort [] = []   quicksort (x:xs) = quicksort lt ++ [x] ++ quicksort gt       where (lt, gt) = partition (<= x) xs   |]

We can now run our debugger with:

$ghci QuickSort.hsGHCi, version 8.2.1: http://www.haskell.org/ghc/ :? for help[1 of 1] Compiling QuickSort ( QuickSort.hs, interpreted )Ok, 1 module loaded.*QuickSort> quicksort "haskell""aehklls"*QuickSort> debugView The call to debugView starts a web browser to view the recorded information, looking something like: From there you can click around to explore the computation. I'm interested in experiences using debug, and also have a lot of ideas for how to improve it, so feedback or offers of help most welcome at the bug tracker. If you're interested in alternative debuggers for Haskell, you should check out the GHCi debugger or Hood/Hoed. ### Michael Snoyman # What Makes Haskell Unique I gave a talk today at the F(by) 2017 conference in Minsk, Belarus. The conference was great, I would definitely recommend it in the future. Thank you very much to the organizers for the opportunity to present on Haskell. I prepared for this talk differently than I've prepared for other talks in the past. I'm very comfortable writing up blog posts, but have always found slide preparation difficult. This time around, I wrote up the content in mostly-blog-post form first, and only created the slides after that was complete. Overall, this worked very well for me, and I'll try it again in the future. (If others want to share their approaches to preparing talks, I'd definitely be happy to hear them.) As a result: I'm able to share the original write-up I did as well. For those who saw the live talk (or the video): you may want to skip towards the end, which covers some material that there wasn't time for in the talk itself. If you'd like to follow with the slides, they're also available. My name is Michael Snoyman. I work at a company called FP Complete. One of the things we do is help individuals and companies adopt Haskell, and functional programming in general. And that leads right in to the topic of my talk today: What makes Haskell unique Programmers today have a large number of languages to choose from when deciding what they will learn and use in their day to day coding. In order to make intelligent decisions about which languages to pursue, people need to be able to quickly learn and understand what distinguishes one language from another. Given that this is a functional programming conference, it's probably no surprise to you that Haskell can be called a functional programming language. But there are lots of languages out there that can be called functional. Definitions vary, but let's take a particularly lax version of functional programming: first class functions, and higher order functions. Well, by this defintion, even a language like C counts! You may want to limit the definition further to include syntactic support for closures, or some other features. Regardless, the same point remains: Haskell may be functional, but that doesn't make it unique In fact, there's a long list of features I could rattle off that could be used to describe Haskell. • Functional • Statically typed • Pure • Lazy • Strongly typed • Green threads • Native executables • Garbage collected • Immutability Some of these features, like being pure and lazy, are relatively rare in mainstream languages. Others, however, are common place. What I'm going to claim is that not one of these features is enough to motivate new people to Haskell—including people in this audience—to start using it. Instead: It's the combination of these features that makes Haskell unique As an example: the intersection of purity, strong typing, and functional programming style, for instance, lends itself to a high level form of expression which is simultaneously easy to write, easy to read, easy to modify, and efficient. I want to share some examples of some code examples in Haskell that demonstrate how the language encourages you to write code differently from other languages. And I'm going to try to claim that this "different" style is awesome, though it also has some downsides. ## Async I/O and Concurrency Let's start off with a use case that's pretty popular today. Look at this pseudocode and tell me what's wrong with it: json1 := httpGet(url1) json2 := httpGet(url2) useJsonBodies(json1, json2) Given the heading of this slide, you may have guessed it: this is blocking code. It will tie up an entire thread waiting for the response body from each of these requests to come back. Instead, we should be using asynchronous I/O calls to allow more efficient usage of system resources. One common approach is to use callbacks: httpGetA(url1, |json1| => httpGetA(url2, |json2| => useJsonBodies(json1, json2) ) ) You may recognize this coding style as "callback hell." There are plenty of techniques in common languages to work around that, usually around the idea of promises or futures. And you may have heard something about how Javascript futures are a monad, and expect me to be talking about how Haskell does monads better. But I'm not going to do that at all. Instead, I want to show you what the asynchronous version of the code looks like in Haskell json1 <- httpGet url1 json2 <- httpGet url2 useJsonBodies json1 json2 This may surprise you, since this looks exactly like the blocking pseudocode I showed above. It turns out that Haskell has a powerful runtime system. It will automatically convert your blocking-style code into asynchronous system calls, and automatically handle all of the work of scheduling threads and waking them up when data is available. This is pretty great, but it's hardly unique to Haskell. Erlang and Go, as two popular examples, both have this as well. If we want to see what makes Haskell different... we have to go deeper. ### Concurrency It's pretty lame that we need to wait for our first HTTP request to complete before even starting our second. What we'd like to do is kick off both requests at the same time. You may be imagining some really hairy APIs with threads, and mutable variables, and locks. But here's how you do this in Haskell: (json1, json2) <- concurrently (httpGet url1) (httpGet url2) useJsonBodies json1 json2 Haskell has a green thread implementation which makes forking threads cheap. The async library provides a powerful, high level interface performing actions in parallel without bothering with the low level aspects of locking primitives and mutable variables. And this builds naturally on top of the async I/O system already described to be cheap about system resource usage. ### Canceling What we've seen already is elegant in Haskell, but it's not terribly difficult to achieve in other languages. Let's take it to the next level. Instead of needing both JSON response bodies, we only need one: whichever one comes back first. In pseudocode, this might look like: promise1 := httpGet(url1) promise2 := httpGet(url2) result := newMutex() promise1.andThen(|json1| => result.set(json1) promise2.cancel()) promise2.andThen(|json2| => result.set(json2) promise1.cancel()) useJsonBody(result.get()) This code is tedious and error prone, but it gets the job done. As you can probably guess, there's a simple API for this in Haskell: eitherJson <- race (httpGet url1) (httpGet url2) case eitherJson of Left json1 -> useJsonBody1 json1 Right json2 -> useJsonBody2 json2 At first, this may seem like it's just a well designed API. But there's quite a bit more going on under the surface. The Haskell runtime system itself supports the idea of an asynchronous exception, which allows us to cancel any other running thread. This feature is vital to making race work. And here's the final piece in the puzzle. All of the thread scheduing and canceling logic I've described doesn't just apply to async I/O calls. It works for CPU-intensive tasks as well. That means you can fork thousands of threads, and even if one of them is busy performing computation, other threads will not be starved. Plus, you can interrupt these long-running computations: let tenSeconds = 10 * 1000 * 1000 timeout tenSeconds expensiveComputation ### Summary: concurrency and async I/O Advantages • Cheap threads • Simple API • Highly responsive Disadvantages • Complicated runtime system • Need to be aware of async exceptions when writing code ## Immutability and purity Most programming languages out there default to mutability: a variable or field in a data structure can be changed at any time. Haskell is different in two ways: 1. Values are immutable by default, and mutability must be explicitly indicated with a variable type 2. Mutating a mutable variable is considered a side effect, and that mutable is tracked by the type system For example, the following Haskell-like code is impossible: let mut total = 0 loop i = if i > 1000000 then total else total += i; loop (i + 1) in loop 1 From pure code, we cannot create, read, or modify a mutable variable. We also need to say what kind of mutable variable we want: total <- newIORef 0 let loop i = if i > 1000000 then readIORef total else do modifyIORef total (+ i) loop (i + 1) loop 1 This is a lot of ceremony for a simple algorithm. Of course, the recommended Haskell way of doing this would be to avoid mutable variables, and use a more natural functional style. let loop i total = if i > 1000000 then total else loop (i + 1) (total + i) in loop 1 0 Besides pushing us towards this supposedly better functional approach, why is immutable, pure code such a nice thing? ### Reasoning about code You'll often hear Haskellers throw around a phrase "reasoning about code." Personally, I think the phrase is used to mean too many different things. But let me give you an example that I think is accurate. Let's look at some pseudocode: // scores.txt Alice,32 Bob,55 Charlie,22 func main() { results := readResultsFromFile("results.txt") printScoreRange(results) print("First result was by: " + results[0].name) } func printScoreRange(results: Vector<TestResult>) { ... } If you look at the code above, what do you expect the output to be? I think it would be reasonable to guess something like: Lowest: 22 Highest: 55 First result was by: Alice However, now let's throw in another piece of information: the definition of printScoreRange: func printScoreRange(results: Vector<TestResult>) { results.sortBy(|result| => result.score) print("Lowest: " + results[0].score) print("Highest: " + results[results.len() - 1].score) } Suddenly our assumptions change. We can see that this function mutates the results value passed to it. If we're passing mutable references to vectors in this made up language, then our output is going to look more like: Lowest: 22 Highest: 55 First result was by: Charlie Since the original results value in our main function has been modified. This is what I mean by hurting our ability to reason about the code: it's no longer sufficient to look at just the main function to understand what will be happening. Instead, we're required to understand what may possibly be occurring in the rest of our program to mutate our variables. In Haskell, the code would instead look like: main :: IO () main = do results <- readResultsFromFile "results.txt" printScoreRange results putStrLn$ "First result was by: " ++ name (head results)

printScoreRange :: [TestResult] -> IO ()
printScoreRange results = do
let results' = sortBy score results
putStrLn $"Lowest: " ++ show (score (head results')) putStrLn$ "Highest: " ++ show (score (last results'))

We know that it's impossible for printScoreRange to modify the results value we have in the main function. Looking at only this bit of code in main is sufficient to know what will happen with the results value.

### Data races

Even more powerful than the single threaded case is how immutability affects multithreaded applications. Ignoring the insanity of multiple threads trying to output to the console at the same time, we can easily parallelize our code:

main :: IO ()
main = do
concurrently_ printFirstResult printScoreRange

printFirstResult results =
putStrLn $"First result was by: " ++ name (head results) printScoreRange results = do let results' = sortBy score results putStrLn$ "Lowest: " ++ show (score (head results'))
putStrLn $"Highest: " ++ show (score (last results')) There's no need to worry about concurrent accesses to data structures. It's impossible for the other threads to alter our data. If you do want other threads to affect your local data, you'll need to be more explicit about it, which we'll get back to. ### Mutability when needed One thing you may be worried about is how this affects performance. For example, it's much more efficient to sort a vector using mutable access instead of only pure operations. Haskell has two tricks for that. The first is the ability to explicitly create mutable data structures, and mutate them in place. This breaks all of the guarantees I already mentioned, but if you need the performance, it's available. And unlike mutable-by-default approaches, you now know exactly which pieces of data you need to handle with care when coding to avoid tripping yourself up. The other approach is to create a mutable copy of the original data, perform your mutable algorithm on it, and then freeze the new copy into an immutable version. With sorting, this looks something like: sortMutable :: MutableVector a -> ST (MutableVector a) sortMutable = ... -- normal sorting algorithm sortImmutable :: Vector a -> Vector a sortImmutable orig = runST$ do
mutable <- newMutableVector (length orig)
copyValues orig mutable
sort mutable
freeze mutable

ST is something we use to have temporary and local mutable effects. Because of how it's implemented, we know that none of the effects can be visible from outside of our function, and that for the same input, the sortImmutable function will always have the same output. While this approach requires an extra memory buffer and an extra copy of the elements in the vector, it avoids completely the worries of your data being changed behind your back.

### Summary: immutability and purity

• Easier to reason about code
• Avoid many cases of data races
• Functions are more reliable, returning the same output for the same input

• Lots of ceremony if you actually want mutation
• Some runtime performance hit for mutable algorithms

## Software Transactional Memory

Let's say you actually need to be able to mutate some values. And for fun, let's say you want to do this from multiple threads. A common example of this is a bank. Let's again play with some pseudocode:

runServer (|request| => {
from := accounts.lookup(request.from)
to := accounts.lookup(request.to)
accounts.set(request.from, from - request.amt)
accounts.set(request.to, to + request.amt)
})

This looks reasonable, except that if two requests come in at the same time for the same account, we can end up with a race condition. Consider something like this:

Thread 1: receive request: Alice gives $25 Thread 2: receive request: Alice receives$25
Thread 1: lookup that Alice has $50 Thread 2: lookup that Alice has$50
Thread 1: set Alice's account to $25 Thread 2: set Alice's account to$75

We know that we want Alice to end up with $50, but because of our data race, Alice ends up with$75. Or, if the threads ran differently, it could be $25. Neither of these is correct. In order to avoid this, we would typically deal with some kind of locking: runServer (|request| => { accounts.lock(request.from) accounts.lock(request.to) // same code as before accounts.unlock(request.from) accounts.unlock(request.to) }) Unfortunately, this leads to deadlocks! Consider this scenario: Thread 1: receive request:$50 from Alice to Bob
Thread 2: receive request: $50 from Bob to Alice Thread 1: lock Alice Thread 2: lock Bob Thread 1: try to lock Bob, but can't, so wait Thread 2: try to lock Alice, but can't, so wait ... This kind of problem is the bane of many concurrent programs. Let me show you another approach. As you may guess, here's some Haskell: runServer$ \request -> atomically $do let fromVar = lookup (from request) accounts toVar = lookup (to request) accounts origFrom <- readTVar fromVar writeTVar fromVar (origFrom - amt request) origTo <- readTVar toVar writeTVar toVar (origTo + amt request) There are helper functions to make this shorter, but I wanted to do this the long way to prove a point. This looks like exactly the kind of race condition I described before. However, that atomically function is vital here. It ensures that only a complete transaction is ever committed. If any of the variables we touch are mutated by another thread before our transaction is complete, all of our changes are rolled back, and the transaction is retried. No need for explicit locking, and therefore many less worries about data races and deadlocks. A TVar is a "transactional variable." It's an alternative to the IORef that I mentioned earlier. There are other kinds of mutable variables in Haskell, including channels and MVars which are like mutexes. This is what I meant when I said you need to be explicit about what kind of mutation you want in Haskell. ### Purity's role What do you think will happen with this program: atomically$ do
buyBitcoins 3 -- side effects on my bank account

modifyTVar myBitcoinCount (+ 3)

Here, buyBitcoins is going off to some exchange a buying about $100,000 in bitcoin (or whatever ridiculous amount they're selling for now). I said before that, if the variables are modified while running, the transaction will be retried. It seems like this function is very dangerous, as it may result in me going about$10,000,000 into debt buying bitcoins!

This is where purity steps in. Inside atomically, you are not allowed to perform any side effects outside of STM itself. That means you can modify TVars, but you cannot read or write files, print to the console, fire the missiles, or place multi million dollar currency purchases. This may feel like a limitation, but the tradeoff is that it's perfectly safe for the runtime system to retry your transactions as many times as it wants.

### Summary of STM

• Makes concurrent data modification much easier
• Bypass many race conditions and deadlocks

• Depends on purity to work at all
• Not really any other disadvantages, so just use it!

## Laziness

It's a little cheeky of me to get this far into a talk about unique features of Haskell and ignore one of its most notable features: laziness. Laziness is much more of a double-edged sword than the other features I've talked about, and let me prove that by revisiting one of our previous examples.

let loop i total =
if i > 1000000
then total
else loop (i + 1) (total + i)
in loop 1 0

I didn't describe it before, but this function will sum up the numbers from 1 to 1,000,000. There are two problems with this function:

1. There's a major performance bug in it
2. It's much more cumbersome than it should be

### Space leaks

The bane of laziness is space leaks, something you've probably heard about if you've read at all about Haskell. To understand this, let's look at how laziness is implemented. When you say something like:

let foo = 1 + 2

foo doesn't actually contain 3 right now. Instead, it contains an instruction to apply the operator + to the values 1 and 2. This kind of instruction is called a thunk. And as you might guess, storing the thunk is a lot more expensive than storing a simple integer. We'll see why this helps in a bit, but for now we just care about why it sucks. Let's look at what happens in our loop function:

let loop i total =
if i > 1000000
then total
else loop (i + 1) (total + i)
in loop 1 0

Each time we step through the loop, we have to compare i to the number 1,000,000. Therefore, we are forced to evaluate it, which means turning it into a simple integer. But we never look at the value of total. Instead of storing a simple integer, which would be cheap, we end up building a huge tree that looks like "add 1 to the result of add 2 to the result of ... to 1,000,000." This is really bad: it uses more memory and more CPU than we'd like.

We can work around this in Haskell by being explicit about which values should be evaluated. There are a few ways to do this, but in our case, the easiest is:

let loop i !total =
if i > 1000000
then total
else loop (i + 1) (total + i)
in loop 1 0

All I've done is added an exclamation point in front of the total argument. This is known as a bang pattern, and says "make sure this is evaluated before running the rest of this function." The need to do this in some cases is definitely a downside to Haskell's laziness. On the other hand, as we'll see shortly, you often don't need to bother if you use the right kinds of functions.

### Laziness is awesome

Let's go back to pseudocode and rewrite our summation:

total := 0
for(i := 1; i <= 1000000; i++) {
total += i
}

Pretty simple. But now let's modify this to only sum up the even numbers:

total := 0
for(i := 1; i <= 1000000; i++) {
if (isEven(i)) {
total += i
}
}

OK, that's fine. But now, let's sum up the indices modulus 13 (for some weird reason):

total := 0
for(i := 1; i <= 1000000; i++) {
if (isEven(i)) {
total += i % 13
}
}

Each of these modifications is fine on its own, but at this point it's getting harder to see the forest for the trees. And fortunately each of these transformations was relatively simple. If some of the requirements were more complicated, fitting it into the for loop may be more challenging.

Let's go back to the beginning with Haskell. We saw how we could do it with a loop, but let's see the real way to sum the numbers from 1 to 1,000,000:

-- Bad
let loop i !total =
if i > 1000000
then total
else loop (i + 1) (total + i)
in loop 1 0

-- Awesome!
sum [1..1000000]

We use list range syntax to create a list with one million numbers in it. On its face, this looks terrible: we need to allocate about 8mb of data to hold onto this integers, when this should run in constant space. But this is exactly where laziness kicks in: instead of allocating all of these values immediately, we allocate a thunk. Each time we step through the list, our thunk generates one new integer and a new thunk for the rest of the list. We're never using more than a few machine words.

There are also other optimizations in GHC to avoid even allocating those thunks, but that's not something I'm going to cover today.

Anyway, let's continue. We can easily tweak this to only add up the even numbers:

sum (filter even [1..1000000])

This uses the filter higher order function, and likewise avoids allocating an entire list at once. And doing the silly modulus 13 trick:

sum (map (mod 13) (filter even [1..1000000]))

Laziness is definitely a mixed bag, but combined with the functional style of Haskell in general, it allows you to write higher level, declarative code, while keeping great performance.

Lots of languages define && and || operators which stop evaluation early, e.g.:

foo() && bar()

bar is only called if foo returns true. Haskell works the same way, but these operators aren't special; they just use laziness!

False && _ = False
True && x = x

True || _ = True
False || x = x

This even scales up to functions working on lists of values, such as and, or, all, and any.

### Other downsides

There's one other downside to laziness, and a historical artifact. Laziness means that exceptions can be hiding inside any thunk. This is also known as partial values and partial functions. For example, what does this mean?

head []

Generally speaking, partiality is frowned upon, and you should use total functions in Haskell.

The historical artifact is that many bad functions are still easily available, and they should be avoided. head is arguably an example of that. Another is the lazy left fold function, foldl. In virtually all cases, you should replace it with a strict left fold foldl'.

### Summary of laziness

• More composable code
• Get efficient results from combining high level functions
• Short-circuiting like && and || is no longer a special case

• Need to worry about space leaks
• Exceptions can be hiding in many places
• Unfortunately some bad functions like foldl still hanging around

Side note There's a major overlap with Python generators or Rust iterators, but laziness in Haskell is far more pervasive than these other approaches.

## Others

Due to time constraints, I'm not going to be able to go into detail on a bunch of other examples I wanted to talk about. Let me just throw out some quick thoughts on them.

### Parser (and other) DSLs

• Abstract type classes like Applicative and Alternative a natural fit, e.g.: parseXMLElement <|> parseXMLText.
• Able to reuse huge number of existing library functions, e.g. optional, many
• General purpose do-notation is great
data Time = Time Hour Minutes Seconds (Maybe AmPm)
data AmPm = Am | Pm

parseAmPm :: Parser Time
parseAmPm = Time
$mega-sdist The mega-sdist command will: • Build tarballs for all local packages • Check what the latest versions of my packages on Hackage are • Do a full diff on these two things and see if anything's changed At the time of writing, here's the output from this repo: The following packages from Hackage have not changed: monad-unlift-0.2.0 The following packages require a version bump: monad-unlift-ref-0.2.1 What this means is: • The monad-unlift package I have locally is at version 0.2.0. And it perfectly matches that version on Hackage. No actions necessary. • The monad-unlift-ref package I have locally is at version 0.2.1. And it doesn't match the code on Hackage. Therefore, if I wanted to run stack upload monad-unlift-ref successfully, I'd need to bump the version number. ## What did I change? Well, again, if I wanted to see what changed, I could run (again, like a caveman): $ git diff monad-unlift-ref/0.2.1 -- monad-unlift-ref

But that's long! mega-sidst's got your back. Just run:

$mega-sdist monad-unlift-ref --get-diffs This will print out the difference between the tarball uploaded to Hackage and what you have locally. Besides my tongue-in-cheek comment above, this is also useful if, for some reason, you either don't have or don't trust the tags in your Git repo. One other thing: this diff is currently based on the pristine tarball from Hackage, ignoring cabal file revisions. So the difference may be slightly different from what you'd get from stack unpack monad-unlift-ref-0.2.1. But ¯\_(ツ)_/¯ that's revisions for you. The default behavior of mega-sdist is to look at all packages specified in your stack.yaml. Targets can be any directory. And mega-sdist will automatically look at packages in any subdirectory, so that mega-sdist . is the same as mega-sdist at the root of your repo*. * Assuming all of your packages are actually in your repo, but only crazy people would do otherwise. ## Preparing a new release OK, now I continue working on my project, and I've: • Made some changes to monad-unlift • Updated the cabal file's version number • And of course I also updated the ChangeLog.md, I'm not some monster From the root of my repo, I run: $ mega-sdist monad-unlift

Or, equivalently, from inside the monad-unlift subdirectory I run:

$mega-sdist . Either way, I get: The following new packages exist locally: monad-unlift-0.2.1 No version bumps required, good to go! This tells me that my package has local changes, and the version number has been updated, so that stack upload monad-unlift will work. Neato! Now, you could just run stack upload ..., but here's what I usually do. First, I'll review the changes I'm about to upload and make sure there are no surprises: $ mega-sdist --get-diffs .

The following new packages exist locally:
0a1,4
> ## 0.2.1
>
> * Silly changes
>
51a52,54
>
> -- I just need some space
>
2c2
< version:             0.2.0
---
> version:             0.2.1

No version bumps required, good to go!

OK, that's what I wanted. Time to release. Next, I'm going to use mega-sdist to tag the release:

$mega-sdist --gittag . From the root of my repo, this would notice that monad-unlift-ref still requires a version bump, and refuse to proceed. But inside the monad-unlift directory, it notices that all necessary version bumps are done, and happily tags: $ mega-sdist --gittag .
The following new packages exist locally:

No version bumps required, good to go!
Raw command: git tag monad-unlift/0.2.1

And suddenly I notice something new:

$ls tarballs/ monad-unlift-0.2.1.tar.gz Neat, mega-sdist left behind tarballs I can upload! To do so, I run: $ stack upload tarballs/*

Note that this will work whether I'm trying to upload just one package, or all of the updated packages in my repo. Finally, I need to push the new tags to Github (or wherever):

$git push --tags And in fact, this upload sequence is so common that I have a shell alias set up: $ alias upload
alias upload='mega-sdist --gittag . && stack upload tarballs/* && git push --tags'

So there you have it: convenient little utility to help manage repos with lots of packages in them.

# Pay what you want for Java Generics and Collections

Humble Book Bundle is selling off a passle of Java books, including Java Generics and Collection by Naftalin and Wadler, on a pay-what-you-want basis (USD $1 minimum), DRM-free. You choose what proportion of the profits go to Humble and what goes to the charity Code for America. A great deal! ## November 18, 2017 ### Sandy Maguire # Type-Directed Code Generation <article> <header> # Type-Directed Code Generation </header> <time>November 18, 2017</time> aka “Type-Level Icing Sugar” ## Context At work recently I’ve been working on a library to get idiomatic gRPC support in our Haskell project. I’m quite proud of how it’s come out, and thought it’d make a good topic for a blog post. The approach demonstrates several type-level techniques that in my opinion are under-documented and exceptionally useful in using the type-system to enforce external contracts. Thankfully the networking side of the library had already been done for me by Awake Security, but the interface feels like a thin-wrapper on top of C bindings. I’m very, very grateful that it exists, but I wouldn’t expect myself to be able to use it in anger without causing an uncaught type error somewhere along the line. I’m sure I’m probably just using it wrong, but the library’s higher-level bindings all seemed to be targeted at Awake’s implementation of protobuffers. We wanted a version that would play nicely with proto-lens, which, at time of writing, has no official support for describing RPC services via protobuffers. If you’re not familiar with proto-lens, it generates Haskell modules containing idiomatic types and lenses for protobuffers, and can be used directly in the build chain. So the task was to add support to proto-lens for generating interfaces to RPC services defined in protobuffers. My first approach was to generate the dumbest possible thing that could work – the idea was to generate records containing fields of the shape Request -> IO Response. Of course, with a network involved there is a non-negligible chance of things going wrong, so this interface should expose some means of dealing with errors. However, the protobuffer spec is agnostic about the actual RPC backend used, and so it wasn’t clear how to continue without assuming anything about the particulars behind errors. More worrisome, however, was that RPCs can be marked as streaming – on the side of the client, server, or both. This means, for example, that a method marked as server-streaming has a different interface on either side of the network: serverSide :: Request -> (Response -> IO ()) -> IO () clientSide :: Request -> (IO (Maybe Response) -> IO r) -> IO r This is problematic. Should we generate different records corresponding to which side of the network we’re dealing with? An early approach I had was to parameterize the same record based on which side of the network, and use a type family to get the correct signature: {-# LANGUAGE DataKinds #-} data NetworkSide = Client | Server data MyService side = MyService { runServerStreaming :: ServerStreamingType side Request Response } type family ServerStreamingType (side :: NetworkSide) input output where ServerStreamingType Server input output = input -> (output -> IO ()) -> IO () ServerStreamingType Client input output = forall r. input -> (IO (Maybe output) -> IO r) -> IO r This seems like it would work, but in fact the existence of the forall on the client-side is “illegally polymorphic” in GHC’s eyes, and it will refuse to compile such a thing. Giving it up would mean we wouldn’t be able to return arbitrarily-computed values on the client-side while streaming data from the server. Users of the library might be able to get around it by invoking IORefs or something, but it would be ugly and non-idiomatic. So that, along with wanting to be backend-agnostic, made this approach a no-go. Luckily, my brilliant coworker Judah Jacobson (who is coincidentally also the author of proto-lens), suggested we instead generate metadata for RPC services in proto-lens, and let backend library code figure it out from there. With all of that context out of the way, we’re ready to get into the actual meat of the post. Finally. ## Generating Metadata According to the spec, a protobuffer service may contain zero or more RPC methods. Each method has a request and response type, either of which might be marked as streaming. While we could represent this metadata at the term-level, that won’t do us any favors in terms of getting type-safe bindings to this stuff. And so, we instead turn to TypeFamilies, DataKinds and GHC.TypeLits. For reasons that will become clear later, we chose to represent RPC services via types, and methods in those services as symbols (type-level strings). The relevant typeclasses look like this: class Service s where type ServiceName s :: Symbol class HasMethod s (m :: Symbol) where type MethodInput s m :: * type MethodOutput s m :: * type IsClientStreaming s m :: Bool type IsServerStreaming s m :: Bool For example, the instances generated for the RPC service: service MyService { rpc BiDiStreaming(stream Request) returns(stream Response); } would look like this: data MyService = MyService instance Service MyService where type ServiceName MyService = "myService" instance HasMethod MyService "biDiStreaming" where type MethodInput MyService "biDiStreaming" = Request type MethodOutput MyService "biDiStreaming" = Response type IsClientStreaming MyService "biDiStreaming" = 'True type IsServerStreaming MyService "biDiStreaming" = 'True You’ll notice that these typeclasses perfectly encode all of the information we had in the protobuffer definition. The idea is that with all of this metadata available to them, specific backends can generate type-safe interfaces to these RPCs. We’ll walk through the implementation of the gRPC bindings together. ## The Client Side The client side of things is relatively easy. We can the HasMethod instance directly: runNonStreamingClient :: HasMethod s m => s -> Proxy m -> MethodInput s m -> IO (Either GRPCError (MethodOutput s m)) runNonStreamingClient = -- call the underlying gRPC code runServerStreamingClient :: HasMethod s m => s -> Proxy m -> MethodInput s m -> (IO (Either GRPCError (Maybe (MethodOutput s m)) -> IO r) -> IO r runServerStreamingClient = -- call the underlying gRPC code -- etc This is a great start! We’ve got the interface we wanted for the server-streaming code, and our functions are smart enough to require the correct request and response types. However, there’s already some type-unsafety here; namely that nothing stops us from calling runNonStreamingClient on a streaming method, or other such silly things. Thankfully the fix is quite easy – we can use type-level equality to force callers to be attentive to the streaming-ness of the method: runNonStreamingClient :: ( HasMethod s m , IsClientStreaming s m ~ 'False , IsServerStreaming s m ~ 'False ) => s -> Proxy m -> MethodInput s m -> IO (Either GRPCError (MethodOutput s m)) runServerStreamingClient :: ( HasMethod s m , IsClientStreaming s m ~ 'False , IsServerStreaming s m ~ 'True ) => s -> Proxy m -> MethodInput s m -> (IO (Either GRPCError (Maybe (MethodOutput s m)) -> IO r) -> IO r -- et al. Would-be callers attempting to use the wrong function for their method will now be warded off by the type-system, due to the equality constraints being unable to be discharged. Success! The actual usability of this code leaves much to be desired (it requires being passed a proxy, and the type errors are absolutely disgusting), but we’ll circle back on improving it later. As it stands, this code is type-safe, and that’s good enough for us for the time being. ## The Server Side ### Method Discovery Prepare yourself (but don’t panic!): the server side of things is significantly more involved. In order to run a server, we’re going to need to be able to handle any sort of request that can be thrown at us. That means we’ll need an arbitrary number of handlers, depending on the service in question. An obvious thought would be to generate a record we could consume that would contain handlers for every method, but there’s no obvious place to generate such a thing. Recall: proto-lens can’t, since such a type would be backend-specific, and so our only other strategy down this path would be Template Haskell. Yuck. Instead, recall that we have an instance of HasMethod for every method on Service s – maybe we could exploit that information somehow? Unfortunately, without Template Haskell, there’s no way to discover typeclass instances. But that doesn’t mean we’re stumped. Remember that we control the code generation, and so if the representation we have isn’t powerful enough, we can change it. And indeed, the representation we have isn’t quite enough. We can go from a HasMethod s m to its Service s, but not the other way. So let’s change that. We change the Service class slightly: class Service s where type ServiceName s :: Symbol type ServiceMethods s :: [Symbol] If we ensure that the ServiceMethods s type family always contains an element for every instance of HasService, we’ll be able to use that info to discover our instances. For example, our previous MyService will now get generated thusly: data MyService = MyService instance Service MyService where type ServiceName MyService = "myService" type ServiceMethods MyService = '["biDiStreaming"] instance HasMethod MyService "biDiStreaming" where type MethodInput MyService "biDiStreaming" = Request type MethodOutput MyService "biDiStreaming" = Response type IsClientStreaming MyService "biDiStreaming" = 'True type IsServerStreaming MyService "biDiStreaming" = 'True and we would likewise add the m for any other HasMethod MyService m instances if they existed. This seems like we can now use ServiceMethods s to get a list of methods, and then somehow type-level map over them to get the HasMethod s m constraints we want. And we almost can, except that we haven’t told the type-system that ServiceMethods s relates to HasService s m instances in this way. We can add a superclass constraint to Service to do this: class HasAllMethods s (ServiceMethods s) => Service s where -- as before But was is this HasAllMethods thing? It’s a specialized type-level map which turns our list of methods into a bunch of constraints proving we have HasMethod s m for every m in that promoted list. class HasAllMethods s (xs :: [Symbol]) instance HasAllMethods s '[] instance (HasMethod s x, HasAllMethods s xs) => HasAllMethods s (x ': xs) We can think of xs here as the list of constraints we want. Obviously if we don’t want any constraints (the '[] case), we trivially have all of them. The other case is induction: if we have a non-empty list of constraints we’re looking for, that’s the same as looking for the tail of the list, and having the constraint for the head of it. Read through these instances a few times; make sure you understand the approach before continuing, because we’re going to keep using this technique in scarier and scarier ways. With this HasAllMethods superclass constraint, we can now convince ourselves (and, more importantly, GHC), that we can go from a Service s constraint to all of its HasMethod s m constraints. Cool! ## Typing the Server We return to thinking about how to actually run a server. As we’ve discussed, such a function will need to be able to handle every possible method, and, unfortunately, we can’t pack them into a convenient data structure. Our actual implementation of such a thing might take a list of handlers. But recall that each handler has different input and output types, as well as different shapes depending on which bits of it are streaming. We can make this approach work by existentializing away all of the details. While it works as far as the actual implementation of the underlying gRPC goes, we’re left with a great sense of uneasiness. We have no guarantees that we’ve provided a handler for every method, and the very nature of existentialization means we have absolutely no guarantees that any of these things are the right ype. Our only recourse is to somehow use our Service s constraint to put a prettier facade in front of this ugly-if-necessary implementation detail. The actual interface we’ll eventually provide will, for example, for a service with two methods, look like this: runServer :: HandlerForMethod1 -> HandlerForMethod2 -> IO () Of course, we can’t know a priori how many methods there will be (or what type their handlers should have, for that matter). We’ll somehow need to extract this information from Service s – which is why we previously spent so much effort on making the methods discoverable. The technique we’ll use is the same one you’ll find yourself using again and again when you’re programming at the type-level. We’ll make a typeclass with an associated type family, and then provide a base case and an induction case. class HasServer s (xs :: [Symbol]) where type ServerType s xs :: * We need to make the methods xs explicit as parameters in the typeclass, so that we can reduce them. The base case is simple – a server with no more handlers is just an IO action: instance HasServer s '[] where type ServerType s '[] = IO () The induction case, however, is much more interesting: instance ( HasMethod s x , HasMethodHandler s x , HasServer s xs ) => HasServer s (x ': xs) where type ServerType s (x ': xs) = MethodHandler s x -> ServerType s xs The idea is that as we pull methods x off our list of methods to handle, we build a function type that takes a value of the correct type to handle method x, which will take another method off the list until we’re out of methods to handle. This is exactly a type-level fold over a list. The only remaining question is “what is this MethodHandler thing?” It’s going to have to be a type family that will give us back the correct type for the handler under consideration. Such a type will need to dispatch on the streaming variety as well as the request and response, so we’ll define it as follows, and go back and fix HasServer later. class HasMethodHandler input output cs ss where type MethodHandler input output cs ss :: * cs and ss refer to whether we’re looking for client-streaming and/or server-streaming types, respectively. Such a thing could be a type family, but isn’t because we’ll need its class-ness later in order to actually provide an implementation of all of this stuff. We provide the following instances: -- non-streaming instance HasMethodHandler input output 'False 'False where type MethodHandler input output 'False 'False = input -> IO output -- server-streaming instance HasMethodHandler input output 'False 'False where type MethodHandler input output 'False 'True = input -> (output -> IO ()) -> IO () -- etc for client and bidi streaming With MethodHandler now powerful enough to give us the types we want for handlers, we can go back and fix HasServer so it will compile again: instance ( HasMethod s x , HasMethodHandler (MethodInput s x) (MethodOutput s x) (IsClientStreaming s x) (IsServerStreaming s x) , HasServer s xs ) => HasServer s (x ': xs) where type ServerType s (x ': xs) = MethodHandler (MethodInput s x) (MethodOutput s x) (IsClientStreaming s x) (IsServerStreaming s x) -> ServerType s xs It’s not pretty, but it works! We can convince ourselves of this by asking ghci: ghci> :kind! ServerType MyService (ServiceMethods MyService) (Request -> (Response -> IO ()) -> IO ()) -> IO () :: * and, if we had other methods defined for MyService, they’d show up here with the correct handler type, in the order they were listed in ServiceMethods MyService. ## Implementing the Server Our ServerType family now expands to a function type which takes a handler value (of the correct type) for every method on our service. That turns out to be more than half the battle – all we need to do now is to provide a value of this type. The generation of such a value is going to need to proceed in perfect lockstep with the generation of its type, so we add to the definition of HasServer: class HasServer s (xs :: [Symbol]) where type ServerType s xs :: * runServerImpl :: [AnyHandler] -> ServerType s xs What is this [AnyHandler] thing, you might ask. It’s an explicit accumulator for existentialized handlers we’ve collected during the fold over xs. It’ll make sense when we look at the induction case. For now, however, the base case is trivial as always: instance HasServer s '[] where type ServerType s '[] = IO () runServerImpl handlers = runGRPCServer handlers where runGRPCServer is the underlying server provided by Awake’s library. We move to the induction case: instance ( HasMethod s x , HasMethodHandler (MethodInput s x) (MethodOutput s x) (IsClientStreaming s x) (IsServerStreaming s x) , HasServer s xs ) => HasServer s (x ': xs) where type ServerType s (x ': xs) = MethodHandler (MethodInput s x) (MethodOutput s x) (IsClientStreaming s x) (IsServerStreaming s x) -> ServerType s xs runServerImpl handlers f = runServerImpl (existentialize f : handlers) where existentialize is a new class method we add to HasMethodHandler We will elide it here because it is just a function MethodHandler i o cs mm -> AnyHandler and is not particularly interesting if you’re familiar with existentialization. It’s evident here what I meant by handlers being an explicit accumulator – our recursion adds the parameters it receives into this list so that it can pass them eventually to the base case. There’s a problem here, however. Reading through this implementation of runServerImpl, you and I both know what the right-hand-side means, unfortunately GHC isn’t as clever as we are. If you try to compile it right now, GHC will complain about the non-injectivity of HasServer as implied by the call to runServerImpl (and also about HasMethodHandler and existentialize, but for the exact same reason.) The problem is that there’s nothing constraining the type variables s and xs on runServerImpl. I always find this error confusing (and I suspect everyone does), because in my mind it’s perfectly clear from the HasServer s xs in the instance constraint. However, because SeverType is a type family without any injectivity declarations, it means we can’t learn s and xs from ServerType s xs. Let’s see why. For a very simple example, let’s look at the following type family: type family NotInjective a where NotInjective Int = () NotInjective Bool = () Here we have NotInjective Int ~ () and NotInjective Bool ~ (), which means even if we know NotInjective a ~ () it doesn’t mean that we know what a is – it could be either Int or Bool. This is the exact problem we have with runServerImpl: even though we know what type runServerImpl has (it must be ServerType s xs, so that the type on the left-hand of the equality is the same as on the right), that doesn’t mean we know what s and xs are! The solution is to explicitly tell GHC via a type signature or type application: instance ( HasMethod s x , HasMethodHandler (MethodInput s x) (MethodOutput s x) (IsClientStreaming s x) (IsServerStreaming s x) , HasServer s xs ) => HasServer s (x ': xs) where type ServerType s (x ': xs) = MethodHandler (MethodInput s x) (MethodOutput s x) (IsClientStreaming s x) (IsServerStreaming s x) -> ServerType s xs runServerImpl handlers f = runServerImpl @s @xs (existentialize f : handlers) (For those of you playing along at home, you’ll need to type-apply the monstrous MethodInput and friends to the existentialize as well.) And finally, we’re done! We can slap a prettier interface in front of this runServerImpl to fill in some of the implementation details for us: runServer :: forall s . ( Service s , HasServer s (ServiceMethods s) ) => s -> ServerType s (ServiceMethods s) runServer _ = runServerImpl @s @(ServiceMethods s) [] Sweet and typesafe! Yes! ## Client-side Usability Sweet and typesafe all of this might be, but the user-friendliness on the client-side leaves a lot to be desired. As promised, we’ll address that now. ### Removing Proxies Recall that the runNonStreamingClient function and its friends require a Proxy m parameter in order to specify the method you want to call. However, m has kind Symbol, and thankfully we have some new extensions in GHC for turning Symbols into values. We can define a new type, isomorphic to Proxy, but which packs the fact that it is a KnownSymbol (something we can turn into a String at runtime): data WrappedMethod (sym :: Symbol) where WrappedMethod :: KnownSymbol sym => WrappedMethod sym We change our run*Client friends to take this WrappedMethod m instead of the Proxy m they used to: runNonStreamingClient :: ( HasMethod s m , IsClientStreaming s m ~ 'False , IsServerStreaming s m ~ 'False ) => s -> WrappedMethod m -> MethodInput s m -> IO (Either GRPCError (MethodOutput s m)) and, with this change in place, we’re ready for the magic syntax I promised earlier. import GHC.OverloadedLabel instance ( KnownSymbol sym , sym ~ sym' ) => IsLabel sym (WrappedMethod sym') where fromLabel _ = WrappedMethod This sym ~ sym' thing is known as the constraint trick for instances, and is necessary here to convince GHC that this can be the only possible instance of IsLabel that will give you back WrappedMethods. Now turning on the {-# LANGUAGE OverloadedLabels #-} pragma, we’ve changed the syntax to call these client functions from the ugly: runBiDiStreamingClient MyService (Proxy @"biDiStreaming") into the much nicer: runBiDiStreamingClient MyService #biDiStreaming ### Better “Wrong Streaming Variety” Errors The next step in our journey to delightful usability is remembering that the users of our library are only human, and at some point they are going to call the wrong run*Client function on their method with a different variety of streaming semantics. At the moment, the errors they’re going to get when they try that will be a few stanza long, the most informative of which will be something along the lines of unable to match 'False with 'True. Yes, it’s technically correct, but it’s entirely useless. Instead, we can use the TypeError machinery from GHC.TypeLits to make these error messages actually helpful to our users. If you aren’t familiar with it, if GHC ever encounters a TypeError constraint it will die with a error message of your choosing. We will introduce the following type family: type family RunNonStreamingClient (cs :: Bool) (ss :: Bool) :: Constraint where RunNonStreamingClient 'False 'False = () RunNonStreamingClient 'False 'True = TypeError ( Text "Called 'runNonStreamingClient' on a server-streaming method." :$$: Text "Perhaps you meant 'runServerStreamingClient'." ) RunNonStreamingClient 'True 'False = TypeError ( Text "Called 'runNonStreamingClient' on a client-streaming method." :$$: Text "Perhaps you meant 'runClientStreamingClient'." ) RunNonStreamingClient 'True 'True = TypeError ( Text "Called 'runNonStreamingClient' on a bidi-streaming method." :$$: Text "Perhaps you meant 'runBiDiStreamingClient'." ) The :$$: type operator stacks message vertically, while :<>: stacks it horizontally. We can change the constraints on runNonStreamingClient: runNonStreamingClient :: ( HasMethod s m , RunNonStreamingClient (IsClientStreaming s m) (IsServerStreaming s m) ) => s -> WrappedMethod m -> MethodInput s m -> IO (Either GRPCError (MethodOutput s m)) and similarly for our other client functions. Reduction of the resulting boilerplate is left as an exercise to the reader. With all of this work out of the way, we can test it: runNonStreamingClient MyService #biDiStreaming Main.hs:45:13: error: • Called 'runNonStreamingClient' on a bidi-streaming method. Perhaps you meant 'runBiDiStreamingClient'. • In the expression: runNonStreamingClient MyService #bidi Amazing! ### Better “Wrong Method” Errors The other class of errors we expect our users to make is to attempt to call a method that doesn’t exist – either because they made a typo, or are forgetful of which methods exist on the service in question. As it stands, users are likely to get about six stanzas of error messages, from No instance for (HasMethod s m) to Ambiguous type variable 'm0', and other terrible things that leak our implementation details. Our first thought might be to somehow emit a TypeError constraint if we don’t have a HasMethod s m instance, but I’m not convinced such a thing is possible. But luckily, we can actually do better than any error messages we could produce in that way. Since our service is driven by a value (in our example, the data constructor MyService), by the time things go wrong we do have a Service s instance in scope. Which means we can look up our ServiceMethods s and given some helpful suggestions about what the user probably meant. The first step is to implement a ListContains type family so we can determine if the method we’re looking for is actually a real method. type family ListContains (n :: k) (hs :: [k]) :: Bool where ListContains n '[] = 'False ListContains n (n ': hs) = 'True ListContains n (x ': hs) = ListContains n hs In the base case, we have no list to look through, so our needle is trivially not in the haystack. If the head of the list is the thing we’re looking for, then it must be in the list. Otherwise, take off the head of the list and continue looking. Simple really, right? We can now use this thing to generate an error message in the case that the method we’re looking for is not in our list of methods: type family RequireHasMethod s (m :: Symbol) (found :: Bool) :: Constraint where RequireHasMethod s m 'False = TypeError ( Text "No method " :<>: ShowType m :<>: Text " available for service '" :<>: ShowType s :<>: Text "'." :$$: Text "Available methods are: " :<>: ShowType (ServiceMethods s) ) RequireHasMethod s m 'True = () If found ~ 'False, then the method m we’re looking for is not part of the service s. We produce a nice error message informing the user about this (using ShowType to expand the type variables). We will provide a type alias to perform this lookup: type HasMethod' s m = ( RequireHasMethod s m (ListContains m (ServiceMethods s) , HasMethod s m ) Our new HasMethod' s m has the same shape as HasMethod, but will expand to our custom type error if we’re missing the method under scrutiny. Replacing all of our old HasMethod constraints with HasMethod' works fantastically: Main.hs:54:15: error: • No method "missing" available for service 'MyService'. Available methods are: '["biDiStreaming"] Damn near perfect! That list of methods is kind of ugly, though, so we can write a quick pretty printer for showing promoted lists: type family ShowList (ls :: [k]) :: ErrorMessage where ShowList '[] = Text "" ShowList '[x] = ShowType x ShowList (x ': xs) = ShowType x :<>: Text ", " :<>: ShowList xs Replacing our final ShowType with ShowList in RequireHasMethod now gives us error messages of the following: Main.hs:54:15: error: • No method "missing" available for service 'MyService'. Available methods are: "biDiStreaming" Absolutely gorgeous. ## Conclusion This is where we stop. We’ve used type-level metadata to generate client- and server-side bindings to an underlying library. Everything we’ve made is entirely typesafe, and provides gorgeous, helpful error messages if the user does anything wrong. We’ve found a practical use for many of these seemingly-obscure type-level features, and learned a few things in the process. In the words of my coworker Renzo Carbonara1: “It is up to us, as people who understand a problem at hand, to try and teach the type system as much as we can about that problem. And when we don’t understand the problem, talking to the type system about it will help us understand. Remember, the type system is not magic, it is a logical reasoning tool.” This resounds so strongly in my soul, and maybe it will in yours too. If so, I encourage you to go forth and find uses for these techniques to improve the experience and safety of your own libraries. 1. Whose article “Opaleye’s sugar on top” was a strong inspiration on me, and subsequently on this post. </article> ## November 16, 2017 ### Tweag I/O # Parallelising your array code Manuel M T Chakravarty This is the fifth post in a series about array programming in Haskell — you might be interested in the first, second, third, and fourth, too. A recurring theme in array programming is performance. After all, many algorithms in numerical computing and data science are computationally intensive. Once the sequential implementation of an array program has been fully optimised, the natural next step is to use one or multiple forms of parallelism to achieve further performance improvements. This can be parallelism within one computational core (SIMD parallelism), multicore parallelism, or distributed multi-machine parallelism. Unfortunately, at this point matters become much more complicated, because parallel programming comes with its own set of serious challenges. In this post, we will focus on multicore parallelism for computations operating on multi-dimensional arrays. In other words, in relation to the vector package, which we discussed in the last post, we have two new ingredients. Firstly, instead of one-dimensional Int-indexed arrays, we have multi-dimensional Int-indexed arrays. Secondly, the collective operations provided on these arrays come with parallel implementations. In fact, the library API is designed to favour collective operations that have good parallel implementations. Similarly, the move to explicitly multi-dimensional arrays is motivated by being able to provide parallel implementations that take the array shape into account, wherever that is an advantage. To make matters concrete, we will discuss the Repa library. Internally it uses many of the same techniques as vector, including strictness, unboxing, and a two-phase initialisation strategy. However, it uses a second array fusion strategy in addition to vector’s stream fusion. More precisely, Repa internally uses vector to represent plain boxed and unboxed arrays and to execute sequential computations on those, which still benefit from stream fusion. However, Repa introduces additional array representations, such as delayed arrays, to also achieve fusion across parallel computations. This additional complication is necessary as stream fusion, by itself, tends to turn parallel into sequential code. In other words, one of the challenges of high-performance parallel array implementations that are built on collective operations is to apply fusion while preserving parallelism. To really get good performance, we need to simultaneously optimize along two orthogonal dimensions: get more done simultaneously, by parallelizing, but also make each sequential unit of work run faster. A second consequence of targeting a parallelisation-friendly API is a very limited use of mutable arrays. Mutable structures generally interact badly with concurrency and parallelism, opening the door to a whole range of hard to diagnose faults. In fact, the focus on immutable arrays for parallel programming is one of the most compelling conceptual improvements of functional over imperative parallel array programming. (To be precise, Repa’s API does provide access to the mutable array structures used to implement two-phase initialisation, but it is usually not necessary to use them directly.) ## Multiple dimensions The obvious structure for indexing multi-dimensional Int-indexed arrays are tuples of Ints. However, they come with two severe drawbacks: (1) they force us to fix the dimensionality of all functions over arrays and (2) they are not sufficient to characterise operations on lower-dimensional subarrays of an array (e.g., a two-dimensional plane within a three-dimensional cube). As an example of the first drawback, consider a fold function that given a three-dimensional cube, reduces it along, say, the x-axis to a two-dimensional plane of sums. The only difference of that operation compared to a fold that sums a two-dimensional plane across one axis to a one-dimensional vector is the number of dimensions that we do not reduce along. Now, we could have a family of fold functions (fold1, fold2, and so on), one for each possible dimension of argument array. But that is hardly satisfactory. Instead, Repa uses a custom datatype for indexing. Index types are built from the infix constructor (:.) and the constant Z, representing a zero-dimensional array (which is the special cases of a singleton array). For example, the type of two-dimensional indices is Z :. Int :. Int and one of its values is Z :. 3 :. 5. By using a type variable instead of Z, we can denote indices with a particular minimum dimensionality. For instance, sh :. Int has at least one dimension, but it might have more, depending on how the type variable sh is instantiated — in any case, instances of sh need to be drawn from the class Shape. On the basis of this index representation, we can capture the entire family of multi-dimensional fold functions in a single type: foldS :: (Shape sh, Source r a, Unbox a) => (a -> a -> a) -> a -> Array r (sh :. Int) a -> Array U sh a  The function foldS implements a sequential, multi-dimensional reduction; hence, the S suffix. It gets three arguments: 1. a -> a -> a is the type of the binary reduction function, which needs to be associative, 2. a is the reduction function’s neutral (i.e, together they form a monoid), and 3. Array e (sh :. Int) a is an at least one-dimensional array of elements of type a, which the type constraint Unbox a requires to be a type that has an associated unboxed representation. Finally, the result of type Array U sh a has one dimension less than the argument array, but contains elements of the same type a. This leaves us with wondering about the meaning of the first type argument of Arrayr and U, respectively— as well as the type constraint Source r a. ## Indexed arrays The first type argument of Array determines the array representation. The available representations include boxed (V) and unboxed (U) representations, but also delayed (D) and cursored (C) representations. The latter are guaranteed to be removed by fusion, but can lead to the superfluous recomputation of array elements that are used more than once. Repa makes the choice of representation explicit to place it under programmer control — experience shows that compiler heuristics for automatic representation selection tend to be fragile and unreliable. A consequence of a representation that is fused away, such as delayed D and cursored C, is that it can only be a data Source of a computation. Hence, the type class of the same name provides elementary array access functions for arrays. The opposite, a Target, provides the functionality to fill an array as part of two-phase initialisation and is only available to manifest representations, such as the boxed V and unboxed U representation. A manifest representation is one which, in contrast to a fused-away delayed representation, is actually stored in memory. In addition to concrete representations, Repa representation tags can also include meta information, such as the interleaving hint I. An array tagged I U uses an unboxed interleaved representation, which improves parallel load balancing in parallel computations where the amount of work strongly varies between different regions in the parallel array. A standard example is computing a Mandelbrot set, where black pixels are significantly more expensive than others. ## Parallelism As we saw above with foldS, Repa follows the convention of adding an S to sequential array operations. Similarly, it uses a P as a suffix for parallel functions. For example, we have foldP :: (Shape sh, Source r a, Unbox a, Monad m) => (a -> a -> a) -> a -> Array r (sh :. Int) a -> m (Array U sh a)  for the parallel version of fold. The distinction between sequential and parallel functions is an important one, since Repa does not support nested parallelism. That is, a parallel function (e.g., foldP) cannot use another parallel function as an argument (e.g., as the combination function). In addition to the suffix, the parallel fold distinguishes itself from the sequential by the use of a not further specified monad. The purpose of this monad is to ensure the one-by-one execution of pipelines of parallel computations. This is important to prevent inadvertent nesting of parallel computations as Haskell is a lazy language and we might otherwise feed a suspended (i.e., not yet evaluated) parallel computation into another parallel computation. ## Parallel matrix multiplication As a simple example of a parallel computation, consider the multiplication of two matrices arr and brr of type Array U DIM2 Double (two-dimensional, unboxed arrays), where type DIM2 = Z :. Int :. Int: mmultP :: Monad m => Array U DIM2 Double -> Array U DIM2 Double -> m (Array U DIM2 Double) mmultP arr brr = do trr <- transpose2P brr computeP (fromFunction (Z :. h1 :. w2) dotp) where (Z :. h1 :. _) = extent arr (Z :. _ :. w2) = extent brr dotp ix = sumAllS$
zipWith (*)
(slice arr (Any :. (row ix) :. All))
(slice trr (Any :. (col ix) :. All))


We assume the existence of a helper function transpose2P, which transposes a matrix in parallel — for example, by using Repa’s backpermute function. Then, we generate the manifest result array by computing all elements of fromFunction (Z :. h1 :. w2) dotpin parallel with computeP. The shape (i.e., the size of the dimensions) of the result is h1 times w2, and fromFunction turns a function, which takes an array index to the corresponding array element , into a delayed array:

fromFunction :: sh -> (sh -> a) -> Array D sh a


At each index ix of the resulting array, we evaluate dotp, which only involves a sequential computation. It’s sequential nature is important for two reasons. Firstly, as mentioned, Repa does not support nested parallelism, so the computations on each result array index triggered by computeP in parallel may themselves not be parallel. Secondly, the work complexity of matrix multiplication is n^3 — that is the number of scalar multiplications that need to be performed. Performing them all in parallel would lead to (a) too much and (b) too fine-grained parallelism. Both too much parallelism and parallel workloads that are each too little work lead to bad performance as they result in too much administrative overhead.

In contrast, the sequential computation performed by dotp obtains a row of the matrix arr and a column of brr (actually, a row of the transposed brr, which is trr) with slice, which extracts an entire subarray from an array. Then, it multiples the row and column pointwise with zipWith (*) and sums up the products with sumAllS, where

zipWith :: (Shape sh, Source r1 a, Source r2 b)
=> (a -> b -> c) -> Array r1 sh a -> Array r2 sh b -> Array D sh c
sumAllS :: (Shape sh, Source r a, Num a) => Array r sh a -> a


This example highlights how reasoning about the decomposition of an algorithm into parallel and sequential components is crucial for good parallel performance. This is assisted by Repa’s clear distinction between sequential and parallel operations.

Repa went through three major iterations before arriving at the current interface. The underlying concepts are described and supported by benchmarks in the papers Regular, shape-polymorphic, parallel arrays in Haskell, Efficient Parallel Stencil Convolution in Haskell, and Guiding Parallel Array Fusion with Indexed Types, respectively. In addition, Data Flow Fusion with Series Expressions in Haskell proposes a further improvement to the fusion system. However, this has not been integrated into the main package.

# The Digits of Pi

In the previous post we were introduced to metamorphisms, which consist of an unfold after a fold—typically on lists, and the fold part typically a ${\mathit{foldl}}$. A canonical example is the conversion of a fraction from one base to another. For simplicity, let’s consider here only infinite fractions, so we don’t have to deal with the end of the input and flushing the state:

$\displaystyle \begin{array}{@{}lcl@{}} \multicolumn{3}{@{}l}{\mathit{stream} :: (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow [\gamma]} \\ \mathit{stream}\;g\;f\;b\;x &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{stream}\;g\;f\;b'\;x \\ \mathit{Nothing} &\rightarrow& \mathbf{case}\;x\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} a:x' &\rightarrow& \mathit{stream}\;g\;f\;(f\;b\;a)\;x' \end{array} \end{array} \end{array}$

So for example, we can convert an infinite fraction in base 3 to one in base 7 with

$\displaystyle \mathit{stream}\;\mathit{next}\;\mathit{step}\;(0,1)$

where

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{next}\;(u,v) &=& \begin{array}[t]{@{}l} \mathbf{let}\;y = \lfloor{7 \times u \times v}\rfloor\;\mathbf{in} \\ \mathbf{if}\;\lfloor{y}\rfloor = \lfloor{7 \times (u+1) \times v}\rfloor\;\begin{array}[t]{@{}l@{\;}l}\mathbf{then}&\mathit{Just}\;(y,(u - y/(v \times 7), v \times 7))\\\mathbf{else}&\mathit{Nothing} \\ \end{array} \end{array} \\ \mathit{stepl}\;(u,v)\;d &=& (u \times 3 + d, v / 3) \end{array}$

In this post, we’ll see another number conversion problem, which will deliver the digits of ${\pi}$. For more details, see my paper—although the presentation here is simpler now.

## Series for pi

Leibniz showed that

$\displaystyle \displaystyle \frac{\pi}{4} = \sum_{i=0}^{\infty} \frac{(-1)^i}{2i+1}$

From this, using Euler’s convergence-accelerating transformation, one may derive

$\displaystyle \pi = \sum_{i=0}^{\infty} \frac{(i!)^2\,2^{i+1}}{(2i+1)!}$

or equivalently

$\displaystyle \pi = 2 + \frac{1}{3} \times \biggl(2 + \frac{2}{5}\times \biggl(2 + \frac{3}{7}\times \biggl( \cdots \biggl(2 + \frac{i}{2i+1}\times \biggl(\cdots\biggr)\biggr)\biggr)\biggr)\biggr)$

This can be seen as the number ${(2;2,2,2...)}$ in a funny mixed-radix base ${(\frac{1}{3}, \frac{2}{5}, \frac{3}{7}...)}$, just as the usual decimal expansion

$\displaystyle \pi = 3 + \frac{1}{10} \times \biggl(1 + \frac{1}{10}\times \biggl(4 + \frac{1}{10}\times \biggl( \cdots\biggr)\biggr)\biggr)$

is represented by the number ${(3;1,4,1...)}$ in the fixed-radix base ${(\frac{1}{10},\frac{1}{10},\frac{1}{10}...)}$. Computing the decimal digits of ${\pi}$ is then a matter of conversion from the mixed-radix base to the fixed-radix base.

## Conversion from a fixed base

Let’s remind ourselves of how it should work, using a simpler example: conversion from one fixed base to another. We are given an infinite-precision fraction in the unit interval

$\displaystyle x = \frac{1}{m} \times \biggl(x_0 + \frac{1}{m}\times \biggl(x_1 + \frac{1}{m}\times \biggl( \cdots\biggr)\biggr)\biggr)$

in base ${m}$, in which ${0 \le x_i < m}$ for each digit ${x_i}$. We are to convert it to a similar representation

$\displaystyle x = \frac{1}{n} \times \biggl(y_0 + \frac{1}{n}\times \biggl(y_1 + \frac{1}{n}\times \biggl( \cdots\biggr)\biggr)\biggr)$

in base ${n}$, in which ${0 \le y_j < n}$ for each output digit ${y_j}$. The streaming process maintains a state ${(u,v)}$, a pair of rationals; the invariant is that after consuming ${i}$ input digits and producing ${j}$ output digits, we have

$\displaystyle x = \frac{1}{n} \times \biggl(y_0 + \cdots + \frac{1}{n}\times \biggl(y_{j-1} + v \times (u + \frac{1}{m} \times \biggl( x_i + \frac{1}{m} \times \biggl(x_{i+1} + \cdots \biggr)\biggr)\biggr)\biggr)\biggr)$

so that ${(u,v)}$ represents a linear function ${(v\times) \cdot (u+)}$ that should be applied to the value represented by the remaining input.

We can initialize the process with ${i=0, j=0, u=0, v=1}$. At each step, we first try to produce another output digit. The remaining input digits ${x_i, x_{i+1},...}$ represent a value in the unit interval; so if ${n \times v \times (u+0)}$ and ${n \times v \times (u+1)}$ have the same integer part, then that must be the next output digit, whatever the remaining input digits are. Let ${y_j = \lfloor n \times v \times u \rfloor}$ be that integer. Now we need to find ${(u',v')}$ such that

$\displaystyle \frac{1}{n} \times \biggl(y_j + v' \times (u' + r)\biggr) = v \times (u + r)$

for any remainder ${r}$; then we can increment ${j}$ and set ${(u,v)}$ to ${(u',v')}$ and the invariant is maintained. A little algebra shows that we should take ${v' = n \times v}$ and ${u' = u - y_j/v'}$.

If ${v \times u}$ and ${v \times (u+1)}$ have different integer parts, we cannot yet tell what the next output digit should be, so we must consume the next input digit instead. Now we need to find ${(u',v')}$ such that

$\displaystyle v \times \biggl(u + \frac{1}{m} \times \biggl(x_i + r\biggr)\biggr) = v' \times (u' + r)$

for any remainder ${r}$; then we can increment ${i}$ and set ${(u,v)}$ to ${(u',v')}$ and the invariant is again maintained. Again, algebraic manipulation leads us to ${v' = v/m}$ and ${u' = m \times u + x_i}$.

For example, ${\frac{1}{4} = 0.020202..._3 = 0.151515..._7}$, and the conversion starts as follows:

$\displaystyle \begin{array}{c|c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}cc} x_i & & 0 && 2 && 0 && && 2 && && 0 && 2 \\ \hline (u,v) & \bigl(\frac{0}{1},\frac{1}{1}\bigr) && \bigl(\frac{0}{1},\frac{1}{3}\bigr) && \bigl(\frac{2}{1},\frac{1}{9}\bigr) && \bigl(\frac{6}{1},\frac{1}{27}\bigr) && \bigl(\frac{15}{7},\frac{7}{27}\bigr) && \bigl(\frac{59}{7},\frac{7}{81}\bigr) && \bigl(\frac{8}{49},\frac{49}{81}\bigr) && \bigl(\frac{24}{49},\frac{49}{243}\bigr) && \bigl(\frac{170}{49},\frac{49}{729}\bigr) & \cdots \vrule height 2.5ex depth 1.5ex width 0pt \\ \hline y_j & & && && && 1 && && 5 \end{array}$

That is, the initial state is ${u_0=\frac{0}{1}, v_0=\frac{1}{1}}$. This state does not yet determine the first output digit, so we consume the first input digit 0 to yield the next state ${u_1 = \frac{0}{1}, v_1 = \frac{1}{3}}$. This state still does not determine the first output, and nor will the next; so we consume the next two input digits 2 and 0, yielding state ${u_3 = \frac{6}{1}, v_3 = \frac{1}{27}}$. This state does determine the next digit: ${v_3 \times u_3 = 0.020_3 = 0.136..._7}$ and ${v_3 \times (u_3+1) = 0.021_3 = 0.154..._7}$ both start with a 1 in base 7. So we can produce a 1 as the first output digit, yielding state ${u_4 = \frac{15}{7}, v_4 = \frac{7}{27}}$. And so on.

The process tends to converge. Each production step widens the non-empty window ${[n \times v \times u, n \times v \times (u+1))}$ by a factor of ${n}$, so it will eventually contain multiple integers; therefore we cannot produce indefinitely. Each consumption step narrows the window by a factor of ${m}$, so it will tend towards eventually producing the next output digit. However, this doesn’t always work. For example, consider converting ${0.333..._{10}}$ to base 3:

$\displaystyle \begin{array}{c|c@{}c@{}c@{}c@{}c@{}c@{}cc} x_i & & 3 && 3 && 3 & \\ \hline (u,v) & \bigl(\frac{0}{1},\frac{1}{1}\bigr) && \bigl(\frac{3}{1},\frac{1}{10}\bigr) && \bigl(\frac{33}{1},\frac{1}{100}\bigr) && \bigl(\frac{333}{1},\frac{1}{1000}\bigr) & \cdots \vrule height 2.5ex depth 1.5ex width 0pt \\ \hline y_j & & && \end{array}$

The first output digit is never determined: if the first non-3 in the input is less than 3, the value is less than a third, and the first output digit should be a 0; if the first non-3 is greater than 3, then the value is definitely greater than a third, and it is safe to produce a 1 as the first output digit; but because the input is all 3s, we never get to make this decision. This problem will happen whenever the value being represented has a finite representation in the output base.

## Conversion from a mixed base

Let’s return now to computing the digits of ${\pi}$. We have the input

$\displaystyle \pi = 2 + \frac{1}{3} \times \biggl(2 + \frac{2}{5}\times \biggl(2 + \frac{3}{7}\times \biggl( \cdots \biggl(2 + \frac{i}{2i+1}\times \biggl(\cdots\biggr)\biggr)\biggr)\biggr)\biggr)$

which we want to convert to decimal. The streaming process maintains a pair ${(u,v)}$ of rationals—but this time representing the linear function ${(u+) \cdot (v\times)}$, since this time our expression starts with a sum rather than a product. The invariant is similar: after consuming ${i-1}$ input digits and producing ${j}$ output digits, we have

$\displaystyle \pi = y_0 + \frac{1}{10} \times \biggl(\cdots y_{j-1} + \frac{1}{10} \times \biggl(u + v \times \biggl(x_i + \frac{i}{2i+1} \times \biggl(x_{i+1} + \frac{i+1}{2i+3} \times \cdots\biggr)\biggr)\biggr)\biggr)$

Note that the output base is fixed at 10; but more importantly, the input digits ${x_i}$ are all fixed at 2, and it is the input base that varies from digit to digit.

We can initialize the process with ${i=1, j=0, u=0, v=1}$. At each step, we first try to produce an output digit. What value might the remaining input

$\displaystyle r = 2 + \frac{i}{2i+1} \times \biggl(2 + \frac{i+1}{2i+3} \times \cdots \biggr)$

represent? Each of the bases is at least ${\frac{1}{3}}$, so it is clear that ${r_{\mathrm{min}} \le r}$, where

$\displaystyle r_{\mathrm{min}} = 2 + \frac{1}{3} \times r_{\mathrm{min}}$

which has unique solution ${r_{\mathrm{min}} = 3}$. Similarly, each of the bases is less than ${\frac{1}{2}}$, so it is clear that ${r < r_{\mathrm{max}}}$, where

$\displaystyle r_{\mathrm{max}} = 2 + \frac{1}{2} \times r_{\mathrm{max}}$

which has unique solution ${r_{\mathrm{max}} = 4}$. So we consider the bounds ${\lfloor u + v \times 3 \rfloor}$ and ${\lfloor u + v \times 4 \rfloor}$; if these have the same integer part ${y_j}$, then that is the next output digit. Now we need to find ${(u',v')}$ such that

$\displaystyle y_j + \frac{1}{10} \times (u' + v' \times r) = u + v \times r$

for any remainder ${r}$, so we pick ${u' = 10 \times (u - y_j)}$ and ${v' = 10 \times v}$. Then we can increment ${j}$ and set ${(u,v)}$ to ${(u',v')}$, and the invariant is maintained.

If the two bounds have different integer parts, we must consume the next input digit instead. Now we need to find ${(u',v')}$ such that

$\displaystyle u' + v' \times r = u + v \times \biggl(x_i + \frac{i}{2i+1} \times r\biggr)$

for all ${r}$, so we pick ${u' = u + v \times x_i}$ and ${v' = v \times i / (2i+1)}$. Then we can increment ${i}$ and set ${(u,v)}$ to ${(u',v')}$, and again the invariant is maintained.

The conversion starts as follows:

$\displaystyle \begin{array}{c|c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}cc} x_i & & 2 && && 2 && 2 && && 2 && 2 \\ \hline (u,v) & \bigl(\frac{0}{1},\frac{1}{1}\bigr) && \bigl(\frac{2}{1},\frac{1}{3}\bigr) && \bigl(\frac{-10}{1},\frac{10}{3}\bigr) && \bigl(\frac{10}{3},\frac{4}{3}\bigr) && \bigl(\frac{-2}{3},\frac{4}{7}\bigr) && \bigl(\frac{-50}{3},\frac{40}{7}\bigr) && \bigl(\frac{-110}{21},\frac{160}{63}\bigr) && \bigl(\frac{-10}{63},\frac{800}{693}\bigr) & \cdots \vrule height 2.5ex depth 1.5ex width 0pt \\ \hline y_j & & && 3 && && && 1 && && \end{array}$

Happily, non-termination ceases to be a problem: the value being represented does not have a finite representation in the output base, being irrational.

## Code

We can plug these definitions straight into the ${\mathit{stream}}$ function above:

$\displaystyle \mathit{piDigits} = \mathit{stream}\;g\;f\;(1,0,0\%1,1\%1)\;(\mathit{repeat}\;2)$

where

$\displaystyle g\;(i,j,u,v) = \begin{array}[t]{@{}l} \mathbf{if}\;y == \mathit{floor}\;(u + v \times 4) \\ \mathbf{then}\;\mathit{Just}\;(y, (i,j+1, 10 \times (u - \mathit{fromIntegral}\;y), 10 \times v)) \\ \mathbf{else}\;\mathit{Nothing} \\ \mathbf{where}\;y = \mathit{floor}\;(u + v \times 3) \end{array}$

and

$\displaystyle f\;(i,j,u,v)\;x = \begin{array}[t]{@{}l} (i+1,j,u + v \times \mathit{fromIntegral}\;x, v \times i' / (2 \times i' + 1)) \\ \mathbf{where}\;i' = \mathit{fromIntegral}\;i \end{array}$

(The ${\%}$s make rational numbers in Haskell, and force the ambiguous fractional type to be ${\mathit{Rational}}$ rather than ${\mathit{Double}}$.)

In fact, this program can be considerably simplified, by inlining the definitions. In particular, the input digits are all 2, so we need not supply them. Moreover, the ${j}$ component of the state is never used, because we treat each output digit in the same way (in contrast to the input digits); so that may be eliminated. Finally, we can eliminate some of the numeric coercions if we represent the ${i}$ component as a rational in the first place:

$\displaystyle \mathit{piDigits} = \begin{array}[t]{@{}l} \mathit{go}\;((1,0,1) :: (\mathit{Rational},\mathit{Rational},\mathit{Rational}))\;\mathbf{where} \\ \qquad \mathit{go}\;(i,u,v) = \begin{array}[t]{@{}ll} \mathbf{if} & y == \mathit{floor}\;(u+v \times 4) \\ \mathbf{then} & y : \mathit{go}\;(i,10 \times (u-\mathit{fromIntegral}\;y),10 \times v) \\ \mathbf{else} & \mathit{go}\;(i+1,u+2 \times v, (v \times i) / (2 \times i+1)) \\ \multicolumn{2}{@{}l}{\qquad \mathbf{where}\; y = \mathit{floor}\;(u+v \times 3)} \end{array} \end{array}$

Then we have

$\displaystyle \mathit{piDigits} = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3...$

# Metamorphisms

It appears that I have insufficient time, or at least insufficient discipline, to contribute to this blog, except when I am on sabbatical. Which I now am… so let’s see if I can do better.

## Hylomorphisms

I don’t think I’ve written about them yet in this series—another story, for another day—but hylomorphisms consist of a fold after an unfold. One very simple example is the factorial function: ${n!}$ is the product of the predecessors ${[n,...,1]}$ of ${n}$. The predecessors can be computed with an unfold:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{preds} &::& \mathit{Integer} \rightarrow [\mathit{Integer}] \\ \mathit{preds} &=& \mathit{unfoldr}\;\mathit{step} \; \mathbf{where} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{step}\;0 &=& \mathit{Nothing} \\ \mathit{step}\;n &=& \mathit{Just}\;(n, n-1) \end{array} \end{array}$

and the product as a fold:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{prod} &::& [\mathit{Integer}] \rightarrow \mathit{Integer} \\ \mathit{prod} &=& \mathit{foldr}\;(\times)\;1 \end{array}$

and then factorial is their composition:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{factorial} &::& \mathit{Integer} \rightarrow \mathit{Integer} \\ \mathit{factorial} &=& \mathit{prod} \cdot \mathit{preds} \end{array}$

Another example is a tree-based sorting algorithm that resembles Hoare’s quicksort: from the input list, grow a binary search tree, as an unfold, and then flatten that tree back to a sorted list, as a fold. This is a divide-and-conquer algorithm; in general, these can be modelled as unfolding a tree of subproblems by repeatedly dividing the problem, then collecting the solution to the original problem by folding together the solutions to subproblems.

## An unfold after a fold

This post is about the opposite composition, an unfold after a fold. Some examples:

• ${\mathit{regroup}\;n = \mathit{group}\;n \cdot \mathit{concat}}$ to reformat a list of lists to a given length;
• ${\mathit{heapsort} = \mathit{flattenHeap} \cdot \mathit{buildHeap}}$ to sort a list;
• ${\mathit{baseconv}\;(b,c) = \mathit{toBase}\;b \cdot \mathit{fromBase}\;c}$ to convert a fraction from base ${c}$ to base ${b}$;
• ${\mathit{arithCode} = \mathit{toBits} \cdot \mathit{narrow}}$ to encode a text in binary by “arithmetic coding”.

In each of these cases, the first phase is a fold, which consumes some structured representation of a value into an intermediate unstructured format, and the second phase is an unfold, which generates a new structured representation. Their composition effects a change of representation, so we call them metamorphisms.

Hylomorphisms always fuse, and one can deforest the intermediate virtual data structure. For example, one need not construct the intermediate list in the factorial function; since each cell gets constructed in the unfold only to be immediately deconstructed in the fold, one can cut to the chase and go straight to the familiar recursive definition. For the base case, we have:

$\displaystyle \begin{array}{ll} & \mathit{factorial}\;0 \\ = & \qquad \{ \mathit{factorial} \} \\ & \mathit{prod}\;(\mathit{preds}\;0) \\ = & \qquad \{ \mathit{preds} \} \\ & \mathit{prod}\;[\,] \\ = & \qquad \{ \mathit{prod} \} \\ & 1 \end{array}$

and for non-zero argument ${n}$, we have:

$\displaystyle \begin{array}{ll} & \mathit{factorial}\;n \\ = & \qquad \{ \mathit{factorial} \} \\ & \mathit{prod}\;(\mathit{preds}\;n) \\ = & \qquad \{ \mathit{preds} \} \\ & \mathit{prod}\;(n : \mathit{preds}\;(n-1)) \\ = & \qquad \{ \mathit{prod} \} \\ & n \times \mathit{prod}\;(\mathit{preds}\;(n-1)) \\ = & \qquad \{ \mathit{factorial} \} \\ & n \times \mathit{factorial}\;(n-1) \\ \end{array}$

In contrast, metamorphisms only fuse under certain conditions. However, when they do fuse, they also allow infinite representations to be processed, as we shall see.

Fusion seems to depend on the fold being tail-recursive; that is, a ${\mathit{foldl}}$:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{foldl} &::& (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow \beta \\ \mathit{foldl}\;f\;b\;(a:x) &=& \mathit{foldl}\;f\;(f\;b\;a)\;x \\ \mathit{foldl}\;f\;b\;[\,] &=& b \end{array}$

For the unfold phase, we will use the usual list unfold:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{unfoldr} &::& (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow \beta \rightarrow [\gamma] \\ \mathit{unfoldr}\;g\;b &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{unfoldr}\;g\;b' \\ \mathit{Nothing} &\rightarrow& [\,] \end{array} \end{array}$

We define a metamorphism as their composition:

$\displaystyle \begin{array}{l} \mathit{meta} :: (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow [\gamma] \\ \mathit{meta}\;g\;f\;b = \mathit{unfoldr}\;g \cdot \mathit{foldl}\;f\;b \end{array}$

This transforms input of type ${[A]}$ to output of type ${[C]}$: in the first phase, ${\mathit{foldl}\;f\;b}$, it consumes all the input into an intermediate value of type ${B}$; in the second phase, ${\mathit{unfoldr}\;g}$, it produces all the output.

## Streaming

Under certain conditions, it is possible to fuse these two phases—this time, not in order to eliminate an intermediate data structure (after all, the intermediate type ${B}$ need not be structured), but rather in order to allow some production steps to happen before all the consumption steps are complete.

To that end, we define the ${\mathit{stream}}$ function as follows:

$\displaystyle \begin{array}{@{}lcl@{}} \multicolumn{3}{@{}l}{\mathit{stream} :: (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow [\gamma]} \\ \mathit{stream}\;g\;f\;b\;x &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{stream}\;g\;f\;b'\;x \\ \mathit{Nothing} &\rightarrow& \mathbf{case}\;x\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} a:x' &\rightarrow& \mathit{stream}\;g\;f\;(f\;b\;a)\;x' \\ {[\,]} &\rightarrow& [\,] \end{array} \end{array} \end{array}$

This takes the same arguments as ${\mathit{meta}}$. It maintains a current state ${b}$, and produces an output element ${c}$ when it can; and when it can’t produce, it consumes an input element instead. In more detail, it examines the current state ${b}$ using function ${g}$, which is like the body of an unfold; this may produce a first element ${c}$ of the result and a new state ${b'}$; when it yields no element, the next element ${a}$ of the input is consumed using function ${f}$, which is like the body of a ${\mathit{foldl}}$; and when no input remains either, we are done.

The streaming condition for ${f}$ and ${g}$ is that

$\displaystyle g\;b = \mathit{Just}\;(c,b') \quad\Rightarrow\quad \forall a \mathbin{.} g\;(f\;b\;a) = \mathit{Just}\;(c, f\;b'\;a)$

Consider a state ${b}$ from which the body ${g}$ of the unfold is productive, yielding some ${\mathit{Just}\;(c,b')}$. From here we have two choices: we can either produce the output ${c}$, move to intermediate state ${b'}$, then consume the next input ${a}$ to yield a final state ${f\;b'\;a}$; or we can consume first to get the intermediate state ${f\;b\;a}$, and again try to produce. The streaming condition says that this intermediate state ${f\;b\;a}$ will again be productive, and will yield the same output ${c}$ and the same final state ${f\;b'\;a}$. That is, instead of consuming all the inputs first, and then producing all the outputs, it is possible to produce some of the outputs early, without jeopardizing the overall result. Provided that the streaming condition holds for ${f}$ and ${g}$, then

$\displaystyle \mathit{stream}\;g\;f\;b\;x = \mathit{meta}\;g\;f\;b\;x$

for all finite lists ${x}$.

As a simple example, consider the buffering’ process ${\mathit{meta}\;\mathit{uncons}\;(\mathbin{{+}\!\!\!{+}})\;[\,]}$, where

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{uncons}\;x &=& \mathbf{case}\;x\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} [\,] &\rightarrow& \mathit{Nothing} \\ c:x' &\rightarrow& \mathit{Just}\;(c,x') \end{array} \end{array}$

Note that ${\mathit{unfoldr}\;\mathit{uncons} = \mathit{id}}$, so ${\mathit{meta}\;\mathit{uncons}\;(\mathbin{{+}\!\!\!{+}})\;[\,]}$ is just a complicated way of writing ${\mathit{concat}}$ as a ${\mathit{foldl}}$. But the streaming condition holds for ${\mathbin{{+}\!\!\!{+}}}$ and ${\mathit{uncons}}$ (as you may check), so ${\mathit{concat}}$ may be streamed. Operationally, the streaming version of ${\mathit{concat}}$ consumes one list from the input list of lists, then peels off and produces its elements one by one; when they have all been delivered, it consumes the next input list, and so on.

## Flushing

The streaming version of ${\mathit{concat}}$ is actually rather special, because the production steps can always completely exhaust the intermediate state. In contrast, consider the regrouping’ example ${\mathit{regroup}\;n = \mathit{meta}\;(\mathit{chunk}\;n)\;(\mathbin{{+}\!\!\!{+}})\;[\,]}$ where

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{chunk}\;n\;[\,] &=& \mathit{Nothing} \\ \mathit{chunk}\;n\;x &=& \mathit{Just}\;(\mathit{splitAt}\;n\;x) \end{array}$

from the introduction (here, ${\mathit{splitAt}\;n\;x}$ yields ${(y,z)}$ where ${y \mathbin{{+}\!\!\!{+}} z = x}$, with ${\mathit{length}\;y=n}$ when ${n \le \mathit{length}\;x}$ and ${y=x}$ otherwise). This transforms an input list of lists into an output list of lists, where each output chunk’ except perhaps the last has length ${n}$—if the content doesn’t divide up evenly, then the last chunk is short. One might hope to be able to stream ${\mathit{regroup}\;n}$, but it doesn’t quite work with the formulation so far. The problem is that ${\mathit{chunk}}$ is too aggressive, and will produce short chunks when there is still some input to consume. (Indeed, the streaming condition does not hold for ${\mathbin{{+}\!\!\!{+}}}$ and ${\mathit{chunk}\;n}$—why not?) One might try the more cautious producer ${\mathit{chunk'}}$:

$\displaystyle \begin{array}{@{}lclcl@{}} \mathit{chunk'}\;n\;x &\mid& n \le \mathit{length}\;x &=& \mathit{Just}\;(\mathit{splitAt}\;n\;x) \\ &\mid& \mathbf{otherwise} &=& \mathit{Nothing} \end{array}$

But this never produces a short chunk, and so if the content doesn’t divide up evenly then the last few elements will not be extracted from the intermediate state and will be lost.

We need to combine these two producers somehow: the streaming process should behave cautiously while there is still remaining input, which might influence the next output; but it should then switch to a more aggressive strategy once the input is finished, in order to flush out the contents of the intermediate state. To achieve this, we define a more general flushing stream operator:

$\displaystyle \begin{array}{@{}lcl@{}} \multicolumn{3}{@{}l@{}}{\mathit{fstream} :: (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow [\gamma]) \rightarrow (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow [\gamma]} \\ \mathit{fstream}\;g\;h\;f\;b\;x &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{fstream}\;g\;h\;f\;b'\;x \\ \mathit{Nothing} &\rightarrow& \mathbf{case}\;x\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} a:x' &\rightarrow& \mathit{fstream}\;g\;h\;f\;(f\;b\;a)\;x' \\ {[\,]} &\rightarrow& h\;b \end{array} \end{array} \end{array}$

This takes an additional argument ${h :: \beta \rightarrow [\gamma]}$; when the cautious producer ${g}$ is unproductive, and there is no remaining input to consume, it uses ${h}$ to flush out the remaining output elements from the state. Clearly, specializing to ${h\;b=[\,]}$ retrieves the original ${\mathit{stream}}$ operator.

The corresponding metamorphism uses an apomorphism in place of the unfold. Define

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{apo} &::& (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow [\gamma]) \rightarrow \beta \rightarrow [\gamma] \\ \mathit{apo}\;g\;h\;b &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{apo}\;g\;h\;b' \\ \mathit{Nothing} &\rightarrow& h\;b \end{array} \end{array}$

Then ${\mathit{apo}\;g\;h}$ behaves like ${\mathit{unfoldr}\;g}$, except that if and when ${g}$ stops being productive it finishes up by applying ${h}$ to the final state. Similarly, define flushing metamorphisms:

$\displaystyle \mathit{fmeta}\;g\;h\;f\;b = \mathit{apo}\;g\;h \cdot \mathit{foldl}\;f\;b$

Then we have

$\displaystyle \mathit{fstream}\;g\;h\;f\;b\;x = \mathit{fmeta}\;g\;h\;f\;b\;x$

for all finite lists ${x}$ if the streaming condition holds for ${f}$ and ${g}$. In particular,

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{regroup}\;n\;\mathit{xs} &=& \mathit{fmeta}\;(\mathit{chunk'}\;n)\;(\mathit{unfoldr}\;(\mathit{chunk}\;n))\;(\mathbin{{+}\!\!\!{+}})\;[\,]\;\mathit{xs} \\ &=& \mathit{fstream}\;(\mathit{chunk'}\;n)\;(\mathit{unfoldr}\;(\mathit{chunk}\;n))\;(\mathbin{{+}\!\!\!{+}})\;[\,]\;\mathit{xs} \end{array}$

on finite inputs ${\mathit{xs}}$: the streaming condition does hold for ${\mathbin{{+}\!\!\!{+}}}$ and the more cautious ${\mathit{chunk'}\;n}$, and once the input has been exhausted, the process can switch to the more aggressive ${\mathit{chunk}\;n}$.

## Infinite input

The main advantage of streaming is that it can allow the change-of-representation process also to work on infinite inputs. With the plain metamorphism, this is not possible: the ${\mathit{foldl}}$ will yield no result on an infinite input, and so the ${\mathit{unfoldr}}$ will never get started, but the ${\mathit{stream}}$ may be able to produce some outputs before having consumed all the inputs. For example, the streaming version of ${\mathit{regroup}\;n}$ also works for infinite lists, providing that the input does not end with an infinite tail of empty lists. And of course, if the input never runs out, then there is no need ever to switch to the more aggressive flushing phase.

As a more interesting example, consider converting a fraction from base 3 to base 7:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{fromBase3} &=& \mathit{foldr}\;\mathit{stepr}\;0 \quad \mathbf{where}\;\mathit{stepr}\;d\;x = (d+x)/3 \\ \mathit{toBase7} &=& \mathit{unfoldr}\;\mathit{next} \quad \mathbf{where}\; \begin{array}[t]{@{}lcl@{}} \mathit{next}\;0 &=& \mathit{Nothing} \\ \mathit{next}\;x &=& \mathbf{let}\;y=7\times x\;\mathbf{in}\;\mathit{Just}\;(\lfloor y\rfloor, y-\lfloor y\rfloor) \end{array} \end{array}$

We assume that the input digits are all either 0, 1 or 2, so that the number being represented is in the unit interval.

The fold in ${\mathit{fromBase3}}$ is of the wrong kind; but we have also

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{fromBase3} &=& \mathit{extract} \cdot \mathit{foldl}\;\mathit{stepl}\;(0,1) \quad \mathbf{where}\; \mathit{stepl}\;(u,v)\;d = (u \times 3 + d, v / 3) \end{array}$

Here, the intermediate state ${(u,v)}$ can be seen as a defunctionalized representation of the function ${(v\times) \cdot (u+)}$, and ${\mathit{extract}}$ applies this function to ${0}$:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{apply}\;(u,v)\;x &=& v \times (u + x) \\ \mathit{extract}\;(u,v) &=& \mathit{apply}\;(u,v)\;0 \end{array}$

Now there is an extra function ${\mathit{extract}}$ between the ${\mathit{foldl}}$ and the ${\mathit{unfoldr}}$; but that’s no obstacle, because it fuses with the ${\mathit{unfoldr}}$:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{toBase7} \cdot \mathit{extract} &=& \mathit{unfoldr}\;\mathit{next'} \quad \mathbf{where}\; \begin{array}[t]{@{}lcl@{}} \mathit{next'}\;(0,v) &=& \mathit{Nothing} \\ \mathit{next'}\;(u,v) &=& \begin{array}[t]{@{}l} \mathbf{let}\;y = \lfloor{7 \times u \times v}\rfloor\;\mathbf{in} \\ \mathit{Just}\;(y,(u - y/(v \times 7), v \times 7)) \end{array} \end{array} \end{array}$

However, the streaming condition does not hold for ${\mathit{stepl}}$ and ${\mathit{next'}}$. For example,

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{next'}\;(1,{{}^{1\!}/_{\!3}}) &=& \mathit{Just}\;(2, ({{}^{1\!}/_{\!7}},{{}^{7\!}/_{\!3}})) \\ \mathit{next'}\;(\mathit{stepl}\;(1,{{}^{1\!}/_{\!3}})\;1) &=& \mathit{next'}\;(4,{{}^{1\!}/_{\!9}}) \\ &=& \mathit{Just}\;(3,({{}^{1\!}/_{\!7}},{{}^{7\!}/_{\!9}})) \end{array}$

That is, ${0.1_3 \simeq 0.222_7}$, but ${0.11_3 \simeq 0.305_7}$, so it is premature to produce the first digit 2 in base 7 having consumed only the first digit 1 in base 3. The producer ${\mathit{next'}}$ is too aggressive; it should be more cautious while input remains that might invalidate a produced digit.

Fortunately, on the assumption that the input digits are all 0, 1, or 2, the unconsumed input—a tail of the original input—again represents a number in the unit interval; so from the state ${(u,v)}$ the range of possible unproduced outputs represents a number between ${\mathit{apply}\;(u,v)\;0}$ and ${\mathit{apply}\;(u,v)\;1}$. If these both start with the same digit in base 7, then (and only then) is it safe to produce that digit. So we define

$\displaystyle \mathit{next''}\;(u,v) = \mathbf{if}\;\lfloor{u \times v \times 7}\rfloor = \lfloor{(u+1) \times v \times 7}\rfloor\;\mathbf{then}\;\mathit{next'}\;(u,v)\;\mathbf{else}\;\mathit{Nothing}$

and we have

$\displaystyle \mathit{unfoldr}\;\mathit{next'} = \mathit{apo}\;\mathit{next''}\;(\mathit{unfoldr}\;\mathit{next'})$

Now, the streaming condition holds for ${\mathit{stepl}}$ and ${\mathit{next''}}$ (as you may check), and therefore

$\displaystyle \mathit{toBase7}\;(\mathit{fromBase3}\;x) = \mathit{fstream}\;\mathit{next''}\;(\mathit{unfoldr}\;\mathit{next'})\;\mathit{stepl}\;(0,1)\;x$

on finite digit sequences ${x}$ in base 3. Moreover, the streaming program works also on infinite digit sequences, where the original does not.

(Actually, the only way this could possibly produce a finite output in base 7 would be for the input to be all zeroes. Why? If we are happy to rule out this case, we could consider only the case of taking infinite input to infinite output, and not have to worry about reaching the end of the input or flushing the state.)

# Functional Conf

This coming weekend, I will present Haskell SpriteKit — a Purely Functional API for a Stateful Animation System and Physics Engine as well as a workshop on Functional Programming in Swift at Functional Conf in Bangalore.

# Backend Ruby and Haskell engineer at Health eFilings (Full-time)

Our backend engineering team manages the ingestion and normalization of data sets, from data extraction through to product delivery. We want to work smarter instead of harder, and create domain specific languages, meta-programming etc. where possible.

Our current code base is written in Ruby and Coffee Script, but some new modules are being written in Haskell. You will be on the front lines of creating a Haskell-based infrastructure that is maintainable and can scale to support our needs as we grow.

We currently expect that about 80% of your work will be in Ruby/CoffeeScript, and 20% in Haskell, but that ratio will decrease over time as we move more of our functionality to Haskell. (The faster you can work to migrate functionality to Haskell, the more Haskell you will be doing.)

WHAT WE WILL EXPECT FROM YOU

You will have ownership of an entire module, including responsibility for:

• Creating new features in a clean and maintainable way
• Re-factoring existing code to ensure that we stay agile
• Reviewing teammates’ code and providing feedback
• Keeping yourself focused and your projects on track
• An “I can run through walls” mentality to ensure that goals are met
• Answering questions from our implementation team and squashing bugs on a monthly support rotation

We are a small team (four engineers), and so it is critical that you be a team player, willing to pitch in and help out your colleagues.

WHAT YOU CAN EXPECT FROM US

• Autonomy to solve problems in the way you best see fit
• A manager who is accountable for ensuring you meet your professional goals
• A team who helps each other and always strives to improve
• The time to focus on creating the right solution, instead of the easiest one

REQUIREMENTS

• Professional experience as a software engineer
• Experience with Haskell and Ruby
• A desire for continual self-improvement
• An understanding of best practices regarding maintainability and scalability
• Must have US work authorization and be located in the US (we cannot sponsor visas at this time)
• There are no formal education requirements for this position

BONUS POINTS

• Experience with data scraping and parsing

LOCATION

This is expected to be a remote position, although our Madison, Wisconsin office is also available as a work location.

Get information on how to apply for this position.

# Algebraic Data Types in Java

At Helix we often code backend services in java. I find modern java acceptable as a language for getting things done. As a long time haskell developer, however, I find java’s facilities for data types frustrating indeed. These frustrations are twofold. Java lacks support for algebraic data types (ADTs), and requires large amounts of boilerplate to define even simple types.

When designing systems, I place great value in applying the "make illegal states unrepresentable" principle1. Using ADTs to more accurately model data is a excellent step in this direction. However, it’s a burden to do in languages like java that lack support for sum types.

Even for regular product types (ie records of fields) java can be tedious. Defining a record of a few fields should really only take a corresponding few lines of code. Yet for a useful value type in java one will generally need to write: constructors, accessors, a comparison function, a hash implementation, serialisation logic etc. It’s common in the java world to use IDEs to automatically generate this kind of boilerplate, but subtle bugs can creep in over time as the once generated code isn’t manually updated to reflect subsequent changes in the data model.

Hence, at Helix we now often use my ADL language to define data types, and generate the corresponding java code from them. As a tiny example, these adl definitions (see complete file here):

    struct Rectangle
{
Double width;
Double height;
};

union Picture
{
Circle circle;
Rectangle rectangle;
Vector<Picture> composed;
Translated<Picture> translated;
};

result in the corresponding Rectangle.java and Picture.java. These two definitions alone correspond to 280 lines of java code (that you really don’t want to write and maintain). As can be seen in the Translated<> type, parametric polymorphism is supported.

I find that being able to define data types concisely encourages me to build more accurate data models, resulting in systems that are more robust and better reflect the problem domain. And ADL’s multi language support (java, haskell, typescript) allows us to easily serialize and transfer the corresponding data values between our java services, and our typescript web and mobile UIs.

1. attributed to Yaron Minsky

# Scala Developer at LeadIQ (Full-time)

Are you the type of engineer who punches juke boxes to make the music start? Do you consider riding your motorcycle off into the a sunset a personal hobby? Is architecting a system from the ground up no big deal to you? We're looking for full-time Scala developer to make this happen.

The Product

We are on a mission to revolutionize Sales industry using data science. Our product helps our customers to collect and enrich their target prospects. Our internal data processing combines human intelligence and data science to enable our customers to find perfect contact information and save to their existing platforms like Salesforce, etc.

The Challenge

• We are at an exciting stage in our growth. We are getting traction with big customers, scaling out, and solving increasingly complex engineering problems.

• Our systems are mostly written in Scala. We have used Kafka as backbone to communicate between our API server and micro-services. Smart architecture design is crucial in order to guarantee our micro-services based systems run smoothly and reliably.

• We're looking for someone who can drive our product backend integration features, refactor existing code for faster responses and becomes an important asset to the rest of the engineering team.

• Data quality is one of the critical factors to make our product successful. We often have needs to process 3rd parties data and clean existing data using Spark. So you need to be comfortable writing Spark scripts.

• We have very complex integrations with 3rd parties systems like Salesforce, etc. These integrations are core to what we're offering to our customers. We're looking for someone who is willing to listen to customer feedback to improve existing features and provide new features for customer success.

The Stack

Scala, Kafka, Spark, MongoDB, ElasticSearch, Docker, Vue.js

The Team

We want team members with attributes like:

• Focus on delivering value to the customer
• Strong belief in collaboration
• Passion that drives you to execute and innovate
• Ability to self-manage and take ownership of a feature
• Ability to juggle many projects and responsibilities
• Extremely entrepreneurial and self-driven
• Not afraid of a steep learning curve
• Passionate about building a big business that transforms the sales industry
• Exceptional at writing scalable, production-ready code
• Thrive in a fast-paced environment
• Avoid over-engineering
• Simple designs and fast execution
• Discipline in following process and documenting your work

These personality traits define the culture we are building and are more important to us than a particular set of technical skills.

The Responsibilities

If you join LeadIQ, you will learn a lot: In terms of technical ability there are many cool tools, technologies, patterns and other great developers that will sharpen your skills. Personally you be given the chance to step up, lead and make your mark in a growing startup as we tackle the challenges in our next phase of growth.

On the technical front, we need you skilled in:

• Scala (but experience in another functional language helps, e.g. Haskell or Clojure)
• Play framework
• Concurrency (futures, actors, basic understanding of threads)

So if you feel like you're a good fit for us, drop us a line! We love meeting developers who are excited by our product!

Get information on how to apply for this position.

# Future proofing test suites

I'll start with the specific case I've seen pop up a few times recently, and then expand to the general. If you're a package author who has been affected by this, please note: I'm putting this information into a blog post since it's easier to state this once and link to it rather than rewrite an explanation on lots of different bug trackers.

hlint is a great tool for getting advice on improving your Haskell codebase (another great Neil Mitchell product). And as such tools go, hlint has new versions which improve its ability to provide useful advice. This means that, sometimes, code which triggered no hlint warnings previously may suddenly present with such warnings under a new hlint version.

Twice recently in my Stackage curation, I've seen a number of test suites fail, even though the code for those packages was unmodified. It turns out that the upgrade to a new version of hlint caused a previously successful test suite to now fail. Clearly the code isn't suddenly broken because a new version of hlint has been released, but as far as the diagnostics of test suite failures are concerned, that's exactly what happened.

## Recommendation

I do strongly recommend projects use hlint to get code improvements. And I've seen some great results with using it as part of the CI process, such as on Stack. (For the record: it wasn't my idea and I didn't implement it. I was just pleasantly surprised when my PRs failed because I had some style errors.) However, making the test suite for the entire package fail because of a new version of hlint is too much. Therefore:

• DO Have some way to run hlint from your CI process, if you want these warnings to block PRs. There are two approaches I can think of:

• The way Stack does it: have a separate part of the build matrix just for style errors. The cabal file for the project itself knows nothing about hlint.
• Via a test suite in your cabal file which is disabled by default. Then: turn on that test suite with a flag from your CI configuration.
• DON'T Set up your package which is uploaded to Hackage/built by Stackage such that it will fail if a style-based error occurs.

## General recommendation

The general takeaway from this is: when you're building your code on CI, be as strict as you want. Set high standards, block PRs, call master broken, for whatever trivial or non-trivial issues you deem worthy. Turn on -Wall -Werror, respect hlint, error out if someone uses tabs* or includes trailing whitespace. That's all good.

* Cue necessary tabs-vs-spaces argument

However, when you're releasing your code elsewhere, make the tests as lenient as possible on optional features. If the code fails to build: that's a problem. If the code builds, but returns incorrect runtime results: that's a problem. These should stop build systems like Stackage from including your package. But stylistic issues, or newly introduced warnings from the compiler, or myriad other issues, should not trigger a failure for downstream consumers of your package.

# Ghcid with VS Code

Summary: New versions of Ghcid and the VS Code extension work even better together.

I've just released Ghcid v0.6.8 and the associated VS Code extension haskell-ghcid v0.2.0. Together they vastly simplify the Ghcid VS Code experience.

A new feature in Ghcid is that if there is a .ghcid file in the current directory it will load it as additional arguments. For example, in the Shake repo I have a .ghcid file:

-c "ghci -fno-code -ferror-spans"

Which tells ghcid to not guess at the command (e.g. using stack if you have a .stack-work) but always run ghci -fno-code -ferror-spans. This command works because I have a .ghci file which loads all the necessary files, while -fno-code speeds up compilation and -ferror-spans gives better error highlighting.

Ghcid VS Code starts ghcid

A new feature in the VS Code extension is the action Start Ghcid which starts a new ghcid terminal, writes the output to a temporary file, and uses that output to populate the Problems pane. Importantly, the extension runs ghcid with no command line arguments, so having a sensible .ghcid lets you control what it does.

The effect of these changes is that to start ghcid in VS Code is now a few key strokes, whereas before it required special flags, opening files, running commands etc.

# Nix on the <br/> Windows Subsystem for Linux

Jonas Chevalier

Nix on Windows: does it run yet? That's the question I wondered about while testing the latest NixOS release, version 17.09. To that end, I had the idea of running the Nix installation process from inside the Windows Subsystem for Linux (WSL) see if it worked. And it worked! Success!

So what does this mean?

You might remember that the Windows NT kernel used to have a POSIX layer. Unfortunately, The POSIX layer always had compatibility issues with BSD and Linux software, because typical applications seldom fit completely and entirely within the confines of an age old API. Nevertheless, the NT kernel was designed from the start to support different subsystems, not just Win32, and the POSIX layer of old was a step in the right direction. The WSL is a revival of that idea but with a specific focus on the Linux ABI. It means that it is now possible to run Linux software natively on Windows. Think of it as reverse Wine. Linux software can execute Windows software and vice versa.

It's not perfect yet. I/O and symlink resolution seem to be slow and not all Linux syscalls have been implemented yet. This is more about the promised land that Microsoft is showing. WSL is not available on the server edition yet, but it looks like they are going to deliver on it.

At Tweag.io we often use Nix to declaratively specify reproducible build environments for our projects and those of our clients. Nix is a good fit for project that mix different languages. It works really well at providing reproducible builds and compose the various parts of the project with external dependencies. Unfortunately it is also not supported on Windows so we have to decide upfront whether to use it based in part on whether Windows is going to become a target platform or not. Thanks to WSL it looks like we will have an escape hatch, at least for non graphical applications.

Another potential use-case that I see is for Haskell development. Today, a lot of good software is being developed directly on top of Linux and macOS. For some of these projects Windows is not a prime target environment anymore. The Glasgow Haskell Compiler (GHC) is actually quite well behaved on Windows when compiling pure Haskell code. But as soon as C library dependencies are involved, the story gets a lot more complicated. In that case, deploying via WSL might just be easier than aiming for a native Windows port.

## How to install

Enable and install WSL following these instructions: https://msdn.microsoft.com/en-us/commandline/wsl/install_guide.

Make sure to have the latest version of Windows 10 installed. I had this version at the time of install:

• Windows Edition: Windows 10 Pro
• Windows Version: 1703
• Windows OS Build: 15063.540
• System Type: 64-bit operating system

Start the “Bash On Ubuntu On Windows” program and type curl https://nixos.org/nix/install | sh.

## Known issues

WSL is an experimental subsystem still. At this point in time, there are still important issues to know about. Here are the workarounds I came up with:

• curl is hanging. Hit Ctrl+C and retry.
• Nix installation crash. Older versions of WSL didn't support all the syscalls needed by Nix. Update Windows and try again.
• nix-shell is broken. Fails with synchronous I/O disk error https://github.com/NixOS/nix/issues/1203. Here's a workaraund: edit /etc/nix/nix.conf and add use-sqlite-wal=false
• It’s slow. Yes, especially I/O and symlinks seem to be quite slow. The only solution here is to wait for Microsoft to optimise their syscalls.
• Nix environment is not started in new logins. Workaround: Run source ~/.profile

## Conclusion

For now, it's just a technology preview that opens new possibilities. Hopefully in the future, when the performance of I/O operations improves, it will also be enjoyable to develop Linux programs under WSL directly. Meanwhile, Microsoft has put out useful resources to go further with WSL:

## November 05, 2017

### Douglas M. Auclair (geophf)

• October 20th, 2017:
You have a list of numbers: [1,2,3,4]
You have a list of the same length of number fns: [succ, id, id, succ]
You want: [2,2,3,5]
•  🇪🇺 Cλément D  🌈  🐇 @clementd zipWith (flip ($)) ? • he adds: zipWith (flip id) is a bit shorter tho • Simon Courtenage @SCourtenage zipWith ($) [succ,id,id,succ] [1,2,3,4]
• lukasz @lukaszklekot getZipList $ZipList [succ, id, id, succ] <*> ZipList [1, 2, 3, 4] • Alexey Radkov @sheshanaag (map (uncurry ($)) .) . zip
• October 5th, 2017: "reverse the sequencing"
You have [[(1,2),(1,3),(1,7)],[(9,2)],[(11,3)]]
You want [(1,[2,3,7]),(9,[2]),(11,[3])]
• bazzargh @bazzargh map ((,) <$> head.(map fst) <*> (map snd)) • bazzargh @bazzargh map ((first head).unzip) • Chris Martin @chris__martin \x -> [(a, b : fmap snd xs) | Just ((a, b) :| xs) <- fmap="" li="" nonempty="" x=""> • Simon Courtenage @SCourtenage fmap (\x -> (fst . head$ x, fmap snd x))
• Denis Stoyanov  🐜 @xgrommx Your solution nice) but u can do it with point free style like
• Denis Stoyanov  🐜 @xgrommx My solution is ugly, but I wanna to solve it with traverse)
• fmap(first head . traverse (first (:[])))
• Andreas Källberg @Anka213 map$fst.head&&&map snd • Scott Fleischma‏ @scottfleischman traverse$ _1
(\case
[y] -> Just y
_ -> Nothing
. nub
)
. unzip
:: [[(Int, Int)]] -> Maybe [(Int, [Int])]
• Scott Fleischman @scottfleischman
let
•  sing [] = Left "Too few"
sing [x] = Right x
sing (_ : _) = Left "Too many"
valid = sing . nub
go = _1 valid . unzip
in traverse go
• matt @themattchan map ((head *** id ) . unzip)
• October 3rd, 2017:
you have [(1,[2,3,4]),(10,[5,6,7])]
you want [(1,2),(1,3),(1,4),(10,5),(10,6),(10,7)]

or, generally: [(a,[b])] -> [(a,b)]

Go!

• bazzargh @bazzargh (uncurry (zip . repeat) =<<)
• Denis Stoyanov  🐜 @xgrommx fmap (uncurry (liftA2(,) . (:[])))
• Darren G @Kludgy I like that this doesn't unnecessarily implicate the sequentiality of bind.
• Darren G @Kludgy Funny this same product came up at work last week.
concatMap $\(a,bs) -> fmap (\b -> (a,b)) bs ## November 04, 2017 ### Neil Mitchell # Understanding HLint rules Summary: I added a degenerate foldr to map rule in the new version of HLint, here I describe how it works. I've just released HLint 2.0.10, which includes a rule to recognise uses of foldr that should really be map. As an example: foldr (\curr acc -> (+1) curr : acc) [] Can be rewritten as: map (\curr -> (+1) curr) Which is much more readable (and then subsequently HLint will suggest map (+1), which is vastly clearer than the initial foldr). The change required to HLint was to add a rule to the hlint.yaml saying: - warn: {lhs: "foldr (\\c a -> x : a) []", rhs: "map (\\c -> x)"} You can read this statement as saying if you see foldr (\c a -> x : a) [], suggest map (\c -> x) as a warning. The HLint matching engine then applies that template to every subexpression in your program. In the rest of the post I'll talk through the steps HLint performs. Step 1: Unification The first step is to try unifying the template foldr (\c a -> x : a) [] against the users subexpression, namely foldr (\curr acc -> (+1) curr : acc) []. HLint is trying to find assignments for the single-letter variables in the template (namely c, a and x) which cause it to match the subexpression. Unification proceeds top-down, and if it finds anything concrete that does not match (e.g. the user had written foldl) then it fails. In this case the unification succeeds with the bindings: • c = curr (from the first argument to the lambda) • a = acc (from the second argument to the lambda) • x = (+1) curr (from before the cons) • a = acc (from after the cons) An example of a subexpression that would have failed unification is foldl (\curr acc -> (+1) curr : acc) []. Step 2: Validity The next step is to check that any value which has been bound more than once is equal in all bindings. In our case only a has been used twice, and it always binds to acc, so the unification is valid. An example of a subexpression that would have failed validity is foldr (\curr acc -> (+1) curr : xs) []. Step 3: Substitution Now we've got some bindings, we can substitute them into the RHS, namely map (\c -> x). We replace c and x using the bindings above. Note that a isn't mentioned on the RHS, so we don't use it. After substitution we get: map (\curr -> (+1) curr) Step 4: Free variable check Consider the expression foldr (\curr acc -> f acc : acc) []. Using the rules above we'd end up with map (\curr -> f acc), which is terrible, since we've gone from referring to a locally bound acc to whatever acc is in scope (if any). To solve that, we check that the result doesn't introduce any new free variables: (freeVars result \\ freeVars hintRuleRHS) isSubsetOf freeVars original Specifically any free variables introduced in the result, which weren't in the RHS (excluding the fake unification variables), must have been in the original subexpression. With that, for foldr, we're done. There are a handful of other steps that apply in some cases. Step A: Dot expansion in the template If you write a hint map f (map g x) ==> map (f . g) x then HLint notices that also implies the rule map f . map g ==> map (f . g) and adds it. As a result, you shouldn't write your HLint rules in point-free style. Step B: Dot/dollar expansion in the subexpression When matching a subexpression HLint will expand f$ x and (f . g) x if doing so results in a match. These operators are used commonly enough that they are often treated more like brackets than functions.

Step C: Scope matching

When unifying qualified function names, HLint uses the active imports to guess whether they match. If you have import qualified Data.Vector as V then the subexpression V.length will unify with Data.Vector.length. Since HLint doesn't have complete import information it uses a few heuristics to figure out matching.

Step D: Scope moving

Similarly to scope matching on the LHS of a rule, after matching, HLint tries to requalify any necessary values on the RHS. As an example, assuming we are producing Data.Vector.null, if we know about import qualified Data.Vector as V then we suggest V.null.

Full code

To see the full code and all supporting definitions go to the HLint source, which defines matchIdea - here I show a gently simplified version. Given scope information, a rule (LHS and RHS) and a subexpression, we optionally produce a resulting expression after substitution.

matchIdea :: Scope -> HintRule -> Exp_ -> Maybe Exp_matchIdea s HintRule{..} original = do    u <- unifyExp hintRuleLHS original    u <- validSubst u    -- need to check free vars before unqualification, but after subst (with e)    -- need to unqualify before substitution (with res)    let result = substitute u hintRuleRHS    guard (freeVars result Set.\\ Set.filter (not . isUnifyVar) (freeVars hintRuleRHS)) Set.isSubsetOf freeVars original -- check no unexpected new free variables return result ### Gabriel Gonzalez # Semantic integrity checks are the next generation of semantic versioning <html xmlns="http://www.w3.org/1999/xhtml"><head> <meta content="text/html; charset=utf-8" http-equiv="Content-Type"/> <meta content="text/css" http-equiv="Content-Style-Type"/> <meta content="pandoc" name="generator"/> <style type="text/css">code{white-space: pre;}</style> <style type="text/css">div.sourceCode { overflow-x: auto; } table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode { margin: 0; padding: 0; vertical-align: baseline; border: none; } table.sourceCode { width: 100%; line-height: 100%; } td.lineNumbers { text-align: right; padding-right: 4px; padding-left: 4px; color: #aaaaaa; border-right: 1px solid #aaaaaa; } td.sourceCode { padding-left: 5px; } code > span.kw { color: #007020; font-weight: bold; } /* Keyword */ code > span.dt { color: #902000; } /* DataType */ code > span.dv { color: #40a070; } /* DecVal */ code > span.bn { color: #40a070; } /* BaseN */ code > span.fl { color: #40a070; } /* Float */ code > span.ch { color: #4070a0; } /* Char */ code > span.st { color: #4070a0; } /* String */ code > span.co { color: #60a0b0; font-style: italic; } /* Comment */ code > span.ot { color: #007020; } /* Other */ code > span.al { color: #ff0000; font-weight: bold; } /* Alert */ code > span.fu { color: #06287e; } /* Function */ code > span.er { color: #ff0000; font-weight: bold; } /* Error */ code > span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */ code > span.cn { color: #880000; } /* Constant */ code > span.sc { color: #4070a0; } /* SpecialChar */ code > span.vs { color: #4070a0; } /* VerbatimString */ code > span.ss { color: #bb6688; } /* SpecialString */ code > span.im { } /* Import */ code > span.va { color: #19177c; } /* Variable */ code > span.cf { color: #007020; font-weight: bold; } /* ControlFlow */ code > span.op { color: #666666; } /* Operator */ code > span.bu { } /* BuiltIn */ code > span.ex { } /* Extension */ code > span.pp { color: #bc7a00; } /* Preprocessor */ code > span.at { color: #7d9029; } /* Attribute */ code > span.do { color: #ba2121; font-style: italic; } /* Documentation */ code > span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */ code > span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */ code > span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */ </style></head><body> The Dhall configuration language just added support for "semantic integrity checks". This post explains what "semantic integrity check" means, motivates the new feature, and compares to semantic versioning. ## The problem I added this feature in response to user concerns about code injection in Dhall configuration files. We'll illustrate the problem using the following example.dhall configuration file which derives a summary of student information from a list of students:  -- Example of an expression imported by URL let map = http://prelude.dhall-lang.org/List/map -- Example of an expression imported by pathin let students = ./students.dhallin let getName = λ(student : { name : Text, age : Natural }) → student.namein { classSize = List/length { name : Text, age : Natural } students , names = map { name : Text, age : Natural } Text getName students } This configuration imports a helper function named map from the Dhall Prelude by URL:  let map = http://prelude.dhall-lang.org/List/mapin ... ... and that URL currently hosts a text file encoding the following Dhall function:  curl -L http://prelude.dhall-lang.org/List/map{-Tranform a list by applying a function to each elementExamples:./map Natural Bool Natural/even ([+2, +3, +5] : List Natural)= [True, False, False] : List Bool./map Natural Bool Natural/even ([] : List Natural)= [] : List Bool-}let map : ∀(a : Type) → ∀(b : Type) → (a → b) → List a → List b    =   λ(a : Type)    →   λ(b : Type)    →   λ(f : a → b)    →   λ(xs : List a)    →   List/build        b        (   λ(list : Type)        →   λ(cons : b → list → list)        →   List/fold a xs list (λ(x : a) → cons (f x))        )in  map

Similarly, our example configuration imports student data from another configuration file by path:

...in  let students = ./students.dhall...

... and we'll assume that file contains the following list of student records:

[ { name = "Jane Doe"    , age = +19 }, { name = "John Rivera" , age = +18 }, { name = "Alice O'Hare", age = +19 }]

Values, functions, and types are all Dhall expressions, so we can inject all of them in our code via URLs or paths. When we interpret a Dhall configuration file these imports get substituted with their contents and then we evaluate the fully resolved configuration file as an expression in a functional language:

$dhall <<< './example.dhall' | dhall-format{ classSize : Natural, names : List Text }{ classSize = +3, names = [ "Jane Doe", "John Rivera", "Alice O'Hare" ] : List Text} Users were concerned that these imports could be compromised, resulting in malicious code injection ## The solution The latest release of Dhall added support for import integrity checks to address user concerns about malicious tampering. We can use these integrity checks to "freeze" our imports by adding a SHA-256 hash after each import. First, we ask the dhall-hash utility to compute the current hash for our imports: $ dhall-hash <<< 'http://prelude.dhall-lang.org/List/map'sha256:3063e9b34fd4235165a7a46e3ee3e0d0d7cded5da16f5572cc9e459ed5452fbb$dhall-hash <<< './students.dhall' sha256:6c4205ed51c0201abcccd1d90be4d7cd4c492246176ab404c35886a03d9dfc06 ... and then we append the hash after each import to freeze the import:  let map = http://prelude.dhall-lang.org/List/map sha256:3063e9b34fd4235165a7a46e3ee3e0d0d7cded5da16f5572cc9e459ed5452fbbin let students = ./students.dhall sha256:6c4205ed51c0201abcccd1d90be4d7cd4c492246176ab404c35886a03d9dfc06in let getName = λ(student : { name : Text, age : Natural }) → student.namein { classSize = length { name : Text, age : Natural } students , names = map { name : Text, age : Natural } Text getName students }  Once you add these integrity checks the Dhall interpreter will enforce them when resolving imports. In this case, the example configuration still successfully evaluates to the same result after adding the integrity checks: $ dhall <<< './example.dhall'  | dhall-format{ classSize : Natural, names : List Text }{ classSize = +3, names     = [ "Jane Doe", "John Rivera", "Alice O'Hare" ] : List Text}

The integrity check passes because we haven't yet modified any of our imports.

## Semantic integrity

Once you freeze an import with a hash, Dhall guarantees that the meaning of the import never changes. These are semantic hashes, not textual hashes.

For example, suppose that we modify ./students.dhall to add a comment, reorder record fields, and modify the formatting, like this:

-- Class of 2017[ { age = +19, name = "Jane Doe" },  { name = "John Rivera" , age = +18 },  { name = "Alice O'Hare", age = +19 } ]

These changes do not affect the computed hash of the file and the interpreter still accepts the ./students.dhall import that we protected with an integrity check:

$dhall <<< './example.dhall' | dhall-format # Still succeeds{ classSize : Natural, names : List Text }{ classSize = +3, names = [ "Jane Doe", "John Rivera", "Alice O'Hare" ] : List Text} The Dhall interpreter accepted the import of ./students.dhall because the semantic hash never changed: $ dhall-hash <<< './students.dhall' sha256:6c4205ed51c0201abcccd1d90be4d7cd4c492246176ab404c35886a03d9dfc06

However, now suppose we try to change the substance of the file by modifying John's age:

-- Class of 2017[ { age = +19, name = "Jane Doe" },  { name = "John Rivera" , age = +20 },  { name = "Alice O'Hare", age = +19 } ]

Now the semantic integrity check fails:

$dhall <<< './example.dhall'Error: Import integrity check failedExpected hash:↳ 6c4205ed51c0201abcccd1d90be4d7cd4c492246176ab404c35886a03d9dfc06Actual hash:↳ 808d921914de5349f50ac656bed93c2894dfe35401991e1ca0c89861834023fb Dhall recognizes that this is no longer the same expression and rejects the import. Only an import that represents the same value can pass the check. This means, for example, that malicious users cannot tamper with our imports, even if we were to distribute the imported code over an insecure channel. The worst that an attacker can do is cause our configuration to reject the import, but they cannot trick the configuration into silently accepting the wrong expression. ## Refactoring We can use these integrity checks to do more than just secure code. We can also repurpose these checks to assert that our code refactors are safe and behavior-preserving. For example, suppose that we change the student list to: -- Class of 2017 let double = λ(x : Natural) → x * +2in [ { name = "Jane Doe" , age = +19 } , { name = "John Rivera" , age = double +9 } , { name = "Alice O'Hare", age = +19 } ] This will still pass the integrity check because the student list still evaluates to the same expected result. We can also refactor our project layout, too. For example, we could modify the student list to import the double function from another file: -- Class of 2017[ { name = "Jane Doe" , age = +19 }, { name = "John Rivera" , age = ./double.dhall +9 }, { name = "Alice O'Hare", age = +19 }] ... where ./double.dhall has the following contents: λ(x : Natural) → x * +2 ... and the integrity check would still pass. I originally introduced semantic integrity checks to protect against malicious code modification then later realized that they can also be used to protect against non-malicious modifications (such as a refactor gone wrong). # Textual hashes The semantic hash provides a more information than a textual hash of the import. For example, suppose we changed our ./double.dhall function to triple the argument: λ(x : Natural) → x * +3 A textual hash of the ./students.dhall import would not detect this change because the real change took place in the text of another file that ./students.dhall imported. However, A semantic hash can follow these imports to detect transitive changes to dependencies. The semantic hash is also more flexible than a textual hash because the semantic hash does not change when we make cosmetic changes like refactoring, reformatting, or commenting code. ## Caveats Dhall's semantic versioning can reject some behavior-preserving changes to functions. Dhall only attempts to detect if two functions are β-equivalent (i.e. the same if fully β-reduced). For example, the following two functions are equivalent, but will not produce the same hash: λ(x : Bool) → x λ(x : Bool) → if x then True else False Similarly, Dhall's semantic hash cannot detect that these two functions are the same: λ(x : Natural) → x * +2 λ(x : Natural) → x + x On the other hand, Dhall will (almost) never give two semantically distinct expressions the same hash. Only an astronomically improbable hash collision can cause this and at the time of this writing there is no known vulnerability in the SHA-256 hash algorithm. Dhall will support other hash algorithms should SHA-256 ever be broken. This is why Dhall prefixes the hash with the algorithm to leave the door open for new hash algorithms. ## Semantic versioning You might wonder how semantic integrity checks compare to semantic versioning. I like to think of semantic integrity checks and semantic versions as two special cases of the following abstract interface: • a package publishes a version string for each official release • you can compare two version strings to detect a breaking change to the package Semantic versioning is one special case of that abstract interface where: • the version string has a major number and minor number • a difference in major version numbers signals a breaking change Some variations on semantic versioning propose independently versioning each exported function/value/type instead of versioning the package as a whole. Also, some languages (like Elm) mechanically enforce semantic versioning by detecting API changes programmatically and forcing a major version bump if there is a breaking change. A semantic integrity check is another special case of that abstract interface where: • the version string is a SHA-256 hash • if two hashes are different then that signals a breaking change The key difference between semantic versioning and semantic integrity checks is how we define "a breaking change". Semantic version numbers (usually) treat changes to types as breaking changes whereas semantic integrity checks treat changes to values as breaking changes. (To be totally pedantic: semantic integrity checks treat changes to expressions as breaking changes, and in a language like Dhall everything is an expression, including types). This does not imply that semantic integrity checks are better than semantic version numbers. Sometimes you want to automatically pick up small changes or improvements from your dependencies without adjusting a hash. In cases like those you want the expected type to be the contract with your dependency and you don't want to pin the exact value. For example, we could "simulate" semantic versioning in Dhall by attaching a type annotation to our ./students.dhall import like this:  let map = http://prelude.dhall-lang.org/List/map sha256:3063e9b34fd4235165a7a46e3ee3e0d0d7cded5da16f5572cc9e459ed5452fbbin let students = ./students.dhall : List { name : Text, age : Natural }in let getName = λ(student : { name : Text, age : Natural }) → student.namein { classSize = List/length { name : Text, age : Natural } students , names = map { name : Text, age : Natural } Text getName students }  ... and now we can add or remove students from our imported list without breaking anything. We've used the type system as a coarser integrity check to state that certain changes to our configuration file's meaning are okay. ## Conclusion You can think of a semantic integrity check as a "value annotation" (i.e. the term-level equivalent of a type annotation). Instead of declaring an expected type we declare an expected value summarized as a hash. This is why the title of this post declares that "semantic integrity checks are the next generation of semantic versioning". If you think of a semantic version as a concise summary of an imported package's type, then a semantic integrity check is a concise summary of an imported package's value. </body></html> ### Keegan McAllister # On depression, privilege, and online activism Update (November 2017): I'm leaving this up as a snapshot of how I felt at the time. Since then a lot has changed in my life, I'm much less angry in general and I no longer give a shit what the toxic assholes think of me, which is pretty great! [Content warning: depression, privilege, online activism] This isn't a general account of my experiences with depression. Many people have written about that, and I don't have much to add. But there's one aspect that I don't hear about very often. It's something that bothers me a lot, and others have told me that it bothers them too. The thing is, I'm not just a person with a mental illness. I'm also a well-off white guy, and I enjoy a whole set of unearned privileges from that. Every day people around the world are harassed, abused, and killed over things I never have to worry about. Even in mundane daily life, most everyone is playing on a higher difficulty setting than I ever will. I've thought about this a lot over the past few years, and I'm trying to understand how I can help make the world more fair and less oppressive. So I give money and I volunteer a little and I speak up when it seems useful, but mostly I listen. I listen to the experiences of people who are different from me. I try to get some understanding of how they feel and why. How is this related to depression? Because the reality of privilege and oppression is fucking depressing. Of course it's depressing to those who are directly harmed. That's a lot of what I read about, and some of the despair transfers to me. But my profiting from the suffering of others in a way that I mostly can't change is also depressing, at least if I make an attempt not to ignore it. And my distress over my role in systems of oppression brings its own layer of guilt. People are actually suffering and I feel sorry for myself because I'm dimly aware of it? But this comes from the voice that has always taunted me about depression. “How can you be sad? Your life is great. If you had real problems you wouldn't be so pathetic. You're not really sick. You're just a whiner.” All of which is part of the disease. I need to own it and work on it every day. But it seems like every time I read an online discussion about social justice, I take a huge step backwards. It's hard to shrug off the “men are horrible” comments when I spend so much effort trying to convince myself that I'm not horrible. When I hear people gloating about delicious white male tears, I think about all the times when I would come home from work and collapse in bed crying. Is this what they want my life to be? I can't give myself permission to tune out, because the same people lecture constantly about my obligation to be a good ally, which mostly takes the form of “shut up and listen.” And then when I'm upset by the things they say, the response is “This isn't for you! Why are you listening?” A local group, one that had recently invited me to hang out as a guest, retweeted a member's declaration to would-be allies: “We're not friends. Fuck you.” Can you see why it feels like they're trying to hurt me? Let me be clear: I truly don't care if people in a room somewhere are talking about how men are the worst. I don't feel oppressed by it, and I have no desire to argue with it. But I can't handle direct exposure. And don't tell me that I'm too stupid to understand why they say these things. I know intellectually that it's not about me. I understand the need to vent and the importance of building solidarity. None of that matters on the emotional level where these comments register like a punch to the gut. I do feel this way, even if I shouldn't and I wish I didn't. I'm talking about mental health, triggers, and unintentionally hurtful speech. Does that sound familiar? One reason I was drawn to intersectional feminism is that it seemed to have a good set of ground rules for how to treat everyone decently. But now I feel like I'm excluded from protection. “Men are horrible” is apparently the one form of speech where intent is all that matters, and I'm a bad person if it triggers something. I've been told it's offensive that I would even try to describe my experience in those terms. It hurts a whole lot to try and really feel someone's pain, and then realize they don't even slightly give a shit about me. It hurts even more when they'll bend over backwards for anyone except me. Look, I get it. You argue all the time with trolls who claim that men have it just as bad as women and will shout “what about the men” as a way to disrupt any discussion. When you're engaged in meme warfare, you can't show them any human empathy. They certainly wouldn't return the favor. And if my voice sounds a little like theirs, that's just too bad for me. I know that this article will serve as ammunition for some people with views I find disgusting. That sucks, but I'm done using political strategy as a reason to stay silent. I understand tone policing as a derailing tactic, and I understand the need to call it out. But at this point it seems there's no room for a sincere request for kindness, especially coming from someone who doesn't get much benefit of the doubt. (The Geek Feminism Wiki basically says that asking for kindness is tone policing if and only if you're a man.) I'm not trying to silence anyone here. I'm not jumping in and derailing an existing conversation. I'm writing on my own blog, on my own schedule, about my own feelings. But I'm told that even this is crossing a line. I know that I can't dictate how others feel about our fucked-up world. Does that mean I must absolutely suppress the way I feel? Even when we agree about the substance of what's wrong? I know that if I ask someone to share their life experiences, they have a right to express anger. When does expressing anger become sustained, deliberate cruelty? “People are being oppressed and you're asking us to care about your feelings?” Yes, I am asking you to care. Just a little bit. I don't claim that my feelings should be a top priority. I hope it wouldn't come up very often. But according to the outspoken few who set the tone, I'm never allowed to bring it up. I don't deserve to ask them to be nice. And that's why I can no longer have anything to do with this movement. It's really that simple. I guess it says something about my state of mind that I felt the need to attach 1,700 words of preemptive defenses. The truth is, when I'm not allowed to say or even think “not all men,” part of me hears “Yes, all men, especially you.” And if I'm ever confused about whether I'm allowed to say “not all men,” there are a dozen unprompted reminders every day. Little jokes, repeated constantly to set the climate about what will and won't be tolerated. When you treat me like one of the trolls, I start to believe that I am one. Guys who say “I support feminism but sometimes they go too far” are usually trying to excuse sexist behavior. So what do I conclude about myself when I have the same thought? I get that “ally” is not a label you self-apply, it's a thing you do, and the label comes from others. The problem is, if a hundred people say I'm a good ally, and one person says I'm a sexist asshole, who do you think I'm going to believe? I'm not allowed to stand up for myself, because doing so is automatically an act of oppression. If a woman treats me like shit, and she's being “more feminist” than me, I conclude that I deserve to be treated like shit. That is the model I've learned of a good ally. I'm not a good ally, or even a bad one. I'm collateral damage. If the point of all this is to give me a tiny little taste of the invalidation that others experience on a regular basis, then congratulations, it worked. You've made your point. Now that you've broken me, how can I possibly help you, when it seems like I'm part of the problem just by existing? It feels like all I can do is engage in emotional self-harm to repay the debt of how I was born. I can't just take a break “until I feel better.” My depressive symptoms will always come and go, and some thoughts will reliably bring them back. I spent years reading about how the most important thing I can do, as a winner of the birth lottery, is to be an ally to marginalized people. And now I've realized that I'm too sick and weak to do it. Even if I give up on being an ally, I can't avoid this subject. It affects a lot of my friends, and I feel even worse when I ask them not to talk about it around me. I don't want to silence anyone. At least I've mostly stopped using Twitter. So this is how I feel, but I'm not sure anyone else can do anything about it. Really, most of the people I've talked to have been sympathetic. Maybe I need to learn not to let bullies get to me, even when they're bullying in service of a cause I support. They don't seem to get much pushback from the wider community, at any rate. What gives me hope is, I recognize that my participation in the endless shouting online wasn't really useful to anyone. If I can let myself ignore all that, maybe I can recover some of my energy for other activities that actually help people. That's all I have to say right now. Thank you for listening to me. ## November 03, 2017 ### Brent Yorgey # Sum of heights in a binary tree Executive summary: every year when teaching data structures I always forget how to analyze the cost of building a binary heap, which amounts to summing the heights of all the nodes in a full binary tree. So I’m writing down the (lovely) proof here in the hopes that I will remember it next time. Suppose you have a full binary tree and you do an operation on every node, where the cost of the operation is proportional to the height of that node. That is, the cost for each of the $n/2$ leaves is $0$, for each of the $n/4$ nodes in the next level up the cost is $1$, and so on. We can visualize the scenario like this: As a function of the total number of nodes $n$, how expensive is this? We can see that $O(n \lg n)$ is an upper bound, since there are $n$ nodes and the height of each node is at most $\lg n$. But it seems like it might actually be faster than this in reality, since, intuitively, most of the nodes have a height which is much smaller than $\lg n$. (One specific motivation for this scenario is that we can build a binary heap from an arbitrary set of data by looping over the nodes from the bottom up and calling reheapDown on each; in the worst case reheapDown takes time proportional to the height of the node, as in this scenario. But it doesn’t matter if you don’t know about binary heaps.) Let’s take the same tree and put a dollar at every node, for a total of $\n$: Now imagine sliding all the money as far up and to the right as it will go. That is, we take each dollar, and keep moving it up as long as it is a left child. As soon as we reach a node which is a right child we stop. The tree ends up looking like this: Now take each pile of money and move it up one step to its parent, except the money at the root of the tree, which you can put in your pocket. And voilà! We now have exactly enough money at each node to pay for the cost of the operations, and we even have a bit left over (which we can use to buy coffee). But we started with $\n$ and only shuffled money around; this shows that the total cost is actually $O(n)$. Exercise for the reader: what does this have to do with the number of bit flips needed to count from $1$ to $n$ with a binary counter? ## November 02, 2017 ### Robert Harper # PFPL Commentary I am building a web page devoted to the 2nd edition of Practical Foundations for Programming Languages, recently published by Cambridge University Press. Besides an errata, the web site features a commentary on the text explaining major design decisions and suggesting alternatives. I also plan to include additional exercises and to make sample solutions available to faculty teaching from the book. The purpose of the commentary is to provide the “back story” for the development, which is often only hinted at, or is written between the lines, in PFPL itself. To emphasize enduring principles over passing fads, I have refrained from discussing particular languages in the book. But this makes it difficult for many readers to see the relevance. One purpose of the commentary is to clarify these connections by explaining why I said what I said. As a starting point, I explain why I ignore the familiar concept of a “paradigm” in my account of languages. The idea seems to have been inspired by Kuhn’s (in)famous book The Structure of Scientific Revolutions, and was perhaps a useful device at one time. But by now the idea of a paradigm is just too vague to be useful, and there are many better ways to explain and systematize language structure. And so I have avoided it. I plan for the commentary to be a living document that I will revise and expand as the need arises. I hope for it to provide some useful background for readers in general, and teachers in particular. I wish for the standard undergraduate PL course to evolve from a superficial taxonomy of the weird animals in the language zoo to a systematic study of the general theory of computation. Perhaps PFPL can contribute to effecting that change. Update: As I had hoped, I have been making many new additions to the commentary, exposing alternatives, explaining decisions, and expanding on topics in PFPL. There are also a few errors noted in the errata; so far, nothing major has come up. (The sections on safety are safely sound.) Filed under: Research, Teaching # It Is What It Is (And Nothing Else) A recent discussion of introductory computer science education led to the topic of teaching recursion. I was surprised to learn that students are being taught that recursion requires understanding something called a “stack” that is nowhere in evidence in their code. Few, if any, students master the concept, which is usually “covered” only briefly. Worst, they are encouraged to believe that recursion is a mysterious bit of esoterica that is best ignored. And thus is lost one of the most important and beautiful concepts in computing. The discussion then moved on to the implementation of recursion in certain inexplicably popular languages for teaching programming. As it turns out, the compilers mis-implement recursion, causing unwarranted space usage in common cases. Recursion is dismissed as problematic and unimportant, and the compiler error is elevated to a “design principle” — to be serpentine is to do it wrong. And thus is lost one of the most important and beautiful concepts in computing. And yet, for all the stack-based resistance to the concept, recursion has nothing to do with a stack. Teaching recursion does not need any mumbo-jumbo about “stacks”. Implementing recursion does not require a “stack”. The idea that the two concepts are related is simply mistaken. What, then, is recursion? It is nothing more than self-reference, the ability to name a computation for use within the computation itself. Recursion is what it is, and nothing more. No stacks, no tail calls, no proper or improper forms, no optimizations, just self-reference pure and simple. Recursion is not tied to “procedures” or “functions” or “methods”; one can have self-referential values of all types. Somehow these very simple facts, which date back to the early 1930’s, have been replaced by damaging myths that impede teaching and using recursion in programs. It is both a conceptual and a practical loss. For example, the most effective methods for expressing parallelism in programs rely heavily on recursive self-reference; much would be lost without it. And the allegation that “real programmers don’t use recursion” is beyond absurd: the very concept of a digital computer is grounded in recursive self-reference (the cross-connection of gates to form a latch). (Which, needless to say, does not involve a stack.) Not only do real programmers use recursion, there could not even be programmers were it not for recursion. I have no explanation for why this terrible misconception persists. But I do know that when it comes to programming languages, attitude trumps reality every time. Facts? We don’t need no stinking facts around here, amigo. You must be some kind of mathematician. If all the textbooks are wrong, what is right? How should one explain recursion? It’s simple. If you want to refer to yourself, you need to give yourself a name. “I” will do, but so will any other name, by the miracle of α-conversion. A computation is given a name using a fixed point (not fixpoint, dammit) operator: fix x is e stands for the expression e named x for use within e. Using it, the textbook example of the factorial function is written thus: fix f is fun n : nat in case n {zero => 1 | succ(n') => n * f n'}. Let us call this whole expression fact, for convenience. If we wish to evaluate it, perhaps because we wish to apply it to an argument, its value is fun n : nat in case n {zero => 1 | succ(n') => n * fact n'}. The recursion has been unrolled one step ahead of execution. If we reach fact again, as we will for a positive argument, fact is evaluated again, in the same way, and the computation continues. There are no stacks involved in this explanation. Nor is there a stack involved in the implementation of fixed points. It is only necessary to make sure that the named computation does indeed name itself. This can be achieved by a number of means, including circular data structures (non-well-founded abstract syntax), but the most elegant method is by self-application. Simply arrange that a self-referential computation has an implicit argument with which it refers to itself. Any use of the computation unrolls the self-reference, ensuring that the invariant is maintained. No storage allocation is required. Consequently, a self-referential functions such as fix f is fun (n : nat, m:nat) in case n {zero => m | succ(n') => f (n',n*m)} execute without needing any asymptotically significant space. It is quite literally a loop, and no special arrangement is required to make sure that this is the case. All that is required is to implement recursion properly (as self-reference), and you’re done. There is no such thing as tail-call optimization. It’s not a matter of optimization, but of proper implementation. Calling it an optimization suggests it is optional, or unnecessary, or provided only as a favor, when it is more accurately described as a matter of getting it right. So what, then, is the source of the confusion? The problem seems to be a too-close association between compound expressions and recursive functions or procedures. Consider the classic definition of factorial given earlier. The body of the definition involves the expression n * fact n' where there is a pending multiplication to be accounted for. Once the recursive call (to itself) completes, the multiplication can be carried out, and it is necessary to keep track of this pending obligation. But this phenomenon has nothing whatsoever to do with recursion. If you write n * square n' then it is equally necessary to record where the external call is to return its value. In typical accounts of recursion, the two issues get confused, a regrettable tragedy of error. Really, the need for a stack arises the moment one introduces compound expressions. This can be explained in several ways, none of which need pictures or diagrams or any discussion about frames or pointers or any extra-linguistic concepts whatsoever. The best way, in my opinion, is to use Plotkin’s structural operational semantics, as described in my Practical Foundations for Programming Languages (Second Edition) on Cambridge University Press. There is no reason, nor any possibility, to avoid recursion in programming. But folk wisdom would have it otherwise. That’s just the trouble with folk wisdom, everyone knows it’s true, even when it’s not. Update: Dan Piponi and Andreas Rossberg called attention to a pertinent point regarding stacks and recursion. The conventional notion of a run-time stack records two distinct things, the control state of the program (such as subroutine return addresses, or, more abstractly, pending computations, or continuations), and the data state of the program (a term I just made up because I don’t know a better one, for managing multiple simultaneous activations of a given procedure or function). Fortran (back in the day) didn’t permit multiple activations, meaning that at most one instance of a procedure can be in play at a given time. One consequence is that α-equivalence can be neglected: the arguments of a procedure can be placed in a statically determined spot for the call. As a member of the Algol-60 design committee Dijkstra argued, successfully, for admitting multiple procedure activations (and hence, with a little extra arrangement, recursive/self-referential procedures). Doing so requires that α-equivalence be implemented properly; two activations of the same procedure cannot share the same argument locations. The data stack implements α-equivalence using de Bruijn indices (stack slots); arguments are passed on the data stack using activation records in the now-classic manner invented by Dijkstra for the purpose. It is not self-reference that gives rise to the need for a stack, but rather re-entrancy of procedures, which can arise in several ways, not just recursion. Moreover, recursion does not always require re-entrancy—the so-called tail call optimization is just the observation that certain recursive procedures are not, in fact, re-entrant. (Every looping construct illustrates this principle, albeit on an ad hoc basis, rather than as a general principle.) Filed under: Programming, Teaching ## November 01, 2017 ### Tweag I/O # The Exodus to Streamgard,<br/> an epic poem Yves Parès If Haskell was a god, often would he be depicted with the ravens Modularity and Abstraction flying above him, hovering the world and reporting to him every detail of our whereabouts. Haskell would sit on the Throne of Purity and look upon the world with full of wisdom. And in his hand, the mighty Haskell would wield the Spear of Lazy Lists, which is said to have the power to tackle each and every problem the world might have to face. And to honour him, we would code and abstract everything with lazy lists. For millenia would lists be used to map, filter, separate, merge, group, . But, one day, the , son of the wicked , would come. And the Real-World Serpent carries an eternal hatred towards lazy lists. Oh, that dreaded Serpent, that will throw everything it can muster to prevent us from staying within the warm comfort of abstraction and laziness. The Serpent will assemble its minions, Early-close and Strictness of effects, and unleash its wrath upon our world. Foldl, son of Haskell and brother of Foldr, would lead humanity to its last bastion, Streamgard, and organize the final fight... So, long story short, streaming is a library that allows you to leverage the insights you have gained while manipulating lazy lists in Haskell to handle effectful streams of data. We already talked about streaming on this blog, with this post discussing the IO part and this one comparing it to pipes and conduit. Here, we will be using streaming for highly efficient data processing and filtering. To this effect, we will use it conjointly with another library, foldl, which gives us an Applicative interface to the usual list functions. In this blog post we will apply them to the task of computing some statistics about a distribution of data. We want to be able to: • process the input data stream only once (aka in one pass), • never repeat the effects that were used to produce that data stream, • maintain the possibility to use the input stream as if it were a list, for instance by splitting it into two subparts, sending each subpart to be processed by a specific function. So lets imagine that the statistics I want to compute on my input data distributions take the shape of a simple summary. This is what I want to obtain in the end: data Summary v a = Summary { summaryLength :: Int , summaryMins :: [a] , summaryMaxes :: [a] , summaryMean :: v , summaryStdDev :: v } deriving (Show)  Nothing too fancy here, I just want to be able to compute the length, the n smallest elements, the n' biggest elements, the mean and the standard deviation of my distribution. We distinguish the types a and v here because our input distribution does not have to be numerical, as long as we have a projection a -> v available. This way, we can compute a summary of a stream of (Double, String) tuples, for instance, if the projection is just fst. So let's have a little reminder of our conditions. We want to be able to read the input data only once. But, we still want modularity and reusability. We do not want to have to recode our Summary-computing function every time we want to add a new field, and we would like to reuse already existing functions computing these statistics. And this is where the foldl package comes in. This package defines a type Fold as follows: data Fold a b = forall acc. Fold (acc -> a -> acc) acc (acc -> b)  You might recognize here the typical arguments of the classical foldl function of the Prelude: a is the type of each element of the input stream we consume, the first field (acc -> a -> acc) is an accumulation function and the second field acc is the initial value of the accumulator. The new component is the b type parameter and the last field (acc -> b). This one is called extract. It is used to extract the final value out of the accumulator. This is necessary so that Fold a can be a Functor and therefore an Applicative. See the original blog post and this talk by Gabriel Gonzalez for more detail, though be aware that Fold had a different shape back then. One of the central ideas of the foldl library is that Fold implements the Applicative type class: instance Applicative (Fold a)  Crucially, this instance combines two Folds, into a guaranteed one-pass traversal of the data. Therefore we can safely decompose the computation of a Summary as follows: import qualified Control.Foldl as L import Data.Function (on) summarizeBy :: (Floating v, Ord v) => (a -> v) -> Int -> Int -> L.Fold a (Summary v a) summarizeBy f nMins nMaxes = Summary <$> L.length
<*> collect ((>=) on f) nMins
<*> collect ((<=) on f) nMaxes
<*> L.premap f L.mean
<*> L.premap f L.std


What's happening here? We are using a few of the functions already present in the foldl package and a new one, so let's delve into it a bit. The function summarizeBy takes a projection f, which we talked about earlier, the number of smallest elements we want to collect and the number of biggest elements. Then our five statistics are computed:

• L.length :: L.Fold a Int gives us the number of elements in the input.
• collect, which we will define a bit later, accumulates either the mins or the maxes given a comparison function.
• L.mean gives us the average. We use L.premap f to turn it into a fold that will work on our projection f.
• L.std gives us the standard deviation.

The combination of the above gives us a Fold a (Summary v a), something that will consume a stream of a's and output a summary. At this point, nothing is consumed, we have only composed folds together, and a Fold is agnostic of the exact nature of the input. Running it on any Foldable datatype for instance is just a matter of calling:

L.fold (summarizeBy id 3 3) [1..100]


The only function is the collect function. Defining it as a brand new Fold is simple:

import Data.Sequence as Seq

collect :: (a -> a -> Bool) -> Int -> L.Fold a [a]
collect skipPred n = L.Fold insertPop Seq.empty (L.fold L.list)
where
insertPop acc x
| Seq.length acc < n = insert x acc
| otherwise          = pop (insert x acc)
insert x s = let (before, after) = Seq.spanl (skipPred x) s
in before <> Seq.singleton x <> after
pop s = case viewr s of
s' :> _ -> s'
_ -> s


Here we manually defined a new Fold from the three elements we mentioned earlier: an accumulation function (insertPop), an initial accumulator value (Seq.empty) and an extract function ((L.fold L.list), which also uses a Fold to turn the final sequence into a plain list).

Now, the astute reader will notice we left streaming aside. Let's get back to it. Let's use as an input the classic Titanic dataset:

PassengerId,Survived,Pclass,Name,Sex,Age,SibSp,Parch,Ticket,Fare,Cabin,Embarked
1,0,3,"Braund, Mr. Owen Harris",male,22,1,0,A/5 21171,7.25,,S
2,1,1,"Cumings, Mrs. John Bradley (Florence Briggs Thayer)",female,38,1,0,PC 17599,71.2833,C85,C
3,1,3,"Heikkinen, Miss. Laina",female,26,0,0,STON/O2. 3101282,7.925,,S
4,1,1,"Futrelle, Mrs. Jacques Heath (Lily May Peel)",female,35,1,0,113803,53.1,C123,S
...


We want to get two different summaries for the fares: one for the passengers that survived and one for those who did not. First, let's load the CSV into a stream by using the streaming-cassava and streaming-bytestring packages:

{-# LANGUAGE OverloadedStrings #-}
import qualified Data.ByteString.Streaming as BS
import Streaming
import Streaming.Cassava

data Passenger { name :: !String, fare :: !Double, survived :: !Bool }
deriving (Show)

instance FromNamedRecord Passenger where
parsedNamedRecord m =
Person <$> m .: "Name" <*> m .: "Fare" <*> (toBool =<< (m .: "Survived")) where toBool 0 = return False toBool 1 = return True toBool _ = mzero streamCsv :: (MonadResource m) => Stream (Of Passenger) m () streamCsv = decodeByName (BS.readFile ".../titanic.csv")  Nothing too fancy here, just a bit of required boilerplate to be able to read Passengers from the CSV file. MonadResource is necessary to track the files opened by our program. The type Stream (Of Passenger) m () means that we will be manipulating a stream whose elements are Passengers, that will run some effects in a monad m and return no result in the end. Now, lets split that input in two different substreams: import qualified Streaming.Prelude as S aliveDead :: Stream (Of Passenger) (Stream (Of Passenger) m) () aliveDead = S.partition survived streamCsv  Let's look at the type of aliveDead: it is a Stream over another Stream. Stream (Of a) is actually a monad transformer, the way the partitioning happens is by creating two layers: one for the live passengers and one for the dead ones. It's not exactly a tuple of two streams (as it would be with Data.List.partition), but is has the same advantages: each layer can be processed by different functions which don't have to know where the stream they process lies in the monad stack. Therefore, each one of these functions can be expressed as: summarizePassengers :: (Monad m) => Stream (Of Passenger) m a -> m (Of (Summary Double Passenger) a) summarizePassengers = L.purely S.fold (summarizeBy fare 3 3)  where m can be any monad. This can be the bottom MonadResource or another Stream, summarizePassengers does not mind and does not have to! Of behaves like a tuple, so it simply means that we return both the newly computed Summary and an a (a may just be (), but here we have to be a little more general). S.fold is the basic folding function for streams. L.purely fn f "unpacks" a Fold f and calls a folding function fn. So now, getting our summaries is just a matter of runAll = runResourceT$ do
(summaryAlive :> summaryDead :> ()) <-

So in the end, we splitted the input file in two substreams, we computed various statistics twice, and despite all this streaming and foldl guarantee that the input will be read only once in bounded memory.