оператор минусов (: :) в F #

Question

Оператор :: в F # всегда добавляет элементы в список. Есть ли оператор, который добавляет в список? Я предполагаю, что с помощью оператора @

[1; 2; 3] @ [4]

будет менее эффективным, чем добавление одного элемента.

Answer 1

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

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

Добавление элементов в конец кажется необходимым, когда вы пишете хвостовую рекурсивную версию функции, используя параметр аккумулятора . Например, (неэффективная) реализация функции filter для списков будет выглядеть так:

let filter f l = 
  let rec filterUtil acc l =
    match l with 
    | [] -> acc
    | x::xs when f x -> filterUtil (acc @ [x]) xs
    | x::xs -> filterUtil acc xs
  filterUtil [] l

На каждом шаге нам нужно добавить один элемент в аккумулятор (который хранит элементы, которые будут возвращены в результате). Этот код можно легко изменить, чтобы использовать оператор :: вместо добавления элементов в конец списка acc:

let filter f l = 
  let rec filterUtil acc l =
    match l with 
    | [] -> List.rev acc                        // (1)
    | x::xs when f x -> filterUtil (x::acc) xs  // (2)
    | x::xs -> filterUtil acc xs
  filterUtil [] l

В (2) мы теперь добавляем элементы в начало аккумулятора, и когда функция собирается вернуть результат, мы обращаемся к списку (1), который намного эффективнее, чем добавление элементов по одному один.

Answer 2

Списки в F # являются односвязными и неизменяемыми.Это означает, что на лицевой стороне находится O (1) (создайте элемент и укажите его на существующий список), тогда как на задней стороне находится O (N) (так как весь список должен быть реплицирован; вы не можете изменитьсуществующий конечный указатель, вы должны создать целый новый список).

Если вам нужно «добавить один элемент к задней части», то, например,

l @ [42]

- это способ сделать это, но это кодовый запах.

Answer 3

Стоимость добавления двух стандартных списков пропорциональна длине списка слева .В частности, стоимость

xs @ [x]

пропорциональна длине xs - это , а не постоянная стоимость.

Если вам нужна абстракция в виде списка с добавлением в постоянное время, вы можете использовать представление функции Джона Хьюза, которое я назову hlist.Я попытаюсь использовать синтаксис OCaml, который, я надеюсь, достаточно близок к F #:

type 'a hlist = 'a list -> 'a list   (* a John Hughes list *)
let empty : 'a hlist = let id xs = xs in id
let append xs ys = fun tail -> xs (ys tail)
let singleton x = fun tail -> x :: tail
let cons x xs = append (singleton x) xs
let snoc xs x = append xs (singleton x)
let to_list : 'a hlist -> 'a list = fun xs -> xs []

Идея состоит в том, что вы представляете список функционально в виде функции от «остальных элементов» до «Финальный список ».Это работает создать, если вы собираетесь построить весь список, прежде чем вы посмотрите на любой из элементов.В противном случае вам придется иметь дело с линейной стоимостью добавления или использования другой структуры данных полностью.

Answer 4

Я предполагаю, что использование оператора @ [...] будет менее эффективным, чем добавление одного элемента.

Если это так, разница будет незначительной. Добавление одного элемента и объединение списка в конец являются O(n) операциями. На самом деле я не могу вспомнить ни одной вещи, которую @ должен сделать, чего не могла бы функция добавления одного элемента.

Answer 5

Может быть, вы хотите использовать другую структуру данных. У нас есть двусторонние очереди (или короткие «Deques») в fsharpx . Вы можете прочитать больше о них на http://jackfoxy.com/double-ended-queues-for-fsharp

Answer 6

Эффективность (или нехватка) зависит от итерации списка, чтобы найти конечный элемент. Поэтому объявление нового списка с [4] будет пренебрежимо мало для всех, кроме самых тривиальных сценариев.

Answer 7

Попробуйте использовать двустороннюю очередь вместо списка. Недавно я добавил 4 версии deques (орфография Окасаки) в FSharpx.Core (доступно через NuGet. Исходный код FSharpx.Core.Datastructures ). Смотрите мою статью об использовании dequeus Двусторонние очереди для F #

Я предложил команде F # сделать оператор cons, :: и активный дискриминатор шаблона доступным для других структур данных с подписью head / tail. 3