运行-Repa 数组的长度编码

Question

我有一个由 0 和 1 组成的一维 Repa 数组，我想计算它的运行长度编码。例如：转 [0,0,1,1,1,0,0,0,1,0,1,1] into [2,3,3,1,1,2] 或类似的东西。（由于可读性，我使用列表表示法）

理想情况下，我想要 1 的运行长度并忽略 0。所以[0,0,1,1,1,0,0,0,1,0,1,1] becomes [3,1,2]。

我希望结果也是一个 (Repa) 数组。

如何使用 Repa 执行此操作？我不能使用 map 或 traverse，因为它们一次只给我一个元素。我可以尝试 fold 使用某种特殊类型的累加器，但这似乎并不理想，我什至不知道它是否可能（由于 monad 法则）。

Answer 1

我目前只是遍历数组并返回一个列表，而不使用任何 Repa 函数。我正在研究 Booleans 而不是 1 和 0，但算法是相同的。之后我将此列表转换为 Repa 数组。

runLength :: Array U DIM1 Bool -> [Length]
runLength arr = go ([], 0, False) 0 arr
  where
    Z :. n = extent arr
    go :: Accumulator -> Int -> Array U DIM1 Bool -> [Length]
    go !acc@(xs, c, b) !i !arr | i == n = if c > 0 then c:xs else xs
                               | otherwise =
                                 if unsafeIndex arr (Z :. i)
                                 then if b
                                      then go (xs, c+1, b) (i+1) arr
                                      else go (xs, 1, True) (i+1) arr
                                 else if b
                                      then go (c:xs, 0, False) (i+1) arr
                                      else go (xs, 0, False) (i+1) arr

运行-Repa 数组的长度编码

Run-length encoding of a Repa array

arrays

haskell

run-length-encoding

repa