학습 Pilog - 6: 더 많은 목록

지난 게시물에서 목록이 어떻게 생겼는지 보여주고 재귀 개념과 member 술어에 대해 논의했습니다. 오늘 우리는 추가 및 반전, 누산기의 개념과 같은 몇 가지 추가 목록 기능을 살펴볼 것입니다.

이 게시물은 this tutorial을 기반으로 합니다.

추가 술어

Pilog의 또 다른 기본 술어는 "append"술어이며 세 가지 인수를 사용합니다. 처음 두 개는 하위 목록이고 세 번째는 연결된 목록입니다.

: (? (append (a b) (c) @X))
 @X=(a b c)
-> NIL

두 개의 하위 목록에서 얼마나 많은 가능성[a,b,c]을 만들어야 하는지 봅시다.

: (? (append @X @Y (a b c)))
 @X=NIL @Y=(a b c)
 @X=(a) @Y=(b c)
 @X=(a b) @Y=(c)
 @X=(a b c) @Y=NIL
-> NIL

이제 append의 정의를 살펴보겠습니다(PicoLisp 설치의 pilog.l 라이브러리 파일에서 찾을 수 있음). member 와 마찬가지로 재귀적으로 정의됩니다. 기본 사례는 빈 목록@L에 목록NIL을 추가하는 것입니다. 즉, 결과는 최종 목록@L과 같습니다.

(be append (NIL @X @X))

기본 사례에 있는 경우 결과 목록은 두 번째 인수와 같습니다. 이제 첫 번째 인수에 하나의 항목만 있는 경우@A 새 목록은 첫 번째 목록의 헤드가 앞에 추가된 두 번째 인수(현재 @Y라고 함)와 동일합니다. 맞습니까? 그리고 이것은 다음과 같이 재귀적으로 반복될 수 있습니다.

(be append ((@A . @X) @Y (@A . @Z)) (append @X @Y @Z))

따라서 정확히 말하면 (Prolog) 술어 이름append이 최선의 선택이 아닐 수 있습니다. concatenated가 (see SWI prolog docs) 더 잘 맞았을 것입니다. 무슨 일이 일어나고 있는지 추적해 봅시다:

: (? append (append (a b) (c) @X))
2 (append (a b) (c) (a . @Z))
2 (append (b) (c) (b . @Z))
1 (append NIL (c) (c))
 @X=(a b c) 
-> NIL

첫 번째 목록은 빈 목록으로 축소되고 두 번째 인수는 세 번째 인수와 동일하게 설정됩니다. 그 후 세 번째 인수는 최종 결과에 도달할 때까지 "채워집니다".

보시다시피 작동하지만 많은 단계가 필요하고 매우 비효율적일 수 있습니다.

역술어

reverse(pilog에 내장되어 있지 않음)라는 또 다른 술어를 살펴보겠습니다. 첫 번째 인수의 요소가 두 번째 인수와 비교하여 역순이면 true를 반환합니다.

: (? (reverse (a b c) @X))
 @X = (c b a)

append를 사용하여 재귀적 접근 방식으로 다시 구현할 수 있습니다. 빈 목록에서 시작하여 헤드를 연결하여 작성합니다.

(be reverse (NIL NIL))

(be reverse ((@A . @X) @R)
   (reverse @X @Z)
   (append @Z (@A) @R))

그러나 append 의 효율이 낮기 때문에 권장하지 않습니다. 더 나은 방법을 찾아봅시다.

어큐뮬레이터 사용

더 나은 아이디어는 누산기를 사용하여 이 작업을 해결하는 것입니다. 누산기는 기본적으로 처리되는 요소를 "채택"하는 목록입니다.

(be accRev ((@H . @T) @A @R)
   (accRev @T (@H . @A) @R) )

(be accRev (NIL @A @A))

결과(세 번째 인수)는 반전된 목록과 정확히 일치합니다. 따라서 우리가 해야 할 일은 (reverse (@L @R)) 술어를 다음과 같이 정의하는 것입니다.

(be reverse (@L @R)
   (accRev @L NIL @R))

우리가 생각하는 대로 작동하는지 확인하기 위해 추적해 봅시다.

: (? reverse accRev ( reverse (a b c) @X))
1 (reverse (a b c) @R)
1 (accRev (a b c) NIL @R)
1 (accRev (b c) (a) @R)
1 (accRev (c) (b a) @R)
2 (accRev NIL (c b a) (c b a))
 @X=(c b a)
-> NIL

장점은 결과가 마지막 단계 이후에 바로 사용 가능하다는 점입니다. 반면에 전체 재귀 트리를 백업하려면 "순진한"리버스가 필요했습니다.

예: 회문 검사기

역방향 목록에 대해 말하자면, 한 가지 예를 빠뜨려서는 안 됩니다. 간단한 회문 검사기를 작성하는 방법입니다. 실제로 하나의 인수인 목록만 취하는 실제palindrome 술어를 제외하고는 이미 필요한 모든 것이 있습니다.

(be palindrome (@L)
   (reverse @L @L) )

reverse 의 경우 이전에 정의한 조건자 중 하나를 사용할 수 있습니다. 테스트해 봅시다:

: (? (palindrome ( r o t a t o r)))
-> T

: (? (palindrome ( a b c d e f g)))
-> NIL

모든 예제here에 대한 소스를 찾을 수 있습니다.

프롤로그 단기집중편 시리즈의 마지막 포스팅에서는 "컷과 부정"에 대해 알아보도록 하겠습니다.

출처

https://www.swi-prolog.org/pldoc/man?predicate=append/3