definition of List.transpose

Doug McIlroy doug at
Sun Mar 1 23:22:43 UTC 2015

Not having participated in haskell' before, I'm not sure how
to put these perfecting amendments--mot langauge changes--into
the pot.

Doug McIlroy

The specification of List.transpose does not tell what a "column"
of a ragged-right list of rows is, either directly or by example.
Here is a fuller spec, plus some properties.


A generalization of the customary matrix operation, transpose returns
a list of columns extracted from a list of rows.  The jth column
of x::[[a]] comprises all extant elements x!!i!!j ordered by i.

In the subdomain of list structures that have positive nonincreasing
row lengths, e.g. matrices and Young tableaux,
	transpose . transpose === id
	(transpose x) !! i !! j === x !! j !! i
In general
	transpose . transpose . transpose === transpose
	sum . map length . transpose === sum . map length

Example: transpose [[10,11],[20],[],[30,31,32]] === [[10,20,30],[11,31],[32]]


The reference definition can be simplified:

transpose xss = case [h | (h:_) <- xss] of
	[] -> []
	hs -> hs : transpose [tss | (_:tss) <- xss]

More information about the Haskell-prime mailing list