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.
Subscribe to:
Post Comments (Atom)
13 comments:
This is one of those simple pleasures, that I find incredibly beautiful.
zip2DWith = zipWith . zipWith
zip3DWith = zipWith . zipWith . zipWith
zip2DWith3 = zipWith3 . zipWith3
etc.
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.
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.
Luke said:
zip2DWith = zipWith . zipWith
zip3DWith = zipWith . zipWith . zipWith
zip2DWith3 = zipWith3 . zipWith3
This gives rise to:
fpow f n = foldr (.) id $ replicate n f
Then,
zip2DWith = zipWith `fpow` 2
zip4DWith = zipWith `fpow` 4
etc. :)
Arnar Birgisson said:
fpow f n = foldr (.) id $ replicate n f
Very nice.
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.
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
By the way, you don't need nested comprehensions to define indices2d. Just write:
indices2d = [(r,c) | r <- [0..], c <- [0..]]
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.
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
Absolutely, feel free to use the code.
Great! Thanks very much - keep up the good work! :)
- Andy
doh! Of course. Brain lapse there. Thanks, Arnar.
Post a Comment