Patrón de recursión común

Question

Me estoy acostumbrando a las funciones de orden superior de Haskell. Usualmente puedo reemplazar patrones explícitos de recursión con funciones como mapa, pliegue y escaneo. Sin embargo, a menudo me encuentro con el siguiente patrón de recursividad, que no entiendo cómo expresar el uso de funciones de orden superior:

f (x:[]) = k x 
    f (x:xs) = g x (f xs) 

Por ejemplo, supongamos que estoy representando cuadros analítica. Luego de crear un tipo de datos tales como:

data Tableau = N Expr | S Expr (Tableau) | B Expr (Tableau) (Tableau) 

Si quiero convertir una lista de Expr s en una estructura de cuadro, quiero una parte la función de los cuales se podría parecer:

f (x:[]) = N x 
    f (x:xs) = S x (f xs) 

Ahora, Veo tres opciones: (1) crear una función que decide, dado un cuadro y una lista, si la siguiente rama en el cuadro debe ser S o N (o B, pero ignoraremos ese caso); (2) use una función de orden superior para encapsular el patrón de recursión de f; (3) use una función como f.

¿Cuál sería la mejor opción?

Answer 1

me gustaría más probable es que utilice la siguiente:

f xs = foldr g (k (last xs)) (init xs) 

Básicamente significa que al final de la lista se sustituye por k x al plegar. Gracias a la evaluación perezosa presente en todas partes, funciona incluso para listas infinitas.

Hay otras dos soluciones: agregar una caja vacía y usar Maybe.

a) añadir caja vacía:

Sería mejor si f [] estaba bien definido.Entonces, se podría escribir la definición como

f [] = c 
f (x:xs) = g x (f xs) 

que es f = foldr g c. Por ejemplo, si cambia

data Tableau = N Expr | S Expr Tableau | B Expr Tableau Tableau 

a

data Tableau = N | S Expr Tableau | B Expr Tableau Tableau 

entonces se puede representar de un solo elemento cuadros como S expr N, y la función se define como una sola línea

f = foldr S N 

Es la La mejor solución siempre que el caso vacío tenga sentido.

B) utilice lo mejor:

Por otro lado, si f [] no es lógico definido, es peor. Las funciones parciales a menudo se consideran feas. Para que sea total, puede usar Maybe. Defina

f [] = Nothing 
f [x] = Just (k x) 
f (x:xs) = Just (g x w) 
      where Just w = f xs 

Es una función total, eso es mejor.

Pero ahora puede volver a escribir la función en:

f [] = Nothing 
f (x:xs) = case f xs of 
       Nothing -> Just (k x) 
       Just w -> Just (g x w) 

que es un pliegue derecha:

addElement :: Expr -> Maybe Tableaux -> Maybe Tableaux 
addElement x Nothing = Just (N x) 
addElement x (Just w) = Just (S x w) 

f = foldr addElement Nothing 

En general, plegado es idiomática y se debe utilizar cuando se encaja en el patrón de la recursividad. De lo contrario, utilice la recursión explícita o intente reutilizar los combinators existentes. Si hay un patrón nuevo, crea un combinador, pero solo si usarás mucho el patrón; de lo contrario, será excesivo. En este caso, el patrón se dobla para listas no vacías definidas por: data List a = End a | Cons a (List a).

Answer 2

Si he entendido la pregunta correctamente, entonces aquí es mi evaluación de sus opciones:

1. Es probablemente un poco desagradable tener que coincidir con el cuadro de debajo de la constructora (presumiblemente arbitrariamente compleja?) para escribir esa función. Este enfoque parece algo frágil, aunque probablemente funcione bien.

2. No veo la necesidad de generalizar el patrón, dado que es una función recursiva que opera en una estructura recursiva. La introducción de un patrón de orden superior podría (creo) ofuscar la lógica real detrás de realizar un recorrido recursivo de esta estructura de datos.

3. Creo que esto tiene mucho sentido. Como ha observado, es un "patrón" razonablemente reconocido, pero creo que coincide con la descripción del algoritmo para escribirlo exactamente de esta manera. Puede no ser tan generalizable o reutilizable, pero dado que es esencialmente el punto crucial del enfoque algorítmico, creo que tiene sentido escribir los casos directamente como lo ha hecho en una función como f. Este sería mi enfoque favorito.

sentimos que no proporciona una respuesta concreta sobre todo, pero es una respuesta bastante subjetiva, por lo que teniendo en cuenta las tres opciones anteriores, la opción 3 por razones de claridad y legibilidad yo escogería.