Понимание базовой рекурсии в Haskell

Question

Я пишу генетический алгоритм как проект для своего класса искусственного интеллекта. Я знаком с концепцией GA, но мой опыт Haskell ограничен. Осталось только одно, что нужно сделать в программе, и это сделать функцию, которая меняет мои другие функции. Я расскажу о своей функции и подробно объясню проблему:

Это функция для второго поколения. Я получаю родители, спариваться их и мутировать геномы, а затем передать новые геномы в список:

generation1 = initialPopulation 
generation2 = [(mutate (mate (fTTS generation1) (sTTS generation1))) | x <- [1..100]] 

Это прекрасно работает. Я могу создать новое поколение и повторить:

generation3 = [(mutate (mate (fTTS generation2) (sTTS generation2))) | x <- [1..100]] 

Таким образом, для каждого нового поколения, я один шаг ближе к целевой геном (который является строка в моем случае). Я хочу создать новое поколение до достижения целевой строки. Я думал, что основная рекурсия бы решить эту проблему, так как в:

g 0 = initialPopulation 
g n = [(mutate (mate (fTTS (g (n - 1))) (sTTS (g (n - 1))))) | x <- [1..100]] 

Это работает на моем ноутбуке до г (3), а затем вычисление принимает возрасты. Моя проблема в том, что я действительно не понимаю, почему. Я думал, что рекурсия Haskell работает следующим образом:

-- g 0 = [(mutate (mate (fTTS initialPopulation) (sTTS initialPopulation))) | x <- [1..100]] = ["N4kiT","Tu1RT","Tu1R<"] 
-- g 1 = [(mutate (mate (fTTS (g 0)) (sTTS (g 0)))) | x <- [1..100]] 
-- g 2 = [(mutate (mate (fTTS (g 1)) (sTTS (g 1)))) | x <- [1..100]] 
-- g 3 = [(mutate (mate (fTTS (g 2)) (sTTS (g 2)))) | x <- [1..100]] 

Что в моей голове должно быть таким же, как функция generation3 выше. Я был бы признателен, если бы кто-то, кто знает больше о Haskell, мог бы объяснить, почему я могу запускать функцию «generation15» без каких-либо проблем, но не более, чем функция «g (3)», прежде чем мне придется принудительно выйти в консоль.

Спасибо!

Answer 1

проблема заключается в том, что g n не memoized - это будет пересчитана 2 * 1000 в вашем списке постижение

g 0 = initialPopulation 
g n = 
    let prev = g (n-1) 
    in [(mutate (mate (fTTS prev) (sTTS prev))) | x <- [1..100]] 

должны улучшить положение вещей (я предполагаю, что это будет хорошая проблема, чтобы получить строгие значения тоже - но это, вероятно, другой вопрос)

---

, но я бы не использовать его таким образом - вместо того, чтобы написать:

nextGen prev = [(mutate (mate (fTTS prev) (sTTS prev))) | x <- [1..100]] 

функция, и тогда вы могли бы сделать что-то вроде:

find gen = if goodEnough gen then gen else find (nextGen gen) 

с надежды

best = find initialPopulation 

(обратите внимание, что, возможно, вы должны иметь экзит-стратегию после того, как к очень поколений тоже - поэтому вы можете включить счетчик поколений или что-то подобное)