CODEWITHSUNDEEP
haskellrefactoringmonads
Newton Migosi
Newton Migosi

Reputation: 3

How do I refactor Haskell list Monad code?

I recently discovered the guard function associated with the Control.Monad module (defined here) and it seemed to be a perfect function to solve a common programming challenge: the eight queens problem. I came up with this solution:

import Control.Monad (guard)

type Pair a = (a, a)

eight_queens :: [[Pair Int]]
eight_queens = do
  r1 <- tag 1 [1..8]
  guard $ all (friendly r1) []
  r2 <- tag 2 [1..8]
  guard $ all (friendly r2) [r1]
  r3 <- tag 3 [1..8]
  guard $ all (friendly r3) [r1, r2]
  r4 <- tag 4 [1..8]
  guard $ all (friendly r4) [r1, r2, r3]
  r5 <- tag 5 [1..8]
  guard $ all (friendly r5) [r1, r2, r3, r4]
  r6 <- tag 6 [1..8]
  guard $ all (friendly r6) [r1, r2, r3, r4, r5]
  r7 <- tag 7 [1..8]
  guard $ all (friendly r7) [r1, r2, r3, r4, r5, r6]
  r8 <- tag 8 [1..8]
  guard $ all (friendly r8) [r1, r2, r3, r4, r5, r6, r7]
  return [r1, r2, r3, r4, r5, r6, r7, r8]

tag :: Int -> [Int] -> [Pair Int]
tag n = zipWith (,) (repeat n)

friendly :: Pair Int -> Pair Int -> Bool
friendly cell@(r,c) cell'@(r',c')
  | r == r' = False
  | c == c' = False
  | diagonal cell cell' = False
  | otherwise = True

diagonal :: Pair Int -> Pair Int -> Bool
diagonal (r,c) (r',c') = abs (r - r') == abs (c - c')

main :: IO ()
main = print eight_queens

The code compiles and gives output that seems mostly correct but I'm trying to refactor to solve the more general n-queens problem with n being passed as an argument to n_queens. The code seems very repetitive suggesting a recursive monadic function could be used but that would remove the found cells from scope. It could also be a fault with using do-notation rather than the bind operator directly.

Ignoring the performance and suitability of the algorithm I've used and my coding style like declaring helper functions in top-level namespace.

Upvotes: 0

Views: 99

Answers (1)

chi
chi

Reputation: 116139

You can recurse while keeping around the list of already-placed queens:

place :: Int -> [Pair Int] -> [[Pair Int]]
place 9 placed = return placed
place n placed = do
   r <- tag n [1..8]
   guard $ all (friendly r) placed
   place (n + 1) (r : placed)

eight_queens :: [[Pair Int]]
eight_queens = place 1 []

The first Int parameter is the tag of the next queen to place, the second [Pair Int] parameter is the list of already-placed queens.

(This will return the queens in the opposite order with respect to your code. If you need that order, use return (reverse placed) instead.)

Upvotes: 1

Related Questions