Tuesday, June 20, 2017

Processing a generic Data.Array matrix

I had an interesting Haskell problem the other week: work on columns and rows of a Data.Array i e.

You only have the Ix i, Ord e class constraints, which make sense because the index must be a Data.Ix. The elements also must be Ord to be able to process them.

The thing about Data.Ix is that it's very opaque. It only extends Ord. There is nothing matrix-related in it. One could use Data.Array for a lot of data structures!

But if you do know it's a matrix, although you have no explicit class constraint, there is a nice trick to use: two neighbouring cells will have a Data.Ix.rangeSize of 2!

So, the rows may be extracted by this little function:

byRows :: Ix i => [i] -> [[i]]
byRows indices = incGroupBy isNeighbour $ indices
    where isNeighbour x y = 2 == rangeSize (x, y)

which is called like

process :: (Ix i, Ord e) => Array i e -> Something
process matrix =

    let rows = byRows $ indices matrix
    ...

Note the unknown incGroupBy which is a groupBy that takes pairs incrementally.

That's it! I had a lot of ideas about using rangeSize to figure out the matrix dimensions, but pairing cells this way was really clean.

The Trouble with Harry time loop

I saw The Trouble with Harry (1955) a while back and it didn't have a big impression on me. But recently I rewatched it and was amazed a...