Post #2735414

2026-05-11 14:01 UTC

@byorgey@mathstodon.xyz @oantolin@mathstodon.xyz @das_g@chaos.social This still takes time proportional to the sum of the partition, because we're only stripping off 1 at a time. You can improve that by stripping off `minimum ns` in one go: ``` conjugate :: [Int] -> [Int] conjugate [] = [] conjugate ns = replicate m (length ns) ++ conjugate (takeWhile (>0) [ n - m | n <- ns ]) where m = minimum ns ``` We are effectively snipping off the largest leftmost rectangle from the Ferrers diagram, rather than a single column. I would guess that this achieves the desired complexity.

Replies (2)

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

@byorgey@mathstodon.xyz @oantolin@mathstodon.xyz @das_g@chaos.social In fact, this recursion is a `concat` after an unfold. So it's also a list futumorphism: ``` futu :: (b -> Maybe ([a],b)) -> b -> [a] futu g z = case g z of Nothing -> [] Just (ys, z') -> ys ++ futu g z' ``` (Not stated is the requirement that the generated chunk `ys` should be nonempty, in order to guarantee progress. Alternatively one can make the body return `Maybe (a,[a],b)`, enforcing the requirement structurally.) Then we have: ``` conjugate :: [Int] -> [Int] conjugate = futu strip where strip [] = Nothing strip ns = Just (replicate m (length ns), takeWhile (>0) [ n - m | n <- ns ]) where m = minimum ns ```

Open ##2735415
@oantolin@mathstodon.xyz 2026-05-11 14:59

@jer_gib@functional.cafe Does this version really have complexity O(length ns + maximum ns)? The minimum of ns is the last element which takes linear time for linked lists. So I think this is (length ns) * maximum ns, but you could make it run in the desired time by using arrays instead of lists. Am I missing something? @byorgey@mathstodon.xyz @das_g@chaos.social

Open ##2735417