转置嵌套数据结构
Transpose nested data structures
我需要一个像 Vector [Vector a] -> Vector [Vector a]
这样的函数,其中所有内容都在同一个列表索引中,但是(对于每个列表索引)第 j 个内部向量的第 i 个元素变为第 j 个- 第 i 个内部向量的第一个元素。 我怀疑我做的比需要的难多了。
我想我特别想使用 this implementation of fixed-length vectors,但我可以考虑其他选项。
我用它来代替 Pair
class 我写的是为了简单起见,但我的实现在很大程度上依赖于针对 Pair
结构的模式匹配,在我认为这种方式不适用于 Vec n
.
Pair
class 几乎不相关;它类似于 Vec nat2
,但我只实现了我认为需要的东西:
data Pair a where
Pair :: a -> a -> Pair a
deriving (Read, Show, Eq)
instance Functor Pair where
fmap f (Pair a1 a2) = Pair (f a1) (f a2)
instance Applicative Pair where
pure a = Pair a a
(Pair f1 f2) <*> (Pair a1 a2) = Pair (f1 a1) (f2 a2)
instance Foldable Pair where
foldr f b (Pair a1 a2) = a1 `f` (a2 `f` b)
(!) :: Pair a -> Bool -> a
(Pair a1 a2) ! b = if b then a2 else a1
universe :: Pair Bool
universe = Pair False True
工作代码:
transpose :: Pair [Pair a] -> Pair [Pair a]
transpose (Pair b1s b2s) = t' b1s b2s
where t' ((Pair a11 a12) : a1s) ((Pair a21 a22) : a2s)
= Pair ((Pair a11 a21) :) ((Pair a12 a22) :) <*> t' a1s a2s
t' [] [] = pure []
-- A runtime error here is ok; I have external guarantees that this won't happen.
t' _ _ = error "Transposition requires the lists to be of equal length."
示例:
> let subject = Pair [
Pair (1, 1, 1) (1, 1, 2),
Pair (1, 2, 1) (1, 2, 2),
Pair (1, 3, 1) (1, 3, 2)
] [
Pair (2, 1, 1) (2, 1, 2),
Pair (2, 2, 1) (2, 2, 2),
Pair (2, 3, 1) (2, 3, 2)
]
> transpose subject
↠ Pair [
Pair (1,1,1) (2,1,1),
Pair (1,2,1) (2,2,1),
Pair (1,3,1) (2,3,1)
] [
Pair (1,1,2) (2,1,2),
Pair (1,2,2) (2,2,2),
Pair (1,3,2) (2,3,2)
]
经过一些努力,我可以几乎 得到一个只使用 list/functor/applicative/index-able 运算符而不是模式匹配的实现(因此应该适用于 Vec n
) , 但我总是卡住。
如何重写我的 transpose
函数以在其他结构上工作 类似 Pair
,但具有参数大小?
我想我会使用 ZipList
和一个新的类似的 ZipVector
来实现这一点。我们将从更标准的 transpose
:
开始
transposeVV :: Vector (Vector a) -> Vector (Vector a)
transposeVV = getZipVector . traverse Finite
为了能够使用它,我们需要能够将两个 Vector
并排放置;我们将通过另外两个彼此相反的转置来完成此操作:
transposeVL :: Vector [a] -> [Vector a]
transposeVL = getZipList . traverse ZipList
transposeLV :: [Vector a] -> Vector [a]
transposeLV = getZipVector . traverse Finite
你想要的东西现在是这些的组合:
transposeVlV :: Vector [Vector a] -> Vector [Vector a]
transposeVlV = transposeLV . fmap transposeVV . transposeVL
好吧,我隐藏了一些功能 ZipVector
。那看起来像什么?这很容易;然而,与 ZipList
相比,一个转折点是我们无法轻松构造无限向量。没什么大不了的,我们会伪造它。 (显然,您的长度索引向量不需要使用这个技巧。)
data ZipVector a
= Inf a
| Finite (Vector a)
deriving Functor
getZipVector :: ZipVector a -> Vector a
getZipVector (Inf a) = V.singleton a -- hmmmm...
getZipVector (Finite as) = as
instance Applicative ZipVector where
pure = Inf
Inf f <*> Inf x = Inf (f x)
Inf f <*> Finite xs = Finite (f <$> xs)
Finite fs <*> Inf x = Finite (($x) <$> fs)
Finite fs <*> Finite xs = Finite (V.zipWith ($) fs xs)
我们现在可以试试了。首先让我们定义你的 subject
:
subject :: Vector [Vector (Int, Int, Int)]
subject =
V.generate 2 $ \i ->
flip map [0..2] $ \j ->
V.generate 2 $ \k ->
(i+1, j+1, k+1)
然后,在 ghci:
> transposeVlV subject
[[[(1,1,1),(2,1,1)],[(1,2,1),(2,2,1)],[(1,3,1),(2,3,1)]],[[(1,1,2),(2,1,2)],[(1,2,2),(2,2,2)],[(1,3,2),(2,3,2)]]]
我需要一个像 Vector [Vector a] -> Vector [Vector a]
这样的函数,其中所有内容都在同一个列表索引中,但是(对于每个列表索引)第 j 个内部向量的第 i 个元素变为第 j 个- 第 i 个内部向量的第一个元素。 我怀疑我做的比需要的难多了。
我想我特别想使用 this implementation of fixed-length vectors,但我可以考虑其他选项。
我用它来代替 Pair
class 我写的是为了简单起见,但我的实现在很大程度上依赖于针对 Pair
结构的模式匹配,在我认为这种方式不适用于 Vec n
.
Pair
class 几乎不相关;它类似于 Vec nat2
,但我只实现了我认为需要的东西:
data Pair a where
Pair :: a -> a -> Pair a
deriving (Read, Show, Eq)
instance Functor Pair where
fmap f (Pair a1 a2) = Pair (f a1) (f a2)
instance Applicative Pair where
pure a = Pair a a
(Pair f1 f2) <*> (Pair a1 a2) = Pair (f1 a1) (f2 a2)
instance Foldable Pair where
foldr f b (Pair a1 a2) = a1 `f` (a2 `f` b)
(!) :: Pair a -> Bool -> a
(Pair a1 a2) ! b = if b then a2 else a1
universe :: Pair Bool
universe = Pair False True
工作代码:
transpose :: Pair [Pair a] -> Pair [Pair a]
transpose (Pair b1s b2s) = t' b1s b2s
where t' ((Pair a11 a12) : a1s) ((Pair a21 a22) : a2s)
= Pair ((Pair a11 a21) :) ((Pair a12 a22) :) <*> t' a1s a2s
t' [] [] = pure []
-- A runtime error here is ok; I have external guarantees that this won't happen.
t' _ _ = error "Transposition requires the lists to be of equal length."
示例:
> let subject = Pair [
Pair (1, 1, 1) (1, 1, 2),
Pair (1, 2, 1) (1, 2, 2),
Pair (1, 3, 1) (1, 3, 2)
] [
Pair (2, 1, 1) (2, 1, 2),
Pair (2, 2, 1) (2, 2, 2),
Pair (2, 3, 1) (2, 3, 2)
]
> transpose subject
↠ Pair [
Pair (1,1,1) (2,1,1),
Pair (1,2,1) (2,2,1),
Pair (1,3,1) (2,3,1)
] [
Pair (1,1,2) (2,1,2),
Pair (1,2,2) (2,2,2),
Pair (1,3,2) (2,3,2)
]
经过一些努力,我可以几乎 得到一个只使用 list/functor/applicative/index-able 运算符而不是模式匹配的实现(因此应该适用于 Vec n
) , 但我总是卡住。
如何重写我的 transpose
函数以在其他结构上工作 类似 Pair
,但具有参数大小?
我想我会使用 ZipList
和一个新的类似的 ZipVector
来实现这一点。我们将从更标准的 transpose
:
transposeVV :: Vector (Vector a) -> Vector (Vector a)
transposeVV = getZipVector . traverse Finite
为了能够使用它,我们需要能够将两个 Vector
并排放置;我们将通过另外两个彼此相反的转置来完成此操作:
transposeVL :: Vector [a] -> [Vector a]
transposeVL = getZipList . traverse ZipList
transposeLV :: [Vector a] -> Vector [a]
transposeLV = getZipVector . traverse Finite
你想要的东西现在是这些的组合:
transposeVlV :: Vector [Vector a] -> Vector [Vector a]
transposeVlV = transposeLV . fmap transposeVV . transposeVL
好吧,我隐藏了一些功能 ZipVector
。那看起来像什么?这很容易;然而,与 ZipList
相比,一个转折点是我们无法轻松构造无限向量。没什么大不了的,我们会伪造它。 (显然,您的长度索引向量不需要使用这个技巧。)
data ZipVector a
= Inf a
| Finite (Vector a)
deriving Functor
getZipVector :: ZipVector a -> Vector a
getZipVector (Inf a) = V.singleton a -- hmmmm...
getZipVector (Finite as) = as
instance Applicative ZipVector where
pure = Inf
Inf f <*> Inf x = Inf (f x)
Inf f <*> Finite xs = Finite (f <$> xs)
Finite fs <*> Inf x = Finite (($x) <$> fs)
Finite fs <*> Finite xs = Finite (V.zipWith ($) fs xs)
我们现在可以试试了。首先让我们定义你的 subject
:
subject :: Vector [Vector (Int, Int, Int)]
subject =
V.generate 2 $ \i ->
flip map [0..2] $ \j ->
V.generate 2 $ \k ->
(i+1, j+1, k+1)
然后,在 ghci:
> transposeVlV subject
[[[(1,1,1),(2,1,1)],[(1,2,1),(2,2,1)],[(1,3,1),(2,3,1)]],[[(1,1,2),(2,1,2)],[(1,2,2),(2,2,2)],[(1,3,2),(2,3,2)]]]