evan_tech -- run length encoding and arrows

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.)

jwz

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

xlerb	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

raevnos	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

flipzagging	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

ext_57786	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 ;-)
reply to this

evan	Re: A slightly more readable solution... Yeah. The point of this post was just that the &&& operator just generalizes the (\x -> (foo x, bar x)) pattern. I think your way of explaining it was clearer, though. :)
reply to this

evan_tech

run length encoding and arrows

A slightly more readable solution...

Re: A slightly more readable solution...