NonDetMonad.hs

import Data.List

data Choose a = Choose [a]
  deriving (Eq, Show)

choices (Choose xs) = xs

instance Functor Choose where
  fmap f (Choose xs) = Choose $ map f xs

instance Applicative Choose where  
  pure x = Choose [x]
  (Choose []) <*> _ = Choose []  
  (Choose fs) <*> (Choose xs) = case ys of [] -> Choose []; _ -> Choose $ head ys
    where ys = sortOn length $ filter (not.null) [[f x | f <- fs] | x <- xs] -- [[f x | x <- xs] | f <- fs]

instance Monad Choose where  
  return x = Choose [x]
  (Choose []) >>= f = Choose []
  (Choose xs) >>= f = case ys of [] -> Choose []; _ -> Choose $ head ys
    where ys = sortOn length $ filter (not.null) $ map (choices.f) xs

ciao = do
  x <- Choose [5,3,4]
  (Choose . flip replicate 0) x

main = do
  print ciao