deep-maps

A DeepMap is a map that has several layers of keys.

type DeepMap :: [Type] -> Type -> Type
data DeepMap ks v where
    Bare :: v -> DeepMap '[] v
    Nest :: Map k (DeepMap ks v) -> DeepMap (k ': ks) v

For a given (k ': ks) :: [Type], the type DeepMap (k ': ks) v is isomorphic to lists of the form [(k, k0, .., kn, v)] where ks = '[k0, ..., kn], but with better performance.

Example

Say you have a table of order IDs, dates, customer IDs, and the total price for that order; and you'd like to track some statistics.

newtype OrderID = OrderID Int
newtype CustomerID = CustomerID Text
newtype Price = Sum Double

type Table = DeepMap '[Day, OrderID, CustomerID] Price

table :: Table
table =
  fromList3
    [ (YearMonthDay 2021 1 1, OrderID 1, CustomerID "Melanie", Sum 13.12)
    , (YearMonthDay 2021 1 1, OrderID 2, CustomerID "Sock", Sum 4.20)
    , (YearMonthDay 2021 1 2, OrderID 3, CustomerID "Sock", Sum 69.69)
    , (YearMonthDay 2021 1 2, OrderID 4, CustomerID "Fiona", Sum 5.00)
    ]

totalSales :: Table -> Price
totalSales = fold

-- How much did customers spend on a given day?
-- (note: use a DeepMap accumulator to fold within the Semigroup)
dailySales :: Table -> Map Day Price
dailySales = toMap . foldMapWithKey3 (\d _o _c p -> d @| p)

-- Who purchased something on which day?
dailyCustomers :: Table -> Map Day [CustomerID]
dailyCustomers = toMap . foldMapWithKey3 (\d _o c _p -> d @| [c])

-- How much has a customer paid throughout history?
totalPerCustomer :: Table -> DeepMap '[CustomerID] Price
totalPerCustomer = foldShallow . foldShallow
{- = foldMapWithKey3 (\_d _o c p -> c @| p) -}

-- What days did each customer purchase something?
customerSaleDates :: Table -> Map CustomerID [Day]
customerSaleDates = toMap . foldMapWithKey3 (\d _o c _p -> c @| [d])
{- = toMap . Map.foldMapWithKey (\d cs -> foldMap (@| [d]) cs) . dailyCustomers -}

-- How much did a customer spend for each order?
-- Useful if e.g. several customers could chip into the same order.
orderTotalPerCustomer :: Table -> DeepMap '[CustomerID, OrderID] Price
orderTotalPerCustomer = invertKeys . foldShallow

-- Using (@!) will NOT throw an error!
-- It's the infix version of `findWithDefault mempty`.
sockTotal :: Table -> Double
sockTotal t = getSum $ totalPerCustomer t @!| CustomerID "Sock"

Shallow & deep functions

You might have noticed the difference between fold and foldShallow in the above example:

fold :: (Monoid v) => DeepMap (k ': ks) v -> v
foldShallow :: (Monoid (DeepMap ks v)) => DeepMap (k ': ks) v -> DeepMap ks v

Here are a few other pairs of similar functions, that operate at different depths:

fmap :: (v -> w) -> DeepMap ks v -> DeepMap ks w
mapShallow :: (DeepMap ks v -> DeepMap ls w) -> DeepMap (k ': ks) v -> DeepMap (k ': ls) w

traverse :: (Applicative f) => (v -> f w) -> DeepMap ks v -> f (DeepMap ks w)
traverseShallow :: (Applicative f) => (DeepMap ks v -> f (DeepMap ls w)) -> DeepMap (k ': ks) v -> f (DeepMap (k ': ls) w)

mapMaybe :: (v -> Maybe w) -> DeepMap (k ': ks) v -> DeepMap (k ': ks) w
mapShallowMaybe :: (DeepMap ks v -> Maybe (DeepMap ls w)) -> DeepMap (k ': ks) v -> DeepMap (k ': ls) w

mapEither ::
  (v -> Either w x) ->
  DeepMap (k ': ks) v ->
  (DeepMap (k ': ks) w, DeepMap (k ': ks) x)
mapShallowEither ::
  (DeepMap ks v -> Either (DeepMap ls w) (DeepMap ms x)) ->
  DeepMap (k ': ks) v ->
  (DeepMap (k ': ls) w, DeepMap (k ': ms) x)