andrewcoppin:

I could try GHC's new debugger. But my experiences with it so far have shown that for all but the most trivial programs possible, it becomes intractably difficult to figure out what the debugger is actually showing you. I actually tried to debug a "normal" LZW implementation once - one that didn't involve two highly convoluted custom monads and a stateful execution model with manually threaded state. This is *not* my idea of a fun time...

For what its worth, people are using this at work on large projects happily.

In a "normal" programming language, at this point you would sprinkle a few print statements around so you can see the intermediate steps the program is taking. But I can't. I'm in the wrong monad. Curses!

Use Debug.Trace.trace.

In the end, the only solution I could come up with was to design a second, "hacked" version of the two monads. Instead of importing one module, you import another that provides the same interface. However, now Reader and Writer are aliases to IO. All write requests cause pretty-printed binary to be sent to stdout, and all read requests pop up a prompt for input from stdin. It worked reasonably well in that I could now add the vitally necessary print statements, and see intermediate values and so forth... It wasn't very pretty though.

You should have used Debug.Trace.

So at least I got that part fixed. Heh. But now I find myself worrying about yet *another* problem: is Writer lazy enough?

I mean, the idea is that you can write a program that lazily reads from a file, pushes it through a Writer, and lazily writes the result back to another file. The thing should chug along reasonably fast and use a constant amount of RAM. But all this is only true of Writer is actually lazy enough. I have a horrible feeling that all the complicated Origami inside makes it too strict. And I have no way to check!

Actually, you can use 'chasingBottoms' to write QuickCheck properties that state your expected laziness or strictness behaviour.

Actually, thinking about it, is Reader lazy enough? You call run_reader and it hands over your data, but if that data is, say, a list, will run_reader build the entire damn list before it'll hand it over? Or will the monadic code by called as-needed to generate the list elements? Obviously I desire the latter, but I'm really not sure what the actual behaviour is...

The mtl Reader class is lazy.

In summary, I've spent several days coding, and I still don't have a single algorithm working. I've spent all my time wrestling with the mundane details of infrastructure rather than the interesting algorithms I actually set out to implement. This makes me very sad. :-(

You should have stopped by #haskell a few days ago.

If anybody can think of a better set of abstractions or another way to do debugging, I'd be interested to hear about it.

There's already a bit layer for Data.Binary on hackage, for what its worth. And an LZW encoder/decoder.

(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...)

Make an Encoder class that updates its own state internally and lazy streams input and output. As Data.Binary does, as zlib does, et al. -- Don

I could try GHC's new debugger. But my experiences with it so far have shown that for all but the most trivial programs possible, it becomes intractably difficult to figure out what the debugger is actually showing you.

GDB is to C as (a) GHCi debugger :: Haskell (b) Pigs :: Farmers (c) Food :: TomMD (d) None of the above Hint: Its not (a). The GHCi debugger seems to catch extra flack because people want to pour through their Haskell code as they do imperative code. I can sympathize - I would like to do that too - but it would be an inaccurate picture of the programs execution. so long as you regard the GHCi as a new/useful tool and not try to pretend its like other debuggers you'll probably be happier. I've found ghcid to be useful when quickcheck + HPC + ChasingBottoms fails to narrow down the problem any further. Its gotten to the point where I often know exactly which LOC/module will be the next step (based on knowledge of the data dependencies). A fair share of bugs have fallen to the sword named vim as a result :-). It really is useful, but like all other haskellisms, one must learn to ride a bike all over again. At times I think of ghcid as the anti-gdb. If there's a series of let bindings, each mutating the predecessor, its enjoyable to see the debugger start at the bottom and crawl its way back up. Tom

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