Haskell - Patrón de coincidencia y recursión

Question

Soy nuevo en Haskell y la programación. Mi pregunta sobre vinculante en el patrón de coincidencia, funciones recursivas. Por ejemplo, supongamos que tengo una función que verifica si una lista dada (x: xs) es una sublista de otra lista, (y: ys). Mi idea inicial, siguiendo los ejemplos en mi libro de texto, era:

sublist [] ys = True 
sublist xs [] = False 
sublist (x:xs) (y:ys) 
    | x == y = sublist xs ys 
    | x /= y = sublist (x:xs) ys 

Esto funciona en los datos de prueba, por ejemplo,

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 

donde esperaba que falle. Espero que falle, ya

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
    = sublist [2, 3] [2, 4, 1, 2, 3] 
    = sublist [3] [4, 1, 2, 3] 

momento en el que, pensé, [3] = 3: [] se combina con (x: xs) en sublista, y [4, 1, 2, 3 ] se combinará con (y: ys) en la sublista. ¿Cómo, entonces, está funcionando la sublista?

Edit: Gracias a todos los presentes, creo que he resuelto mi problema. Como noté, estaba ("subconscientemente") queriendo que la sublista me retractara. Utilizando la última respuesta (BMeph) publicada como guía, decidí abordar el problema de manera diferente, para resolver el "problema vinculante", es decir, el problema de "retroceso".

subseq :: (Eq a) => [a] -> [a] -> Bool 
subseq [] _ = True 
subseq _ [] = False 
subseq (x:xs) (y:ys) = 

-- subseq' decides whether the list bound to (x:xs) = M is a prefix of the list 
-- bound to L = (y:ys); it recurses through L and returns a Bool value. subseq 
-- recurses through M and L, returning a disjunction of Bool 
-- values. Each recursive call to subseq passes M and ys to subseq', which 
-- decides whether M is a prefix of the **current list bound to ys**. 

    let subseq' :: (Eq a) => [a] -> [a] -> Bool 
     subseq' [] _ = True 
     subseq' _ [] = False 
     subseq' (x:xs) (y:ys) = (x == y) && subseq' xs ys 
      in subseq' (x:xs) (y:ys) || subseq (x:xs) ys 

Answer 1

Se está trabajando porque:

• [3] está adaptada como x:xs como 3:[],
• [4, 1, 2, 3] está adaptada como y:ys como 4:[1,2,3]
• 3/=4 por lo sublist (x:xs) ys se evalúa, lo que finalmente es True

traza:

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
    = sublist [2, 3] [2, 4, 1, 2, 3] 
    = sublist [3] [4, 1, 2, 3] 
    = sublist [3] [1, 2, 3] 
    = sublist [3] [2, 3] 
    = sublist [3] [3] 
    = sublist [] [] = True 

Answer 2

sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
= sublist [2, 3] [2, 4, 1, 2, 3] 
= sublist [3] [4, 1, 2, 3] 
= sublist [3] [4, 1, 2, 3] 
= sublist (3:[]) (4:[1,2,3])  -- Since 3 /= 4, we take sublist (x:xs) ys 
= sublist (3:[]) [1,2,3] 
= sublist (3:[]) (1:[2,3]) 
= sublist (3:[]) [2,3] 
= sublist (3:[]) (2:[3]) 
= sublist (3:[]) [3] 
= sublist [] [] 
= True 

cheques sublista si cabezas de listas son iguales. Si es así, entonces los elimina y procede (sublist xs ys). Si no, elimina el encabezado de la segunda lista (sublist (x:xs) ys). De esta manera se "encuentra" la siguiente asociación:

1 2 3 
| | | 
| | \-----\ 
| |  | 
1 2 4 1 2 3 

En otras palabras, para comprobar sublist [1,2,3] ys por alguna lista que aparece ys elementos de ys, siempre y cuando no son 1. Entonces aparece como elementos siempre y cuando sean no 2. Entonces aparece elementos siempre que no sean 3. Si [1,2,3] está agotado, entonces informa True; si ys está agotado, informa False.

Answer 3

YuppieNetworking y sdcwc ya han explicado cómo funciona la coincidencia. Por lo tanto, su sublist busca una sublista en el mismo sentido que subsequence (no necesariamente los mismos elementos en una fila, puede haber algo intermedio).

Quiero señalar que a menudo puede evitar la recursión explícita para eliminar elementos innecesarios del frente de la lista con dropWhile.Además, quería dar un ejemplo de cómo verificar si dos listas tienen los mismos prefijos (necesita esto para verificar si la segunda lista contiene elementos del primero en una fila).

El primer ejemplo es similar a la función, que permite que la partida en el medio, pero se utiliza dropWhile para eliminar los elementos frente a ys:

-- Test: 
-- map ("foo" `subListOf`) ["kungfoo", "f-o-o!", "bar"] == [True,True,False] 

[] `subListOf` _ = True 
(x:xs) `subListOf` ys = 
    let ys' = dropWhile (/= x) ys  -- find the first x in ys 
    in case ys' of 
     (_:rest) -> xs `subListOf` rest 
     [] -> False 

El segundo ejemplo busca una lista secundaria "densa":

-- Test: 
-- map ("foo" `denseSubListOf`) ["kungfoo!", "-f-o-o-"] == [True,False] 

[] `denseSubListOf` _ = True 
_ `denseSubListOf` [] = False 
xs `denseSubListOf` ys = 
    let ps = zip xs ys in 
    (length ps == length xs && all (uncurry (==)) ps) -- same prefix of xs and ys 
    || xs `denseSubListOf` (tail ys)     -- or search further 

Tenga en cuenta que para comprobar que la segunda lista contiene toda la primera en el comienzo comparo elementos de dos en dos (subo la cremallera juntos para hacerlo).

Es más fácil explicar por ejemplo:

zip [1,2,3] [1,2,3,4,5] -- gives [(1,1), (2,2), (3,3)], 4 and 5 are truncated 
uncurry (==)    -- an equivalent of (\(a,b) -> a == b) 
all      -- gives True iff (uncurry (==)) is True for all pairs 
length ps == length xs -- this is to ensue that the right list is long enough 

Answer 4

Debug.Trace es su amigo. Con sublist instrumentados como

sublist [] ys = trace ("A: [] "   ++ show ys) True 
sublist xs [] = trace ("B: " ++ (show xs) ++ " []") False 
sublist (x:xs) (y:ys) 
    | x == y = trace (info "C" "==") 
       sublist xs ys 
    | x /= y = trace (info "D" "/=") 
       sublist (x:xs) ys 
    where info tag op = 
      tag ++ ": " ++ (show x) ++ " " ++ op ++ " " ++ (show y) ++ 
      "; xs=" ++ (show xs) ++ ", ys=" ++ show ys 

ves lo que está pasando, es decir, que se está tirando repetidamente de distancia de la cabeza de la segunda lista hasta que encuentre una coincidencia:

*Main> sublist [1, 2, 3] [1, 2, 4, 1, 2, 3] 
C: 1 == 1; xs=[2,3], ys=[2,4,1,2,3] 
C: 2 == 2; xs=[3], ys=[4,1,2,3] 
D: 3 /= 4; xs=[], ys=[1,2,3] 
D: 3 /= 1; xs=[], ys=[2,3] 
D: 3 /= 2; xs=[], ys=[3] 
C: 3 == 3; xs=[], ys=[] 
A: [] [] 
True

Otra herramienta que le ayudará a implementar sublist correctamente es Test.QuickCheck, una biblioteca que crea automáticamente datos de prueba para usarlos en la verificación de las propiedades que usted especifique.

Por ejemplo, supongamos que desea sublist para tratar xs y ys como conjuntos y determinar si el primero es un subconjunto de este último. Podemos utilizar Data.Set para especificar esta propiedad:

prop_subsetOf xs ys = 
    sublist xs ys == fromList xs `isSubsetOf` fromList ys 
    where types = (xs :: [Int], ys :: [Int]) 

Esto dice sublist debería ser equivalente a la definición de la derecha. El prefijo prop_ es una convención popular para nombrar propiedades de prueba que se utilizarán con QuickCheck.

Correr también identifica un caso de fracaso:

*Main> quickCheck prop_subsetOf 
*** Failed! Falsifiable (after 6 tests):     
[0,0] 
[0]

Answer 5

Creo en la que puede ser mal entendido, es que (cuando se escribió por primera vez la función) se supone que en su cheque x /= y = sublist (x:xs) ys que (de manera inconsciente?) supusieron que la función sería retroceder y volver a hacer su función con la cola de la segunda lista original, no la cola de la parte de la lista que esté utilizando cuando no coincida.

Una agradable (e inquietante) cosa sobre Haskell es sólo lo ridículamente poderosa que es.

Por ejemplo, aquí es como lo que quería debería haber buscado:

sublist []  ys = True 
sublist xs  [] = False 
sublist (x:xs) (y:ys) | x /= y = False 
         | otherwise = sublist xs ys || sublist (x:xs) ys 

que comprobar si todas las piezas de la primera lista. La definición "oficial" de la función (consulte "isInfixOf" en su documentación) tiene algunas funciones adicionales que básicamente significan lo mismo.

Ésta es otra manera escribirlo, que se parece más "explicativa" a los ojos:

sublist [] ys = True 
sublist xs [] = False 
sublist xs ys = (xs == take (length xs) ys) || sublist xs (tail ys)