CODEWITHSUNDEEP
f#
kev
kev

Reputation: 161864

Help me to explain the F# Matrix transpose function

There is a Matrix transpose function:

let rec transpose = function
    | (_::_)::_ as M -> List.map List.head M :: transpose (List.map List.tail M)
    | _ -> []

[[1; 2; 3]; [4; 5; 6]; [7; 8; 9]] |> transpose |> printfn "%A"

It works fine.
What does ( _ :: _ ) :: _ mean?
I don't understand the whole code!
Who can explain it?
Thank You!

I find the answer:
( _ :: _ ) :: _ is a pattern matching on value of type list of lists of ints

If i write:

let rec transpose (M:int list list) =
    match M with
    | hd::tl -> List.map List.head M :: transpose (List.map List.tail M)
    | _ -> []

It throw an runtime exception. Is there something wrong with hd?
Yes, it make something like [ [ ];[ ];[ ] ] when call List.tail, then it throws exception when call List.head!

Problem Solved!
Thank you all!

Upvotes: 15

Views: 5748

Answers (5)

zorrooo
zorrooo

Reputation: 65

I'm sorry for bumping an outdated thread, but your original answer is almost right. The only thing that's wrong is the termination condition for an empty list. The code should look something like this: 

let rec transpose M = 
    match M with 
    | []::_ -> []
    | _ -> List.map List.head M::transpose(List.map List.tail M)

Upvotes: 3

Tomas Petricek
Tomas Petricek

Reputation: 243096

The function is not particularly readably written, which may be the reason for your confusion. The construct (_::_)::_ is a pattern matching on value of type list of lists of ints that says that the first case should be run when you get a non-empty list of non-empty lists.

The same thing can be written like this. This is more verbose, but it should be clear what is going on here:

let rec transpose matrix = 
  match matrix with   // matrix is a list<list<int>>
  | row::rows ->      // case when the list of rows is non-empty
    match row with    // rows is a list<int>
    | col::cols ->    // case when the row is non-empty
      // Take first elements from all rows of the matrix
      let first = List.map List.head matrix
      // Take remaining elements from all rows of the matrix
      // and then transpose the resulting matrix
      let rest = transpose (List.map List.tail matrix) 
      first :: rest
    | _ -> []
  | _ -> []

As you can see, we don't really need the values row, rows, col and cols. That's why the original implementation replaces these with _ (which ignores the value and only checkes that the list can be decomposed in the required way).

In the recursive case, we deconstruct the matrix like this:

[ [ x; y; y ];                               [ y; y ] 
  [ x; y; y ];   =>  [ x; x; x] :: transpose [ y; y ]
  [ x; y; y ] ]                              [ y; y ]

I hope that the picture makes it more clear for you!

Upvotes: 30

J D
J D

Reputation: 48687

This maps head over the lists to extract the first column and uses that to form the first row prepended to the result of transposing the remaining columns.

Upvotes: 1

Turtle
Turtle

Reputation: 1350

This may also help you:

Understanding a Matrix transposition Function in Haskell

It is a very similar function in a similar programming language (Haskell).

Upvotes: 5

Turtle
Turtle

Reputation: 1350

(_::_)::_ is pattern matching. _ is simply an unused variable. This would be equivalent:

(a::b)::c as M -> List.map List.head M :: transpose (List.map List.tail M)

Upvotes: 3

Related Questions