Post #2735401

2026-05-10 21:54 UTC

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.

Replies (3)

@byorgey@mathstodon.xyz 2026-05-10 22:08

Aha, I think it must have something to do with the bijection between encodings of integer partitions as (1) nonincreasing lists of natural numbers and (2) arbitrary lists of natural numbers, witnessed by sending a nondecreasing list to its list of successive differences. For example, the partition [6,6,4,3] corresponds to [0,2,1,3]. (6 - 6 = 0, 6 - 4 = 2, etc.) I'm quite sure I have seen this bijection exploited before, perhaps in Richard Bird's book Pearls of Functional Algorithm Design? I'll have to look once I get back to my office tomorrow.

Open ##2735402
@oantolin@mathstodon.xyz 2026-05-10 23:06

@byorgey@mathstodon.xyz Another approach is to use binary search on each integer from 1 to maximum p to find between which two indices of p it would go. Depending on whether binary search favors the lower or upper value, that can directly give you the conjugate and is O(maximum p * log length p). In J that would be I.i.@{. @das_g@chaos.social

Open ##2735412
@jer_gib@functional.cafe 2026-05-11 14:01

@byorgey@mathstodon.xyz @oantolin@mathstodon.xyz @das_g@chaos.social Here's another go, I think getting to your desired running time of O(length p + maximum p). Start off by observing that it's an unfold: ``` conjugate :: [Int] -> [Int] conjugate = unfoldr strip where strip [] = Nothing strip ns = Just (length ns, takeWhile (>0) [ n - 1 | n <- ns ]) ``` This assumes that the input is a non-increasing list of positive naturals, and returns a result similarly.

Open ##2735413