Post #2735399
2026-05-09 19:10 UTC
Replies (3)
-
@byorgey@mathstodon.xyz 2026-05-09 19:13
Incidentally, if anyone wants to play with this, here's my fiddly but efficient version: ``` conjugatePartition :: [Int] -> [Int] conjugatePartition ps = go (length ps) 0 ps where go :: Int -> Int -> [Int] -> [Int] go !r !l [] = [] go !r !l ps@(p : _) = replicate (p - l) r ++ go (r - length pre) p rest where (pre, rest) = span (== p) ps ```
-
@byorgey@mathstodon.xyz 2026-05-10 21:54
So far I've managed to prove that map length . transpose . map (`replicate` ()) = foldr (\n -> zipWithExt (+) 0 (replicate n 1)) [] where zipWithExt :: (a -> a -> b) -> a -> [a] -> [a] -> [b] zips the lists together with the given function, using the provided value of type a to fill in missing values from the shorter list. This is very similar to @oantolin@mathstodon.xyz 's implementation, and does indeed get rid of the unit values, but it turns out the unit values themselves weren't the problem: the real problem is that we want to avoid the use of `replicate` to encode `Int` values in unary. This version with foldr is still O(sum p), i.e. linear in the total size of the partition, but we want an implementation which is O(length p + maximum p), i.e. linear in the number of parts plus the size of the maximum part. I think my fiddly directly recursive implementation achieves that, as does @das_g@chaos.social 's implementation, but I want to figure out a way to derive those from the direct specification.
-
@oantolin@mathstodon.xyz 2026-05-09 21:30
@byorgey@mathstodon.xyz Maybe I've spent too much time with array languages, but I'd write this function as: conjugatePartition p = foldr1 (zipWith (+)) [[fromEnum(k⌜⟜(↕⊑) J: +/@(>/ i.@{.) k: {+/x>\:!*x}