Dowemo
0 0 0 0


Question:

I just started learning to code Haskell so apologies if this is a stupid question. I am trying to redo the 8 queen 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 to

[[]]>>= 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?


Best Answer:


replicateM is wrong choice here:

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

this means that in the expression replicateM 8 addqueen, m a ~ ([Int] -> [[Int]]) i.e. m ~ ((->) [Int]) and a ~ [[Int]]. And its type 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: this expression, x1 = foldl1 (>=>) $ replicate 8 addqueen, stands on its own, in Prolog terms corresponding to a "goal" of adding 8 queens to an initial solution. It uses a slightly above-basic-level operator "fish"1 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. We use x1 by feeding an initially empty solution into it, [ [] ] >>= x1.

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

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




Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs