arrayshaskellrun-length-encodingrepa

Run-length encoding of a Repa array


I have a one-dimensional Repa array that consists of 0's and 1's and I want to calculate its run-length encoding. E.g.: Turn [0,0,1,1,1,0,0,0,1,0,1,1] into [2,3,3,1,1,2] or something similar. (I'm using a list representation because of readability)

Ideally, I would like the run-length of the 1's and ignore the 0's. So [0,0,1,1,1,0,0,0,1,0,1,1] becomes [3,1,2].

I would like the result to be a (Repa) array as well.

How can I do this using Repa? I can't use map or traverse since they only give me one element at a time. I could try to fold with some special kind of accumulator but that doesn't seem to be ideal and I don't know it it's even possible (due to monad laws).


Solution

  • I'm currently just iterating over the array and returning a list without using any Repa function. I'm working on Booleans instead of 1's and 0's but the algorithm is the same. I'm converting this list to a Repa Array afterwards.

    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