Repa数组的游程编码

Question

我有一个由0和1组成的一维Repa数组，我想计算它的游程编码。例如: Turn [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，但这似乎不是理想的，我不知道它甚至是可能的(由于单数定律)。

Answer 1

我目前只是迭代数组并返回一个列表，而不使用任何Repa函数。我正在研究Boolean，而不是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