haskell - 更改 Haskell 树中的索引

Question

(抱歉，上下文描述很长，但我找不到更简单的方法来解释我的问题)考虑以下类型:

import Data.Array

data UnitDir = Xp | Xm | Yp | Ym | Zp | Zm
    deriving (Show, Eq, Ord, Enum, Bounded, Ix)

type Neighborhood a = Array UnitDir (Tree a)

data Tree a = Empty | Leaf a | Internal a (Neighborhood a)
    deriving (Eq, Show)

显然，Tree 可以定义为 Functor 的实例，如下所示:

instance Functor Tree where
    fmap _ Empty           = Empty
    fmap f (Leaf x)        = Leaf (f x)
    fmap f (Internal x ts) = Internal (f x) $ fmap (fmap f) ts

我想定义一个函数，通过排列 Array UnitDir (Tree a) 的索引来遍历 Tree 的实例(因此它是 6 的排列) UnitDir 的可能值)。

一种可能的实现是这样的:

type Permutation = Array UnitDir UnitDir

applyPermutation :: Permutation -> Tree a -> Tree a
applyPermutation _ Empty = Empty
applyPermutation _ (Leaf x) = Leaf x
applyPermutation f (Internal x ts) = Internal x (applyPermutation' ts)
    where applyPermutation' ts = ixmap (Xp, Zm) (f !) (applyPermutation f <$> ts)

我的问题如下:是否有一个自然的 Haskell 结构可以在重新索引子级时“遍历”树？

Functor 不起作用，因为我用它来更改树的内容，而不是它的索引方案。看来我需要两个 Functor 实例，一个用于更改内容，另一个用于更改数组索引。

我认为 Traversable 是正确的选择，但所提供函数的签名都不与 applyPermutation 匹配。

预先感谢您的帮助。

Answer 1

Functor does not work, since I use it to change the content of the tree, not its indexing scheme. It seems I would need two instances of Functor, one to change the content and the other to change the array indices.

你的直觉是正确的:一个作用于 Neighborhood a 的仿函数field 会做你需要的事情，将这样的东西称为“仿函数”是正确的。这是 applyPermutation 的一种可能的重构:

{-# LANGUAGE LambdaCase #-}

-- I prefer case syntax for this sort of definition; with it, there is less stuff
-- that needs to be repeated. LambdaCase is the icing on the cake: it frees me
-- me from naming the Tree a argument -- without it I would be forced to write
-- mapOverNeighborhoods f t = case t of {- etc. -}
mapOverNeighborhoods :: (Neighborhood a -> Neighborhood a) -> Tree a -> Tree a
mapOverNeighborhoods f = \case 
    Empty -> Empty
    Leaf x -> Leaf x
    Internal x ts -> Internal x (f (mapOverNeighborhoods f <$> ts))

applyPermutation :: Permutation -> Tree a -> Tree a
applyPermutation perm = mapOverNeighborhoods applyPermutation'
    where applyPermutation' = ixmap (Xp, Zm) (perm !)

(您可能更愿意更进一步，使用直接采用 UnitDirection -> UnitDirection 的映射，而不是 Neighborhood a -> Neighborhood a 。我这样做主要是为了让它更接近地反射(reflect)这个答案的其余部分，但也因为它可以说是一个更诚实的界面——重新排列 Array 中的索引并不像对索引应用任意函数那么简单。)

定义另一个仿函数的尝试有两个限制:

• 我们已经有一个 Functor实例，正如你所指出的。仅针对此用例进行替换并定义 newtype 是不明智的。因为这太烦人了。

• 即使事实并非如此，mapOverNeighborhoods不能做成Functor例如，如 fmap任意取a -> b功能，改变社区类型是不可能的。

这两个问题已由光学库解决，例如 lens (不过，如果您最终在代码库中只使用光学来完成这一件事，那么您可能更喜欢 microlens 以获得更小的依赖足迹)。

{-# LANGUAGE TemplateHaskell #-} -- makeLenses needs this.
{-# LANGUAGE DeriveFunctor #-} -- For the sake of convenience.
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}

-- Record fields on sum types are nasty; these, however, are only here for the
-- sake of automatically generating optics with makeLenses, so it's okay.
data Tree a
    = Empty 
    | Leaf { _value :: a } 
    | Internal { _value :: a, _neighborhood :: Neighborhood a }
    deriving (Eq, Show, Functor, Foldable, Traversable)
makeLenses ''Tree

applyPermutation :: Permutation -> Tree a -> Tree a
applyPermutation perm = over neighborhood applyPermutation'
    where applyPermutation' = ixmap (Xp, Zm) (perm !)

over (中缀拼写: %~ )实际上是 fmap它允许选择目标。我们通过向其传递适当的光学器件(在本例中为 neighborhood ，即 Traversal ，以树中的所有邻域为目标 - over neighborhood 可以解读为“所有邻域的 map ”)来实现这一点。请注意，我们无法更改邻域类型这一事实并不是问题(而且，在其他情况下，也可以使用类型更改光学器件)。

最后一点， neighborhoods 的类型是 Traversal' (Tree a) (Neighborhood a) 。如果我们展开Traversal'输入同义词，我们得到:

GHCi> :t neighborhood
neighborhood
  :: Applicative f =>
     (Neighborhood a -> f (Neighborhood a)) -> Tree a -> f (Tree a)

虽然深入探讨为什么会导致这个答案太长，但值得注意的是，这很像 traverse 的签名对于 Tree ...

GHCi> :set -XTypeApplications
GHCi> :t traverse @Tree
traverse @Tree
  :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)

...只不过它作用于邻域而不是值(参见 fmap 和 mapOverNeighborhoods 之间的相似之处)。事实上，如果您要充分实现traverse如果与该类型类似，您将能够使用它来代替 makeLenses 自动生成的类型.