Uso de patrones para encontrar el enésimo elemento

Question

Estoy trabajando en Aprenda You A Haskell para familiarizarse con los conceptos básicos de Haskell. Me siento muy cómodo tanto con la programación funcional como con la coincidencia de patrones, pero esta última más que con la forma en que lo hace Mathematica.

En el mismo espíritu que la aplicación ingenua de head en el capítulo 4.1, que procedieron con una aplicación ingenua de last como:

last1 :: [a] -> a 
last1 (_:x:[]) = x 

Sin embargo, llamando last1 [1,2,3,4] dio un error Exception: ... Non-exhaustive patterns in function last1. Entiendo que este error implica que el patrón especificado no cubre todas las entradas posibles y, por lo general, es necesario un patrón global (que no he proporcionado). Sin embargo, no estoy exactamente seguro de por qué recibo este error para mi entrada.

Pregunta 1: Mi comprensión (de mi enfoque incorrecto) es que el primer elemento es capturado por _ y el resto se asignan a x, que no es exactamente lo que había previsto. Sin embargo, ¿no debería dar un error de tipo, porque he especificado [a] -> a, pero x ahora es una lista?

Tenga en cuenta que esto es no acerca de cómo escribir un last función de trabajo - Sé que puedo escribir como (entre otras posibilidades)

last2 :: [a] -> a 
last2 [x] = x 
last2 (_:x) = last2 x 

Pregunta 2: A lo largo del mismo tema de una mejor Entender la coincidencia de patrones en Haskell, ¿cómo puedo usar la coincidencia de patrones para elegir el último elemento o, más en general, el elemento n de una lista determinada, por ejemplo, [1..10]?

This answer sugiere que puede enlazar el último elemento utilizando coincidencia de patrones con la extensión ViewPatterns, pero parece extraño que no hay un patrón similar "simple" como por head

En Mathematica, que sería probablemente escribir como:

Range[10] /. {Repeated[_, {5}], x_, ___} :> x 
(* 6 *) 

de seleccionar el sexto elemento y

Range[10] /. {___, x_} :> x 
(* 10 *) 

para seleccionar el último elemento de una lista no vacía.

Me disculpo si esto se trata más adelante en el texto, pero trato de relacionar cada tema y concepto a medida que los encuentro, a cómo se maneja en otros idiomas que conozco para que pueda apreciar las diferencias y similitudes.

Answer 1

Para dar sentido al resultado de su primer intento, necesita ver cómo se define la información de la lista . Las listas disfrutan de una sintaxis algo especial, pero podría escribirlo de de esta manera.

data List a = (:) a (List a) 
      | [] 

Así, la lista [1 .. 10] es en realidad estructurada como

(1 : (2 : (3 : (4 : [])))) 

Además, debido a la derecha de la asociatividad (:) operador, su patrón para last1 en realidad se ve como

last1 :: [a] -> a 
last1 (_:(x:[])) = x 

Es por eso que 'x' tiene el mismo tipo que un elemento de su lista; es el primer argumento para el (:) constructor.

La coincidencia de patrones le permite deconstruir estructuras de datos como listas, pero necesita saber qué "forma" tienen que hacer. Es por eso que no puede directamente especificar un patrón que extraerá el último elemento de una lista, porque hay son un número infinito de longitudes que una lista puede tener. Es por eso que la solución de trabajo (last2) usa recursión para resolver el problema.Sabes qué patrón tiene una lista de longitud uno y dónde encontrar el elemento final; para todo lo demás, puede descartar el primer elemento y extraer el último elemento de la lista resultante, más corta.

Si quisiera, podría agregar más patrones, pero no sería útil . Se puede escribir como

last2 :: [a] -> a 
last2 (x:[])  = x 
last2 (_:x:[]) = x 
last2 (_:_:x:[]) = x 
     ... 
last2 (x:xs) = last2 xs 

sin embargo, un número infinito de casos, nunca se podría completar la función para todas las longitudes de listas de entrada. Es aún más dudoso si tenemos en cuenta el hecho de que las listas pueden ser infinitamente largas; ¿Qué patrón usarías para unir eso?

Answer 2

No hay forma de que la coincidencia de patrón obtenga el "último" elemento sin utilizar los patrones de vista. Esto se debe a que no hay forma de obtener el último elemento de una lista sin utilizar la recursión (al menos implícitamente), y lo que es más, no hay decidible forma de obtener el último elemento.

Su código

last1 (_:x:[]) = x 

deberían analiza como

last1 (_:(x:[])) = x 

que puede ser de extracción del azúcar en

last1 a = case a of 
       (_:b) -> case b of 
          (x:c) -> case c of 
              [] -> x 

haya concluido el ejercicio vemos lo que hace el código: usted ha escrito un patrón que coincidirá con una lista SI el constructor más externo de una lista es una celda cons ND el siguiente constructor es un inconveniente Y el tercer constructor es un nulo. solamente

por lo que en el caso de

last1 [1,2,3,4] 

tenemos

last1 [1,2,3,4] 
= last1 (1:(2:(3:(4:[])))) 
= case (1:(2:(3:(4:[])))) of 
     (_:b) -> case b of 
        (x:c) -> case c of 
            [] -> x 
= case (2:(3:(4:[]))) of 
     (x:c) -> case c of 
        [] -> x 
= let x = 2 in case (3:(4:[])) of 
        [] -> x 
= pattern match failure 

Answer 3

Su ejemplo

last1 (_:x:[]) = x 

partidos listas que contienen dos elementos es decir, listas de la forma a:b:[]. _ coincide con el encabezado de la lista sin enlace, x coincide con el siguiente elemento y la lista vacía se empareja a sí misma.

Cuando coinciden las listas de patrones, solo el elemento situado más a la derecha representa una lista: el final de la lista coincidente.

Puede obtener el enésimo elemento de una lista con una función como:

getNth :: [a] -> Int -> a 
getNth [] _ = error "Out of range" 
getNth (h:t) 0 = h 
getNth (h:t) n = getNth t (n-1) 

Esta integrada mediante el operador !! por ejemplo, [1..10] !! 5

Answer 4

Puede utilizar efectivamente ViewPatterns que ver la coincidencia de patrones al final de una lista, por lo que vamos a hacer:

{-# LANGUAGE ViewPatterns #-} 

y redefinir su last1 y last2 mediante la inversión de la lista antes de que el ajuste de patrones. Esto lo hace O (n), pero eso es inevitable con una lista.

last1 (reverse -> (x:_)) = x 

La sintaxis

mainFunction (viewFunction -> pattern) = resultExpression

es el azúcar sintáctica para

mainFunction x = case viewFunction x of pattern -> resultExpression

para que pueda ver que en realidad sólo se invierte de la lista a continuación, patrón coincide con eso, pero se siente más agradable . viewFunction es cualquier función que desee. (Uno de los objetivos de la extensión fue permitir a la gente a utilizar de manera limpia y fácil de acceso para funciones coincidencia de patrones para que no tuvieran que utilizar la estructura subyacente de su tipo de datos cuando definir funciones en él.)

Este last1 da un error si la lista está vacía, al igual que el last original.

*Main> last []
*** Exception: Prelude.last: empty list
*Main> last1 []
*** Exception: Patterns.so.lhs:7:6-33: Non-exhaustive patterns in function last1

Bueno, está bien, no exactamente, pero podemos cambiar eso mediante la adición de

last1 _ = error "last1: empty list" 

que le da

*Main> last1 []
*** Exception: last1: empty list

Por supuesto, podemos usar el mismo truco para last2:

last2 (reverse -> (_:x:_)) = x 
last2 _ = error "last2: list must have at least two elements" 

pero sería más agradable para definir

maybeLast2 (reverse -> (_:x:_)) = Just x 
maybeLast2 _ = Nothing 

Usted puede continuar de esta manera con, por ejemplo last4:

last4 (reverse -> (_:_:_:x:_)) = x 

Y puede ver que con el patrón de vista reverse, hemos cambiado la semántica de (_:_:_:x:_) de (ignore1st,ignore2nd,ignore3rd,get4th,ignoreTheRestOfTheList) a (ignoreLast,ignore2ndLast,ignore3rdLast,get4thLast,ignoreTheRestOfTheList).

Observa que en Mathematica, el número de guiones bajos se usa para indicar la cantidad de elementos que se ignoran. En Haskell, sólo tiene que utilizar el _, pero se puede utilizar para cualquier valor ignorado, y en presencia de la asimétrica lista constructor :, la semántica dependen de qué lado estás, por lo que en a:b, la a debe significar un elemento y la b debe haber una lista (que puede ser en sí mismo, porque c:d: es asociativa derecha - a:b:c significa a:(b:c)). Esta es la razón por la cual un guión bajo final en cualquier patrón de lista contiene ignoreTheRestOfTheList, y en la presencia de la función de visualización reverse, eso significa ignorar los elementos frontales de la lista.

La recursividad/retroceso oculto bajo el capó en Mathematica es explícita aquí con la función de vista reverse (que es una función recursiva).