оператор недостатков (: :) в F#
:: оператор в F# всегда предварительно ожидает элементы к списку. Существует ли оператор, который добавляет к списку? Я предполагаю то использование оператор
[1; 2; 3] [4]
было бы менее эффективным, чем добавление одного элемента.
5 ответов
Как сказали другие, такого оператора не существует, потому что в нем не было бы смысла. На самом деле я думаю, что это хорошо, потому что так легче понять, что операция не будет эффективной. На практике оператор не нужен - обычно есть лучший способ написать то же самое.
Типичный сценарий: Я думаю, что типичный сценарий, когда вы можете подумать, что вам нужно добавить элементы в конец, настолько распространен, что может быть полезно его описать.
Добавление элементов в конец кажется необходимым, когда вы пишете хвостовую рекурсивную версию функции, использующую параметр накопитель. Например, (неэффективная) реализация функции 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), что гораздо эффективнее, чем добавлять элементы один за другим.
Стоимость добавления двух стандартных списков пропорциональна длине списка слева . В частности, стоимость
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 []
Идея состоит в том, что вы представляете список функционально как функцию от «остальных элементов» до «окончательного списка». Это отлично работает, если вы собираетесь составить весь список, прежде чем смотреть на какой-либо из элементов. В противном случае вам придется иметь дело с линейной стоимостью добавления или полностью использовать другую структуру данных.
Списки в F # односвязны и неизменяемы. Это означает, что переход на передний план - это O (1) (создать элемент и указать ему на существующий список), тогда как переход на задний план - O (N) (поскольку весь список должен быть реплицирован; вы не можете изменить существующий конечный указатель, вы должны создать полностью новый список).
Если вам нужно «добавить один элемент в конец», то, например,
l @ [42]
- это способ сделать это, но это запах кода.
Я предполагаю, что использование оператора @ [...] будет менее эффективным, чем добавление одного элемента.
Если да, то разница будет незначительной. И добавление одного элемента, и объединение списка в конец - это операции O (n) . На самом деле я не могу придумать ни одной вещи, которую должен делать @ , чего не могла бы сделать функция добавления одного элемента.
Эффективность (или ее отсутствие) достигается за счет итерации по списку для поиска последнего элемента. Таким образом, объявление нового списка с помощью [4] будет несущественным для всех, кроме самых тривиальных сценариев.