queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
import Control.Monad
queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c, x /= c + n, x /= c - n, safe x y (n+1)]
main = mapM_ print $ queens 8
Hm. And maybe that's why Haskell isn't catching on. That looks little better than terminal scripting languages. Its concise, sure. But maybe that's not as helpful as you might think, in communicating a problem solution.
But you're right, examples like this are extremely poor marketing for Haskell. It's really not how you'd write most Haskell programs. A lot of the Haskell code on sites like Rosetta Code is deliberately terse to show off.
I changed the indentation a little bit, to make it more clear:
queens n = foldM
(\y _ -> [x:y | x <- [1..n], safe x y 1])
[]
[1..n]
safe x [] n = True
safe x (c:y) n = and [ x /= c
, x /= c + n
, x /= c - n
, safe x y (n+1)
]
main = mapM_ print $ queens 8
'queens' is essentially a for loop that concatenates the elements between 1..n that are safe, and 'safe' is a function that returns true if it's given an empty list, or if the input satisfies all of the predicates in the other list (notice the recursion that's possible because of laziness.) The function 'and' that it calls takes a list of bools and returns true if all of them are true. 'main' prints each list that results from running 'queens 8'
There is some syntax and convention you have to learn, e.g. what the _ in mapM_ means, what a list comprehension is, or what : means, etc. but once you have it's a fairly elegant solution (compare to the code snippets from imperative languages.)
thanks for the link , it's great , by the way i would buy a book that gather algorithms like that in any 'major' programming language (Java,C,C++, C#, Ruby, Python, javascript,whatever...) with a little explanation note for each algorithm.
import Control.Monad
queens n = foldM (\y _ -> [ x : y | x <- [1..n], safe x y 1]) [] [1..n] safe x [] n = True safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)]
main = mapM_ print $ queens 8
---- http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscel...