haskell - Euler 43 - 是否有一个单子(monad)可以帮助编写此列表理解？

Question

这是解决欧拉问题 43 的一种方法(如果没有给出正确答案，请告诉我)。是否有单子(monad)或其他一些合成糖可以帮助跟踪 notElem条件？

toNum xs = foldl (\s d -> s*10+d) 0 xs

numTest xs m = (toNum xs) `mod` m == 0

pandigitals = [ [d0,d1,d2,d3,d4,d5,d6,d7,d8,d9] |
                d7 <- [0..9],
                d8 <- [0..9], d8 `notElem` [d7],
                d9 <- [0..9], d9 `notElem` [d8,d7],
                numTest [d7,d8,d9] 17,
                d5 <- [0,5],  d5 `notElem` [d9,d8,d7],
                d3 <- [0,2,4,6,8], d3 `notElem` [d5,d9,d8,d7],
                d6 <- [0..9], d6 `notElem` [d3,d5,d9,d8,d7],
                numTest [d6,d7,d8] 13,
                numTest [d5,d6,d7] 11,
                d4 <- [0..9], d4 `notElem` [d6,d3,d5,d9,d8,d7],
                numTest [d4,d5,d6] 7,
                d2 <- [0..9], d2 `notElem` [d4,d6,d3,d5,d9,d8,d7],
                numTest [d2,d3,d4] 3,
                d1 <- [0..9], d1 `notElem` [d2,d4,d6,d3,d5,d9,d8,d7],
                d0 <- [1..9], d0 `notElem` [d1,d2,d4,d6,d3,d5,d9,d8,d7]
              ]

main = do
         let nums = map toNum pandigitals
         print $ nums
         putStrLn ""
         print $ sum nums

例如，在这种情况下，赋值给 d3不是最优的——它确实应该移到 numTest [d2,d3,d4] 3 之前测试。但是，这样做意味着更改 notElem 中的一些内容。删除 d3 的测试从正在检查的列表中。由于连续 notElem列表是通过将最后一个选择的值与前一个列表相结合来获得的，看起来这应该是可行的 - 不知何故。

更新:这是上面用 Louis 重写的程序 UniqueSel下面的单子(monad):

toNum xs = foldl (\s d -> s*10+d) 0 xs
numTest xs m = (toNum xs) `mod` m == 0

pandigitalUS =
  do d7 <- choose
     d8 <- choose
     d9 <- choose
     guard $ numTest [d7,d8,d9] 17
     d6 <- choose
     guard $ numTest [d6,d7,d8] 13
     d5 <- choose
     guard $ d5 == 0 || d5 == 5
     guard $ numTest [d5,d6,d7] 11
     d4 <- choose
     guard $ numTest [d4,d5,d6] 7
     d3 <- choose
     d2 <- choose
     guard $ numTest [d2,d3,d4] 3
     d1 <- choose
     guard $ numTest [d1,d2,d3] 2
     d0 <- choose
     guard $ d0 /= 0
     return [d0,d1,d2,d3,d4,d5,d6,d7,d8,d9]

pandigitals = map snd $ runUS pandigitalUS [0..9]

main = do print $ pandigitals

Answer 1

当然。

newtype UniqueSel a = UniqueSel {runUS :: [Int] -> [([Int], a)]}
instance Monad UniqueSel where
  return a = UniqueSel (\ choices -> [(choices, a)])
  m >>= k = UniqueSel (\ choices -> 
    concatMap (\ (choices', a) -> runUS (k a) choices')
      (runUS m choices))

instance MonadPlus UniqueSel where
  mzero = UniqueSel $ \ _ -> []
  UniqueSel m `mplus` UniqueSel k = UniqueSel $ \ choices ->
    m choices ++ k choices

-- choose something that hasn't been chosen before
choose :: UniqueSel Int
choose = UniqueSel $ \ choices ->
  [(pre ++ suc, x) | (pre, x:suc) <- zip (inits choices) (tails choices)]

然后你像对待 List monad 一样对待它，使用 guard强制选择，除了它不会多次选择一个项目。一旦你有 UniqueSel [Int]计算，只做 map snd (runUS computation [0..9])给它 [0..9]作为可供选择的选项。