Эффективная очередь в Хаскеле

Question

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

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

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

Answer 1

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

В качестве альтернативы общеизвестной реализацией чисто функциональной очереди является использование двух списков. Один для постановки в очередь, а другой для отвода. Enqueue будет просто минусы со списком enqueue. Dequeue занимает главу списка dequeue. Когда список очереди короче списка очереди, заполните его, перевернув список очереди. См. чисто функциональные структуры данных Криса Окасаки.

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

Answer 2

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

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

Хорошо, начнем.

1. Возможна постоянная реализация очереди с амортизированной 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
   

2. И почему эта амортизированная O (1) даже используется постоянно ? Haskell ленив, поэтому reverse rs на самом деле не происходит, пока это не нужно. Чтобы заставить reverse rs, ему нужно сделать | fs | шагов, прежде чем достигнуть reverse rs. Если мы повторим tail до достижения приостановки reverse rs, то результат будет запомнен, поэтому во второй раз потребуется только O (1) . С другой стороны, если мы используем версию до установки приостановки fs ++ reverse rs, то снова она должна пройти fs шагов, прежде чем достигнуть reverse rs. Формальное доказательство с использованием (модифицированного) метода Банкира содержится в книге Окасаки.

3. Ответ @ Apocalisp

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

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

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

   Окасаки описал свою амортизированную O (1) постоянную очередь в канале 6.

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

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

Answer 3

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

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

Answer 4

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