尝试 lens/traversal 对其键的子集进行映射多次更新

Question

我正在尝试通过遍历来整体更新 IntMap 的多个键。

消除 XY：我不是简单地尝试更新它们，我需要遍历到 return 到调用者以进行进一步组合。或者至少可以与镜头组合。

我已经尝试了很多常见组合器的变体。我试过使用基于函子的定义，通过大量实验改变 forall 的范围，但没有成功。再次从头开始构建，这就是我所在的位置：

import Control.Lens
import Control.Lens.Unsound

-- base case: traverse a single fixed element
t1 :: Traversal' (IntMap a) (Maybe a)
t1 = at 0

-- build-up case: traverse a pair of fixed elements
t2 :: Traversal' (IntMap a) (Maybe a)
t2 = at 0 `adjoin` at 1

-- generalizing case: do it with a fold
t3 :: Traversal' (IntMap a) (Maybe a)
t3 = foldr (\e t -> at e `adjoin` t) (at 1) [0]

t1 和 t2 工作正常；我将 t3 设计为等同于 t2，但它因以下错误而失败：

• Couldn't match type ‘f1’ with ‘f’
  ‘f1’ is a rigid type variable bound by a type expected by the context:
    Traversal' (IntMap a) (Maybe a)
  ‘f’ is a rigid type variable bound by the type signature for:
    t3 :: forall a. Traversal' (IntMap a) (Maybe a)
  Expected type: (Maybe a -> f1 (Maybe a)) -> IntMap a -> f1 (IntMap a)
  Actual type: (Maybe a -> f (Maybe a)) -> IntMap a -> f (IntMap a)
• In the second argument of ‘adjoin’, namely ‘t’   
  In the expression: at x `adjoin` t
  In the first argument of ‘foldr’, namely ‘(\ x t -> at x `adjoin` t)’

我想这是一些 rank-2 的诡计，我仍然有点难以理解。有什么办法可以做到这一点吗？

我的目标是

的最终签名

ats :: Foldable l => l Int -> Traversal' (IntMap a) (Maybe a)

...当然假设唯一键。我梦想的可以像 t3.

一样实现

Answer 1

Traversal' 是包含 forall 的类型的类型同义词，这使它成为类型系统中的第二个 class 公民：我们不能用这样的实例化类型变量一种。

特别是，我们在这里尝试使用 foldr :: (a -> b -> b) -> b -> [a] -> b，我们无法实例化 b = Traversal' _ _，因为 Traversal' 包含一个 forall.

一种解决方法是将 Traversal' 包装在新类型 ReifiedTraversal 中。在将 at 1 传递给 foldr 之前包装（使用 Traversal 构造函数）；在 foldr 内，展开以使用 adjoin，然后重新包装；最后打开。

t3 :: Traversal' (IntMap a) (Maybe a)
t3 = runTraversal (foldr (\e t -> Traversal (at e `adjoin` runTraversal t)) (Traversal (at 1)) [0])

遍历是一个函数Applicative f => (t -> f t) -> (s -> f s)。你有一个函数 f :: Maybe a -> f (Maybe a) 并且你想将它应用到 IntMap a.

中的一些条目

使用 Applicative 有点令人费解（使用 Monad 有一个更自然的解决方案），但与将遍历组合为 first-class 值相比，它需要的专业知识更少:

import Control.Applicative
import Data.IntMap (IntMap)
import qualified Data.IntMap as M

-- [Int] -> Traversal' (IntMap a) (Maybe a)
traverseAtKeys :: Applicative f => [Int] -> (Maybe a -> f (Maybe a)) -> IntMap a -> f (IntMap a)
traverseAtKeys keys f m =
  let go i k = liftA2 (insertMaybe i) (f (M.lookup i m)) k
      insertMaybe i Nothing = M.delete i
      insertMaybe i (Just v) = M.insert i v
  in foldr go (pure m) keys

Answer 2

解决此类问题的一种方法是使用新类型包装器。具体来说，请考虑以下内容：

newtype TravJoiner a b = TravJoiner { unTravJoiner :: Traversal' a b }
instance Semigroup (TravJoiner a b) where
  TravJoiner x <> TravJoiner y = TravJoiner $ adjoin x y

有了这个，您就可以毫不费力地编写 t3:

t3 :: Traversal' (IntMap a) (Maybe a)
t3 = unTravJoiner $ foldr (\e t -> TravJoiner (at e) <> t) (TravJoiner $ at 1) [0]

你的 ats 函数从那里很好地遵循：

ats :: Foldable l => l Int -> Traversal' (IntMap a) (Maybe a)
ats = unTravJoiner . foldr (\e t -> TravJoiner (at e) <> t) (TravJoiner ignored)

尝试 lens/traversal 对其键的子集进行映射多次更新

Attempting lens/traversal map multi-update on a subset of its keys

haskell

lenses

haskell-lens