Andrew Coppin wrote:
[design of a bitwise binary library]
(This would all be so trivial in an OO language. Just make an Encoder
object that updates its own state internally and talks to a Source
object and a Destination object for its data...)
I guess it's on the same level of trivialness in Haskell, too, but to be
fair, I haven't tried it... I would proceed as follows:
(1) Try to not shadow names from the mtl or other standard packages.
I choose BitSink and BitSource instead of Reader and Writer.
(2) Select a small number of primitive operations.
I select the operations "read n bits" and "put n bits" as primitive
operations. As interface format, I choose [Boolean], which is
not exactly optimized, but easy to understand.
It is easy to implement operations for single bits, bytes etc. on
top of this operations. We will later include them into the
typeclass, but we will first make the [Boolean]-based operations
correct.
(2) Make BitSink and BitSource composable, e.g., as monad transformers.
The type classes could look like:
class MonadBitSource m where
getBits :: Int -> m [Boolean]
class MonadBitSink m where
putBits :: [Boolean] -> m ()
And we need a lot of trivial instances for the various mtl monad
transformers in the style of:
instance MonadBitSink m => MonadBitSink (ReaderT m) where
putBits = lift . putBits
(3) Write a very simple implementation to (a) check that the typeclasses
makes sense and is implementable and (b) have a test-implementation
for later correctness tests.
The easiest implementation I can think of consists of a state monad
which handles a list of booleans. It could look like this:
newtype BitListT m a = BitListT (StateT [Boolean] m a)
deriving (Functor, Monad, MonadReader r, MonadWriter w, ...)
You should be able to derive all mtl classes except
MonadTransformer, MonadIO and MonadState. Instantiate these
yourself:
instance MonadTransformer BitListT where
lift (BitListT p) = BitListT (lift p)
instance MonadIO m => MonadIO (BitListT m) where
liftIO = lift . liftIO
We want to hide BitListT's state and expose a state in the nested
monad to the user, if there is any.
instance MonadState s m => MonadState s (BitListT m) where
get = lift get
put = lift . put
Finally, the real stuff:
instance MonadBitSink (BitListT m) where
putBits x = BitListT $ modify (++ x)
instance MonadBitSource (BitListT m) where
getBits n = BitListT $ do
result <- gets (take n)
guard (length result == n)
modify (drop n)
return result
runSinkBitListT :: BitListT m a -> m (BitListT ([Boolean], a))
runSinkBitListT (BitListT p) = return $ runState p []
runSourceBitListT :: BitListT m a -> [Boolean] -> m a
runSourceBitListT (BitListT p) bits = return $ evalState p bits
(4) Check the simple implementation
Now we can write quickcheck properties (if you believe in XP, you
can write them before (3), of course) to check our simple
implementation and document the specification. given simple function
runSink = runIdentity . runSinkBitListT and runSource bits =
runIdentity . runSourceBitListT bits, we have such properties as
forall n . forall bits . length bits >= n ==>
length (runSource (getBits n)) == n
forall bits . runSource (getBits (length bits)) == bits
forall a . forall b .
(runSource (liftM2 (++) (getBits a) (getBits b)))
== runSource (getBits (a + b))
forall p . forall q .
runSink p ++ runSink q == runSink (p ++ q)
usw. Use the tricks already mentioned in this thread for the last
property. Don't forget to write properties for the high-level
interface putWord8 etc.
(5) Write a more realistic instance, e.g. by replacing [Boolean] through
(Int, ByteString) and doing clever things in getBits / putBits. Test
this instance both with the existing properties and against the
simple instance, i.e., verify that getBits and setBits means the
same in both monads.
(6) move the high-level functions getWord8 & Co. into the typeclass,
keep the definition as defaults. they are fine for BitListT, but
implement your own versions for the other instance. Quickcheck them
against the properties, against the simple implementation in
BitListT and against the default definitions.
(7) if you need tracing, use liftIO (print ...) and finally understand
what's the point about monad transformer stacks and MonadIO and
why you almost always want to define a monad transformer instead
of a monad.
(8) Write your LZW stuff with
newtype EncoderT s m a = EncoderT (StateT (LZW s) (BitSink m) a)
deriving (a lot of stuff)
(9) Have fun!
Tillmann
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
