Функциональная итерация O (1) и O (n) из структуры данных первого списка элементов

Question

Я ищу функциональную структуру данных, которая поддерживает следующие операции:

• Append, O (1)
• В итерации заказа, O (n)

Нормальный функциональный связанный список поддерживает только добавление O (n), в то время как я мог бы использовать нормальный LL и затем обратить его обратно, обратная операция будет также O (n), которая (частично) отрицает O (1).) минусы операции.

Answer 1

Вы можете использовать списки добавления Джона Хьюза с постоянным временем, которые в настоящее время кажутся именуемыми DList. Представление - это функция от списков к спискам: пустой список - это функция тождества; append - композиция, а singleton - минусы (частично применены). В этом представлении каждое перечисление будет стоить вам n ассигнований, так что это может быть не так хорошо.

Альтернатива состоит в том, чтобы создать ту же алгебру, что и структура данных:

type 'a seq = Empty | Single of 'a | Append of 'a seq * 'a seq

Перечисление - это обход дерева, который либо будет стоить некоторого стекового пространства, либо потребует некоторого представления молния. Вот прогулка по дереву, которая преобразуется в список, но использует пространство стека:

let to_list t =
  let rec walk t xs = match t with
  | Empty -> xs
  | Single x -> x :: xs
  | Append (t1, t2) -> walk t1 (walk t2 xs) in
  walk t []

Вот то же самое, но с использованием постоянного стека:

let to_list' t =
  let rec walk lefts t xs = match t with
  | Empty -> finish lefts xs
  | Single x -> finish lefts (x :: xs)
  | Append (t1, t2) -> walk (t1 :: lefts) t2 xs
  and finish lefts xs = match lefts with
  | [] -> xs
  | t::ts -> walk ts t xs in
  walk [] t []

Вы можете написать функцию свертывания, которая посещает те же элементы, но фактически не обновляет список; просто замените минусы и ноль на что-то более общее:

val fold : ('a * 'b -> 'b) -> 'b -> 'a seq -> 'b

let fold f z t =
  let rec walk lefts t xs = match t with
  | Empty -> finish lefts xs
  | Single x -> finish lefts (f (x, xs))
  | Append (t1, t2) -> walk (t1 :: lefts) t2 xs
  and finish lefts xs = match lefts with
  | [] -> xs
  | t::ts -> walk ts t xs in
  walk [] t z

Это ваше перечисление с постоянным стеком за линейное время. Веселись!

Answer 2

Как насчет списка различий?

type 'a DList = DList of ('a list -> 'a list)

module DList =
  let append (DList f) (DList g) = (DList (f << g))
  let cons x (DList f) = (DList (fun l -> x::(f l)))
  let snoc (DList f) x = (DList (fun l -> f(x::l)))
  let empty = DList id
  let ofList = List.fold snoc empty
  let toList (DList f) = f []

Answer 3

Я считаю, что вы можете просто использовать стандартный функциональный связанный список:

• Чтобы добавить элемент, вы можете использовать cons (что составляет O (1) )
• Для итерации элементов в том порядке, в котором они были вставлены, вы можете сначала перевернуть список,
  (то есть O (N) ), а затем пройти по нему, чтотакже O (N) (и 2xO (N) по-прежнему просто O (N) ).

Answer 4

Вы можете создать функциональную Deque, которая обеспечивает O(1) добавление к любому концу и O(N) для итерации в любом направлении.Эрик Липперт написал об интересной версии неизменного Deque в своем блоге и обратите внимание, что если вы посмотрите вокруг, вы найдете другие части серии, но это объяснение конечного продукта.Также обратите внимание, что с небольшой настройкой его можно изменить, чтобы использовать различимые союзы F # и сопоставление с образцом (хотя это зависит от вас).

Еще одно интересное свойство этой версии, O(1) просмотр, удаление идобавить, что с любого конца (т.е. dequeueLeft, dequeueRight, dequeueLeft, dequeueRight и т. д. все еще O (N), в отличие от O (N * N) с методом двойного списка).

Answer 5

А как насчет кругового списка ?Он поддерживает O ( 1 ) и O ( n ).