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).
I'm currently just iterating over the array and returning a list without using any Repa
function. I'm working on Boolean
s 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