Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: f4264e112d
Fetching contributors…

Cannot retrieve contributors at this time

file 39 lines (32 sloc) 1.041 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
import Criterion.Main
import Control.Monad
import Control.Monad.Stream

main :: IO ()
main = defaultMain
  [ bench "permsort" $ nf (toList . permSort) ([1..4]++[8,7..5]),
    bench "8 queens" $ nf (toList . nQueens) 8 ]

permSort :: [Int] -> Stream [Int]
permSort xs = do ys <- permute xs
                 guard (ascending ys)
                 return ys

permute :: [a] -> Stream [a]
permute [] = return []
permute xs = do (y,ys) <- select xs
                zs <- permute ys
                return (y:zs)

select :: [a] -> Stream (a,[a])
select [] = mzero
select (x:xs) = return (x,xs)
        `mplus` do (y,ys) <- select xs
                   return (y,x:ys)

ascending :: [Int] -> Bool
ascending [] = True
ascending [_] = True
ascending (x:y:zs) = x <= y && ascending (y:zs)

nQueens :: Int -> Stream [Int]
nQueens n = do qs <- permute [1..n]
               guard (safe qs)
               return qs

safe :: [Int] -> Bool
safe qs = and [ j-i /= abs (qj-qi) | (i,qi) <- iqs, (j,qj) <- iqs, i < j ]
 where iqs = zip [1..] qs
Something went wrong with that request. Please try again.