10 ms·

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

taeric 12y ago
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 12y ago
  Here you go! C (http://rosettacode.org/wiki/N-queens_problem#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 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?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/BOOK/INT2PROGINATS/CODE/CHAP_FUNCTION/JS/queens.dats 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 12y ago
    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 12y ago
      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 12y ago
        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 12y ago
        > 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?

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 12y ago
Here you go! C (http://rosettacode.org/wiki/N-queens_problem#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 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?mycode_url=https://raw.githubusercontent.com/githwxi/ATS-Postiats/master/doc/BOOK/INT2PROGINATS/CODE/CHAP_FUNCTION/JS/queens.dats 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 12y ago
  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 12y ago
    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 12y ago
      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 12y ago
      > 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?