Help me to explain the F# Matrix transpose functio

2019-01-11 18:31发布

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!

标签: f#
5条回答
看我几分像从前
2楼-- · 2019-01-11 18:59

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)
查看更多
放我归山
3楼-- · 2019-01-11 19:03

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.

查看更多
The star\"
4楼-- · 2019-01-11 19:04

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!

查看更多
爷的心禁止访问
5楼-- · 2019-01-11 19:13

This may also help you:

Understanding a Matrix transposition Function in Haskell

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

查看更多
神经病院院长
6楼-- · 2019-01-11 19:17

(_::_)::_ 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)
查看更多
登录 后发表回答