중첩 목록을 만들지 않고 erlang에서리스트를 연결하는 방법은 무엇입니까?

Question

나는 좋은 erlanger가되고 "++"를 피하려고 노력하고있다. 중첩 목록을 만들지 않고 목록 끝에 튜플을 추가해야합니다. (역으로 빌드하고 역순으로 할 필요가 없기를 바랍니다.) 튜플 T를 감안할 때 L0과 L1 나열 : 나는 [T | L0]를 사용하면

가을 내가 얻을 [튜플,리스트 0]. 내가 사용할 때

는하지만 [L0를 | T], 나는 중첩 된 목록을 [[리스트 0] | 튜플]. 마찬가지로 [L0 | L1]은 [[list0] | list1]을 반환합니다.

외부 목록 대괄호를 제거하면 L0 | [T] 구문 오류가 발생합니다.

왜 "|" 대칭 적이 지 않습니까? "|"을 사용하여 원하는 것을 할 수있는 방법이 있습니까?

Answer 1

|은 비어 있지 않은 목록에 머리와 단일 꼬리표가 있고 꼬리가 다른 목록 인 꼬리가 있기 때문에 "대칭"이 아닙니다. 표현 [foo | bar]foo은 목록의 머리를 나타내고 bar은 꼬리입니다. 꼬리가 적절한 목록이 아니면 결과도 적절한 목록이 아닙니다. 헤드가리스트 인 경우, 결과는 그리스트를 첫 번째 요소로 갖는리스트가됩니다.

O (n)보다 적은 시간에 연결된 목록의 끝에 추가 할 수있는 방법이 없습니다. 이것이 대체로 회피되는 이유는 ++입니다. 목록 끝에 추가 할 특수 구문이 있다면 여전히 O (n) 시간이 걸릴 것이고 해당 구문을 사용하면 ++을 사용하는 것보다 "좋은 erlanger"가 더 이상 필요하지 않을 것입니다.

삽입 당 O (n) 비용을 피하려면 사전에 추가 한 다음 되돌려 야합니다. 비용을 기꺼이 부담한다면 ++을 사용할 수도 있습니다.

목록 작업 방법에 대한 좀 더 세부 사항 :

[ x | y ] 무언가는 단점 셀을했다. C 언어에서는 기본적으로 두 멤버가있는 구조체입니다. 올바른 목록은 빈 목록 ([])이거나 두 번째 구성원이 적절한 목록 인 조건부 셀입니다.이 경우 첫 번째 구성원은 머리로, 두 번째 구성원은 꼬리라고합니다.

이렇게하면 [1, 2, 3]을 쓸 때 [1 | [2 | [3 | []]]]이라는 단락 셀이 생성됩니다. 나는. 목록은 첫 번째 구성원 (해당 헤드)이 1이고 두 번째 구성원 (꼬리)이 다른 cons 셀인 cons 셀로 표시됩니다. 그 다른 단점 셀은 머리가 2 개이고 꼬리가 또 다른 단점이 있습니다. 그 셀은 머리가 3이고 꼬리가 빈 목록입니다.

이러한 목록을 순회하는 것은 먼저 목록의 헤드에서 작동 한 다음 목록의 끝에있는 순회 기능을 호출하여 재귀 적으로 수행됩니다.

이제 목록에 항목을 추가하려면 매우 쉽습니다. 머리를 새 항목으로하고 꼬리를 이전 목록으로 사용하는 다른 죄수군 셀을 만들면됩니다.

그러나 하나의 단락 셀을 작성하는 것만으로는 충분하지 않기 때문에 항목을 추가하는 것이 훨씬 더 비쌉니다.마지막 단락 셀의 꼬리가 머리가 새 요소이고 꼬리가 빈 목록 인 새 단락 셀이어야한다는 점을 제외하고는 이전 것과 동일한 목록을 만들어야합니다. 따라서 전체 목록을 거치지 않고 목록에 추가 할 수는 없습니다. O (n)입니다.