Minimum or small enough

Question

I am writing a Haskell solver for a simple board game. I have this function:

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

Basically, bestMove is a step that leaves the least number of options from the remaining moves. However, I know that not a single element leaves less than one choice. How to write this function to interrupt the minimum search, if such a movement is found?
In other words, I need a function that returns the minimum or first item I encounter that is small enough (without going through the rest of the list).

This is my first Haskell program, so it is probably very simple. It is a backtracking solver, so it’s important not to iterate over the entire list in a function that is called millions of times.

Answer 1

I will simplify your question since you do not provide types for some of my functions:

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

Such a function has the type:

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

... where the first argument is the known lower bound (i.e. 1 choice), and the second argument is the search list.

We can define this function by composing two simpler functions. The first function simply lazily takes all the elements from the list until it reaches the bottom border or the end of the list:

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

Then we will compose it with a minimum:

 minimum' minElem = minimum . chop minElem 

This is a common pattern in functional programming: creating simple solutions to solve complex problems.