Haskell fajny język. Jak człowiek całe życie programował imperatywnie, to podobno rozwijające jest, jak się trochę poprogramuje w całkiem inny sposób, bo bardzo to rozwija umysł.
Z Haskellem jest tylko jeden problem: że nic tam się nie da zrobić normalnie, tylko trzeba kombinować. Na przykład w normalnych językach jakbym miał policzyć silnię, to bym zrobił jakoś tak:
funkcja silnia(n):
wynik = 1
for i = 2 to n:
wynik = wynik * i
return wynik
a w Haskellu trzeba kombinować jakoś rekurencyjnie. Zastanawiam się więc, czy nie dałoby się jednak zmusić Haskella, żeby programować w nim normalnie, imperatywnie. Na przykład, czy dałoby się jakoś zapisać w Haskellu ten powyższy prosty, imperatywny algorytm na liczenie silni? W sumie można. Jego istotą jest to, że jest pewien globalny stan, składający się z dwu integerów – wyniku oraz i – i potem w kółko odpalane jest polecenie, które zmienia ten stan. Tak długo, jak długo globalny stan spełnia pewien warunek. Można więc powyższy algorytm zapisać w Haskellu tak:
data Stan = Stan {
i :: Integer,
wynik :: Integer
} deriving Show
stan = Stan {i=2, wynik=1}
petla :: Stan -> Stan
petla stan
| i stan > 4 = stan
| otherwise = petla (stan { i = (i stan) + 1, wynik = (wynik stan) * (i stan) })
silnia4 = wynik (petla stan)
Można by to trochę uogolnić, żeby mieć funkcję liczącą nie silnię z czterech, a silnię z dowolnej liczby:
data Stan = Stan {
i :: Integer,
wynik :: Integer
} deriving Show
stan = Stan {i=2, wynik=1}
petla :: Stan -> Integer -> Stan
petla stan n
| i stan > n = stan
| otherwise = petla (stan { i = (i stan) + 1, wynik = (wynik stan) * (i stan) }) n
silnia :: Integer -> Integer
silnia n = wynik (petla stan n)
Jak widać, da się zwykłe, imperatywnie pomyślane algorytmy prosto zapisywać w Haskellu, jak się trochę postarać. Ponieważ taka pętla wykonująca polecenie tak długo, jak długo spełniony jest pewien warunek, może się jeszcze nieraz przydać, można ten program zrefaktoryzować – robiąc funkcję, której przekażemy dowolne polecenie (polecenie to funkcja, która zmienia globalny stan), a ona wykonuje to polecenie tak długo, jak długo i (to i to integer będący polem w globalnym stanie) nie przekroczy zadanej wartości. O, tak:
data Stan = Stan {
i :: Integer,
wynik :: Integer
} deriving Show
stan = Stan {i=2, wynik=1}
type Polecenie = (Stan -> Stan)
petla :: Stan -> Polecenie -> Integer -> Stan
petla stan polecenie n
| i stan > n = stan
| otherwise = petla (polecenie stan) polecenie n
polecenie :: Polecenie
polecenie stan = stan { i = (i stan) + 1, wynik = (wynik stan) * (i stan) }
silnia :: Integer -> Integer
silnia n = wynik (petla stan polecenie n)
Zauważcie, że zdefiniowałem nowy typ Polecenie – polecenie to funkcja zmieniająca globalny stan, czyli przyjmująca jakiś stan i zwracająca jakiś stan.
Skoro już robię tę funkcję petla tak, żeby dało się ją też uzyć w innych programach, to można ją uogólnić jeszcze bardziej. Tak, żeby można jej było zadać dowolny warunek. Żeby to był taki bardziej while niż for. O, tak:
data Stan = Stan {
i :: Integer,
wynik :: Integer
} deriving Show
stan = Stan {i=2, wynik=1}
type Polecenie = Stan -> Stan
type Warunek = Stan -> Bool
petla :: Stan -> Polecenie -> Warunek -> Stan
petla stan polecenie warunek
| warunek stan = stan
| otherwise = petla (polecenie stan) polecenie warunek
polecenie :: Polecenie
polecenie stan = stan { i = (i stan) + 1, wynik = (wynik stan) * (i stan) }
warunek :: Warunek
warunek stan = i stan > 4
silnia4 :: Integer
silnia4 = wynik (petla stan polecenie warunek)
Używając tej nowej, lepszej pętli możemy znowu zrobić funkcję, która policzy silnię z dowolnej liczby, a nie tylko z czterech:
data Stan = Stan {
i :: Integer,
wynik :: Integer
} deriving Show
stan = Stan {i=2, wynik=1}
type Polecenie = Stan -> Stan
type Warunek = Stan -> Bool
petla :: Stan -> Polecenie -> Warunek -> Stan
petla stan polecenie warunek
| warunek stan = stan
| otherwise = petla (polecenie stan) polecenie warunek
polecenie :: Polecenie
polecenie stan = stan { i = (i stan) + 1, wynik = (wynik stan) * (i stan) }
dajWarunek :: Integer -> Warunek
dajWarunek n stan = i stan > n
silnia :: Integer -> Integer
silnia n = wynik (petla stan polecenie (dajWarunek n))
Choć nie wiem, może ładniej by było, gdyby to n, do którego chcemy policzyć silnię, też było przechowywane w stanie:
data Stan = Stan {
n :: Integer,
i :: Integer,
wynik :: Integer
} deriving Show
type Polecenie = Stan -> Stan
type Warunek = Stan -> Bool
petla :: Stan -> Polecenie -> Warunek -> Stan
petla stan polecenie warunek
| warunek stan = stan
| otherwise = petla (polecenie stan) polecenie warunek
polecenie :: Polecenie
polecenie stan = stan { i = (i stan) + 1, wynik = (wynik stan) * (i stan) }
warunek :: Warunek
warunek stan = i stan > (n stan)
silnia :: Integer -> Integer
silnia n = wynik (petla (Stan {n=n, i=2, wynik=1}) polecenie warunek)
Czasem może być potrzebne, wygodne, eleganckie, żeby w pętli było wykonywane nie jedno polecenie, tylko kilka. Na przykład w tym przykładzie z silnią może ładnie byłoby mieć w pętli dwa osobne polecenia: jedno mnożące wynik, drugie zwiększające i. Łatwe: polecenia można komponować:
data Stan = Stan {
n :: Integer,
i :: Integer,
wynik :: Integer
} deriving Show
type Polecenie = Stan -> Stan
type Warunek = Stan -> Bool
petla :: Stan -> Polecenie -> Warunek -> Stan
petla stan polecenie warunek
| warunek stan = stan
| otherwise = petla (polecenie stan) polecenie warunek
pomnoz :: Polecenie
zwieksz :: Polecenie
polecenie :: Polecenie
pomnoz stan = stan { wynik = (wynik stan) * (i stan) }
zwieksz stan = stan { i = (i stan) + 1 }
polecenie = zwieksz . pomnoz
warunek :: Warunek
warunek stan = i stan > (n stan)
silnia :: Integer -> Integer
silnia n = wynik (petla (Stan {n=n, i=2, wynik=1}) polecenie warunek)
Skoro już tak bawimy się w komponowanie, to pewnie warto by przerobić funkcję petla, żeby jej wynikiem też było polecenie. Dzięki temu będzie na przyklad można robić pętlę w pętli. Powinno to być proste, bo skoro Polecenie to Stan -> Stan, to w funkcji petla wystarczy zmienić kolejność parametrów. Jest:
petla :: Stan -> Polecenie -> Warunek -> Stan
a ma być:
petla :: Polecenie -> Warunek -> Stan -> Stan
czyli:
petla :: Polecenie -> Warunek -> Polecenie
Uwaga: dymi czacha? Zmieniłem kolejność argumentów. Przez to ostatni argument to Stan i zwracany typ to Stan. I teraz typ ostatniego argumentu i typ zwracanej wartości zastępuję jednym typem. To jest jeden z tych momentów, w których załamuje się uproszczone myślenie, według którego mamy w Haskellu funkcje wieloargumentowe, tylko dziwnie stawiamy te strzałki.
Więc teraz funkcję petla zmieniam z takiej:
petla :: Stan -> Polecenie -> Warunek -> Stan
petla stan polecenie warunek
| warunek stan = stan
| otherwise = petla (polecenie stan) polecenie warunek
na taką:
petla :: Polecenie -> Warunek -> Polecenie
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
Ciekawie jest przyjrzeć się tym dwu linijkom:
petla :: Polecenie -> Warunek -> Polecenie
petla polecenie warunek stan
(...)
Jeśli wyobrażać sobie, że w Haskellu mamy funkcje wieloparametrowe, to z deklaracji typu wynikałoby, że ta funkcja dostaje dwa parametry, a w definicji są trzy parametry. No, ale ten trzeci parametr to jest połowa zwracanej wartości.
Żeby sprawdzić, czy ta nowa funkcja petla dobrze działa, spróbuję zapisać Haskellem taki algorytm:
funkcja sumaIloczynow(a, b):
suma = 0
for i = 1 to a:
for j = 1 to b:
suma = suma + i * j
return suma
Wychodzi coś takiego:
data Stan = Stan {
a :: Integer,
b :: Integer,
i :: Integer,
j :: Integer,
suma :: Integer
} deriving Show
type Polecenie = Stan -> Stan
type Warunek = Stan -> Bool
petla :: Polecenie -> Warunek -> Polecenie
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
polecenie :: Polecenie
polecenie stan = stan { suma = (suma stan) + ((i stan) * (j stan)) }
zwiekszI :: Polecenie
zwiekszJ :: Polecenie
zwiekszI stan = stan { i = (i stan) + 1 }
zwiekszJ stan = stan { j = (j stan) + 1 }
petla1 :: Polecenie
petla1 = petla (zwiekszJ . polecenie) ((\stan -> (j stan) >= (b stan)) :: Warunek)
petla2 :: Polecenie
petla2 = petla (zwiekszI . petla1) ((\stan -> (i stan) >= (a stan)) :: Warunek)
sumaIloczynow :: Integer -> Integer -> Integer
sumaIloczynow a b = suma (petla2 (Stan {a=a, b=b, i=1, j=1, suma=0}))
Warunków, jak widzicie, nie tworzyłem w zmiennych, tylko pisałem na miejscu. Tylko podawałem przy nich typy, w razie jakbym zrobił jakiś błąd, to żeby mieć sensowne komunikaty.
Podoba mi się to miejsce, jak się wywołuje funkcję petla. W definicji funkcji widzę trzy parametry – polecenie, warunek i stan, ale przekazuję tylko dwa pierwsze (polecenie i warunek). Bo ostatni parametr to, jak pamiętamy, nie jest naprawdę parametr, tylko pierwsza połowa zwracanej wartości.
Nie musiałem definiować typów Polecenie i Warunek. Ale warto, bo dzięki temu jak zrobię coś nie tak, to będę miał lepsze komunikaty o błędach. Na przykład jakbym napisał taki prosty program, który sumuje liczby od 0 do zadanej liczby:
data Stan = Stan {
a :: Integer,
i :: Integer,
suma :: Integer
} deriving Show
type Polecenie = Stan -> Stan
type Warunek = Stan -> Bool
petla :: Polecenie -> Warunek -> Polecenie
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
polecenie :: Polecenie
polecenie stan = stan { suma = (suma stan) + (i stan) }
zwiekszI :: Polecenie
zwiekszI stan = stan { i = (i stan) + 1 }
petelka :: Polecenie
petelka = petla (zwiekszI . polecenie) ((\stan -> (i stan) > (a stan)) :: Warunek)
f :: Integer -> Integer
f a = suma (petelka (Stan {a=a, i=0, suma=0}))
Rozważmy, co by wyszło, jakbym przy wywołaniu funkcji petla pomylił kolejność argumentów. Znaczy, zamiast napisać tak:
petelka = petla (zwiekszI . polecenie) ((\stan -> (i stan) > (a stan)) :: Warunek)
napisałbym tak:
petelka = petla ((\stan -> (i stan) > (a stan)) :: Warunek) (zwiekszI . polecenie)
Znaczy, program w takiej błędnej wersji będzie wyglądał tak:
data Stan = Stan {
a :: Integer,
i :: Integer,
suma :: Integer
} deriving Show
type Polecenie = Stan -> Stan
type Warunek = Stan -> Bool
petla :: Polecenie -> Warunek -> Polecenie
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
polecenie :: Polecenie
polecenie stan = stan { suma = (suma stan) + (i stan) }
zwiekszI :: Polecenie
zwiekszI stan = stan { i = (i stan) + 1 }
petelka :: Polecenie
petelka = petla ((\stan -> (i stan) > (a stan)) :: Warunek) (zwiekszI . polecenie)
f :: Integer -> Integer
f a = suma (petelka (Stan {a=a, i=0, suma=0}))
No i co będzie, jak taki błędny program spróbuję uruchomić? Taki komunikat dostanę:
[1 of 1] Compiling Main ( test.hs, interpreted )
test.hs:44:18:
Couldn't match type `Bool' with `Stan'
Expected type: Polecenie
Actual type: Warunek
In the first argument of `petla', namely
`((\ stan -> (i stan) > (a stan)) :: Warunek)'
In the expression:
petla
((\ stan -> (i stan) > (a stan)) :: Warunek) (zwiekszI . polecenie)
In an equation for `petelka':
petelka
= petla
((\ stan -> (i stan) > (a stan)) :: Warunek) (zwiekszI . polecenie)
test.hs:44:62:
Couldn't match type `Stan' with `Bool'
Expected type: Stan -> Bool
Actual type: Polecenie
In the first argument of `(.)', namely `zwiekszI'
In the second argument of `petla', namely `(zwiekszI . polecenie)'
In the expression:
petla
((\ stan -> (i stan) > (a stan)) :: Warunek) (zwiekszI . polecenie)
Failed, modules loaded: none.
No, bardzo ładny komunikat o błędzie. Od razu widać, że w pierwszym argumencie funkcji pętla miało być Polecenie, a jest Warunek.
A teraz zobaczmy, co by było, gdybym ten program napisał nie definiując typów. Jakbym napisał ten program bezbłędnie, to by działał – oto przykład:
data Stan = Stan {
a :: Integer,
i :: Integer,
suma :: Integer
} deriving Show
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
polecenie stan = stan { suma = (suma stan) + (i stan) }
zwiekszI stan = stan { i = (i stan) + 1 }
petelka = petla (zwiekszI . polecenie) ((\stan -> (i stan) > (a stan)))
f a = suma (petelka (Stan {a=a, i=0, suma=0}))
Ale rozważmy, co by wyszło, jakbym przy wywołaniu funkcji petla pomylił kolejność argumentów. Znaczy, zamiast napisać tak:
petelka = petla (zwiekszI . polecenie) ((\stan -> (i stan) > (a stan)))
napisałbym tak:
petelka = petla ((\stan -> (i stan) > (a stan))) (zwiekszI . polecenie)
Znaczy, program w takiej błędnej wersji będzie wyglądał tak:
data Stan = Stan {
a :: Integer,
i :: Integer,
suma :: Integer
} deriving Show
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
polecenie stan = stan { suma = (suma stan) + (i stan) }
zwiekszI stan = stan { i = (i stan) + 1 }
petelka = petla ((\stan -> (i stan) > (a stan))) (zwiekszI . polecenie)
f a = suma (petelka (Stan {a=a, i=0, suma=0}))
Teraz jak go uruchomię, to komunikat o błędzie będzie dużo gorszy – taki:
[1 of 1] Compiling Main ( test.hs, interpreted )
test.hs:15:31:
Couldn't match expected type `Stan' with actual type `Bool'
In the first argument of `i', namely `stan'
In the first argument of `(>)', namely `(i stan)'
In the expression: (i stan) > (a stan)
test.hs:15:42:
Couldn't match expected type `Stan' with actual type `Bool'
In the first argument of `a', namely `stan'
In the second argument of `(>)', namely `(a stan)'
In the expression: (i stan) > (a stan)
test.hs:15:51:
Couldn't match type `Stan' with `Bool'
Expected type: Stan -> Bool
Actual type: Stan -> Stan
In the first argument of `(.)', namely `zwiekszI'
In the second argument of `petla', namely `(zwiekszI . polecenie)'
In the expression:
petla ((\ stan -> (i stan) > (a stan))) (zwiekszI . polecenie)
test.hs:15:62:
Couldn't match type `Stan' with `Bool'
Expected type: Bool -> Stan
Actual type: Stan -> Stan
In the second argument of `(.)', namely `polecenie'
In the second argument of `petla', namely `(zwiekszI . polecenie)'
In the expression:
petla ((\ stan -> (i stan) > (a stan))) (zwiekszI . polecenie)
Failed, modules loaded: none.
No więc dobrze jest zdefiniować te typy Polecenie i Warunek. Ale te typy zależą od typu Stan. A typ Stan będzie w każdym programie wyglądał inaczej. Więc jeśli zechcę raz napisać funkcję petla a potem z niej korzystać, będzie problem: jak zrobić, żeby typy Polecenie i Warunek nie zależały od typu Stan. Można zrobić, żeby to nie były typy tylko konstruktory typów – tak:
type Polecenie stan = stan -> stan
type Warunek stan = stan -> Bool
Teraz funkcja petla wygląda tak:
petla :: Polecenie stan -> Warunek stan -> Polecenie stan
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
A cały program razem – tak:
data Stan = Stan {
a :: Integer,
b :: Integer,
i :: Integer,
j :: Integer,
suma :: Integer
} deriving Show
type Polecenie stan = stan -> stan
type Warunek stan = stan -> Bool
petla :: Polecenie stan -> Warunek stan -> Polecenie stan
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
polecenie :: Polecenie Stan
polecenie stan = stan { suma = (suma stan) + ((i stan) * (j stan)) }
zwiekszI :: Polecenie Stan
zwiekszJ :: Polecenie Stan
zwiekszI stan = stan { i = (i stan) + 1 }
zwiekszJ stan = stan { j = (j stan) + 1 }
petla1 :: Polecenie Stan
petla1 = petla (zwiekszJ . polecenie) ((\stan -> (j stan) >= (b stan)) :: Warunek Stan)
petla2 :: Polecenie Stan
petla2 = petla (zwiekszI . petla1) ((\stan -> (i stan) >= (a stan)) :: Warunek Stan)
sumaIloczynow :: Integer -> Integer -> Integer
sumaIloczynow a b = suma (petla2 (Stan {a=a, b=b, i=1, j=1, suma=0}))
No to od teraz będę w przykładach jakoś wydzielał wizualnie, że najpierw będzie część z rzeczami, co można je ponownie użyć, przeklejać z programu do programu – taka jakby biblioteka – a potem sprawy specyficzne dla danego zastosowania.
To może teraz zobaczmy, czy da się tego użyć do czegoś praktycznego. Napiszmy funkcję, która liczy pierwszych n wyrazów ciągu Fibonacciego. Według takiego algorytmu:
a = 1
b = 1
wynik = [1, 1]
for j = 1 to n:
c = a + b
a = b
b = c
wynik.push(c)
No, to proste. Najpierw wrzucę bibliotekę, czyli tę taką część wspólną:
type Polecenie stan = stan -> stan
type Warunek stan = stan -> Bool
petla :: Polecenie stan -> Warunek stan -> Polecenie stan
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
Potem zdefiniuję typ opisujący stan programu:
data StanDoFibonacciego = StanDoFibonacciego {
a :: Integer,
b :: Integer,
c :: Integer,
j :: Integer,
n :: Integer,
rezultat :: [Integer]
} deriving Show
Potem spora część: napiszę poszczególne polecenia i połączę je kropkami. Tylko uwaga, bo przecież kropki w Haskellu działają w drugą stronę, więc trzeba pisać polecenia w odwrotnej kolejności:
cialoPetli :: Polecenie StanDoFibonacciego
cialoPetli = (
(\stan -> stan { j = (j stan) + 1 })
. (\stan -> stan { rezultat = (rezultat stan) ++ [c stan] })
. (\stan -> stan { b = (c stan) })
. (\stan -> stan { a = (b stan) })
. (\stan -> stan { c = (a stan) + (b stan) })
)
Potem zapisuję sobie warunek pętli:
warunekPetli :: Warunek StanDoFibonacciego
warunekPetli stan = (j stan) >= (n stan)
No i już mogę napisać funkcję, której daje się liczbę, a ona tworzy początkowy stan, w którym w n jest ta liczba, puszcza pętlę rozpoczynającą się od tego stanu, a potem z wyniku pętli wyciąga rezultat:
ciagFibonacciego :: Integer -> [Integer]
ciagFibonacciego x = rezultat (
petla cialoPetli warunekPetli StanDoFibonacciego {a = 1, b = 1, c = 999, j = 1, n = x, rezultat = [1, 1]}
)
Razem wychodzi z tego taki ładny program:
-- biblioteka
type Polecenie stan = stan -> stan
type Warunek stan = stan -> Bool
petla :: Polecenie stan -> Warunek stan -> Polecenie stan
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
-- właściwy program
data StanDoFibonacciego = StanDoFibonacciego {
a :: Integer,
b :: Integer,
c :: Integer,
j :: Integer,
n :: Integer,
rezultat :: [Integer]
} deriving Show
cialoPetli :: Polecenie StanDoFibonacciego
cialoPetli = (
(\stan -> stan { j = (j stan) + 1 })
. (\stan -> stan { rezultat = (rezultat stan) ++ [c stan] })
. (\stan -> stan { b = (c stan) })
. (\stan -> stan { a = (b stan) })
. (\stan -> stan { c = (a stan) + (b stan) })
)
warunekPetli :: Warunek StanDoFibonacciego
warunekPetli stan = (j stan) >= (n stan)
ciagFibonacciego :: Integer -> [Integer]
ciagFibonacciego x = rezultat (
petla cialoPetli warunekPetli StanDoFibonacciego {a = 1, b = 1, c = 999, j = 1, n = x, rezultat = [1, 1]}
)
Fajne, nie? Tylko żeby się jeszcze dało pisać te polecenia w normalnej kolejności. Na szczęście to akurat jest proste. Wystarczy zrobić funkcję, która komponuje dwie funkcje, ale tak, żeby najpierw wykonywała się lewa, a potem prawa:
(==>) :: (a -> b) -> (b -> c) -> a -> c
(==>) = flip (.)
W efekcie program wygląda tak:
-- biblioteka
type Polecenie stan = stan -> stan
type Warunek stan = stan -> Bool
petla :: Polecenie stan -> Warunek stan -> Polecenie stan
petla polecenie warunek stan
| warunek stan = stan
| otherwise = petla polecenie warunek (polecenie stan)
(==>) :: (a -> b) -> (b -> c) -> a -> c
(==>) = flip (.)
-- właściwy program
data StanDoFibonacciego = StanDoFibonacciego {
a :: Integer,
b :: Integer,
c :: Integer,
j :: Integer,
n :: Integer,
rezultat :: [Integer]
} deriving Show
cialoPetli :: Polecenie StanDoFibonacciego
cialoPetli = (
(\stan -> stan { c = (a stan) + (b stan) })
==> (\stan -> stan { a = (b stan) })
==> (\stan -> stan { b = (c stan) })
==> (\stan -> stan { rezultat = (rezultat stan) ++ [c stan] })
==> (\stan -> stan { j = (j stan) + 1 })
)
warunekPetli :: Warunek StanDoFibonacciego
warunekPetli stan = (j stan) >= (n stan)
ciagFibonacciego :: Integer -> [Integer]
ciagFibonacciego x = rezultat (
petla cialoPetli warunekPetli StanDoFibonacciego {a = 1, b = 1, c = 999, j = 1, n = x, rezultat = [1, 1]}
)
Taki sposób pisania programów nie dość, że bez sensu, to ma jeszcze jedną zaletę. Przy klasycznym rekurencyjnym liczeniu silni każde kolejne wywołanie funkcji – wyobraź to sobie, bo nie chce mi się rysować porządnego rysunku – reprezentuje policzenie silni z coraz to mniejszej liczby. I obliczenia dzieją się tak:
Policz, ile to silnia z czterech.
Dobrze, policzę, tylko on niech policzy, ile to silnia z trzech.
Dobrze, tylko on niech policzy, ile to silnia z dwu.
Dobrze, tylko on niech policzy, ile to silnia z jeden.
To proste, jeden.
Dobra, to mi wychodzi jeden razy dwa – czyli dwa.
Dobra, to mi wychodzi dwa razy trzy – czyli sześć.
Dobra, to mi wychodzi trzy razy cztery – czyli dwanaście.
O, wyszło ci dwanaście – dziękuję.
Jak widać, najpierw jest budowany stos (wcięcia rosną), a potem zdejmowane są z niego kolejne ramki; i to przy tym zdejmowaniu są robione kolejne kroki obliczeń.
A przy moim sposobie liczenia silni każdy kolejny krok reprezentuje policzenie silni z coraz większej liczby. To jest tak:
Każecie mi policzyć silnię z czterech. Dobrze, przygotowuję stan zawierający silnię z jeden i czwórkę, do której dążymy. Masz, teraz ty ją przekształć.
Dziękuję. To ja otrzymaną od ciebie silnię mnożę przez dwa i wynik umieszczam w stanie. Czy doszliśmy do czwórki? A, nie – to niech teraz on ją przekształci. Masz.
Dziękuję. To ja otrzymaną od ciebie silnię mnożę przez trzy i wynik umieszczam w stanie. Czy doszliśmy do czwórki? A, nie – to niech teraz on ją przekształci. Masz.
Dziękuję. To ja otrzymaną od ciebie silnię mnożę przez cztery i wynik umieszczam w stanie. Czy doszliśmy do czwórki? O, widzę, że tak. No to to jest nasz wynik. Oddaję ci zmieniony stan.
Oddaję ci stan, który dostałem.
Oddaję ci stan, który dostałem.
Dziękuję. Ze stanu, który dostałem, wyciągam wynik i go zwracam.
Przy moim liczeniu obliczenia dzieją się, kiedy stos rośnie – a zdejmowanie ramek to tylko formalność, potrzebna tylko do tego, żeby wrócić do tego, od którego się zaczęło. Można by więc ramki, które są na dole stosu, kasować w trakcie obliczeń, żeby nie zajmowały pamięci. Byle tylko mieć tę początkową ramkę – żeby pamiętać gdzie wrócić.
No, i o to chodzi w rekurencji ogonowej. Jakoś nigdy z wikipedii nie mogłem zrozumieć, co w niej takiego dobrego, i dopiero na tym przykładzie zrozumiałem, o co chodzi.
I jeszcze tak sobie myślę, że może i w tej wersji liczenia silni, kiedy rekurencja jest nieogonowa, też można by te ramki, co są w dole stosu, kasować? Przecież jak będą potrzebne, to można je będzie łatwo odtworzyć. W tych ramkach są przechowywane argumenty kolejnych wywołań, a one są kolejnymi liczbami naturalnymi. Więc jak wracam z wywołania, w którym argument wynosił pięć, to mam trafić do ramki, w której argument wynosił cztery. Hm, przemyślę to.