Monday, August 4, 2008

Two-dimensional zip

I've been doing battle with things like CSS recently (the W3C will be first against the wall when the revolution comes,) so it was a pleasure to run into a little Haskell puzzle and an elegant solution.

I was working with a matrix represented with a list of lists: [[a]]. I wanted to add the row and column indices to each element, giving: [[((Integer,Integer),a)]].

This isn't a pattern I remember seeing before, but it seemed simple enough, so I just hacked away. Here's my first try:

> index grid = zipWith indexrow [0..] grid
>     where indexrow rn rs = zipWith (\cn r -> ((rn,cn),r)) [0..] rs

Serviceable, but neither pretty nor general. The one dimensional case is so elegant; for any list, you can add indices with:

> index1d xs = zip [0..] xs

The zip function is simple and the infinite list of indices covers all cases. So it occurred to me I was looking for two things: a two-dimensional version of zip; and a grid of index tuples, semi-infinite in both directions.

Both turned out to be simple enough. Here's the grid of tuples using list comprehensions:

> indices2d = [[(r,c) | c <- [0..]] | r <- [0..]]

And the two-dimensional zip:

> zip2d = zipWith zip

And it's easy to reproduce the "With" version:

> zip2dWith f = zipWith (zipWith f)

So now my function looks like this:

> index2d grid = zip2d indices2d grid

or just:

> index2d' = zip2d indices2d

This version is clearer, simpler and easily generalizable to higher dimensions.


Luke Palmer said...

This is one of those simple pleasures, that I find incredibly beautiful.

zip2DWith = zipWith . zipWith
zip3DWith = zipWith . zipWith . zipWith
zip2DWith3 = zipWith3 . zipWith3

Luke Palmer said...

Of course this relates to zipping being an applicative functor. So the implementation for zip2DWith is just the applicative functor instance for ZipList :. ZipList (where (:.) is from TypeCompose), zip2DWith 3 is just liftA3 on that functor, etc.

Clifford Beshers said...

I thought about exploring the point-free forms some more but decided it was time to post. Thanks for the TypeCompose observation as well. I haven't read that code since it first came out; clearly time to catch up. I was thinking that Conal must have done something similar to this zip in his Image work. I remember he was thinking about how to make the sets infinite in both directions.

Arnar Birgisson said...

Luke said:

zip2DWith = zipWith . zipWith
zip3DWith = zipWith . zipWith . zipWith
zip2DWith3 = zipWith3 . zipWith3

This gives rise to:

fpow f n = foldr (.) id $ replicate n f


zip2DWith = zipWith `fpow` 2
zip4DWith = zipWith `fpow` 4

etc. :)

Clifford Beshers said...

Arnar Birgisson said:

fpow f n = foldr (.) id $ replicate n f

Very nice.

Anonymous said...

Since fpow really means iterated function, one might express it thus:

fiter f n x = iterate f x !! n

Or, to emphasize operating on functions:

fiter f n = \x -> iterate f x !! n

Unfortunately some pointless-y goodness is lost, though.

Arnar Birgisson said...

Ah, nice. I didn't know about iterate.

If you want at least the rhs of your second definition to be point-free, it is not too exotic:

fiter f n = (!!n) . iterate f

Brent said...

By the way, you don't need nested comprehensions to define indices2d. Just write:

indices2d = [(r,c) | r <- [0..], c <- [0..]]

Arnar Birgisson said...

Brent said: indices2d = [(r,c) | r <- [0..], c <- [0..]]

That doesn't work, in fact it is equivalent to [(0,c) | c <- [0..]]

The type is not even the same. What Clifford needed was a two-dimensional list of the type [[(Integer,Integer)]], i.e. a 2-D lattice of integers.

obsidian123 said...

Hi Clifford!

Really nice code - I love seeing elegant solutions like this!

I'm looking at doing a public-domain crosstab app in Haskell, so I was wondering - could I include this code? (I'll give acknowledgement of course, if it is used).

Thanks for doing this post! Bye for now -
- Andy

Clifford Beshers said...

Absolutely, feel free to use the code.

obsidian123 said...

Great! Thanks very much - keep up the good work! :)
- Andy

Brent said...

doh! Of course. Brain lapse there. Thanks, Arnar.