我正在尝试更熟练地使用递归方案，因为它们迄今为止确实有助于将粗糙的显式递归代码转换为不那么复杂的代码。在实现可能与显式递归混淆的算法时，我倾向于使用的另一个工具是单子转换器/可变性。理想情况下，我希望对递归模式感到足够舒适，这样我就可以完全抛弃有状态性。一个算法的例子，我仍然会用到变压器，它是带有修剪的极大极小。我用变形和极大极小f代数(data MinimaxF a f = MMResult a | MMState [f] Bool)做了一般的极大极小，但我不确定如何将它扩展到修剪。我想也许我可以使用组织同构，或者也许有一些自定义的解决方案，但是我不知道如何使用这两种技术来尝试解决方案。
除了一个带有递归模式的alpha - beta剪接版本外，我将非常感谢您对处理类似问题的任何一般性建议。例如，我在将递归方案应用于Dijkstra等算法时遇到了麻烦，这些算法通常以命令式的方式实现。
Alpha-beta可以看作是极大极小的实例，其中min和max是用一个精心选择的格实例化的。完整的要点。
我们将游戏表示为一棵树，其中每个内部节点是游戏中的一个位置，等待指定的玩家选择到子节点的移动，每个叶子是带有分数或值的最终位置。
-- | At every step, either the game ended with a value/score,
-- or one of the players is to play.
data GameF a r = Value a | Play Player (NonEmpty r)
deriving Functor
type Game a = Fix (GameF a)
-- | One player wants to maximize the score,
-- the other wants to minimize the score.
data Player = Mini | Maxi
minimax将作用于任何晶格，由以下类定义:
class Lattice l where
inf, sup :: l -> l -> l
Lattice类比Ord更通用，Ord实例是具有可判定相等性的Lattice(Eq)。如果我们可以重新定义Ord，那么将Lattice添加为超类是合适的。但是这里必须使用newtype:
-- The Lattice induced by an Ord
newtype Order a = Order { unOrder :: a }
deriving (Eq, Ord)
instance Ord a => Lattice (Order a) where
inf = min
sup = max
这是极大极小。通过将最终值的leaf :: a -> l嵌入到所选晶格中来参数化它。一名玩家最大化嵌入值，另一名玩家最小化嵌入值。
-- | Generalized minimax
gminimax :: Lattice l => (a -> l) -> Game a -> l
gminimax leaf = cata minimaxF where
minimaxF (Value x) = leaf x
minimaxF (Play p xs) = foldr1 (lopti p) xs
lopti :: Lattice l => Player -> l -> l -> l
lopti Mini = inf
lopti Maxi = sup
"regular"Minimax直接使用游戏的分数作为格:
minimax :: Ord a => Game a -> a
minimax = unOrder . gminimax Order
对于α - β剪枝，我们的想法是我们可以跟踪最优分数的一些界限，这允许我们缩短搜索。因此，搜索将由区间(alpha, beta)参数化。这导致我们得到一个函数格Interval a -> a:
newtype Pruning a = Pruning { unPruning :: Interval a -> a }
区间可以用(Maybe a, Maybe a)表示，允许任意一侧无界。但是为了清晰起见，我们将使用更好的命名类型，并且还将在每一侧利用不同的Ord实例:
type Interval a = (WithBot a, WithTop a)
data WithBot a = Bot | NoBot a deriving (Eq, Ord)
data WithTop a = NoTop a | Top deriving (Eq, Ord)
我们将要求f满足clamp i (f i) = clamp i (f (Bot, Top))才能构造Pruning f，其中clamp定义如下。这样，f是一个搜索算法，如果它知道它的结果在区间之外，它可能会短路，而不必找到确切的结果。
clamp :: Ord a => Interval a -> a -> a
clamp (l, r) = clampBot l . clampTop r
clampBot :: Ord a => WithBot a -> a -> a
clampBot Bot x = x
clampBot (NoBot y) x = max y x
clampTop :: Ord a => WithTop a -> a -> a
clampTop Top x = x
clampTop (NoTop y) x = min y x
函数通过逐点提升形成格。当我们只考虑满足clamp i (f i) = clamp i (f (Bot, Top))的函数，并将它们与一个合适的等价关系(如果clamp <*> f = clamp <*> g，则Pruning f = Pruning g)模等价时，晶格的短路定义就成为可能。
两个函数l和r的inf，给定一个区间i = (alpha, beta)，首先运行l (alpha, beta)得到一个值vl。如果是vl <= alpha，那么它必须是clamp i vl == alpha == clamp i (min vl (r i))，这样我们就可以停止并返回vl，而不需要查看r。否则，我们运行r，知道最终结果不会超过vl，所以我们也可以更新传递给r的上界。sup是对称定义的
instance Ord a => Lattice (Pruning a) where
inf l r = Pruning (alpha, beta) ->
let vl = unPruning l (alpha, beta) in
if NoBot vl <= alpha then vl else min vl (unPruning r (alpha, min (NoTop vl) beta))
sup l r = Pruning (alpha, beta) ->
let vl = unPruning l (alpha, beta) in
if beta <= NoTop vl then vl else max vl (unPruning r (max (NoBot vl) alpha, beta))
因此我们得到了一个极大极小的例子。一旦定义了上面的晶格，我们只需要一些简单的包装和展开。
alphabeta :: Ord a => Game a -> a
alphabeta = runPruning . gminimax constPruning
constPruning :: a -> Pruning a
constPruning = Pruning . const
runPruning :: Pruning a -> a
runPruning f = unPruning f (Bot, Top)
如果一切顺利，alphabeta和minimax应该有相同的结果:
main :: IO ()
main = quickCheck g -> minimax g === alphabeta (g :: Game Int)