New Haskell Symposium paper on “twisted functors”

Satvik Chauhan, Piyush Kurur and I have a new paper which will appear at the 2016 Haskell Symposium in Japan:

How to Twist Pointers without Breaking Them

Although pointer manipulations are used as a primary motivating example, at heart the paper is really about “twisted functors”, a class of applicative functors which arise as a natural generalization of the semi-direct product of two monoids where one acts on the other. It’s a really cute idea1, one of those ideas which seems “obvious” in retrospect, but really hadn’t been explored before.

We give some examples of applications in the paper but I’m quite certain there are many other examples of applications out there. If you find any, let us know!


  1. I can say that since it wasn’t actually my idea!

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in haskell, writing and tagged , , , , , , , , , . Bookmark the permalink.

5 Responses to New Haskell Symposium paper on “twisted functors”

  1. Edward Kmett says:

    Nice!

    I’ve used this monoid many times in the past, but never had a name for the concept, so I’ll steal yours!

    Here are a couple of simple examples I’ve found useful in the past.

    Say you want to compute a hash function in parallel. You might try doing something like saying that the hash is the bitstring mod q where q is an odd number, since an odd number is coprime with 2, you can compute this answer for the concatenation of two bitstrings by simply tracking how many bits you have (which you combine with +), and by computing

    (a,n) (b,m) = (mod (a*2^m + b) q, m + n)

    Here our monoids are addition, and addition mod q, the action of m on a is multiplying a * 2^m.

    If you do this in a Galois field instead of the usual integer ring, and store x^m and x^n, instead of m and n, then you can easily compute standard CRCs in parallel!

    (a,x_n) (b,x_m) = (a * x_m + b, x_n * x_m)

    https://www.schoolofhaskell.com/user/edwardk/parallel-crc

    When you’re done, just ‘forget’ the x_n, term, and use the usual the usual CRC finalization of flipping all the bits to get your answer.

    (I found out after that the ability to compute that result in parallel had been written up a couple of years before in Kadatch and Jenkins: https://github.com/rurban/crcutil/raw/master/doc/crc.pdf)

    Minor modifications allow the computation of Adler32 or Fletcher checksums in a similar way.

  2. Edward Kmett says:

    Er, I omitted the relevant twisted functor and just stopped with the semi-direct project:

    We can make an instance of `MonadPut` and `MonadGet` in `bytes` for a monad transformer that computes such a CRC as it reads or writes using an underlying monad. This is basically a glorified WriterT. Then the ‘twisted functor’ here is to let this monoid ‘act’ on that writer monad in the obvious way.

  3. Gabor says:

    Spotted “concatnation”, which is a cute word, but you meant something else :-)

    • Brent says:

      Thanks much! Your comment reminded me that I had forgotten to run a final spell check, so I did and also found three or four other misspelled words. Thankfully there was something a bit wrong with our camera-ready copy so I get to resubmit a version without the typos =)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s