차이점 리스트
Difference list컴퓨터 과학에서 차분 리스트라는 용어는 효율적인 O(1) 연결 연산을 가진 리스트를 나타내는 데이터 구조를 말하며, 그 길이에 비례하는 시간에 링크드 리스트로 변환한다.차분 리스트는 퍼스트 클래스 함수 또는 통일 기능을 사용하여 구현할 수 있습니다.차이 목록이 다른 목록 표현보다 더 효율적인지 여부는 사용 패턴에 따라 달라집니다.알고리즘이 작은 목록을 연결하여 목록을 작성하는 경우, 차분 목록을 사용하면 목록 작성 연산을 효과적으로 "평탄화"함으로써 성능을 향상시킬 수 있습니다.
기능을 사용한 구현
차분 리스트 f는 단일 인수 함수 부가 L로, 링크 리스트 X를 인수로 지정하면 X 앞에 부가된 L을 포함하는 링크 리스트를 반환합니다.차분 리스트의 연계가 함수 구성으로서 실장된다.내용은 f [][1]를 사용하여 검색할 수 있습니다.
이 구현은 보통 Haskell과 같은 함수형 프로그래밍 언어에서 사용됩니다.단, 명령형 언어에서도 사용할 수 있습니다.
함수로서, 차이 리스트는 모노이드로서, 또는 더 구체적으로 왼쪽 곱셈에 의해 유도되는 변환 모노이드의 케일리 표현이다.
사용 예로는 해스켈의 서곡의 ShowS 타입과 [2]해스켈의 Donald Bruce Stewart의 차이점 목록 라이브러리가 있습니다.
통합에 의한 구현
논리 프로그래밍 언어 Prolog의 또 다른 구현은 통일 [3]변수를 사용합니다.차이 리스트는 쌍 OpenList-Hole입니다.첫 번째 요소 OpenList는 Unbound Unified 변수(Hole)를 포함하는 목록이고 두 번째 요소 Hole은 홀에 대한 참조입니다.
