evan_tech

12:42 pm, 31 Jul 07

run length encoding and arrows

Run length encoding in Haskell casually tosses in this bit:
encode = map (length &&& head) . group
Which produces RLE'd tuples:
> encode "aaaabbaaa"
[(4,'a'),(2,'b'),(3,'a')]

But what's this &&& bit? It's from Control.Arrow, the implementation of arrows, which are reportedly a generalization of monads. The last time I tried to look at this was before I grokked monads so it's probably worth another look, but the superficial understanding needed here is that &&& runs two functions "in parallel" (not as in simultaneously, just in that they're not interacting) and produces a pair of their two outputs.

That is,
> :t length &&& head
length &&& head :: [a] -> (Int, a)

where the first component of the tuple is the length and the second is the head of the list.

What a peculiar but also imaginably useful operator! (Of course, in the arrows docs the application of this just to functions is the most basic of the many generalizations.)

• If I understand that right, that is the Common Lisp 'map' function:(map 'list '(lambda (x y) (list x y)) '(a b c) '(1 2 3)) ==> ((a 1) (b 2) (c 3)) reply to this
• It's a bit more like this, in Scheme: > (define (&&& f g) (lambda (x) (cons (f x) (g x)))) &&& > (map (&&& length car) '((a a a a) (b b) (a a a))) ((4 . a) (2 . b) (3 . a)) reply to this
• I've used this in other (functional) languages, but not to the point of having a function/operator to express it -- it's never been complex enough to express to be worth the bother. For example, in scheme: (map (lambda (x) (list (f x) (g x))) some-list) reply to this
• Wow, come to think of it, that pattern is very common. I just wrote a little object serializer that does something really similar, iterating through various properties of the object and making appropriate string conversions. Only now I'm always going to wish I had Haskell. Thanks a lot, dude. reply to this
• A slightly more readable solution...

encode = map (\x -> (length x, head x)) . group

also seems to work, and has the benefit of being understandable by mortals ;-) 