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