Is there a standard name for this operation?

Question

So in working on a Haskell project, I've ended up writing the following function

reGrid :: [[[a]]] -> [[a]]
reGrid [] = []
reGrid xs | any null xs = []
          | otherwise = (concat $ map head xs) : reGrid (map tail xs)

For those who don't speak Haskell, this takes a list of matrices, and joins the corresponding rows into a new matrix.

Its popped up several times in this project, and I the feeling that this is some kind of common operation that I've missed.

Is there a standard name for this operation? Searching Hoogle for

[[[a]]] -> [[a]

Yields nothing useful.

Answer 1

You have a bunch of things, and you want to turn them into one thing. The usual way to do that is with a fold of some sort. So let's start off with that:

regrid [] = []
regrid xs = foldr go (repeat []) xs

Now suppose you have one matrix and you also have the result of re-gridding the rest. How can you combine them? Well, you want to merge the rows together until one runs out, which sounds like a job for zipWith. So putting everything together,

regrid = foldr (zipWith (++)) []

That's not one standard function, but it's short and doesn't monkey around with partial functions. It does, however, have an efficiency problem if the list is long. To fix that, you could switch to a left fold, but getting the strictness right will be tricky. I can write that up later.

Answer 2

Your function is very similar (but not identical) to this one:

reGrid' = map concat . transpose

For example, my QuickCheck property \xs -> reGrid xs == reGrid' xs turns up this difference:

*Main> reGrid [[[]],[]]
[]
*Main> reGrid' [[[]],[]]
[[]]

In short, your version will "cut off" more stuff that you might actually care about (or not). For a more telling example:

*Main> reGrid [["abc"],[]]
[]
*Main> reGrid' [["abc"],[]]
["abc"]

You can judge for yourself whether the cases where they differ matter to you.