在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

我想Tree通过置换索引来定义一个遍历实例的函数Array UnitDir (Tree a)(所以它是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不起作用,因为我用它来改变树的内容,而不是它的索引方案.看来我需要两个实例Functor,一个用于更改内容,另一个用于更改数组索引.

你的直觉就在于:在Neighborhood a场上行动的仿函数会做你需要的东西,把这样的东西称为"仿函数"是正确的.这是一个可能的重构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.我没有这样做主要是为了让它更接近于这个答案的其余部分,但也因为它可以说是一个更诚实的界面 - - 重新排列a中的索引Array并不像将任意函数应用于索引那样简单.)

这种尝试定义另一个仿函数有两个局限性:

• Functor正如你所指出的,我们已经有了一个实例.仅仅为这个用例替换它是不明智的,并且newtype为它定义一个太烦人了.

• 即使不是这种情况,mapOverNeighborhoods也不能成为一个Functor实例,因为fmap需要任意a -> b函数,并且改变邻域的类型不是一种选择.

这两个问题是由光学库,比如解决镜头(如果你最终使用的只是这样一件事光学在你的代码库,不过,你可能更喜欢微透镜的依赖性较小的占地面积).

{-# 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可以读作"所有邻域的地图").请注意,我们无法改变邻域类型的事实不是问题(并且在其他情况下,也可能有类型变化光学器件).

最后一点,类型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.