¿Cómo funciona la coincidencia de patrones entre bastidores en F #?

Question

Soy completamente nuevo en F # (y la programación funcional en general) pero veo la coincidencia de patrones utilizada en todas partes en el código de muestra. Me pregunto, por ejemplo, cómo funciona la coincidencia de patrones. Por ejemplo, me imagino que funciona igual que un bucle for en otros idiomas y verificando coincidencias en cada elemento de una colección. Esto probablemente está lejos de ser correcto, ¿cómo funciona realmente detrás de escena?

Answer 1

Depende de qué tipo de coincidencia de patrón quieras decir: es una construcción bastante poderosa y se puede usar de muchas maneras. Sin embargo, intentaré explicar cómo funciona la coincidencia de patrones en las listas. Puede escribir, por ejemplo, estos patrones:

match l with 
| [1; 2; 3] -> // specific list of 3 elements 
| 1::rest -> // list starting with 1 followed by more elements 
| x::xs ->  // non-empty list with element 'x' followed by a list 
| [] ->   // empty list (no elements) 

La lista F # es en realidad una unión discriminada contiene dos casos - [] que representa una lista vacía o x::xs que representa una lista con el primer elemento de x seguido por algunos otros elementos. En C#, esto podría ser representada así:

// Represents any list 
abstract class List<T> { } 
// Case '[]' representing an empty list 
class EmptyList<T> : List<T> { } 
// Case 'x::xs' representing list with element followed by other list 
class ConsList<T> : List<T> { 
    public T Value { get; set; } 
    public List<T> Rest { get; set; } 
} 

Los patrones anteriormente se compilan en la siguiente (estoy usando pseudo-código para hacerlo mas simple):

if (l is ConsList) && (l.Value == 1) && 
    (l.Rest is ConsList) && (l.Rest.Value == 2) && 
    (l.Rest.Rest is ConsList) && (l.Rest.Rest.Value == 3) && 
    (l.Rest.Rest.Rest is EmptyList) then 
    // specific list of 3 elements 
else if (l is ConsList) && (l.Value == 1) then 
    var rest = l.Rest; 
    // list starting with 1 followed by more elements 
else if (l is ConsList) then 
    var x = l.Value, xs = l.Rest; 
    // non-empty list with element 'x' followed by a list 
else if (l is EmptyList) then 
    // empty list (no elements) 

Como se puede ver, no hay bucle involucrado. Al procesar listas en F #, utilizaría la recursión para implementar el bucle, pero la coincidencia de patrones se usa en elementos individuales (ConsList) que juntos componen la lista completa.

coincidencia de patrones en las listas es un caso específico de unión discriminado que se discute por sepp2k. Hay otras construcciones que pueden aparecer en la coincidencia de patrones, pero esencialmente todas se compilan usando alguna declaración (complicada) if.

Answer 2

No, no tiene bucle. Si usted tiene un partido el patrón de esta

match x with 
| Foo a b -> a + b 
| Bar c -> c 

esta compila a algo como esto pseudo código:

if (x is a Foo) 
    let a = (first element of x) in 
    let b = (second element of x) in 
    a+b 
else if (x is a Bar) 
    let c = (first element of x) in 
    c 

Si foo y bar son constructores de un tipo de datos algebraica (es decir, un tipo definido como type FooBar = Foo int int | Bar int) las operaciones x is a Foo y x is a Bar son comparaciones simples. Si están definidos por un active pattern, las operaciones están definidas por ese patrón.

Answer 3

¿Cómo funciona realmente la coincidencia de patrones? Lo mismo que un bucle for?

Es casi tan lejos de un bucle for como se podía imaginar: en lugar de bucle, una comparación de patrones es compilado a un autómata eficiente. Hay dos estilos de autómata, que llamo el "árbol de decisión" y el "estilo francés". Cada estilo ofrece diferentes ventajas: el árbol de decisión inspecciona el número mínimo de valores necesarios para tomar una decisión, pero una implementación ingenua puede requerir espacio de código exponencial en el peor de los casos. El estilo francés ofrece una compensación de tiempo-espacio diferente, con garantías buenas pero no óptimas para ambos.

Pero el trabajo absolutamente definitivo a este problema es excelente documento de Luc Maranget "Compiling Pattern Matching to Good Decisions Trees del taller ML 2008. El papel de Luc básicamente muestra cómo obtener lo mejor de ambos mundos. Si desea un tratamiento que puede ser un poco más accesible para el aficionado, humildemente recomiendo mi propia oferta When Do Match-Compilation Heuristics Matter?

Escribir un compilador de patrón-partido es fácil y divertido!

Answer 4

Si compila su código F # en un .exe, eche un vistazo con Reflector y verá el "equivalente" C# del código F #.

He utilizado este método para examinar los ejemplos de F # un poco.