Queste funzioni sono ricorsive?

Question

Sto imparando la ricorsione della coda e sto riscontrando alcune difficoltà nel determinare se la mia funzione è ricorsiva della coda o meno (principalmente su funzioni che uso un'altra funzione).

Ho implementato le due seguenti funzioni, ma non sono sicuro che siano ricorsive o meno.

Il primo è una funzione per concatenare due elenchi.

conca list [] = list 
conca [] result = result 
conca (h:t) result = conca (init (h:t)) (last(h:t):result) 

concatenate::[a]->[a]->[a] 
concatenate list1 list2 = conca list1 list2 

I calcoli nella funzione vengono elaborati prima della chiamata ricorsiva, ma il suo utilizzo e ultimo init, che non sono coda ricorsiva (ho controllato loro definizione in http://ww2.cs.mu.oz.au/172/Haskell/tourofprelude.html)

La seconda funzione è quella di rimuovere la prima occorrenza di un dato numero in una data lista.

invert [] result = result 
invert (h:t) result = invert t (h:result) 

remov n [] aux result = invert result [] 
remov n (h:t) aux result 
     | aux==1 = remov n t 1 (h:result) 
     | n==h = remov n t 1 (result) 
     | otherwise = remov n t 0 (h:result) 

remove n list = remov n list 0 [] 

L'aux parametro (che possono assumere 0 o 1 come valore) viene utilizzato per marcare se l'occorrenza è stato rimosso o meno.

Nella funzione di rimozione mentre il risultato parziale è passato attraverso la chiamata ricorsiva la lista viene invertita, al termine la lista è senza la prima occorrenza ma capovolta, quindi deve essere invertita per essere restituita come un risultato.

Answer 1

conca (h:t) result = conca (init (h:t)) (last(h:t):result) 

è una chiamata coda, ma last(h:t):result inizia la vita come thunk non valutata, quindi è un (a mano ondulato) po 'come queste chiamate di funzione nidificate sono in pila ancora.

conca corrispondenze modello sul primo argomento, pertanto init verrà valutato nel richiamo ricorsivo.

conca non è rigido nel suo secondo argomento, quindi quei thunk non verranno valutati durante l'applicazione della chiamata ricorsiva di conca.

---

remov è coda ricorsiva, sì, ma ....

Usa True e False invece di 0 e 1 per rendere il codice più chiaro:

remov n [] found result = invert result [] 
remov n (h:t) found result 
     | found = remov n t True (h:result) 
     | n==h = remov n t True (result) 
     | otherwise = remov n t False (h:result) 

remove n list = remov n list False [] 

Questo sarebbe meglio non passando così tanti dati, riducendo la copia di n e utilizzando due funzioni invece di una singola funzione che verifica un parametro booleano:

remove' n list = seek list [] where 
    seek []  result = invert result [] 
    seek (h:t) result | h == n = got t result 
        | otherwise = seek t (h:result) 
    got [] result = invert result [] 
    got (h:t) result = got t (h:result) 

ma got a result solo calcola reverse result ++ a, quindi si potrebbe scrivere

remove'' n list = seek list [] where 
    seek []  result = invert result [] 
    seek (h:t) result | h == n = invert result [] ++ t 
        | otherwise = seek t (h:result) 

Tuttavia, tutto sembra piuttosto un sacco di fatica, e attraversa ancora l'elenco due volte. Perché non andare a fare una chiamata non-tail:

removeFast n [] = [] 
removeFast n (h:t) | h == n = t 
        | otherwise = h:removeFast n t 

Questo ha il vantaggio di produrre il suo primo elemento da subito piuttosto che correre l'intera lista, e scorciatoie per tornare t senza ulteriori calcoli, una volta che ha trovato l'elemento di rimuovere.Prova a correre length (removeFast 1 [1..100000]) contro length (remove 1 [1..100000]) (modifica il numero di zeri in base alla velocità del processore).

---

Se si vuole fare una coda più efficiente ricorsiva conca, è possibile utilizzare il trucco da remove:

conc this result = prepend (invert this []) result 

prepend [] result = result 
prepend (h:t) result = prepend t (h:result) 

Come in precedenza, il gioco è attraversando this due volte, una volta invert ing esso, il altro prepending esso, ma è ancora un algoritmo lineare e molto meglio dell'utilizzo di init e last per ciascun elemento, che è quadratico.