[codygman]

There are concise declarative solutions in languages such as Ocaml and Haskell.

[taeric]

Depends entirely on what solutions we are talking about.

Show me a nice concise solution to the N-Queens problem in those languages.

Now add performance as a requirement. :)

[codygman]

Here you go!

C (http://rosettacode.org/wiki/N-queens_problem#C)

Program 1 (compiled with gcc -O3 c1.c -o bin/c1)[0]

    real	0m0.003s
    user	0m0.000s
    sys	        0m0.002s

Program 2: (compiled with gcc -O3 c2.c -o bin/c2)[1]

Same as above, second code listing (faster while still readable,excluded unreadable fastest c version)

    real	0m0.001s
    user	0m0.000s
    sys	        0m0.001s

Haskell (http://rosettacode.org/wiki/N-queens_problem#Haskell)

Program 1 (modified to do 8 queens like the c versions, compiled with: ghc -O2 -threaded haskell2.hs -o bin/haskell2)[2]

    real	0m0.010s
    user	0m0.005s
    sys	        0m0.005s

Program 2 (modified to do 8 queens like the c version, compiled with: ghc -O2 -threaded haskell2.hs -o bin/haskell2)[3] (word of warning, this program is only 52% efficient according to ghc and has a lot of optimization that could be done)

    real	0m0.006s
    user	0m0.006s
    sys	        0m0.000s

Note that the fastest Haskell solution was also the shortest by quite a bit. Are you convinced yet?

EDIT: Found an ATS solution, but I'm not setup to compile it: http://www.ats-lang.org/SERVER/MYCODE/Patsoptaas_serve.php?m...

0: C, solution 1

    #include <stdio.h>
    #include <stdlib.h>
 
    int count = 0;
    void solve(int n, int col, int *hist)
    {
    	if (col == n) {
    		printf("\nNo. %d\n-----\n", ++count);
    		for (int i = 0; i < n; i++, putchar('\n'))
    			for (int j = 0; j < n; j++)
    				putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.');
     
    		return;
    	}
     
    #	define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
    	for (int i = 0, j = 0; i < n; i++) {
    		for (j = 0; j < col && !attack(i, j); j++);
    		if (j < col) continue;
     
    		hist[col] = i;
    		solve(n, col + 1, hist);
    	}
    }
     
    int main(int n, char **argv)
    {
    	if (n <= 1 || (n = atoi(argv[1])) <= 0) n = 8;
    	int hist[n];
    	solve(n, 0, hist);
    }

1: c solution 2

    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
     
    typedef uint32_t uint;
    uint full, *qs, count = 0, nn;
     
    void solve(uint d, uint c, uint l, uint r)
    {
    	uint b, a, *s;
    	if (!d) {
    		count++;
    #if 0
    		printf("\nNo. %d\n===========\n", count);
    		for (a = 0; a < nn; a++, putchar('\n'))
    			for (b = 0; b < nn; b++, putchar(' '))
    				putchar(" -QQ"[((b == qs[a])<<1)|((a + b)&1)]);
    #endif
    		return;
    	}
     
    	a = (c | (l <<= 1) | (r >>= 1)) & full;
    	if (a != full)
    		for (*(s = qs + --d) = 0, b = 1; b <= full; (*s)++, b <<= 1)
    			if (!(b & a)) solve(d, b|c, b|l, b|r);
    }
     
    int main(int n, char **argv)
    {
    	if (n <= 1 || (nn = atoi(argv[1])) <= 0) nn = 8;
     
    	qs = calloc(nn, sizeof(int));
    	full = (1U << nn) - 1;
     
    	solve(nn, 0, 0, 0);
    	printf("\nSolutions: %d\n", count);
    	return 0;
    }

2: Haskell solution 1 (comments stripped out for comparison)

    import           Control.Monad
    import           Data.List
    
    queens :: Int -> [[Int]]
    queens n = map fst $ foldM oneMoreQueen ([],[1..n]) [1..n]  where
      oneMoreQueen (y,d) _ = [(x:y, delete x d) | x <- d, safe x]  where
        safe x = and [x /= c + n && x /= c - n | (n,c) <- zip [1..] y]
    printSolution y = do
         let n = length y
         mapM_ (\x -> putStrLn [if z == x then 'Q' else '.' | z <- [1..n]]) y
         putStrLn ""
    
    main = mapM_ printSolution $ queens 8

3: Haskell solution 2

    import           Control.Monad (foldM)
    import           Data.List     ((\\))
    
    main :: IO ()
    main = mapM_ print $ queens 8
    
    queens :: Int -> [[Int]]
    queens n = foldM f [] [1..n]
        where
          f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs]
          q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) <- qs `zip` [1..]]

[taeric]

What is the speed of this on N of 16 to 20? At 8, any implementation should suffice nowdays.

Edit: Also, apologies for the possibly ninja edit. This is ultimately somewhat silly. I am not going to lie and say that the these are easily readable. I fully cede that this could just be a training thing. I picked this particular example because I had fun with it using the DLX algorithm. Which is admittedly far above my understanding in many ways. :) Just the naive recursive solution was much easier to read, but much much slower to execute. To the point that it was laughable. (If interested, I can post my code.)

[art-w]

This example is bizarre, because a fast implementation is probably going to rely on a SAT solver, at which point the "queens code" (in any language) becomes a declarative specification of the solution!

Also, I don't think that Haskell, OCaml, (or Prolog) are that much declarative: They have a very clear evaluation model, which you need to know in order to write any code. They also have debuggers as a result.

[taeric]

That was what my point was supposed to be. Just like saying that "foo.sorted()" is more declarative than looking at the implementation of quicksort. However, the implementation of quicksort (that is actually fast) is much easier to understand in most imperative implementations than it is otherwise.

Regardless, I do apologize for the noise.

[codygman]

> They have a very clear evaluation model, which you need to know in order to write any code.

What programming languages don't require you knowing their evaluation model?