欧拉43 - 有没有一个monad来帮助写这个列表的理解？ [英] Euler 43 - is there a monad to help write this list comprehension?
问题描述
notElem 条件？ toNum xs = foldl（\sd - > 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（\sd - > s * 10 + d）0 xs
numTest xs m =（toNum xs）`mod` m == 0
pandigitalUS =
do d7 < - 选择
d8 < - 选择
d9 < - 选择
guard $ numTest [d7，d8，d9 ] 17
d6 < - 选择
guard $ numTest [d6，d7，d8] 13
d5 < - 选择
guard $ d5 == 0 || d5 == 5
guard $ numTest [d5，d6，d7] 11
d4 < - 选择
guard $ numTest [d4，d5，d6] 7
d3 < - 选择
d2 < - 选择
guard $ numTest [d2，d3，d4] 3
d1 < - 选择
guard $ numTest [d1，d2，d3] 2
d0 < - 选择
guard $ d0 / = 0
返回[d0，d1，d2，d3，d4，d5，d6，d7，d8，d9]
pandigitals = map snd $ runUS pandigitalUS [0..9]
main =打印$ pandigitals
当然。
newtype UniqueSel a = UniqueSel {runUS :: [Int] - > [（[Int]，a）]}
实例Monad UniqueSel其中
返回a = UniqueSel（\ choices - > [（choices，a）]）
m>> = k = UniqueSel（\ options - >
concatMap（\（choices'，a） - > runUS（ka）options'）
（runUS m choices））
实例MonadPlus UniqueSel其中
mzero = UniqueSel $ \ _ - > []
UniqueSel m`mplus` UniqueSel k = UniqueSel $ \ choices - >
m选择++ k选择
- 选择在
之前未选择的内容choose :: UniqueSel Int
选择= UniqueSel $ \选项 - > ;
[（pre ++ suc，x）| （pre，x：suc）< - zip（inits choices）（tails options）]
和那么你把它当作List monad来处理，用 guard 来强制选择，除了它不会多次选择一个项目。一旦你有一个 UniqueSel [Int] 计算，只需做 map snd（runUS computation [0..9]）给它 [0..9] 作为可供选择的选项。
Here is a way to solve Euler problem 43 (please let me know if this doesn't give the correct answer). Is there a monad or some other syntatic sugar which could assist with keeping track of the notElem conditions?
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
For instance, in this case the assignment to d3 is not optimal - it really should be moved to just before the numTest [d2,d3,d4] 3 test. Doing that, however, would mean changing some of the notElem tests to remove d3 from the list being checked. Since the successive notElem lists are obtained by just consing the last chosen value to the previous list, it seems like this should be doable - somehow.
UPDATE: Here is the above program re-written with Louis' UniqueSel monad below:
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
Sure.
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)]
and then you treat it like the List monad, with guard to enforce choices, except that it won't choose an item more than once. Once you have a UniqueSel [Int] computation, just do map snd (runUS computation [0..9]) to give it [0..9] as the choices to select from.
这篇关于欧拉43 - 有没有一个monad来帮助写这个列表的理解？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
