On Tue, Apr 19, 2016 at 11:14 AM, Dániel Arató
Hi guys,
Here is my solution to Problem 50 from Ninety-Nine Haskell Problems: https://github.com/nilthehuman/H-99/blob/master/Logic.hs#L75
(`consume' is defined here: https://github.com/nilthehuman/H-99/blob/master/Lists.hs#L107 )
I'm not satisfied with the code quality. I feel like especially `go', `group' and `min2' should be more succint and readable.
Dániel, Looking at your code, there are several things that I note immediately. First, your 'consume' combinator can be rewritten as
consume f g a = foldl f a . chunk g chunk g = unfoldr (fmap g . (\xs -> if null xs then Nothing else Just xs))
Second, you may want to reconsider your data model. As it is, your code is inefficient, since you are simulating priority queues using lists. Not everything can be solved naturally with lists. Assume we proceed anyway with your model, despite these misgivings. Note that any operation on your symbols is most naturally expressed in terms of sets of symbols with a common root. Hence, you may want to use
gatherRoots = chunk (partition (compare `on` root)) to split your queue into these sets. Note that this also gives you an easier way of expressing 'done' as done = (<=1) . length . gatherRoots
Once that is obtained, you want the minimal two sets by weight. Hence:
(x:y:xs) = map fst . sortBy (compare `on` snd) . map (id &&& flatten) where flatten = sum . map weight weight (_,w,_,_) = w
Finally, you want to
go xs = map (update '0') x ++ map (update '1') y ++ xs where update p (c,w,ps,_) = (c,w,p:ps, rn) rn = rNext xs
Note that this also avoids the ugly nested-if you had there. I played around with your code and refactored it to my taste. I extracted the main priority-queue simulation code into a typeclass instance so that you can see that the majority of the complexity of your code comes from simulating priority queues using lists. The completed code is here [0]. Note that I've taken some liberties with the naming and refactoring, and this may not all be to your taste. YMMV. I hope this helps, and that the criticism I gave was correct and will be well-received. Regards, Gesh P.S. You would be correct in claiming that this rewrite is too distant from the original to be of use. My apologies if this is the case. [0] - https://gist.github.com/anonymous/cd4e21105676894dcd579fcf8d4c4b41