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 idea, 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!

## About Brent

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

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.

Ah nice! I remember reading about your parallel checksum stuff but I hadn’t remembered that it used a semi-direct product.

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.

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

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 =)