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!
-
I can say that since it wasn’t actually my idea!↩
blog :: Brent -> [String] 
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 =)
This is a very nice explanation. I spotted something related in my 2014 thing at IFL on “Buildable” (http://gbaz.github.io/slides/buildable2014.pdf) — see the “Scan” type in section 8.This is a semi-direct product of “buildables” (structures with “actions”, i’d now say) which generalize monoids in a related way. I think you could _probably_ do some of the same stuff as you do with twisted functors, though I haven’t worked through the details. One aspect of the Scan type is that we don’t mix in “actions” and “monoids” but work in a uniform way. On the other hand, I didn’t spot the generalization to Applicative in the “distributive” instance at all, and that’s really where this paper pays off in terms of developing a powerful new abstraction.