Cons operator (::) в F #

Ответ 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), который намного эффективнее, чем добавлять элементы по одному один.

Ответ 2

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

Если вам нужно "добавить один элемент назад", то, например,

l @ [42]

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

Ответ 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 []

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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