I'm currently attempting to learn Haskell after a fair history of imperative programming. When I saw the Pizza Hut Pi Day math problems, I thought the first one would be a good candidate for my Haskell experimenting.  The question is:Im thinking of a ten-digit integer whose digits are all distinct. It happens that the number formed by the first n of them is divisible by n for each n from 1 to 10. What is my number?And I came up with the following code:module Main where                               import System.Environment                       import Data.List                                pizza2 = [ x | x <- [1000000000..9999999999],               (x `div` (10 ^ 0)) `mod` (10) == 0,             (x `div` (10 ^ 1)) `mod` (9) == 0,              (x `div` (10 ^ 2)) `mod` (8) == 0,              (x `div` (10 ^ 3)) `mod` (7) == 0,              (x `div` (10 ^ 4)) `mod` (6) == 0,              (x `div` (10 ^ 5)) `mod` (5) == 0,              (x `div` (10 ^ 6)) `mod` (4) == 0,              (x `div` (10 ^ 7)) `mod` (3) == 0,               (x `div` (10 ^ 8)) `mod` (2) == 0,              (x `div` (10 ^ 9)) `mod` (1) == 0,              nub ( show x ) == show x]           main :: IO ()                                   main = do                                       putStrLn (show (nub (pizza2)))              To my suprise, this actually compiles, runs, and returns the correct result. However, due to my inexperience (I think), it takes about 9 minutes to run and I feel like it should take less than a minute on the long side and just a couple seconds on the short side.Two questions:Why does this take so long?I really feel like all those extra conditions I wrote should be able to be abstracted into one condition, but I couldn't figure it out on my own. Any ideas on how to condense that into one, more abstract condition?
Pizza Hut math problem #1 in Haskell
programming challenge;haskell;combinatorics;time limit exceeded
Any ideas on how to condense that into one, more abstract condition?Assuming x is in scope, you can simplify those conditions like this: all (\n -> (x `div` (10^n)) `mod` (10 - n) == 0) [0..9])Where all is a method from Data.Foldable with type (a -> Bool) -> [a] -> Bool.Here is a more efficient algorithm which, instead of checking the whole interval of numbers, extracts ten digits from 0..9 without replacement. The bad news it that it requires some knowledge of monads and monad transformers. It has been adapted very closely from this blog post by Justin Le.import Control.Monad             (guard, replicateM)import Control.Monad.Trans.Stateselect :: [a] -> [(a, [a])]select []     = []select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]pizza3 :: Integerpizza3 = head . flip evalStateT [0..9] $ do    x0 <- StateT select    let x0' = x0    x1 <- StateT select    let x1' = x1 * 10    x2 <- StateT select    let x2' = x2 * 100    x3 <- StateT select    let x3' = x3 * 1000    x4 <- StateT select    let x4' = x4 * 10000    x5 <- StateT select    let x5' = x5 * 100000    x6 <- StateT select    let x6' = x6 * 1000000    x7 <- StateT select    let x7' = x7 * 10000000    x8 <- StateT select    let x8' = x8 * 100000000    x9 <- StateT select    let x9' = x9 * 1000000000        total = x0' + x1' + x2' + x3' + x4' + x5' + x6' + x7' + x8' + x9'     guard (all (\n -> (total `div` (10^n)) `mod` (10 - n) == 0) [0..9])    return totalThis code uses a syntax called do-notation which, in the case of the lists, is similar to using list comprehensions with several generators.The idea is that each select non-deterministically draws a digit from a list containing digits not taken by previous selects. The non-determinism is provided by the list monad, the not taken by previous selects memory is provided by the State monad.guard is a function that culls unwanted paths for monads that have non-determinism, using a predicate.Here is a more succint version of the code above that uses replicateM from Control.Monad to remove repetition:pizza4 :: Integerpizza4 = head . flip evalStateT [0..9] $ do    digitlist <- replicateM 10 (StateT select)    let total = sum (zipWith (*) digitlist (iterate (*10) 1))     guard (all (\n -> (total `div` (10^n)) `mod` (10 - n) == 0) [0..9])    return totalreplicateM performs a monadic action n times (here the action is sampling without replacement) and returns another monadic action whose value is a list of n samples.