모나크를 풀기 위해 선택 모나드를 사용하는 방법은 무엇입니까?

Question

모나드가 어떻게 작동하는지 이해하려고합니다. 분명히 그것은 Cont의 사촌이며 역 추적 검색에 사용될 수 있습니다. 내가 대신 Select을 사용하려면이 솔루션을 적용하기 위해 사투를 벌인거야

-- All the ways of extracting an element from a list. 
oneOf :: [Int] -> [(Int,[Int])] 
oneOf [] = [] 
oneOf (x:xs) = (x,xs) : map (\(y,ys) -> (y,x:ys)) (oneOf xs) 

-- Adding a new queen at col x, is it threathened diagonally by any of the 
-- existing queens? 
safeDiag :: Int -> [Int] -> Bool 
safeDiag x xs = all (\(y,i) -> abs (x-y) /= i) (zip xs [1..]) 

nqueens :: Int -> [[Int]] 
nqueens queenCount = go [] [1..queenCount] 
    where 
    -- cps = columsn of already positioned queens. 
    -- fps = columns that are still available 
    go :: [Int] -> [Int] -> [[Int]] 
    go cps [] = [cps] 
    go cps fps = [ps | (p,nfps) <- oneOf fps, ps <- go (p:cps) nfps, safeDiag p cps] 

:

나는의 n 여왕 문제에이 목록 기반 솔루션이있다.

Select은 답변을 비교하는 데 사용되는 "평가 기능"을 통해 추상화 할 수 있습니다. 이 함수는 runSelect으로 전달됩니다. 내 솔루션에서 safeDiag 같은 것을 평가 함수로 사용할 수 있다고 생각하지만 계산 방법을 Select 자체로 구성하는 방법이 있습니까?

또한 Select 모나드 만 사용하면 충분합니까? 아니면 목록에 트랜스포머 버전을 사용해야합니까?

Answer 1

Select은 "콤팩트"공간에서 검색의 추상화로 볼 수 있으며 일부 술어로 안내됩니다. 귀하의 의견에 SAT를 언급 하셨으며 SAT 인스턴스로 모델링을 시도한 후 Select (this paper의 정신으로)을 기반으로 한 해결사에 던지셨습니까? 안에 N-queens 특정 제약 조건을 적용하고 SAT 해결자를 N-queens 해결 자로 바꾸기 위해 검색을 전문화 할 수 있습니다.

Answer 2

jd823592의 대답에 영감을하고 paper에서 SAT 예보고 후, 나는이 코드를 작성했습니다

:

ghci> nqueens 8 
[1,5,8,6,3,7,2,4] 

: 유효한 솔루션

import Data.List 
import Control.Monad.Trans.Select 

validBoard :: [Int] -> Bool 
validBoard qs = all verify (tails qs) 
    where 
    verify [] = True 
    verify (x : xs) = and $ zipWith (\i y -> x /= y && abs (x-y) /= i) [1..] xs 

nqueens :: Int -> [Int] 
nqueens boardSize = runSelect (traverse selectColumn columns) validBoard 
    where 
    columns = replicate boardSize [1..boardSize] 
    selectColumn candidates = select $ \s -> head $ filter s candidates ++ candidates 

(천천히이기는하지만) 도착하는 것을

그러나 나는 그것을 아주 잘 이해하지 못합니다. 특히 sequence이 Select에서 작동하는 방식으로 전체 보드에서 작동하는 함수 (validBoard)를 단일 열 인덱스를 사용하는 함수로 변환하는 것은 매우 마술처럼 보입니다.

---

sequence 기반 솔루션은 열에 퀸 퍼팅 후속 퀸 대해 동일한 항목을 선택할 수있는 가능성을 배제하지 않는 결함이있다; 우리는 불필요하게 운명의 가지를 탐험하게됩니다. 우리는 우리의 열 선택은 이전의 결정에 의해 영향을받을하려면

, 우리는 Applicative 넘어 Monad의 힘을 사용할 필요가 :

nqueens :: Int -> [Int] 
nqueens boardSize = fst $ runSelect (go ([],[1..boardSize])) (validBoard . fst) 
    where 
    go (cps,[]) = return (cps,[]) 
    go (cps,fps) = (select $ \s -> 
    let candidates = map (\(z,zs) -> (z:cps,zs)) (oneOf fps) 
    in head $ filter s candidates ++ candidates) >>= go 

---

는 모나드 버전은 여전히 ​​문제가있다가 그것이 단지 부분적으로 완료된 게시판에 충돌이있는 것으로 확인되면 바로 원래의 목록 기반 솔루션이 다시 추적 될 때 완성 된 게시판을 검사합니다. 나는 Select을 사용하여 그것을하는 방법을 모른다.