Euler 43 – is there a monad to help write this list comprehension?

by

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.

More Related Contents:

  1. Answer to this Haskell expression [closed]
  2. Good examples of Not a Functor/Functor/Applicative/Monad?
  3. Applicatives compose, monads don’t
  4. Operating on a return from a Maybe that contains “Just”
  5. A monad is just a monoid in the category of endofunctors, what’s the problem?
  6. A Haskell function of type: IO String-> String
  7. Is monad bind (>>=) operator closer to function composition (chaining) or function application?
  8. IO happens out of order when using getLine and putStr
  9. What is indexed monad?
  10. How to extract value from monadic action
  11. Large-scale design in Haskell? [closed]
  12. Splitting list into a list of possible tuples
  13. What is the purpose of the reader monad?
  14. Is Haskell truly pure (is any language that deals with input and output outside the system)?
  15. Should do-notation be avoided in Haskell?
  16. Haskell: I/O and Returning From a Function
  17. Why does haskell’s bind function take a function from non-monadic to monadic
  18. Difference between Monad and Applicative in Haskell
  19. Is there a way to place some impure code inside pure functions?
  20. Concrete example showing that monads are not closed under composition (with proof)?
  21. How to use (->) instances of Monad and confusion about (->)
  22. What are free monads?
  23. Converting IO Int to Int
  24. Is there a monad that doesn’t have a corresponding monad transformer (except IO)?
  25. How to enumerate a recursive datatype in Haskell?
  26. How to handle side effect with Applicative?
  27. Haskell – depth for each node in binary tree using Reader monad
  28. How does the ST monad work?
  29. In what sense is the IO Monad pure?
  30. Is Haskell’s mapM not lazy?

Leave a Comment