algorithm - mal - ¿Cómo funciona la coincidencia de patrones detrás de las escenas en F#?

patron del mal detras de camaras

Question

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

Answer 1

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

Está tan lejos de un bucle for como podría imaginar: en lugar de un bucle, se compila una coincidencia de patrón con un autómata eficiente . Hay dos estilos de autómatas, 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 un espacio de código exponencial en el peor de los casos. El estilo francés ofrece una compensación de tiempo-espacio diferente, con buenas pero no óptimas garantías para ambos.

Pero el trabajo absolutamente definitivo sobre este problema es el excelente artículo de Luc Maranget "Compilación de patrones que concuerdan con los árboles de buenas decisiones del Taller ML 2008. El documento 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, recomiendo humildemente mi propia oferta ¿Cuándo son importantes las heurísticas de compilación?

¡Escribir un compilador de patrones es fácil y divertido!

Answer 2

Depende de qué tipo de coincidencia de patrón quiere decir: es una construcción bastante potente y se puede utilizar de muchas maneras. Sin embargo, intentaré explicar cómo funciona la coincidencia de patrones en las listas. Puedes 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 que contiene dos casos: [] representa una lista vacía o x::xs representa una lista con el primer elemento x seguido de algunos otros elementos. En C #, esto podría ser representado 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 anteriores se compilarían con lo siguiente (estoy usando pseudocódigo para hacer esto más 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 puedes ver, no hay bucles involucrados. Al procesar las listas en F #, usarí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.

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

Answer 3

No, no se repite. Si tienes un patrón como este

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

Esto compila a algo como este 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 algebraico (es decir, un tipo definido como type FooBar = Foo int int | Bar int ), las operaciones x is a Foo x is a Bar son comparaciones simples. Si están definidos por un patrón activo , las operaciones están definidas por ese patrón.

Answer 4

Si compila su código F # en un archivo .exe, entonces eche un vistazo con Reflector para ver qué es el "equivalente" de C # del código F #.

He usado este método para ver ejemplos de F # bastante.