Ayúdame a explicar la función F # Matrix

Question

transponer

existe una matriz transponer función:

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" 

Trabaja muy bien.
¿Qué significa (_ :: _) :: _?
¡No entiendo todo el código!
¿Quién puede explicarlo?
¡Gracias!

puedo encontrar la respuesta:
(_ :: _) _ :: es un patrón de coincidencia sobre el valor del tipo lista de listas de enteros

---

Si Yo escribo:

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

Lanza una excepción de tiempo de ejecución. ¿Hay algún problema con hd?
Sí, que hacen algo así como [[] [] []] cuando la llamada List.tail, entonces se lanza una excepción cuando la llamada List.head!

---

¡Problema resuelto!
¡Gracias a todos!

Answer 1

La función no está escrita de forma especialmente legible, lo que puede ser el motivo de su confusión. El constructo (_::_)::_ es un patrón que coincide con el valor del tipo lista de listas de ints que dice que el primer caso debe ejecutarse cuando obtiene una lista no vacía de listas no vacías.

Lo mismo se puede escribir así. Esto es más detallado, pero debe quedar claro lo que está pasando aquí:

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 
    | _ -> [] 
    | _ -> [] 

Como se puede ver, que realmente no necesita los valores row, rows, col y cols. Es por eso que la implementación original reemplaza estos con _ (que ignora el valor y solo comprueba que la lista se puede descomponer de la manera requerida).

En el caso recursivo, deconstruimos la matriz de la siguiente manera:

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

espero que la imagen hace que sea más clara para usted!

Answer 2

(_::_)::_ es coincidencia de patrón. _ es simplemente una variable no utilizada. Esto sería equivalente:

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

Answer 3

Esto también le puede ayudar a:

Understanding a Matrix transposition Function in Haskell

Es una función muy similar en un lenguaje de programación similar (Haskell).

Answer 4

Esto asigna head sobre las listas para extraer la primera columna y la usa para formar la primera fila antepuesta al resultado de transponer las columnas restantes.

Answer 5

Lamento haber topado con un hilo obsoleto, pero su respuesta original es casi correcta. Lo único que está mal es la condición de terminación para una lista vacía. El código debería verse más o menos así:

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