list - 通过索引交换列表中的两个元素

Question

如果我对元素的唯一了解是它们在列表中出现的位置，是否有任何方法可以交换列表中的两个元素。

更具体地说，我正在寻找这样的东西:

swapElementsAt :: Int -> Int -> [Int] -> [Int]

那会是这样的:

> swapElementsAt 1 3 [5,4,3,2,1] -- swap the first and third elements
[3,4,5,2,1]

我认为 Haskell 中可能存在为此的内置函数，但我无法找到它。

Answer 1

警告:微积分。 我并不打算完全认真地回答这个问题，因为它更像是一个大锤胡桃夹子。但这是我随身携带的大锤，那为什么不做一些运动呢？除了这可能比提问者想知道的要多，对此我深表歉意。这是一种尝试挖掘已经提出的明智答案背后的更深层次的结构。

可微仿函数类至少提供以下零碎。

class (Functor f, Functor (D f)) => Diff (f :: * -> *) where
  type D f :: * -> *
  up   :: (I :*: D f) :-> f
  down :: f :-> (f :.: (I :*: D f))

我想我最好解开其中的一些定义。它们是组合仿函数的基本工具包。这东西

type (f :-> g) = forall a. f a -> g a

用于容器操作的多态函数类型的缩写。

这里是容器的常数、同一性、成分、总和和乘积。

newtype K a x = K a                       deriving (Functor, Foldable, Traversable, Show)
newtype I x = I x                         deriving (Functor, Foldable, Traversable, Show)
newtype (f :.: g) x = C {unC :: f (g x)}  deriving (Functor, Foldable, Traversable, Show)
data (f :+: g) x = L (f x) | R (g x)      deriving (Functor, Foldable, Traversable, Show)
data (f :*: g) x = f x :*: g x            deriving (Functor, Foldable, Traversable, Show)

D通过通常的微积分规则计算仿函数的导数.它告诉我们如何表示一个元素的单孔上下文。让我们再次阅读这些操作的类型。

up   :: (I :*: D f) :-> f

说我们可以做一个整体 f来自 f 中的一个元素和该元素的上下文对.它是“向上”，因为我们在层次结构中向上导航，专注于整体而不是一个元素。

down :: f :-> (f :.: (I :*: D f))

同时，我们可以用它的上下文将每个元素装饰在一个可微的仿函数结构中，计算所有“向下”到特定元素的方法。

我会离开 Diff基本组件的实例到此答案的末尾。对于我们得到的列表

instance Diff [] where
  type D [] = [] :*: []
  up (I x :*: (xs :*: ys)) = xs ++ x : ys
  down [] = C []
  down (x : xs) = C ((I x :*: ([] :*: xs)) :
    fmap (id *:* ((x :) *:* id)) (unC (down xs)))

在哪里

(*:*) :: (f a -> f' a) -> (g a -> g' a) -> (f :*: g) a -> (f' :*: g') a
(ff' *:* gg') (f :*: g) = ff' f :*: gg' g

所以，例如，

> unC (down [0,1,2])
[I 0 :*: ([] :*: [1,2]),I 1 :*: ([0] :*: [2]),I 2 :*: ([0,1] :*: [])]

依次挑选出每个上下文中的元素。

如果 f也是 Foldable ，我们得到一个广义的 !!运算符(operator)...

getN :: (Diff f, Foldable f) => f x -> Int -> (I :*: D f) x
getN f n = foldMap (: []) (unC (down f)) !! n

...额外的好处是我们获得了元素的上下文以及元素本身。

> getN "abcd" 2
I 'c' :*: ("ab" :*: "d")

> getN ((I "a" :*: I "b") :*: (I "c" :*: I "d")) 2
I "c" :*: R ((I "a" :*: I "b") :*: L (K () :*: I "d"))

如果我们想要一个仿函数提供两个元素的交换，它最好是两次可微的，它的导数最好也是可折叠的。开始。

swapN :: (Diff f, Diff (D f), Foldable f, Foldable (D f)) =>
  Int -> Int -> f x -> f x
swapN i j f = case compare i j of
  { LT -> go i j ; EQ -> f ; GT -> go j i } where
  go i j = up (I y :*: up (I x :*: f'')) where
    I x :*: f'   = getN f i          -- grab the left thing
    I y :*: f''  = getN f' (j - 1)   -- grab the right thing

现在很容易将两个元素取出并以相反的方式将它们重新插入。如果我们对位置进行编号，我们只需要注意删除元素重新编号位置的方式。

> swapN 1 3 "abcde"
"adcbe"

> swapN 1 2 ((I "a" :*: I "b") :*: (I "c" :*: I "d"))
(I "a" :*: I "c") :*: (I "b" :*: I "d")

与以往一样，您无需深入挖掘有趣的编辑操作即可找到工作中的差异结构。

为了完整性。 以下是上述涉及的其他实例。

instance Diff (K a) where     -- constants have zero derivative
  type D (K a) = K Void
  up (_ :*: K z) = absurd z
  down (K a) = C (K a)

instance Diff I where         -- identity has unit derivative
  type D I = K ()
  up (I x :*: K ()) = I x
  down (I x) = C (I (I x :*: K ()))

instance (Diff f, Diff g) => Diff (f :+: g) where  -- commute with +
  type D (f :+: g) = D f :+: D g
  up (I x :*: L f') = L (up (I x :*: f'))
  up (I x :*: R g') = R (up (I x :*: g'))
  down (L f) = C (L (fmap (id *:* L) (unC (down f))))
  down (R g) = C (R (fmap (id *:* R) (unC (down g))))

instance (Diff f, Diff g) => Diff (f :*: g) where  -- product rule
  type D (f :*: g) = (D f :*: g) :+: (f :*: D g)
  up (I x :*: (L (f' :*: g))) = up (I x :*: f') :*: g
  up (I x :*: (R (f :*: g'))) = f :*: up (I x :*: g')
  down (f :*: g) = C     (fmap (id *:* (L . (:*: g))) (unC (down f))
                      :*: fmap (id *:* (R . (f :*:))) (unC (down g)))

instance (Diff f, Diff g) => Diff (f :.: g) where  -- chain rule
  type D (f :.: g) = (D f :.: g) :*: D g
  up (I x :*: (C f'g :*: g')) = C (up (I (up (I x :*: g')) :*: f'g))
  down (C fg) = C (C (fmap inner (unC (down fg)))) where
    inner (I g :*: f'g) = fmap wrap (unC (down g)) where
      wrap (I x :*: g') = I x :*: (C f'g :*: g')