Czy te funkcje są rekursywne?

Question

Uczę się rekursji ogona i mam pewne trudności w określeniu, czy moja funkcja jest rekurencyjna czy też nie (głównie w funkcjach, w których używam innej funkcji).

Zaimplementowałem dwie następujące funkcje, ale nie jestem pewien, czy są one rekursywne, czy też nie.

Pierwszy to funkcja łączenia dwóch list.

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 

Obliczenia w funkcji są przetwarzane przed rekurencyjnego rozmowy, ale jest za pomocą ostatniego i INIT, które nie są ogon rekurencyjne (I zaznaczone ich definicji w http://ww2.cs.mu.oz.au/172/Haskell/tourofprelude.html)

Drugą funkcją jest usunięcie pierwsze wystąpienie danej liczby w podanej liście.

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 [] 

droga Aux parametr (który może przyjmować 0 lub 1, a wartość) jest używany do oznaczania, czy wcześniejszego występowania została usunięta czy nie.

W funkcji usuwania, gdy wynik częściowy jest przekazywany przez wywołanie rekursywne, lista jest odwracana, na końcu lista jest bez pierwszej wartości, ale odwrócona, dlatego musi być odwrócona do zwrócenia jako wynik.

Answer 1

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

jest wezwaniem ogon, ale last(h:t):result zaczyna życie jako unevaluated thunk, tak to jest (ręcznie faliste) trochę jak tych zagnieżdżonych wywołań funkcji są nadal na stosie.

conca dopasowuje wzorce do pierwszego argumentu, więc init zostanie ocenione w wywołaniu rekurencyjnym.

conca jest nie-ścisłym w swoim drugim argumencie, więc te thunks nie zostaną ocenione podczas stosowania wywołania rekursywnego conca.

---

remov jest ogon rekurencyjnej, tak, ale ....

Zastosowanie True i False zamiast 0 i 1 aby Twój kod wyraźniej:

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 [] 

Byłoby lepiej być nie przekazywanie tak dużej ilości danych, zmniejszanie kopiowania n i używanie dwóch funkcji zamiast pojedynczej funkcji, która testuje parametr boolowski:

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) 

ale got a result tylko oblicza reverse result ++ a, więc można napisać

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

Jednak to wszystko wydaje się dość dużo wysiłku, i nadal przegląda listę dwukrotnie. Dlaczego nie pójść na rozmowy non-Ogon:

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

Ma to tę zaletę wytwarzania jej pierwszy element od razu, a nie działa całą listę, a skróty do powrotu t bez dalszych obliczeń po jej znalezieniu elementem usunąć.Wypróbuj wyścig length (removeFast 1 [1..100000]) przeciwko length (remove 1 [1..100000]) (zmieniaj liczbę zer w zależności od szybkości procesora).

---

Jeśli chcesz, aby bardziej wydajne ogon rekurencyjnej conca, można użyć sztuczki z remove:

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

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

Jak poprzednio, jesteś z poruszaniem this dwa razy, raz invert ing go do inny, ale nadal jest to algorytm liniowy i znacznie lepszy niż użycie init i last dla każdego elementu, który jest kwadratowy.