Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib@types.pl.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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]
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@byorgey@mathstodon.xyz Given lzw, I think you have
conjugate :: [Int] -> [Int]
conjugate = foldr incr []
where incr n ms = lzw (+) (replicate n 1) ms
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@byorgey@mathstodon.xyz What's more, lzw is another unfold. To be more precise, uncurry (lzw f) is an instance of unfoldr.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@byorgey@mathstodon.xyz Like this:
transpose :: [[a]] -> [[a]]
transpose = unfoldr next where
next xss = case takeWhile (not . null) xss of
[] -> Nothing
yss -> Just (map head yss, map tail yss)
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@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).
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
@pigworker@types.pl You'll enjoy this month's Guardian Genius crossword
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.
Professor of Computing at University of Oxford: functional programming, types, program construction, verification. Formerly @jer_gib.