## Saturday, August 12, 2017

### Transpose

Transpose

If we are to represent a row of a matrix as a list of numbers, then a matrix can naturally be represented as a list of lists of numbers.

The transpose of a matrix $\mathbf{A}$ is a new matrix denoted $\mathbf{A^{T}}$. The traditional mathematical definition of $\mathbf{A^{T}}$ is expressed as saying the $i$ th row, $j$ th column element of $\mathbf{A^{T}}$ is the $j$ th row, $i$ th column element of $\mathbf{A}$:

$\left[\mathbf{A}\right]_{ij} = \left[\mathbf{A^{T}}\right]_{ji}$.

As definitions go, this isn't terribly helpful in explaining how to compute a transpose. A better equivalent definition for the functional programmer is : the matrix obtained by writing the columns of $\mathbf{A}$ as the rows of $\mathbf{A^{T}}$.

An elegant program for computing a transpose follows from a direct translation of that last definition.

let rec transpose (ls : 'a list list) : 'a list list =
match ls with
| [] | [] :: _ -> []
| ls -> List.map (List.hd) ls :: transpose (List.map (List.tl) ls)


It is not at all hard to understand how the program works when you've seen an example:

transpose [[1; 2]; [3; 4;]; [5; 6]]
= [1; 3; 5] :: transpose [; [4;]; ]
= [1; 3; 5] :: [2; 4; 6] :: transpose [[]; []; []]
= [1; 3; 5] :: [2; 4; 6] :: []
= [[1; 3; 5]; [2; 4; 6]]

Being as pretty as it is, one is inclined to leave things be but, as a practical matter it should be rephrased to be tail-recursive.

let rec transpose (ls : 'a list list) : 'a list list  =
let rec transpose_rec acc = function
| [] | [] :: _ -> List.rev acc
| ls -> transpose_rec (List.map (List.hd) ls :: acc) (List.map (List.tl) ls)
in transpose_rec [] ls


References:
"An Introduction to Functional Programming Systems Using Haskell" -- Davie A J T., 1992
{"ft_lang_label":"__label__en","ft_lang_prob":0.82193094,"math_prob":0.9964819,"size":1652,"snap":"2019-26-2019-30","text_gpt3_token_len":495,"char_repetition_ratio":0.14563107,"word_repetition_ratio":0.11513158,"special_character_ratio":0.3510896,"punctuation_ratio":0.20718232,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9996179,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-23T13:27:44Z\",\"WARC-Record-ID\":\"<urn:uuid:ad7af90a-7229-42ed-a9eb-60857d853251>\",\"Content-Length\":\"87856\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:865392d1-55e4-4e30-b481-1f897eb1e8ca>\",\"WARC-Concurrent-To\":\"<urn:uuid:270d2cb5-2421-499e-99dd-9b6280fdfcc2>\",\"WARC-IP-Address\":\"172.217.3.115\",\"WARC-Target-URI\":\"http://blog.shaynefletcher.org/2017/08/transpose.html\",\"WARC-Payload-Digest\":\"sha1:CVGMZBHQN6QNTWPX5YJAL44MQP5JKV2R\",\"WARC-Block-Digest\":\"sha1:4Y7KKDGMBCPZTD46TY3AFETI72EWKU7V\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195529406.97_warc_CC-MAIN-20190723130306-20190723152306-00319.warc.gz\"}"}