Lenses for association list

Question

There is at lens for Map/HashMap/etc in Control.Lens.At. But is any lens similar to at for association list type [(k, v)] (which is convertible to map)?

Answer 1

I don't know of one that's provided for you, but at belongs to the typeclass At, so we could certainly write it ourselves. To avoid having to get our hands dirty with flexible (and possibly overlapping) instance extensions, we'll do this in a newtype.

newtype AList k v = AList [(k, v)]

First, we need a couple of family instances.

{-# LANGUAGE TypeFamilies #-}

type instance IxValue (AList k v) = v
type instance Index (AList k v) = k

This just defines what the "key" and "value" is in our new type, which is straightforward. Now, we need to be able to read and write values at a specific key. Haskell already gives us a way to read values (Data.List.lookup), but we have to make the writing function ourselves. Nothing fancy or lens-y here: just ordinary old Haskell filters and maps.

replaceAt :: Eq k => k -> Maybe v -> AList k v -> AList k v
replaceAt k Nothing (AList m) = AList $ filter (\(k', _) -> k /= k') m
replaceAt k (Just v) (AList m) =
    case lookup k m of
      Nothing ->
          -- Not present in the list; add it
          AList ((k, v) : m)
      Just _ ->
          -- Present; replace it
          AList $ map (\(k', v') -> if k == k' then (k', v) else (k', v')) m

Now we need to write the At instance, which depends on the Ixed instance. Fortunately, the lens library provides a default implementation for Ixed as long as we're implementing At, so the first instance declaration is simple.

instance Eq k => Ixed (AList k v)

Writing at is fairly straightforward as well. Just look at the types and follow your nose a bit, and the implementation you arrive at is the one we want.

instance Eq k => At (AList k v) where
    at k f (AList m) = fmap (\v' -> replaceAt k v' (AList m)) $ f (lookup k m)

And we're done. Now at will work for AList. If the newtype wrapper bothers you, you could pretty easily make a new function (at', if you will) that does the newtype wrapping/unwrapping for you.

Proving that this instance satisfies the lens laws is left as an exercise to the reader.

Complete code

{-# LANGUAGE TypeFamilies #-}

import Control.Lens.At
import Data.List(lookup)

newtype AList k v = AList [(k, v)]

type instance IxValue (AList k v) = v
type instance Index (AList k v) = k

replaceAt :: Eq k => k -> Maybe v -> AList k v -> AList k v
replaceAt k Nothing (AList m) = AList $ filter (\(k', _) -> k /= k') m
replaceAt k (Just v) (AList m) =
    case lookup k m of
      Nothing ->
          -- Not present in the list; add it
          AList ((k, v) : m)
      Just _ ->
          -- Present; replace it
          AList $ map (\(k', v') -> if k == k' then (k', v) else (k', v')) m

-- Just take the default implementation here.
instance Eq k => Ixed (AList k v)

instance Eq k => At (AList k v) where
    at k f (AList m) = fmap (\v' -> replaceAt k v' (AList m)) $ f (lookup k m)