优化 Haskell 函数以防止堆栈溢出

Question

我正在尝试创建一个函数，使用遗传算法递归地玩所有可能的井字游戏，然后返回一个元组（赢，输，平）。然而，当像这样调用时，下面的函数总是会溢出堆栈：

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)

其中players是染色体列表。溢出不会仅在 1 名玩家中发生，而是在 2 名玩家中发生。

编辑：如果按以下方式调用该函数，则不会溢出堆栈。

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

但是，以下方式确实会导致堆栈溢出。

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

作为参考，ScoredPlayer 定义为（字符串是玩家标记，[Int] 是染色体，Float 是分数）：

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

根据我对 Haskell 的了解，playAll'< /code> 函数不是尾递归的，因为我使用的 foldl' 调用正在对函数结果执行进一步处理。但是，我不知道如何消除 foldl' 调用，因为需要它来确保玩所有可能的游戏。有什么方法可以重构函数，使其成为尾递归（或者至少不会溢出堆栈）？

预先感谢，并对大量代码清单表示歉意。

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's 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

foldl' 函数是尾递归的，问题是它不够严格。这是唐·斯图尔特在评论中提到的问题。

将 Haskell 数据结构视为惰性盒子，其中每个新构造函数都会创建一个新盒子。当你有一个折叠时，

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

元组是一个盒子，其中的每个元素都是另一个盒子。 foldl' 的严格性仅删除最外面的框。元组中的每个元素仍然位于惰性框中。

为了解决这个问题，您需要应用更深层次的严格性来删除多余的框。 Don 的建议是

data R = R !Int !Int !Int

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

现在 foldl' 的严格性就足够了。 R 的各个元素都是严格的，因此当删除最外面的框（R 构造函数）时，内部的三个值也会被评估。

在没有看到更多代码的情况下，我只能提供这些。我无法运行此列表，因此我不知道这是否可以解决问题，或者完整程序中是否存在其他问题。

作为一种风格，您可能更喜欢以下内容，而不是嵌套的 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's a tie 
    _ -> ... --code omitted