20 grudnia 2008

Fresh i Reset bez użycia zmiennych globalnych

Rozważmy następujący problem. Mamy stworzyć dwie funkcje: fresh i reset. Pierwsza z nich ma generować kolejne liczby naturalne dodatnie, druga ma nam posłużyć do zerowania naszego stanu liczniki. Przykładowa sesja programu może wyglądać na przykład tak:
# fresh ();;
- : int = 1
# fresh ();;
- : int = 2
# fresh ();;
- : int = 3
# fresh ();;
- : int = 4
# reset ();;
- : unit = ()
# fresh ();;
- : int = 1
# fresh ();;
- : int = 2
Cały problem w napisaniu tej funkcji polega na tym, że w implementacji nie możemy korzystać ze zmiennych globalnych. Polecam, abyś sam przez chwilę zastanowił się jak ten problem rozwiązać zanim przeczytasz moje rozwiązanie.

Zmienna w OCamlu "żyje" tak długo aż istnieje wskaźnik na tą wartość. I nie ważne czy zmienna ta została zdefiniowana globalnie czy lokalnie w funkcji.

Pierwszy pomysł to stworzenie funkcji, która jako argument bierze unit, a zwraca parę funkcji (fresh, reset). Zadeklaruje ona lokalnie zmienną, która będzie użyta do zdefiniowania funkcji. Po wyjściu zmienna ta nie będzie już nigdzie widoczna poza zwróconą parą funkcji.
type r = { mutable x : int };;

let create () =
let y = ref {x = 0} in
((fun () -> (ignore (!y.x <- !y.x + 1) ; (!y.x))),
fun () -> ignore (!y.x <- 0));;

let x = create () ;;
let fresh = fst x and reset = snd x;;
Takie rozwiązanie ma swoje wady i zalety. Zaletą jest to że możemy tworzyć wiele par fresh-reset, wadą to, że pozwalamy na korzystanie ze zmiennej x bez konieczności użycia funkcji fresh i reset.

Edit: W komentarzach pojawiły się inne (imho lepsze) rozwiązania tego zadania. Polecam lekturę tych komentarzy ;)

4 komentarze:

Unknown pisze...

Ależ wcale nie trzeba robić tego w ten sposób, nie trzeba korzystać ze zmiennych globalnych. Przepiszę Twój przykład w taki właśnie sposób:

let create war =
let x = ref war in
let fresh () = x := !x + 1; !x
and reset () = x := 0 in
(fresh, reset);;

Potem inicjujesz (np. na zerze):
let (fresh, reset) = create 0;;
i działa... A łatwiej, ładniej i lepiej. :)

npb pisze...

Jeszcze łatwiej, jeszcze ładniej i jeszcze lepiej. Bez żadnych innych zbędnych funkcji, tylko te dwie, o które nas proszono w zadaniu:

let (fresh, reset) =
let x = ref 0 in
let f () = !x <- !x + 1; !x and
r () = !x <- 0 in
(f, r);;

Nie trzeba inicjować :)

Unknown pisze...

Fakt. :) Ale masz błędy w kodzie, podstawienia robi się przez:
x := !x + 1
Czyli podobnie jak w bashu - co innego zmienna, a co innego jej wartość (potrzebny jest operator wyłuskania "!"). Po lewej stronie masz zmienną, po prawej wartość. Składnia ze strzałką tu nie zadziała.

A co do inicjowania - jak dla mnie ma więcej zalet, bo mogę w każdej chwili zdefiniować alternatywną parę funkcji i będą sobie działać niezależnie. No ale to zależy od tego, co się z tym potem chce robić. :)

Btw.: skoro znasz przykład, to czemu nie podałeś go od razu w takiej lepszej formie?

npb pisze...

Co do błędu to masz rację, co mnie trochę zdziwiło, bo wydawało mi się, że operacja przypisania jest tylko cukrem syntaktycznym :-)

Oczywiście masz rację. Jest to niepodwarzalna (razem?) zaleta twojego rozwiązania. Mi w mojej podoba się jednak to, że utworzyliśmy dokładnie te dwie funkcje o które nas prosili w zadaniu i nie wygenerowaliśmy żadnych dodatkowych śmieci (takich jak zmienna x czy funkcja generująca te funkcję) i pod takim względem to rozwiązanie jest piękne ;)

Nie napisałem go od razu bo... nie znałem lepszej wersji tego programu kiedy pisałem tą notkę. Zainspirował mnie dopiero Twój komentarz oraz informacja jaką przekazał mi Maciek (dużo osób [np. Piotrek] mówiło mi że nie da się tego zrobić tak jak ja chcę, dopiero Maciek podsunął mi ten pomysł).