Alternative instance

[polachok]

Well, it turns out isEmpty is not actually sufficient for my needs (but useful anyway).

  let f xs = isEmpty >>= \b ->
              if b
                 then return xs
                 else (getWord8 7) >>= \x -> f (x:xs)
  in
    not (L.null bs) ==> 
      fromIntegral (length (runGet (runBitGet $ f []) bs)) == (8 * L.length bs `div` 7)

oops, "demandInput: not enough bytes"

I'd be glad to hear suggestions on how to implement Alternative instance for BitGet.

[kolmodin]

I didn't plan on adding Alternative for BitGet, but it's probably doable by piggybacking on the Alternative instance for Get.

I didn't get from your code snippet above what you're trying to do?

[polachok]

I'm trying to emulate some (actually it's more like many).

The actual problem is that I'm working on a binary format for which the spec says: "there're some records in these N bytes, decode them like this until you run out of data". It turns out that after decoding some records, there're padding bits left, and the parser tries decoding these bits as the next record and fails with "not enough bytes".

[kolmodin]

Ah, I see.
You could also solve the problem if you knew the bit offset in the current byte, and whether the current byte is the last one. That might be easier to use than Alternative, and probably easier to test.

[polachok]

I tend to disagree that it would be easier to use. Easier to implement - definetely (it looks like a lot of changes are required to implement Alternative, probably mirroring the code for Get monad), but nothing can compete with high-level construct like some (get :: BitGet SomeType) for simplicity and readability.

[kolmodin]

A subtile problem with many and some is that they stop not only when you run out of input, but also if the decoder runs fail. fail can be called for many reasons, to backtrack, to complain about corrupt input, maybe the decoded message is using some unsupported extension, etc. The code will look very simple, yes, but it's very easy to get bugs this way.

In contrast, a function that keeps trying a decoder if there is at least 7 bits left, no surprises there.

Since BitGet internally uses Get, it's probable that we can implement Alternative by just using the one from Get.

[polachok]

Okay, here's my attempt: polachok@8284c5b
What do you think? Is this the right direction or not?

[kolmodin]

I'm afraid it's not the best approach. I believe Alternative could be implemented with much less effort, by reusing the Alternative implementation from binary.

I imagine that it could be done by piggybacking on Get with something like this (untested);

instance Alternative BitGet where
  (<|>) = plus

plus :: BitGet a -> BitGet a -> BitGet a
plus a b = B $ \s -> runState a s <|> runState b s

The testing is quite superficial. Implementing Alternative introduces a lot of new code paths since there is a main computation but also a fallback computation for when the main computation fails. Not only the BitGet state must be managed, but also the state of Get.
For my best attempt of testing Alternative, please see https://github.com/kolmodin/binary/blob/master/tests/Action.hs from binary. We will need to do something similar to make sure we don't have bugs.