递归列表转换中重叠实例的行为

Question

在我的递归列表转换中，重叠实例的优先级未达到预期。

我正在尝试创建一个对任意深度的嵌套列表进行操作的转置函数。目标是有两个函数，一个可以将 'highest dimension' 转置为 'lowest'，也就是说，维度为 [a, b, c] 的嵌套列表将转换为具有维度 [b, c, a] 和相反的维度 [a, b, c] 到 [c, a, b]。

{-# LANGUAGE FlexibleContexts, FlexibleInstances #-}
module Transpose where
import Data.List

class DeepTranspose a where
    deepTransposeDown :: a -> a
    deepTransposeUp   :: a -> a

instance {-# OVERLAPPING #-} (DeepTranspose a) => DeepTranspose [[a]] where
    deepTransposeDown = map deepTransposeDown.transpose
    deepTransposeUp   = transpose.map deepTransposeUp

instance {-# OVERLAPPABLE #-} DeepTranspose a where
    deepTransposeDown = id
    deepTransposeUp   = id

我的意图是第一个实例应用于所有嵌套列表，第二个实例应用于其他所有内容。

下面是一些测试示例，'ref' 表示函数的预期行为


a = [[1,2],[3,4]] :: [[Int]]
b = [[[1,2],[3,4]],[[5,6],[7,8]]] :: [[[Int]]]
c = [[[[1,2],[3,4]],[[5,6],[7,8]]],[[[9,10],[11,12]],[[13,14],[15,16]]]] :: [[[[Int]]]]

ref1a = transpose a
test1a = deepTransposeDown a
ref1b = map transpose.transpose $ b
test1b = deepTransposeDown b
ref1c = map (map transpose.transpose).transpose $ c
test1c = deepTransposeDown c

ref2a = transpose a
test2a = deepTransposeUp a
ref2b = transpose.map transpose $ b
test2b = deepTransposeUp b
ref2c = transpose.map (transpose.map transpose) $ c
test2c = deepTransposeUp c

参考和测试的结果是不同的，例如：

>>>c
[[[[1,2],[3,4]],[[5,6],[7,8]]],[[[9,10],[11,12]],[[13,14],[15,16]]]]
>>>ref1c
[[[[1,9],[2,10]],[[3,11],[4,12]]],[[[5,13],[6,14]],[[7,15],[8,16]]]]
>>>test1c
[[[[1,2],[3,4]],[[9,10],[11,12]]],[[[5,6],[7,8]],[[13,14],[15,16]]]]

我没有太多使用重叠实例的经验，所以我不确定如何选择实例。在我看来，换位似乎只发生在第一个 'layer' 中，之后使用第二个实例 (id)。这有效地将它变成了正常的转置，这不是很有趣。

Answer 1

我不完全明白这是怎么回事，但你需要

instance {-# OVERLAPPING #-} (DeepTranspose [a]) => DeepTranspose [[a]] where
                                         -- ^^^ --

这是因为在您的实例中 map deepTransposeDown.transpose 需要 DeepTranspose [a]。如果你只需要 DeepTranspose a，这还不足以满足要求的约束，所以它回落到 id 实例（即使 a=[[Int]]）。

递归列表转换中重叠实例的行为

Behaviour of overlapping instances in recursive list transform

haskell

overlapping-instances