Understanding basic recursion in Haskell

Question

I'm writing a genetic algorithm as a project for my artificial intelligence class. I'm familiar with the concept behind a GA but my experience of Haskell is limited. There is only one thing that's left to do in the program and that's to make a function which loops my other functions. I will present my function and explain the problem more in detail:

This is the function for the second generation. I get the parents, mate them and mutate the genomes, and then pass the new genomes into a list:

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

This works great. I can create a new generation and repeat:

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

So for each new generation I'm one step closer to the target genome (which is a String in my case). I want to generate a new generation until the target String is reached. I thought that a basic recursion would solve this, as in:

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

This works on my laptop up to g (3), but then the computation takes ages. My problem is that I don't really understand why. I thought that Haskell recursion worked like following:

-- 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]]

Which in my head should be the same as the generation3 function above. I would appreciate if someone who knows more about Haskell could explain why I'm able to run a "generation15"-function without any trouble but not more than a "g (3)"-function before I have to force-exit in the console.

Thanks!

Random Dev · Accepted Answer · 2016-05-12 14:15:20Z

5

the problem is that g n is not memoized - it will be re-calculated 2 * 1000 in your list-comprehension

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

should improve things (I guess it would be a good problem to get strict values too - but that's probably another question)

but I would not use it that way - instead write a:

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

function and then you could do something like:

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

with a hopeful

best = find initialPopulation

(note that maybe you should have a exit-strategy after to much generations too - so you might want to include a generation counter or something similar)

edited May 12, 2016 at 14:15

answered May 12, 2016 at 14:10

Random Dev

52.4k9 gold badges95 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Martin V Over a year ago

Thank you Carsten! I thought it had something to do with the way I handled the lists but now I know for sure! I have a "maximumGen" Int that should set a roof on how many generations it should work through :)

Collectives™ on Stack Overflow

Understanding basic recursion in Haskell

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related