关联列表的镜片

Question

Control.Lens.At中有一个针对Map/HashMap/等类型的at镜头。但是是否有类似于at的适用于关联列表类型[(k, v)]（可转换为映射）的镜头呢？

- RandomB

---

如果您不关心排序并且可以删除重复的键，则可以编写一个快速的Iso：“myAList ^. Iso Map.fromList M.toList . at key”。 - Chris Penner

如果您不需要添加或删除条目，那么traversed.itraversed :: IndexedTraversal' k [(k, v)] v可以使用，并且您可以使用index来限制给定的键。 - Naïm Favier

Answer 1

我不知道是否有现成的代码可供使用，但是at属于类型类At，所以我们可以自己编写。为了避免涉及灵活（可能重叠）的实例扩展，我们将在新类型中进行。

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

首先，我们需要一些家族实例。

{-# LANGUAGE TypeFamilies #-}

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

这只是定义了我们新类型中的"key"和"value"，非常直观。现在，我们需要能够在特定的键上读写值。Haskell已经为我们提供了一种读取值的方法 (Data.List.lookup)，但我们必须自己编写写入函数。这里没有任何花哨或镜头：只是普通的 Haskell 过滤器和映射。

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

现在我们需要编写 At 实例，它依赖于 Ixed 实例。幸运的是，镜头库为 Ixed 提供了一个默认实现，只要我们正在实现 At，因此第一个实例声明很简单。

instance Eq k => Ixed (AList k v)

编写 at 也相当简单。只需查看类型并稍微跟随一下，然后您得到的实现就是我们想要的实现。

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

我们完成了。现在at将适用于AList。如果新类型包装让您困扰，您可以很容易地创建一个新函数（例如at'），它为您执行新类型的包装/解包操作。

证明此实例满足镜头定律留给读者作为练习。

完整代码

{-# 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)

- Silvio Mayolo