F# - wyniki gimnastyki

Ok, rozwiązań do F-szarpowych ćwiczeń z posta http://wojtek-m.blogspot.com/2009/10/f-i-gimnastyka-umysu.html nikt nie umieścił, więc pora na mnie :P

1. Własna funkcja zwracająca długość listy (rekurencja ogonowa).

Wersja bez rekurencji ogonowej jest dość oczywista:

let length l =
    match l with
    | [] -> 0
    | h::t -> (length t) + 1

Rekurencję ogonową można osiągnąć z użyciem drugiego parametru, który będzie zliczał długość dotychczas przejrzanej listy - początkowo ma on wartość 0. Jeżeli dojdziemy do końca listy, zwracamy wartość tego parametru. Dzięki temu nie wykorzystujemy w ogóle stosu wywołań funkcji - działamy jak iteracyjna pętla ;)

let length l =
    let rec length l acc =
        match l with
        | [] -> acc
        | h::t -> length t (acc + 1)
    in
        length l 0

2. Funkcja odwracająca listę (złożoność O(n) i rekurencja ogonowa).

Żeby osiągnąć złożoność liniową ze względu na długość listy do odwrócenia należy uważnie dodawać do niej elementy - dodanie na początek (lub pobranie z początku) listy to operacja o stałej złożoności, a dodanie na jej koniec lub pobranie ostatniego elementu wymaga przejrzenia całej listy...
Dlatego tutaj wykorzystamy również dwa parametry - pierwszy to lista do odwrócenia, drugi to dotychczasowy wynik (już przejrzane elementy w odwrotnym porządku). Jednak aby zachować złożoność liniową nie możemy stosować "naiwnego" algorytmu:

1. Weź ostatni element listy do przejrzenia.
2. Dodaj go jako ostatni element listy wynikowej.

ponieważ ma on złożoność O(n³). Zauważmy, że słowo ostatni pojawia się dwukrotnie w algorytmie - dlatego spokojnie można go "odwrócić" i zacząć od końca (a właściwie od początku, bo działamy tylko na początkach list):

1. Weź pierwszy element listy do odwrócenia.
2. Dodaj go jako pierwszy element listy wynikowej.

let reverse l =
    let rec reverse l acc =
        match l with
        | [] -> acc
        | h::t -> reverse t (h::acc)
    in
        reverse l []

Powyższy algorytm zadziała, ponieważ pierwszy element odwracanej listy jako pierwszy trafi na początek wyniku, drugi element odwracanej listy trafi na początek wyniku jako drugi, ..., a ostatni element odwracanej listy trafi na początek wyniku tuż przed zakończeniem algorytmu.
Osiągnęliśmy zatem złożoność liniową (dwie operacje dla każdego elementu listy) jak i rekurencyjność ogonową (podobnie jak w 1).

Ćwiczenie nr 3 doczeka się rozwiązania w terminie późniejszym, inaczej ten post byłby zbyt długi ;)