Sposoby pozbywania się jawnej rekurencji w językach czysto funkcyjnych

Wiadomo, dla kolekcji mamy map, fold, foldr, foldl. Wiec chodzi mi wszystkie pozostałe sytuacje gdy nie pracujemy na kolekcjach

Jak chcemy wygenerować kolekcję to jest unfoldr. A nawet unfoldl dla Sequence. W zasadzie przydałby się jeszcze unfoldl dla DList. Dziwne że go nie ma. Może jeszcze nie wszystko zrozumiałem.

Jak chcemy wyliczyć pojedynczą wartość za pomocą rekurencj to mamy loop i loopM

Czy to już jest wszystko? Widziałem kod gdzie ktoś rozmontował rekurencję na leniwą listę używając monady State. Konkretnie w intepreterze języka false. Zastanawiam się czy jeszcze jakaś opcja mi umknęła. Bo ta monada State wydaje się bardzo kusząca. zwłaszcza że walczę z problemem że często program wpada mi w nieskończaną rekurencję i zajmuje coraz więcej zasobów. W Haskellu nie ma StackOverflowException, po prostu program zjada całą pamięć. Tak mógłbym ograniczyć na potrzeby testów ilość iteracji w rekurencji i uratować się przed śmiercją GUI Linuxa

Jest jeszcze fix, ale to chyba żart. Nie widzę sytuacji gdzie miałoby to przewagę nad loop. No chyba że nie da się wszystkiego zapisać jako loop, hm

A coś w stylu, https://en.wikipedia.org/wiki/Tail_call ? Fajnie by było też zobaczyc ten kawałek kodu:)

@KamilAdam: wyobraź sobie że piszesz w jakimś uczciwym języku imperatywnym, np C. Czy umiesz każdą rekurencję (aka. niejawnie fix) zmienić na pętlę? Może i tak, ale czasem jest jednak potrzeba stosu (który de facto symuluje rekurencję). Np. jak (w zależności od warunku) możesz mieć dwa wywołania rekurencyjne.

Btw. jak twierdzisz że loop jest lepsze od fix to widać że jednak jesteś imperatywny we krwi :P

KamilAdam napisał(a):

Czy to już jest wszystko? Widziałem kod gdzie ktoś rozmontował rekurencję na leniwą listę używając monady State. Konkretnie w intepreterze języka false. Zastanawiam się czy jeszcze jakaś opcja mi umknęła. Bo ta monada State wydaje się bardzo kusząca. zwłaszcza że walczę z problemem że często program wpada mi w nieskończaną rekurencję i zajmuje coraz więcej zasobów. W Haskellu nie ma StackOverflowException, po prostu program zjada całą pamięć. Tak mógłbym ograniczyć na potrzeby testów ilość iteracji w rekurencji i uratować się przed śmiercją GUI Linuxa

Ale o co Ci chodzi konkretnie, co chcesz osiągnąć i czemu jawna rekurencja Ci nie pasuje.

Jest jeszcze fix, ale to chyba żart. Nie widzę sytuacji gdzie miałoby to przewagę nad loop. No chyba że nie da się wszystkiego zapisać jako loop, hm

fix to po prostu Y-combinator w Haskellu (naiwna implementacja nie działa ze względu na rekurencyjny typ).

Możesz zasymulować listę nieskończoną iteratorem i zrobić na nim map, a z mapy można wyjść jak się zwróci brak elementu czyli zakończyć.

Ewentualnie czasem warto zbadać problem z natury matematycznej, bo czasem się okazuje, że te nieskończone rekurencje można wyliczyć i otrzymać pojedyncze przejście zamiast nieskończonego błądzenia po grafie.

Continuation monad

https://hackage.haskell.org/package/mtl-2.3/docs/Control-Monad-Cont.html
przykład
https://stackoverflow.com/a/3331251

Główna zaleta to "stack safe" działanie na kodzie, którego nie da się załatwić trywialną rekursją ogonową.

Jak chcemy wyliczyć pojedynczą wartość za pomocą rekurencj to mamy loop i loopM

Mamy też trampoline i trampolineM XD Tak sa te same funkcje tylko Either ma typy na odwrót XD

Szkoda tylko że trzeba łądować całą Agdę, żeby użyc jednej funkcji bibliotecznej XD Mogli by utilsy z Agda wydzielić do osobnej paczki