[Haskell-cafe] Sparse records/ADTs

[Roman Cheplyaka]

* Jon Fairbairn <jon.fairbairn at cl.cam.ac.uk> [2012-10-24 11:08:29+0100]
> Is there a convenient way of handling a data structure with lots
> of fields of different types that may or may not be filled in?
> 
> Something equivalent to
> 
> data D = D {a::Maybe A, b::Maybe B, c::Maybe C, …}
> 
> but with better space efficiency and a more convenient empty
> object.
> 
> An easy alternative is
> 
> data E = Ea A | Eb B | Ec C | …
> type R = [E]
> 
> which has a straightforward empty object, but one then must
> define
> 
>    getA e = listToMaybe [a | Ea a <- e]
> 
> for each field, which is tedious (and O(n)). Obviously Templates
> would help, but is there an alternative I’ve missed?

For runtime efficiency it's better to use Data.Map.

For keys of this map you have two alternatives: either define

    data Key = Ka | Kb | Kc | ...

or, to prevent this duplication at the cost of less convenient notation,
you can do something like

    -- Identity combinator; or use one from Control.Monad.Identity
    newtype I a = I a

    -- Constant combinator
    newtype K a b = K a
      deriving (Eq, Ord)

    data E c = Ea (c A) | Eb (c B)

    deriving instance Eq (E (K ()))
    deriving instance Ord (E (K ()))

    type R = Map.Map (E (K ())) (E I)

When you set a value, you infer the key from the value. (This inference
needs to be written manually or generated.)

When you get a value by the key, you check that the returned constructor
is what you expect and throw an error otherwise (but the latter should
never happen if you maintain the invariant).

Roman