如何检查哪个列表中某个元素的副本最少？

Question

我正在 Haskell 中编写一个数独游戏，我有一个 [[Maybe Int]]，我需要在其中检查哪个 [Maybe Int] 包含最少的 Nothing 元素。换句话说，在下面的代码中我应该 return 1，这是列表的位置，只有两个 Nothing:

newtype Puzzle = Puzzle [[Maybe Int]]


deriving (Show, Eq) 
    example :: Puzzle
    example =    [ [Just 3, Just 6, Nothing,Nothing,Just 7, Just 1, Just 2, Nothing,Nothing]
                 , [Just 7,Just 5, Just 4, Just 9, Just 4, Nothing, Just 1, Just 8, Just 2]
                 , [Nothing,Nothing,Just 9, Just 2, Nothing,Just 4, Just 7, Nothing,Nothing]
                 , [Nothing,Nothing,Nothing,Nothing,Just 1, Just 3, Nothing,Just 2, Just 8]
                 , [Just 4, Nothing,Nothing,Just 5, Nothing,Just 2, Nothing,Nothing,Just 9]
                 , [Just 2, Just 7, Nothing,Just 4, Just 6, Nothing,Nothing,Nothing,Nothing]
                 , [Nothing,Nothing,Just 5, Just 3, Nothing,Just 8, Just 9, Nothing,Nothing]
                 , [Nothing,Just 8, Just 3, Nothing,Nothing,Nothing,Nothing,Just 6, Nothing]
                 , [Nothing,Nothing,Just 7, Just 6, Just 9, Nothing,Nothing,Just 4, Just 3]
                 ]

[编辑]

我已经想出了一个可以满足我要求的解决方案，但这非常缓慢且效率低下，所以我想知道是否有任何方法可以用算法更快的方式编写它。

nrOfBlanks :: Puzzle -> [Int]
nrOfBlanks sud = map length [ filter isNothing r | r <- rows sud] 

whichBlock :: Puzzle -> Maybe Int
whichBlock sud = 
whichBlock sud = let i = nrOfBlanks sud 
                  in head(map (\x -> case x of
                              0 -> elemIndex (foldl1' min (tail i)) i
                               _ -> elemIndex (foldl1' min i) i) i)

有什么帮助吗？提前致谢！

Answer 1

所以你想根据一些指标找到最小元素的（索引）——在你的例子中数量Nothing元素，但显然这是一个更一般概念的特例：您有一些函数 a -> Int 用于 [a] 列表的元素。换句话说，您需要一个签名类似于

的助手
minIndexAccordingTo :: (a -> Int) -> [a] -> Int

或

minimumAccordingTo :: (a -> Int) -> [a] -> a

问 Hoogle 这样的事情总是个好主意。 The first one doesn't give useful results, but the second 给出前两个建议

maximumOn :: (Partial, Ord b) => (a -> b) -> [a] -> a minimumOn :: (Partial, Ord b) => (a -> b) -> [a] -> a

所以，minimumOn 几乎正是您所需要的。你可以导入它from the extra package，或者这里有一个只使用base:
的定义
import Data.List (sortOn) minimumOn :: Ord b => (a -> b) -> [a] -> a minimumOn f = head . sortOn f

请注意，即使排序是 O (n · log n)，这由于懒惰，定义在线性时间内工作。

现在，要使用它来查找 index，您首先需要将元素与索引配对，相应地更改指标，然后丢弃原始值结束：

minimumIndexOn :: Ord b => (a -> b) -> [a] -> Int minimumIndexOn f = fst . minimumOn (f . snd) . zip [0..]

如何检查哪个列表中某个元素的副本最少？

How can I check which list has the least copies of one element?

haskell

functional-programming

list

maybe