Separation of code into functions and use of patern matching in Haskell
To me, serialize especially seems pretty ugly; the use of the where clauses and the similarity of the latter two pattern match cases all seems bad to me, yet I'm unsure what should be done instead.


You can rewrite the serialize function using as-patterns which will eliminate the where clause like so.

serialize :: Atom -&gt; Word8
serialize TerminationAtom = 0
serialize all@(NonOffsetAtom _ _ _) = fromIntegral $ (getAtomType all) `shiftL` 6 .|.
                                                     (getFillField all) `shiftL` 4 .|.
                                                     (getDataField all)
serialize all@(OffsetAtom _ _ _)    = fromIntegral $ (getAtomType all) `shiftL` 6 .|.
                                                     (getFillField all) `shiftL` 3 .|.
                                                     (getDataField all)


You could eliminate the duplication further by extracting the body of the function into another function parameterized over the shift value. Something like this.

serialize all@(NonOffsetAtom _ _ _) = shifty 4 all
serialize all@(OffsetAtom _ _ _)    = shifty 3 all

shifty n a = fromIntegral $ (getAtomType a) `shiftL` 6 .|.
                            (getFillField a) `shiftL` n .|.
                            (getDataField a)



  Should I use Word8 as the return type of all the functions (the return values are all small enough to fit)?


Yes. If your functions logically only operate on 8-bit byte values, then that's an important fact you can and should capture in the type signature. If returning a value of 256 or 500000 or -1 would be absurd, then eliminate the possibility of that even happening!

In General

There are other odds and ends that could be changed or cleaned up, like comparing Bool arguments to True or False instead of using them directly (getAtomType) or using ifs instead of more pattern matching (getFillField (NonOffsetAtom _ True _) = ...).



Update

Having slept on it and cleared my head, I think your code would be much improved by leveraging ADTs and a serialization typeclass. As it stands your solution feels very C-like, and your data types are used like structs, arrays and low-level machine ints instead of rich data. I'll sketch an outline of what I would do here, please feel welcome to interrogate me in the comments if the full picture doesn't come through for you.

data Four = Zero | One | Two | Three

data AtomType = ShortBase   Four | LongBase
              | ShortOffset Bool | LongOffset

newtype FillType = Fill Four

data DataField = ...

data Word = Terminal
          | Word AtomType FillType DataField

class Serialize a where
    serialize :: a -&gt; Word8

instance Serialize Four where
    serialize Zero  = 0
    serialize One   = 1
    serialize Two   = 2
    serialize Three = 3

instance Serialize AtomType where
    serialize (ShortBase n)       = serialize n `shiftL` 6
    serialize LongBase            = 4 `shiftL` 6
    serialize (ShortOffset False) = 5 `shiftL` 6
    serialize (ShortOffset True)  = 7 `shiftL` 6
    serialize LongOffset          = 6 `shiftL` 6

...

instance Serialize Word where
    serialize Terminal     = 0
    serialize (Word t f d) = serialize t .|. serialize f .|. serialize d


My goal here was to make everything as correct-by-construction as possible (q.v. the Four type) and to reduce the opportunities for ambiguity (e.g., a "Fill Field" may mean any number of things if all you're looking at is a literal 0, so the representation should be as precise as necessary and no more).

On the benefits of this approach


If you can determine the names based on the problem domain, this will be extremely readable
Requires less dead code (In particular I'm looking at the support for TerminationAtom everywhere)
Easily made symmetrical with a Deserialize class


Intermediary representations of data can always slow down your code, but with aggressive inlining I don't think this would be too much of a performance hit.