Jak się implementuje spamiętywanie w Haskellu?

Przymuszony na studiach zdołałem napisać w Haskellu interpreter wymyślonego przez siebie języka programowania, nawet z konieczności transformaturów monad używałem, choć oczywiście ani trochę nie czuję, bym rozumiał, co robiłem.

Niewątpliwie programowanie funkcyjne to zaległość, którą trzeba będzie nadrobić, ale na poważnie się za to wezmę kiedy indziej...

Na razie jedno proste pytanie: Jak zaimplementować w Haskellu coś tak prostego, jak Fibonacci lub 3n+1? Myślałem nad tym i naprawdę nie mam pojęcia.

Te problemy wymagają spamiętywania, by ich złożoność nie rosła do absurdalnych wielkości. Jak takie coś się implementuje w Haskellu?

Widzę dwie możliwości: (a) funkcja licząca fibonacciego zawsze oczekuje jako argumentu i zwraca nie tylko wynik, ale i obecną tablicę z cache. Ale taki pattern to jest dokładnie to, co - o ile rozumiem - mają abstrahować monady. A więc (b) monada State - ale to wydaje się być jakiś overkill.

Nie piszę w Haskhellu, ale wydaje mi się, że musiałbyś wykorzystać rekurencję ogonową.

Jest wiki:
https://wiki.haskell.org/The_Fibonacci_sequence
A dokładniej, taki pseudokod do zimplementowania:

def fibo_iterative(a, b, cnt):
    if cnt == 0:
        return b
    else:
        return fibo_iterative(a + b, a, cnt - 1)

lion137 napisał(a):

Jest wiki:
https://wiki.haskell.org/The_Fibonacci_sequence
A dokładniej, taki pseudokod do zimplementowania:

def fibo_iterative(a, b, cnt):
    if cnt == 0:
        return b
    else:
        return fibo_iterative(a + b, a, cnt - 1)

Tam gdzie nie da się zamienić rekurencji-rekurencji (złej) na rekurencji-iterację (dobrą) można jeszcze użyć Memoize

lion137 napisał(a):

Jest wiki:
https://wiki.haskell.org/The_Fibonacci_sequence
A dokładniej, taki pseudokod do zimplementowania:

def fibo_iterative(a, b, cnt):
    if cnt == 0:
        return b
    else:
        return fibo_iterative(a + b, a, cnt - 1)

A teraz wyobraźmy sobie, że wołam fibo_iterative dla kolejnych liczb naturalnych bo chcę mieć tablicę wartości.

Albo muszę szybko odpowiadać online na zapytania o wartości liczb Fibonaciego dla dowolnych argumentów.

Nadal jestem w ciemnej dupie.

Dlatego świadomie pytałem o spamiętywanie, a nie o rekurencję ogonową.

Rekurencja ogonowa jest OK ale jeśli się nie mylę nie może w pełni zastąpić spamiętywania

Jak chcesz mieć tablicę wartości to możesz ją przekazać jako akumulator w rekurencji ogonowej.

Albo muszę szybko odpowiadać online na zapytania o wartości liczb Fibonaciego dla dowolnych argumentów.

Popatrz w tym wiki, najszybsze fibo jest logarytmiczne.

"Haskell memoization" - pierwszy wynik z DDG. Dodatkowo wydaje mi się, że GHC czasem to robi "automagicznie" jeśli "zauważy", że może.