Author Archives: Brent

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Counting inversions via rank queries

Posted on December 18, 2019

In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in time. As a reminder, given a sequence , an inversion is a pair of positions such that and … Continue reading →

Posted in haskell | Tagged , , , , , , , , , | 4 Comments

Computing Eulerian paths is harder than you think

Posted on November 20, 2019

Everyone who has studied any graph theory at all knows the celebrated story of the Seven Bridges of Königsberg, and how Euler gave birth to modern graph theory while solving the problem. Euler’s proof is clever, incisive, not hard to … Continue reading →

Posted in learning | Tagged , , , , | 5 Comments

Competitive Programming in Haskell: reading large inputs with ByteString

Posted on October 12, 2019

In my last post in this series, we looked at building a small Scanner combinator library for lightweight input parsing. It uses String everywhere, and usually this is fine, but occasionally it’s not. A good example is the Kattis problem … Continue reading →

Posted in haskell | Tagged , , , , , | 1 Comment

Lightweight invertible enumerations in Haskell

Posted on July 5, 2019

In a previous post I introduced a new Haskell library for enumerations (now on Hackage as simple-enumeration). The Data.Enumeration module defines a type Enumeration a, represented simply by a function Integer -> a which picks out the value of type … Continue reading →

Posted in combinatorics, haskell, projects | Tagged , , , , , , | 1 Comment

Competitive Programming in Haskell: Scanner

Posted on May 22, 2019

In my previous post I explored solving a simple competitive programming problem in Haskell. The input of the problem just consisted of a bunch of lines containing specific data, so that we could parse it using lines and words. There … Continue reading →

Posted in haskell | Tagged , , , , | 8 Comments

Lightweight, efficiently sampleable enumerations in Haskell

Posted on May 14, 2019

For another project I’m working on, I needed a way to enumerate and randomly sample values from various potentially infinite collections. There are plenty of packages in this space, but none of them quite fit my needs: universe (and related … Continue reading →

Posted in combinatorics, haskell, projects | Tagged , , , , | 10 Comments

Code style and moral absolutes

Posted on April 30, 2019

In my previous post about my basic setup for solving competitive programming problems with Haskell, I (somewhat provocatively) used lists to represent pairs, and wrote a partial function to process them. Commenter Yom responded with a proposed alternative that was … Continue reading →

Posted in haskell | Tagged , , | 6 Comments