implementazione principiante/studente di foreach in haskell

Question

Sto cercando di implementare un morfismo foreach in modo da mettere alla prova la mia comprensione della definizione del morfismo e della corrispondenza del modello ... Ovviamente mi mancano completamente entrambi i punti.

Potresti correggermi? Voglio il morfismo foreach per prendere un elenco di a e un morfismo f come argomenti e per restituire l'elenco di tutti i risultati r di f applicato a tutti gli elementi a.

foreach :: [a] → f → [r] 
foreach [] f = [] 
foreach x:[] f = (f x):[] 
foreach []:x f = []:(f x) 
foreach (x:xs) f = (f x) : (foreach (xs f)) 

Quando compilato, ho src\Main.hs:23:0: Parse error in pattern

Answer 1

Il problema è s yntactic, in questa linea:

foreach x:[] f = (f x):[] 

applicazione Constructor nei modelli di solito bisogno di essere tra parentesi. Questo dovrebbe funzionare:

foreach (x:[]) f = (f x):[] 

Per inciso ... applicazione funzione è più alta precedenza, così d'altra parte non è necessario parentesi sul lato destro:

foreach (x:[]) f = f x:[] 

Quanto sopra vale per ogni costruttore di infisso, ma come una nota finale, per gli elenchi, in particolare, v'è una sintassi speciale:

foreach [x] f = [f x] 

ci sono altri problemi con il codice così com'è, ma questo è l'errore immediato. Una rapida panoramica degli altri problemi:

foreach :: [a] → f → [r] 

variabili di tipo sono implicitamente universalmente quantificate, quindi questo significa qualsiasi tipof. Hai bisogno di un tipo più specifico, ovvero a -> r.

foreach x:[] f = (f x):[] 

Ciò non è necessario - il caso ricorsivo funziona correttamente qui, applicando f-x e si fa chiamare sulla coda, dando il caso lista vuota.

foreach []:x f = []:(f x) 

non credo che questo significa quello che pensi che significa - questo è il pattern matching capo di una lista con l'elenco vuoto [], il che implica che la funzione sta lavorando su una lista di liste.

foreach (x:xs) f = (f x) : (foreach (xs f)) 

Le parentesi qui sono non necessarie o errate. Ancora una volta, l'applicazione della funzione ha una precedenza più elevata rispetto agli operatori come :. Inoltre, (xs f) significa applicare xs a f, come se fosse una funzione.Per applicare foreach a due argomenti, è sufficiente foreach xs f.

---

Per confronto, ecco il codice sorgente per il (identici tranne che per ordine degli argomenti) funzione di libreria standard map:

map :: (a -> b) -> [a] -> [b] 
map _ []  = [] 
map f (x:xs) = f x : map f xs 

Answer 2

quali hai dimenticato di mettere in ()foreach []:x f = []:(f x) e in modo non corretto specificato il tipo di funzione, il seguente dovrebbe ora essere compilabile:

foreach :: [a] -> (a -> r) -> [r] 
foreach [] f = [] 
foreach (x:[]) f = (f x):[] 
foreach (x:xs) f = (f x) : (foreach xs f) 

ed eseguire:

*Main> foreach [1..20] (+1) 
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21] 

Answer 3

La firma tipo si dà, è (almeno nel parere del compilatore Haskell) fasullo. È una funzione che prende un elenco di elementi di qualsiasi a e un valore di qualsiasi tipo f e produce un elenco di valori di qualsiasi tipo r. È come dire "Ho un mucchio di elefanti e un cacciavite. Trasforma ogni elefante in un mango".

Sembra il vostro obiettivo è quello di implementare la funzione map:

map :: (a -> b) -> [a] -> [b] 

Naturalmente, è perfettamente valido per capovolgere gli argomenti:

foreach :: [a] -> (a -> b) -> [b] 

L'implementazione è abbastanza vicino, ma ci sono un pochi problemi.

La cosa più importante è quello di tenere a mente che si sta lavorando con liste, non array. L'operatore :, noto anche come "contro", accetta un elemento e lo antepone a un elenco (ad esempio 1 : [2,3,4]). Non è possibile utilizzarlo per concatenare arbitrariamente articoli ed elenchi, come nel caso []:(f x). Esiste l'operatore ++ che concatena due elenchi (ad esempio [f x] ++ xs, che è lo stesso di (f x) : xs), ma non dovrebbe essere necessario per implementare foreach.

Infine, (foreach (xs f)) non fa ciò che si potrebbe pensare di fare. Non è come foreach(xs,f) in un linguaggio in stile C, è come foreach(xs(f)). (xs f), di per sé, è come utilizzare xs come una funzione e applicare f come argomento. Invece, si desidera (foreach xs f).

Mi fermo qui, per evitare di dare troppo. Un piccolo inconveniente: l'applicazione della funzione ha la precedenza più alta di qualsiasi operatore, quindi invece di (f x) : (foreach xs f), puoi dire f x : foreach xs f.