list - 最小或足够小

Question

我正在为简单的棋盘游戏编写 Haskell 求解器。我有这个功能:

bestMove :: Board -> (Int,Int)
bestMove brd = minimumBy (comparing $ length.choices brd) (remaining brd)

基本上 bestMove 是一种移动，它从剩余的移动中留下最少的选择。然而，我知道没有任何元素会留下少于一种选择。如果找到这样的移动，我该如何编写这个函数来终止搜索最小值？
换句话说，我想要一个函数，它返回最小或第一个遇到的足够小的元素(不遍历列表的其余部分)。

这是我的第一个 Haskell 程序，所以它可能非常基础。它是一个回溯求解器，因此不要在调用数百万次的函数中遍历整个列表很重要。

Answer 1

我将简化您的问题，因为您没有为您的某些功能提供类型:

How do you write a function to take the minimum of a list, given a known lower bound on the minimum?

这样的函数将具有类型:

minimum' :: (Ord a) => a -> [a] -> a

... 其中第一个参数是已知的下限(即 1 个选择)，第二个参数是要搜索的列表。

我们可以通过组合两个更简单的函数来定义这个函数。第一个函数只是懒惰地从列表中获取所有元素，直到它到达列表的下限或末尾:

chop :: (Ord a) => a -> [a] -> [a]
chop minElem as =
    let (prefix, suffix) = span (> minElem) as
    in  case suffix of
            []      -> prefix
            s:uffix -> prefix ++ [s]

然后我们用最小值组合它:

minimum' minElem = minimum . chop minElem

这是函数式编程中的常见模式:组合简单的解决方案来解决复杂的问题。