Haskell function optimization to prevent

Question

I am trying to create a function that recursively plays all possible tic-tac-toe games using a genetic algorithm, and then returns a tuple (wins, losses, connections). However, the function below always overflows the stack when called like this:

scoreOne :: UnscoredPlayer -> [String] -> ScoredPlayer scoreOne player boards = ScoredPlayer (token player) (chromosome player) (evaluateG $! testPlayer player boards) ... let results = map (\x->scoreOne x boards) players print (maximum results) 

where players is a list of chromosomes. Overflow does not occur with only 1 player, but with two cases.

EDIT: if a function is called as follows, it does not overflow the stack.

 let results = map (\player -> evaluateG (testPlayer player boards)) players print (maximum results) 

However, the next path overflows the stack.

 let results = map (\player -> ScoredPlayer (token player) (chromosome player) (evaluateG $! testPlayer player boards)) players 

For reference, ScoredPlayer defined as (a string is a player’s token, [Int] is a chromosome, and Float is an estimate):

 data ScoredPlayer = ScoredPlayer String ![Int] !Float deriving (Eq) 

From what I know about Haskell, the playAll' function is not tail recursion, because the call to foldl' that I use performs further processing of the results of the function. However, I have no idea how to eliminate the foldl' call, since it should ensure that all possible games are played. Is there a way to restructure a function so that it is recursive (or at least doesn't overflow the stack)?

Thanks in advance, and sorry for the massive list of codes.

 playAll' :: (Num a) => UnscoredPlayer -> Bool -> String -> [String] -> (a,a,a) -> (a,a,a) playAll' player playerTurn board boards (w,ls,t)= if won == self then (w+1,ls,t) -- I won this game else if won == enemy then (w,ls+1,t) -- My enemy won this game else if '_' `notElem` board then (w,ls,t+1) -- It a tie else if playerTurn then --My turn; make a move and try all possible combinations for the enemy playAll' player False (makeMove ...) boards (w,ls,t) else --Try each possible move against myself (foldl' (\(x,y,z) (s1,s2,s3) -> (x+s1,y+s2,z+s3)) (w,ls,t) [playAll' player True newBoard boards (w,ls,t)| newBoard <- (permute enemy board)]) where won = winning board --if someone has one, who is it? enemy = (opposite.token) player --what player is my enemy? self = token player --what player am I? 

Answer 1

The foldl' function is tail recursive, the problem is that it is not strict enough. This is a problem Don Stewart mentions in his comment.

Think of Haskell data structures as lazy boxes, where each new constructor creates a new box. When you have a fold like

 foldl' (\(x,y,z) (s1,s2,s3) -> (x+s1,y+s2,z+s3)) 

tuples are one square, and each element inside them is another box. The rigor from foldl' deletes only the outermost box. Each element inside the tuple is still in a lazy field.

To get around this, you need to apply a deeper rigor to remove excess boxes. Don offered to do

 data R = R !Int !Int !Int foldl' (\(R xyz) (s1,s2,s3) -> R (x+s1) (y+s2) (z+s3)) 

Now foldl' rigor is enough. The individual elements of R are strict, therefore, when the external block (constructor R) is deleted, three values ​​inside are also evaluated.

Not seeing any more code, which is about everything I can provide. I could not run this list, so I do not know if this problem resolves or whether there are other problems in the full program.

As a style point, you may prefer the following instead of the nested if :

 playAll' player playerTurn board boards (w,ls,t)= case () of _ | won == self -> (w+1,ls,t) -- I won this game _ | won == enemy -> (w,ls+1,t) -- My enemy won this game _ | '_' `notElem` board -> (w,ls,t+1) -- It a tie _ -> ... --code omitted