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?

Mastic

It is not really clear what you expect [[]]>>= replicateM 8 addqueen to do. Note that [[]] >>= f equals f []. – Johnettajohnette

I can get the result if I do "[[]]>>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen >>=addqueen" but that is really tedious. I am looking for a "syntax sugar" thing to simplify the call. – Mastic

That looks like iterate (>>= addqueen) [[]] !! 8 if I'm not mistaken. – Johnettajohnette

foldl (>>=) [[]] $ replicate 8 addqueen – Replicate

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

Libna

Answer 2

You miss spaces

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

Second, do not use several infix function together

--this code is invalid:
[[]] >>= replicateM 8 $ addqueen -- read as [[]] >>= (replicateM 8 $) addqueen

The reason is: infixl 1 >>= and infixr 0 $

Third, if you use GHCi, write signature for "empty" data.

>([[]] :: [[Int]])>>= replicateM 8 addqueen

Your code is valid

> [[]]>>= replicateM 8 addqueen
[[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]],[[1],[2],[3],[4],[5],[6],[7],[8]]]

Debbydebee

I still cannot make it work. Here is what I get: No instance for (Monad ((->) [Int])) arising from a use of replicateM' Possible fix: add an instance declaration for (Monad ((->) [Int])) In the second argument of (>>=)', namely replicateM 8 addqueen' In the expression: ([[]] :: [[Int]]) >>= replicateM 8 addqueen In an equation for it': it = ([[]] :: [[Int]]) >>= replicateM 8 addqueen – Mastic

replicateM 3 (1+) $ 4 ==> [5,5,5]. Not [5,6,7]. – Libna

@Mastic right now you're missing instance Monad ((->) r). But it's a good thing. Try Prelude> :m +Control.Applicative ; the code will work but it will not do what you want, but something else instead. – Libna

[[]] >>= replicateM 8 $ addqueen is actually read as ([[]] >>= replicateM 8) $ addqueen which of course does not make much sense at all. – Libna