존재감없는 검색과 질의

Question

내장 된 논리 프로그래밍 언어를 구현하지 않고 하스켈에 존재 진술을 작성하는 확장 가능하고 효율적인 방법이 있습니까? 내가 알고리즘을 구현있을 때 때때로, 나는 ∈이 목록에 오버로드

∃x.∃y.x,y ∈ xs ∧ x ≠ y ∧ p x y 

같은 존재 적 정량화 된 최초의 차 문을 표현하고 싶다. 나는 서둘러 해요, 내가

find p []  = False 
find p (x:xs) = any (\y -> x /= y && (p x y || p y x)) xs || find p xs 

또는

find p xs = or [ x /= y && (p x y || p y x) | x <- xs, y <- xs] 

같습니다 그러나이 방법은 쿼리가 여러 arities의 값이나 조건 또는 함수를 반환 잘 일반화하지 않는 명쾌한 코드를 작성할 수 있습니다 . 예를 들어,

∃x.∃y.x,y,z ∈ xs ∧ x ≠ y ≠ z ∧ f x y z = g x y z 

과 같은 간단한 문장조차도 다른 검색 절차를 작성해야합니다. 그리고 이것은 상당한 양의 상용구 코드를 의미합니다. 검색 모두를 수행하고 값을 반환하는, 상당히 표기법을 남용

find(p,xs,z) = x ∈ xs & y ∈ xs & x =/= y & f x y =:= g x y =:= z 

: 물론, 축소 또는 해상도 엔진 구현할 Curry 또는 Prolog 같은 언어는 프로그래머가 같은 문장을 작성할 수 있습니다. 이 문제는 형식적으로 지정된 알고리즘을 구현할 때 자주 발생하며 종종 fmap, foldr 및 mapAccum과 같은 함수 조합으로 해결되지만 대개는 명시 적 재귀를 통해 해결됩니다. 하스켈에서 이와 같은 코드를 작성하는보다 일반적이고 효율적인, 또는 일반적이고 표현적인 방법이 있습니까?

Answer 1

대신 exists의 find을 사용할 수 있습니다

∃x ∈ xs : P 

exists (\x -> P) xs 

당신이 증거를 생산해야하는 경우

에 당신이 변환 할 수있는 표준 변환이있다.

논리 언어 반대로 하스켈에서 추상화 이런 종류의 일을 진짜 귀찮은 당신이 정말 이은 "우주"를 통과해야하는 매개 변수로 xs을 설정합니다. 나는 이것이 당신이 당신의 제목에서 언급 한 "소란"에 가져 오는 것이라고 믿습니다.

원하는 경우 범용 세트 (검색 대상)를 모나드에 넣을 수 있습니다. 그런 다음 자신 만의 버전 인 exists 또는 find을 모나 딕 상태로 정의 할 수 있습니다. 효율성을 높이려면 Control.Monad.Logic을 시도해 볼 수는 있지만 Oleg의 논문을 상대로 머리를 부러 뜨릴 수도 있습니다.

어쨌든, 고전적인 인코딩은 실존 및 수량 한정사를 포함하여 모든 바인딩 구성을 lambdas로 대체하고 적절한 함수 호출을 진행하는 것입니다. 내 경험에 따르면이 인코딩은 구조가 많은 복잡한 중첩 쿼리에서도 작동하지만 항상 복잡하지는 않습니다.

Answer 2

어쩌면 내가 이해할 수없는 부분일지도 모르지만 목록 작성에있어 문제가 있습니까? 두 번째 예는된다 :

이

[(x,y,z) | x <- xs, y <- xs, z <- xs 
, x /= y && y /= z && x /= z 
, (p1 x y z) == (p2 x y z)] 

이것은 당신이 값을 반환 할 수 있습니다; 수식이 만족되는지 확인하려면 null을 사용하십시오 (게으름으로 인해 필요 이상으로 평가되지 않음).