목록의 머리 부분과 끝 부분에 2 개의 뷰를 가질 수있는 목록 데이터 구조를 효과적으로 구현할 수 있습니다. 역순으로 값 비싼 호출을하지 않고도 목록의 꼬리를 항상 가리킬 수 있습니다. 즉 :Haskell의 효율적인 큐
start x = []
end x = reverse start -- []
start1 = [1,2,3] ++ start
end start1 -- [3,2,1]
끝 '역'호출 단순히 자동으로 역에있는 목록의 관점에서 주어진리스트를 보지 않고이 작업을 수행 할 수 있어야합니다. 연결을 시작으로 새 목록을 만들면 동일하게 유지됩니다.
당신은 언제나 Data.Sequence를 사용할 수 있습니다.
완전히 기능적인 대기열의 잘 알려진 구현은 두 개의 목록을 사용하는 것입니다. 하나는 대기열에 넣고 다른 하나는 대기열에 넣기위한 것입니다. Enqueue는 단순히 enqueue 목록에 위배됩니다. 대기열에서 대기열에 추가하면 대기열에없는 대기열 목록의 머리글이 사용됩니다. 큐 해제 목록이 비어 있으면 큐 목록을 반대로 다시 채 웁니다. Chris Okasaki의 Purely Functional Datastructures.
이 구현이 reverse을 사용하더라도이 시간의 상각 된 시간 비용은 점근 적으로 중요하지 않습니다. 그것은 모든 enqueue에 대해 dequeue list refill을 위해 Θ (1)의 시간 채무를 부과하도록 작동합니다. 따라서 dequeue의 예상 시간은 enqueue의 예상 시간의 두 배가됩니다. 이것은 일정한 요소이므로 두 연산의 비용은 Θ (1)입니다.
ephemerally 경우에만 * 사소한 * 사용 *. 응용 프로그램이 지속성에 좌우되는 경우 대기열에 액세스 할 때마다 해당 O (n) 사례를 실행할 수 있습니다. – Juliet
@Juliet laziness와 memoization을 사용하여, 지속성을 유지하면서 amortized bound는 여전히 O (1)입니다. – Yuhta
@Yuhta는 게으름과 메모를 사용하여 예제를 보여줄 수 있습니까? – CMCDragonkai
저는 하스켈 사용자가 아니지만, 상각 된 상수 시간에 작동 될 수있는 하스켈 대기열을 설명한다고 주장하는 a blog post을 발견했습니다. Chris Okasaki의 우수한 Purely Functional Data Structures의 디자인을 기반으로합니다.
Data.Dequeue 무엇을 찾고 계십니까?
(그것은reverse을 가지고 있지 않지만 꽤 쉽게 추가하고 작성자에게 패치를 보낼 수 있습니다.)
하스켈에서는 값을 변경할 수 없습니다. 'start'는 항상 빈리스트가 될 것이고'end'는 항상 그것의'reverse' 일 것입니다 (빈리스트). 상태를 유지하려면 상태 모나드를 살펴야합니다. –
수정 : 업데이트로 리바 인드를 의미합니다. – TheOne
@Absolute : 하스켈에서 변경할 수없는 것들 ('IO' 모나드에도 불구하고)을 바꿀 수 없다는 궁극적 인 진실은 당신이 무엇이라고 부르는 지 바꾸지 않습니다. 너는 물건을 다시 바인딩 할 수 없다. –