Jeremy Gibbons

@byorgey@mathstodon.xyz I call that operator "long zip with", or lzw for short. It's in my Underappreciated Unfold paper (1998), but also in my dissertation (1991).

@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

@byorgey@mathstodon.xyz Your way is a fold. There's also (of course!) an unfold:

transpose :: [[a]] -> [[a]]
transpose = unfoldr next where
  next xss
    | any null xss = Nothing
    | otherwise    = Just (map head xss, map tail xss)

That works for rectangular arrays. Coping also with upper left triangular ones needs a bit more work.

@byorgey@mathstodon.xyz Given lzw, I think you have

conjugate :: [Int] -> [Int]
conjugate = foldr incr []
  where incr n ms = lzw (+) (replicate n 1) ms

@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.

@byorgey@mathstodon.xyz For this you want the heterogeneous big brother of lzw:

lzw2 :: (a->b->c) -> a -> b -> [a] -> [b] -> [c]
lzw2 f u v (x:xs) (y:ys) = f x y : lzw2 f u v xs ys
lzw2 f u v xs []         = [ f x v | x <- xs ]
lzw2 f u v [] ys         = [ f u y | y <- ys ]

then you can write

conjugate' :: [Int] -> [Int]
conjugate' = foldr incr []
  where incr n ms = lzw2 ($) id 0 (replicate n succ) ms

@byorgey@mathstodon.xyz I guess lzw3 is the more natural one. Given

data OneOrBoth a b = This a | That b | Those a b

then it is equivalently

lzw3 :: (OneOrBoth a b -> c) -> [a] -> [b] -> [c]

@byorgey@mathstodon.xyz What's more, lzw is another unfold. To be more precise, uncurry (lzw f) is an instance of unfoldr.

@pigworker@types.pl You'll enjoy this month's Guardian Genius crossword

@byorgey@mathstodon.xyz There should also be a way to write that using replicate n succ directly, but now I have to rush off and do something less interesting.

@byorgey@mathstodon.xyz I'm in two minds about whether I prefer lzw2 above or lzw3 below:

lzw3 :: (a->b->c) -> (b->c) -> (a->c) -> [a] -> [b] -> [c]
lzw3 f g h (x:xs) (y:ys) = f x y : lzw3 f g h xs ys
lzw3 f g h xs []         = map h xs
lzw3 f g h [] ys         = map g ys

lzw3 is more general (you can implement lzw2 using it, and I think not vice versa), but at least in this case a bit clunkier to use:

conjugate' :: [Int] -> [Int]
conjugate' = foldr incr []
  where incr n ms = lzw3 ($) id ($0) (replicate n succ) ms

@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.