Witam.
Próbuję zrozumieć rekurencję ogonową.
Kiedy patrzę na najprostsze przykłady (z użyciem akumulatora), to niby
to rozumiem, ale kiedy próbuję z funkcją troszkę bardziej
skomplikowaną niż silnia to wymiękam.
Konkretnie wymiękłem na takiej prostej implementacji insert sorta, czy
da się to zmusić do bycia tail-recursive?
Gdyby ktoś zechciał mi to jakoś opisowo wytłumaczyć na tym przykładzie
to będę bardzo wdzięczny

let rec insertSort l =
let rec insert elem lst =
match lst with
| [] -> [elem]
| head::tail -> if elem < head then elem::head::tail else
head::(insert elem tail)
match l with
| [] -> []
| f::r -> insert f <| insertSort r

Pozdrawiam.

do góry

On Feb 10, 8:10 pm, Jakub Owczarski <j...@g...com> wrote:
> Witam.
> Próbuję zrozumieć rekurencję ogonową.
> Kiedy patrzę na najprostsze przykłady (z użyciem akumulatora), to niby
> to rozumiem, ale kiedy próbuję z funkcją troszkę bardziej
> skomplikowaną niż silnia to wymiękam.
> Konkretnie wymiękłem na takiej prostej implementacji insert sorta, czy
> da się to zmusić do bycia tail-recursive?
> Gdyby ktoś zechciał mi to jakoś opisowo wytłumaczyć na tym przykładzie
> to będę bardzo wdzięczny
>
> let rec insertSort l =
>     let rec insert elem lst =
>         match lst with
>         | [] -> [elem]
>         | head::tail -> if elem < head then elem::head::tail else
> head::(insert elem tail)
>     match l with
>     | [] -> []
>     | f::r -> insert f <| insertSort r

Nie znam F# więc może źle to odczytuję, ale wygląda, jakbyś
przekazywał wynik rekurencyjnie wywoływanego insertSort jako argument
- czy się mylę? Jeśli tak, to to nie jest rekurencja ogonowa, tylko
zwykła rekurencja.

do góry

On Feb 11, 10:15 am, Andrzej Jarzabek <a...@g...com>
wrote:

> Nie znam F# więc może źle to odczytuję, ale wygląda, jakbyś
> przekazywał wynik rekurencyjnie wywoływanego insertSort jako argument
> - czy się mylę? Jeśli tak, to to nie jest rekurencja ogonowa, tylko
> zwykła rekurencja.

Tak, rekurencyjnie sortuję listę pomniejszoną o pierwszy element, do
momentu w którym nie ma już żadnej reszty.
Wiem, że to jest zwykła rekurencja, i bardzo chciałbym zobaczyć jak da
się to przerobić, żeby była ogonowa :)

Wiem, że F# nie jest jakiś super popularny, ale może ktoś zna OCamla,
podobno są bardzo zbliżone.

pzdr.

do góry

On Feb 11, 10:39 am, Jakub Owczarski <j...@g...com>
wrote:
> On Feb 11, 10:15 am, Andrzej Jarzabek <a...@g...com>
> wrote:
>
> Wiem, że to jest zwykła rekurencja, i bardzo chciałbym zobaczyć jak da
> się to przerobić, żeby była ogonowa :)
>
> Wiem, że F# nie jest jakiś super popularny, ale może ktoś zna OCamla,
> podobno są bardzo zbliżone.

Nie znam też zbytnio OCamla, więc nie bij jak coś jest nie tak ze
składnią, ale intencja mam nadzieję będzie czytelna:
let insertSort l =
let rec iter_sort sorted unsorted =
let rec insert lst_less elem lst_rest =
match lst_rest with
| [] -> lst_less:elem
| head::tail -> if head<elem then
insert lst_less:head elem tail
else lst_less::elem::lst_rest
match unsorted with
| [] -> sorted
| head::tail iter_sort (insert [] head sorted) tail
iter_sort [] l

Ogólnie jeśli chodzi o tego typu problemy problemy, to przeczytaj
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H
-11.html#%_sec_1.2.1

W ogóle polecam całą tę książkę jak się chce nauczyć technik
programowania funkcyjnego.

do góry