Monads in Haskell (chapter 11)

-- All permutations of a list, without using monads.

permut1 :: [a] -> [[a]]
permut1 [] = [[]]
permut1 (x:xs) = concat (map (insert1 x) (permut1 xs))

insert1 :: a -> [a] -> [[a]]
insert1 x [] = [[x]]
insert1 x (y:ys) = (x:y:ys) : map (y:) (insert1 x ys)

-- All permutations of a list, using the List monad.
-- The code looks like we're nondeterministically choosing one permutation of the list.

permut :: [a] -> [[a]]
permut [] = [[]]
permut (x:xs) = do ys <- permut xs; insert x ys

insert :: a -> [a] -> [[a]]
insert x ys =
  return (x:ys) ++
  case ys of
    [] -> []
    y:ys -> do zs <- insert x ys; return (y:zs)

-- Some monad-polymorphic functions: mmap, liftM2

mmap :: Monad m => (t -> m a) -> [t] -> m [a]
mmap f [] = return []
mmap f (x:xs) = do y <- f x; ys <- mmap f xs; return (y:ys)

liftM2 :: Monad m => (t1 -> t2 -> b) -> m t1 -> m t2 -> m b
liftM2 f xx yy = do x <- xx; y <- yy; return (f x y)

-- Test harness

main :: IO ()
main =
  do
    print (permut [1,2,3]);
    mmap print [5,6,7];
    print (liftM2 (+) [1,2,3] [4,5,6])