gistfile1.txt

-- some custom atomic datatype, defined in Atom.hs
newtype Atom = Atom ByteString deriving (Ord)
-- another custom datatype
newtype DbInt = DbInt Word64 deriving (Ord)
-- and so on.

-- DbIndex.hs
-- an index doesn't know of all the possible datatypes we might want to use.
-- So we can't use a sum type (Expression Problem), but need these datatypes wrapped in an existential type.
data Cell where
    Cell :: c -> Cell
-- The index must be able to index any possible row ("key") type, for example (DbInt, Atom, Atom) or (DbInt, DbInt)
-- A row is represented as a list here. For efficiency it could as well be represented
-- as an array of bytes with a custom encoding...
type Row = [Cell]

-- An (Index v) is a map (Row -> v) with a dynamic comparison function
data Index v = DynMap (Row -> Row -> Ordering) (Node Row v)
createIndex :: (Row -> Row -> Ordering) -> Index v
addToIndex :: Index v -> Row -> v -> Index v
lookupIndex :: Index v -> Row -> Maybe v

-- Let's make an index for a 3-column table (DbInt, Atom, Atom).
-- we promise to never put anything in it but Rows that are actually of (DbInt, Atom, Atom) type.
myCompare :: Row -> Row -> Ordering
myCompare [Cell a, Cell b, Cell c] [Cell x, Cell y, Cell z] = compare (a', b', c') (x', y', z')
 where
    a' = unsafeCoerce a :: DbInt
    b' = unsafeCoerce b :: Atom
    c' = unsafeCoerce c :: Atom
    x' = unsafeCoerce x :: DbInt
    y' = unsafeCoerce y :: Atom
    z' = unsafeCoerce z :: Atom
myIndex :: Index Int
myIndex = createIndex myCompare

-- in the same way we could make a function that makes a comparison function given a schema
data Celltype = AtomType | DbIntType

mkComparer :: [Celltype] -> (Row -> Row -> Ordering)
...