How to use replicateM solving the eight queens problem?

Question

I just started learning to code Haskell so apologies if this is a stupid question. I am trying to redo the eight queens problem by making use of the [] monad. Here is the code,

import Control.Monad

addqueen :: [Int] -> [[Int]]
addqueen xs = [ x:xs | x <- [1,2..8], 
    not $ x `elem` xs 
        || (any (\ (index,q) -> abs (x-q) == index) $ zip [1..] xs) ]

When I try

[[]] >>= replicateM 8 addqueen

it does not work but yields the following error:

Couldn't match expected type `t0 -> t1' with actual type `[[a0]]'
The first argument of ($) takes one argument,
but its type `[[a0]]' has none
In the expression: [[]] >>= replicateM 8 $ addqueen
In an equation for `it': it = [[]] >>= replicateM 8 $ addqueen

So how do I achieve what I want to do here?

Answer 1

replicateM is the wrong choice here:

Prelude Control.Monad> :t replicateM
replicateM :: (Monad m) => Int -> m a -> m [a]

Prelude Control.Monad> :t addqueen
addqueen :: [Int] -> [[Int]]

this means that in the expression replicateM 8 addqueen, the type of addqueen is matched up with m a, giving m a ~ ([Int] -> [[Int]]), i.e. m ~ ((->) [Int]) and a ~ [[Int]]. And thus the type of replicateM 8 addqueen is m [a] ~ ([Int] -> [[[Int]]]). This is not what you intended.

(if you get a type error "No instance for (Monad ((->) [Int]))", try loading e.g. Control.Applicative first, to bring in the definition for instance Monad ((->) r). This will happen if you're using an older version of GHC).

Try this, instead:

Prelude> :m +Control.Monad

Prelude Control.Monad> :t (>=>)
(>=>) :: (Monad m) => (a -> m b) -> (b -> m c) -> a -> m c

Prelude Control.Monad> :t foldl1 (>=>) $ replicate 8 addqueen
foldl1 (>=>) $ replicate 8 addqueen :: [Int] -> [[Int]]

Prelude Control.Monad> :t [[]] >>= ( foldl1 (>=>) $ replicate 8 addqueen )
[[]] >>= ( foldl1 (>=>) $ replicate 8 addqueen ) :: [[Int]]

---

update: the expression g = foldl1 (>=>) $ replicate 8 addqueen has a meaning on its own. In Prolog terms it is a "goal" of adding 8 queens to an initial solution. We use g by feeding it an initially empty solution, [ [] ] >>= g.

( This uses a slightly above-basic-level operator "fish"¹ i.e. left-to-right Kleisli composition operator >=>, defined so that

(m >>= a) >>= b  ===  m >>= (a >=> b)

i.e. >=> is a composition operator for monadic functions. )

The expression given to you in the comments by Sassa NF, foldl (>>=) [[]] $ replicate 8 addqueen, uses the basic monadic bind operator >>=, but only works as a whole.

¹http://haskellrescue.blogspot.com/2011/03/cooking-delicious-fish.html