Post #2373356
2026-05-09 18:56 UTC
I wanted a #Haskell function to efficiently compute the conjugate of an integer partition. I think I know how to write it, but it's fiddly. There's a nice, succinct functional specification:
conjugate = reverse . map length . transpose . map (`replicate` ())
but it's slow. Now I'm wondering whether it's possible to derive an efficient version from this specification, #Bird-Meertens style. Anyone know of previous work along these lines? Or should I add it to my list of interesting projects?
Replies (3)
-
@byorgey@mathstodon.xyz 2026-05-09 19:10
I guess the idea would be to expand the definition of transpose and then start commuting/fusing the `map length` and `map (replicate ())` with things until they "cancel out" and there are no unit values left anywhere in the computation.
-
@das_g@chaos.social 2026-05-09 21:48
@byorgey@mathstodon.xyz How is `transpose` defined? Edit: Ah, I guess it's https://hackage.haskell.org/package/base/docs/Data-List.html#v:transpose
-
@jer_gib@functional.cafe 2026-05-10 14:45
@byorgey@mathstodon.xyz What's the conjugate of an integer partition?