最小或足夠小

我正在爲簡單的棋盤遊戲編寫Haskell解算器。我有這個功能：最小或足夠小

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

基本上bestMove是一個舉動，留下剩餘移動的最小數量的選擇。然而，我知道沒有任何元素不會少於一個選擇。如果發現這種移動，我該如何編寫此函數來終止搜索最小值？
換句話說，我想要一個返回最小或第一個遇到的元素的函數，它足夠小（不需要遍歷列表的其餘部分）。

這是我的第一個Haskell程序，所以它可能是非常基本的。這是一個回溯求解器，所以不能在被稱爲數百萬次的函數中遍歷整個列表是非常重要的。

來源

2013-04-16 Piotr Lopusiewicz

我將簡化你的問題，因爲你不爲某些功能提供了類型：

你怎麼寫給一個函數取最小值列表中，已知的下界最小？

這種函數將具有類型：

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

這是一個常見的模式在函數式編程中：編寫簡單的解決方案來解決複雜的問題。

來源

2013-04-16 05:11:41

最小或足夠小

回答

相關問題