implementazione Haskell di "cerniera" strano errore

Question

Ho la seguente implementazione della funzione zip in Haskell

myzip (a:b) (z:g) 
    | b == [] = [] 
    | g == [] = [] 
    | otherwise = (a,z) : myzip b g 

Quando carico in ghci, ottengo il seguente errore

No instance for (Eq b) 
    arising from a use of `==' 
In the expression: g == [] 
In a stmt of a pattern guard for 
       an equation for `myzip': 
    g == [] 
In an equation for `myzip': 
    myzip (a : b) (z : g) 
     | b == [] = [] 
     | g == [] = [] 
     | otherwise = (a, z) : myzip b g 

fallito, moduli caricati: nessuno.

Non sono davvero sicuro del motivo per cui questo non funziona. Qualcuno può offrirmi un aiuto?

Answer 1

In realtà, la funzione che hai fornito nella domanda viene compilata correttamente. Si potrebbe ottenere l'errore che hai citato, se ciò che si aveva era invece:

myzip :: [a] -> [b] -> [(a, b)] 
myzip (a:b) (z:g) 
    | b == [] = [] 
    | g == [] = [] 
    | otherwise = (a, z) : myzip b g 

Con una firma di tipo esplicito dicendo che myzip opere in lista di qualsiasi tipoa e b. Ma hai usato b == [] e g == []. L'operatore di uguaglianza non è definito su alcun tipo, solo su tipi che sono un membro della classe di tipo Eq, quindi il codice che hai scritto non corrisponde al tipo che hai dato.

Questo è ciò che il messaggio di errore dice abbastanza semplice, ma se stai solo imparando e non hai ancora imparato a digitare classi, allora è un po 'poco chiaro.

Se si modifica la firma tipo per myzip dire che a e b bisogno di essere membri della classe Eq tipo, allora il codice che ha dato funzionerà:

myzip :: (Eq a, Eq b) => [a] -> [b] -> [(a, b)] 

Oppure, se si lascia la firma di tipo completamente fuori (come hai fatto nella domanda), GHC in realtà deduce questo tipo dal fatto che hai usato l'operatore ==, e il codice semplicemente compila così com'è.

Tuttavia, verificare se l'elenco è vuoto può essere fatto senza utilizzare l'operatore ==, in modo da poter scrivere myzip in modo che in realtà non operare su qualsiasi tipo a e b. Un modo è quello di utilizzare la funzione null:

myzip :: [a] -> [b] -> [(a, b)] 
myzip (a:b) (z:g) 
    | null b = [] 
    | null g = [] 
    | otherwise = (a, z) : myzip b g 

Ma un modo molto più comune è utilizzare semplicemente equazioni multiple per definire myzip, con casi basi corrispondenza con il modello [] e una custodia principale che arriva a supporre che la gli elenchi non sono vuoti:

myzip :: [a] -> [b] -> [(a, b)] 
myzip (a:[]) _ = [] 
myzip _ (z:[]) = [] 
myzip (a:b) (z:g) = (a, z) : myzip b g 

Si noti che questo stile ha anche reso evidente che c'è un bug nella propria implementazione. Stai buttando via l'ultimo a o z, e non c'è motivo per quando gli elenchi sono completamente vuoti!

Quando l'equazione detto myzip (a:b) (z:g) e poi controllato b e g contro la lista vuota, in realtà è stato controllando la cosa sbagliata troppo tardi. Non è necessario verificare se b è [], è necessario verificare se l'elenco completo era vuoto.Ma avevi già pensato che non fosse vuoto e decomposto in a:b. Ciò si traduce nel codice (a) che restituisce il risultato errato, in quanto elimina l'ultima coppia di elementi che dovrebbe essere zippata e (b) produce un errore quando uno degli argomenti è la lista vuota.

ricorsione su liste appare normalmente più simile a questo:

myzip :: [a] -> [b] -> [(a, b)] 
myzip [] _ = [] 
myzip _ [] = [] 
myzip (a:b) (z:g) = (a, z) : myzip b g 

Questo comporta correttamente.