Cálculo de patrones

El cálculo de patrones basa toda la computación en la coincidencia de patrones de un tipo muy general. Al igual que el cálculo lambda , admite un tratamiento uniforme de la evaluación de funciones . Además, permite que las funciones se pasen como argumentos y se devuelvan como resultados. Adicionalmente, el cálculo de patrones admite el acceso uniforme a la estructura interna de los argumentos, ya sean pares, listas o árboles . También permite que los patrones se pasen como argumentos y se devuelvan como resultados. El acceso uniforme se ilustra mediante una función de coincidencia de patrones que calcula el tamaño de una estructura de datossize arbitraria . En la notación del lenguaje de programación bondi , se da por la función recursiva

sea ​​tamaño_registro = | x y -> ( tamaño x ) + ( tamaño y ) | x - > 1

El segundo caso, o predeterminado,x -> 1 compara el patrón x con el argumento y devuelve 1. Este caso se usa solo si la coincidencia falló en el primer caso. El primer caso, o especial, compara con cualquier compuesto , como una lista no vacía o un par. La coincidencia vincula xal componente izquierdo y yal componente derecho. Luego, el cuerpo del caso suma los tamaños de estos componentes.

Técnicas similares generan consultas genéricas para búsqueda y actualización. La combinación de recursión y descomposición de esta manera produce polimorfismo de rutas .

La capacidad de pasar patrones como parámetros ( polimorfismo de patrones ) se ilustra definiendo un eliminador genérico. Supongamos que se dan constructores Leafpara crear las hojas de un árbol y Countpara convertir números en contadores. Los eliminadores correspondientes son entonces

eliminarHoja = | Hoja y -> y eliminarConteo = | Conteo y -> y

Por ejemplo, elimLeaf (Leaf 3)se evalúa 3como lo hace elimCount (Count 3).

Estos ejemplos se pueden producir aplicando el eliminador genérico elima los constructores en cuestión. Se define por

eliminar = | x -> | { y } x y -> y

Ahora elim Leafse evalúa como | {y} Leaf y -> ylo cual es equivalente a elimLeaf. También elim Countes equivalente a elimCount.

En general, las llaves {}contienen las variables ligadas del patrón, de modo que xes libre y yestá ligada en | {y} x y -> y.