[Teoria] Logica per l'informatica e ricorsione strutturale

[Zingarelli1]

Dovendo ancora dare, ahimè, l'esame di Logica per l'Informatica, mi stavo esercitando sulle vecchie prove e sono piantato su questo esercizio con zero idee sul come risolverlo.

"Sia L::= [] | N :: L la grammatica delle liste di numeri naturali, dove [] rappresenta la lista vuota, N è un numero naturale e :: è associativo a destra. Scrivere, per ricorsione strutturale su L, una funzione f(L) che restituisca la lista dalla quale sono stati eliminati i numeri duplicati. Esempio: f(1 :: 4 :: 1 :: 3 :: 1 :: []) = 1 :: 4 :: 3 :: []."

Qualcuno può aiutarmi o darmi uno spunto?
Grazie mille

[apatriarca]

Non ho mai dato un esame con quel nome e non ho quindi idea di quali siano gli argomenti e la notazione usata. Tuttavia ho esperienza di programmazione in Haskell in cui le liste sono definite esattamente in quel modo (a parte la notazione diversa). Se supponi di avere una funzione g(L, N) che elimina un particolare valore da una lista, allora potresti definire la tua operazione nel modo seguente:

f([]) = []
f(n :: ns) = n : f(g(ns, n))

Ogni volta che incontri un valore lo elimini insomma dal resto della stringa prima di applicare ricorsivamente la tua funzione.