Prolog 인터프리터에서 차이 목록을 사용하는 방법

Question

this question on an empty list as a difference list을 작성할 때 이러한 구조를 알고 있는지 테스트하고 싶습니다. 그러나 다른 표기법을 비교하는 것만 큼 간단하게 시도했을 때 내가 틀렸다고 생각했고 이 아니고은 실제로 차이 목록으로 무엇이 진행되는지 이해합니다.

?- L = [a,b,c|[d,e]]-[d,e], L = [a,b,c]. 
false % expected true 

나는 이것을 SICStus뿐만 아니라 SWI-Prolog에서도 테스트했습니다. 이 표기법은 Bratko의 Prolog Programming in AI,210 페이지에 쓰여졌 기 때문에이 표기법을 검증했지만 명백하게 통일은 불가능합니다. 왜 그런가요? 이 표기법은 같은 선언적 의미를 가지고 있지 않습니까?

Answer 1

당신은 Prolog 인터프리터가 차이 목록을 특별한 것으로 취급한다고 생각합니다. Prolog는 차이 목록 (또는 구문 설탕을 제외한 거의 모든 개념의 개념)을 인식하지 못합니다. 그는 단지보고 :

L=-(|(a, |(b, |(c, |(d, |(e, []))))), |(d, |(e, []))) 

-/2 및 |/2이 펑터이다

및 a, b, c, d, e 및 []는 상수이다.

차이리스트는 단순히 프로그래밍 기술 있습니다 (예를 동적 프로그래밍뿐만 아니라 기술처럼, 컴파일러는 감지도 다르게 동적 프로그래밍 프로그램을 취급 할 수 없음). 표현식의 깊숙이 부분적으로 통일되지 않은 부분을 효율적으로 통합하는 데 사용됩니다.

append/3 두 개의 목록이 필요하다고 가정 해보십시오.

%append(A,B,C). 
append([],L,L). 
append([H|T],L,[H|B]) :- 
    append(T,L,B). 

을하지만이 O (n)이에서 실행 : 다음과 같이이 작업을 수행 할 수 있습니다 먼저 전체 첫 번째 목록을 반복해야합니다. 그 목록에 수천 개의 요소가 포함되어 있다면 많은 시간이 걸릴 것입니다.

이제

당신은 당신이 append_diff/3 목록뿐만 아니라 공급합니다 자신 계약,하지만 List 목록의 시작 부분에 대한 참조입니다 튜플 -(List,Tail)을 정의 할 수 있으며, Tail는 말에 대한 참조입니다 통합 목록이 아닙니다. 이 요구 사항을 충족시키는 구조의 예는 Tail-Tail, [a|Tail]-Tail, [1,4,2,5|Tail]-Tail입니다.

이제 효과적으로 할 수 append_diff/3에서 O (1)와 :

append_diff(H1-T1,T1-T2,H1-T2). 

이유는 무엇입니까? 첫 번째 목록의 통합되지 않은 꼬리를 두 번째 목록과 통합하기 때문입니다. 이제 두 번째 목록의 일치하지 않는 꼬리가 최종 목록의 꼬리가됩니다.그래서 예를 들어 가지고 : 위에서 보는 바와 같이 우리는 또한 T2에 대한 참조를 갖고 있기 때문에

append_diff([a|T1]-T1,[1,4,2,5|T2]-T2,L). 

을 술어를 호출하면, T1는, 이제 첫 번째 목록은 [a|[1,4,2,5|T2]] 이하 [a,1,4,2,5|T2]에 붕괴, [1,4,2,5|T2]로 통합됩니다, 우리는 "프롤로그에서 아무것도 이으로 반환되었습니다", "[a,1,4,2,5|T2]-T2"을 반환 할 수 있습니다 : 열린 꼬리가있는 새로운 차이 목록 T2. 당신은 특별한 의미를 자신-을 제공 때문에 그러나 이것은 단지입니다 : 프롤로그 - 단순히 -입니다, 그것은하지 마이너스, 그것은 계산하지 않는 차이 등 프롤로그 펑에 의미를를 첨부하지 않습니다. - 대신 +을 사용했다면 그다지 큰 차이가 없었을 것입니다.

다시 질문에 답하십시오 : 당신은 단순히 L = -([a,b,c,d,e],[d,e]) 이상상태라고 Prolog에 상태. 이제이 두 표현식이 통일 될 수 없음이 분명합니다. 그래서 Prolog는 false라고 말합니다.