Just a quick implementation of a RLE algorithm for lists in haskell. We compress a list by converting “runs” of consecutive elements into a tuple of the form: (run length, element).
1 2 3 4 5 6 7 8
&&& combinator looks foreign to you, check out David R. Maciver’s
very enlightening blog about Arrow functions.
I’m always curious to see how naive-looking functions like the above compare in performance to a from-scratch implementation with explicit recursion, so I came up with the following:
1 2 3 4 5 6
I tested both functions on a list of 100,000 random 1s and 0s and found the
explicit version to be only marginally better performing, completing the list
49 ticks & 130Mb, compared to
54 ticks & 139 Mb for the one-liner!