"Container" polymorphic lookup function, mapping over [(a,b)]

Learn
#1

I would like to define a typeclass with a single function lookup, in the hopes to use it across multiple container types that have a key → value mapping.

Example implementations

  • For Map lookup = Data.Map.lookup
  • For list of (k,v) tuples lookup = Data.List.lookup

I’m stuck on how to unpack the type of a list of tuples to fit a definition.

class Lookup c k where
  lookup :: k -> c k a -> Maybe a

instance (Ord k) => Lookup Map k where
  lookup :: k -> Map k a -> Maybe a
  lookup = Data.Map.lookup

instance (Eq k) => Lookup ??? k where
  lookup :: k -> [] (k,a) -> Maybe a -- [] (k,a) for visual symmetry
  lookup = Data.List.lookup
#2

You could use a newtype wrapper for your [(k,v)] type.

newtype LookupList k v = LookupList {getList :: [(k,v)]}

Would do the trick. You would just have to wrap your lists in this newtype before passing it to the generic function, as the Lookup instance would be on LookupList k

If you are willing to take on some other restrictions you could also do something like

class Lookup c k v | c -> k, c -> v where
    lookup :: k -> c -> Maybe v

instance Ord k => Lookup (Data.Map.Map k v) k v where
    lookup = Data.Map.lookup

instance Eq k => Lookup [(k,v)] k v where
    lookup = Data.List.lookup

But things get slightly more complicated now as the type v is all tied up in the instance. But that might be OK for your use case.

1 Like
#3

Thanks @lukec the definition with functional dependencies helped. You might want to update your code to replace the typo letter t for c so that future viewers aren’t tripped up by the example code.