Эффективная очередь в Haskell

Как я могу эффективно реализовать структуру данных списка, где у меня может быть 2 вида в голову и конец списка, которые всегда указывают на хвост списка без дорогостоящих обращений. то есть:

start x = []
end x = reverse start -- []
start1 = [1,2,3] ++ start
end start1 -- [3,2,1]

end должен иметь возможность сделать это, не вызывая "обратное", а просто глядя на данный список с точки зрения автоматического преобразования списка. То же самое должно быть выполнено, если я создам новые списки из конкатенаций для запуска.

Ответ 1

Вы всегда можете просто использовать Data.Sequence.

Известная реализация чисто функциональной очереди заключается в использовании двух списков. Один для очереди, а другой для dequeue. Enqueue просто пропустит список очередей. Dequeue возглавляет список dequeue. Когда список dequeue пуст, пополните его, изменив регистр очереди. См. Chris Okasaki Чисто функциональные структуры данных.

Несмотря на то, что в этой реализации используется reverse, амортизированная стоимость этого времени незначительна асимптотически. Это работает так, что для каждой очереди вы берете на себя долгую задолженность Θ (1) за повторное заполнение списка. Таким образом, ожидаемое время детекции вдвое больше, чем в очереди. Это постоянный коэффициент, поэтому стоимость обеих операций равна Θ (1).

Ответ 2

Является Data.Dequeue, что вы ищете?

(У него нет reverse, но вы можете легко добавить его и отправить исправление автору.)

Ответ 3

Этот вопрос появляется в качестве третьего результата на первой странице, пока я в Haskell queue Google Haskell queue, но ранее предоставленная информация вводит в заблуждение. Итак, я чувствую, что есть необходимость уточнить некоторые вещи. (И первым результатом поиска является сообщение в блоге, которое содержит небрежную реализацию...)

Все, что ниже, в основном из статьи Окасаки, Простых и эффективных чисто функциональных очередей и заявок в 1995 году или его книги.

Хорошо, давай начнем.

Возможна постоянная реализация очереди с амортизированной временной сложностью O (1). Хитрость заключается в том, чтобы перевернуть список, представляющий заднюю часть очереди, при условии, что передняя часть достаточно длинна, чтобы амортизировать стоимость reverse операции. Таким образом, вместо того, чтобы перевернуть заднюю часть, когда передняя часть пуста, мы изменяем ее, когда передняя часть короче задней части. Следующий код взят из приложения к книге Окасаки
```
data BQueue a = BQ !Int [a] !Int [a]

check :: Int -> [a] -> Int -> [a] -> BQueue a
check lenf fs lenr rs =
  if lenr <= lenf 
  then BQ lenf fs lenr rs 
  else BQ (lenr+lenf) (fs ++ reverse rs) 0 [] 

head :: BQueue a -> a
head (BQ _ []    _ _) = error "empty queue"
head (BQ _ (x:_) _ _) = x

(|>) :: BQueue a -> a -> BQueue a 
(BQ lenf fs lenr rs) |> x = check lenf fs (lenr + 1) (x:rs)

tail :: BQueue a -> BQueue a
tail (BQ lenf (x:fs) lenr rs) = check (lenf-1) fs lenr rs
```
И почему этот амортизированный O (1) даже постоянно используется? Haskell ленив, так что reverse rs самом деле не происходит, пока это не нужно. Чтобы заставить reverse rs, он должен принять | fs | шаги до достижения reverse rs. Если мы повторим tail до того, как достигнем reverse rs подвески, результат будет запомнен, так что во второй раз он займет только O (1). С другой стороны, если мы используем версию до размещения fs ++ reverse rs приостановки fs ++ reverse rs, то снова она должна пройти шаги fs до достижения reverse rs. Формальное доказательство с использованием (модифицированного) метода Банкира содержится в книге Окасаки.
Ответ @Apocalisp

Когда список очереди пуст, заполните его, перевернув список очереди

это реализация в гл. 5 его книги с предупреждением в самом начале

К сожалению, простой взгляд на амортизацию, представленный в этой главе, нарушается при наличии настойчивости

Окасаки описал свою амортизированную постоянную очередь O (1) в гл. 6.
До сих пор мы говорили только о сложности амортизированного времени. На самом деле можно полностью исключить амортизацию, чтобы достичь временной сложности O (1) для наихудшего случая для постоянной очереди. Хитрость заключается в том, что reverse должен принудительно увеличиваться при каждом вызове удаления/постановки в очередь. Реальную реализацию здесь немного сложно объяснить.

Опять же, все уже в его газете.

Ответ 4

Я не являюсь пользователем Haskell, но нашел сообщение в блоге, которое утверждает, что описывает очередь Haskell, на которой можно работать в амортизированном постоянном времени. Это основано на дизайне от Криса Окасаки, отличных чисто функциональных структур данных.