Minimum ou assez petit

Question

J'écris un solveur Haskell pour un simple jeu de société. J'ai cette fonction :

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

Fondamentalement, le meilleur coup est celui qui laisse le plus petit nombre de choix parmi les autres coups. Je sais cependant qu'aucun élément ne laisse moins d'un choix. Comment puis-je écrire cette fonction pour terminer la recherche du minimum si un tel coup est trouvé ?
En d'autres termes, je veux une fonction qui renvoie le minimum ou le premier élément rencontré qui est suffisamment petit (sans traverser le reste de la liste).

C'est mon premier programme Haskell, il est donc probablement très basique. Il s'agit d'un solveur backtracking, il est donc important de ne pas parcourir toute la liste dans une fonction qui est appelée des millions de fois.

Answer 1

Je vais simplifier votre question puisque vous ne fournissez pas de types pour certaines de vos fonctions :

Comment écrire une fonction qui prend le minimum d'une liste, étant donné une limite inférieure connue du minimum ?

Une telle fonction aurait un type :

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

... où le premier argument est la limite inférieure connue (c'est-à-dire 1 choix), et le second argument est la liste à rechercher.

Nous pouvons définir cette fonction en composant deux fonctions plus simples. La première fonction prend simplement paresseusement tous les éléments de la liste jusqu'à ce qu'elle atteigne la borne inférieure ou la fin de la liste :

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

Puis nous le composons avec le minimum :

minimum' minElem = minimum . chop minElem

Il s'agit d'un modèle courant en programmation fonctionnelle : composer des solutions simples pour résoudre des problèmes complexes.