I have some code where I need a type-level function that takes two lists of key-value pairs that are sorted on the keys and has each key only once and then merges them into one such list (preferring the first list if keys exist in both lists).
After a lot of trial-and-error I finally managed to get the following working:
{-# LANGUAGE DataKinds, KindSignatures, PolyKinds, TypeFamilies, TypeOperators, UndecidableInstances #-}
import Data.Proxy
import GHC.TypeLits
data KVPair s a = Pair s a
type family Merge (as :: [KVPair Symbol *]) (bs :: [KVPair Symbol *]) :: [KVPair Symbol *] where
Merge '[] bs = bs
Merge as '[] = as
Merge ((Pair k1 a) : as) ((Pair k2 b) : bs) = Merge' (CmpSymbol k1 k2) ((Pair k1 a) : as) ((Pair k2 b) : bs)
type family Merge' (ord :: Ordering) (as :: [k]) (bs :: [k]) :: [k] where
Merge' LT (a : as) (b : bs) = a : Merge as (b : bs)
Merge' EQ (a : as) (b : bs) = a : Merge as bs
Merge' GT (a : as) (b : bs) = b : Merge (a : as) bs
test :: Proxy (Merge [Pair "A" Int, Pair "Hello" (Maybe Char), Pair "Z" Bool] [Pair "Hello" String, Pair "F" ()])
test = Proxy
and when asking for the type of test in GHCi you get the expected:
*Main> :t test
test
:: Proxy
'['Pair "A" Int, 'Pair "Hello" (Maybe Char), 'Pair "F" (),
'Pair "Z" Bool]
This uses two type families so that the second one can actually pattern-match on the ordering of the keys, but that seems a lot more complicated than it ought to be. Is there a way to get a similar situation going with just a single type family?