Почему F # предпочитает списки по массивам?

Ответ 1

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

Ответ 2

Я бы не согласился с тем, что "F # делает неудобным работу с массивами". Фактически, F # делает работу с массивами довольно приятной по сравнению с большинством языков.

Например, F # имеет строчную конструкцию массива: let arr = [|1;2;3;4;|]. И, возможно, даже более круто, сопоставление образцов по массивам:

match arr with
| [|1;2;_;_|] -> printfn "Starts with 1;2"
| [|_;_;3;4|] -> printfn "Ends with 3;4"
| _ -> printfn "Array not recognized"

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

let x = [2;3]
let y = 1::x

Здесь y создается путем добавления 1 к x, но x не изменяется и не копируется, поэтому y очень дешево. Мы можем немного понять, как это возможно, поскольку x указывает на головку 2 из первоначально построенного списка и может двигаться только вперед, и поскольку элементы списка, на которые он указывает, не могут быть мутированы, это не что y делится с ним узлами.

Ответ 3

Прежде всего, массивы представляют собой довольно низкоуровневую структуру данных, и они действительно полезны, если вы знаете длину массива при его создании. Это не часто случается и что причина, по которой программисты С# используют System.Collections.Generic.List<T>, а программисты F # используют F # list<T>.

Причина, по которой F # предпочитает свой собственный функциональный список вместо использования .NET list<T>, заключается в том, что функциональные языки предпочитают неизменные типы. Вместо того, чтобы изменять объект, вызывая list.Add(x), вы можете создать новый список с элементами, добавленными спереди, написав let newList = x::list.

Я также согласен с Стивеном, что использование массивов в F # не является неудобным вообще. Если вам известно количество элементов, с которыми вы работаете, или вы преобразовываете некоторый существующий источник данных, то работа с массивами довольно проста:

/ You can create arrays using `init`
let a = Array.init 10 (fun i -> (* calculate i-th element here *) )

// You can transform arrays using `map` and `filter`
a |> Array.map (fun n -> n + 10)
  |> Array.filter (fun n -> n > 12)

// You can use array comprehensions:
let a2 = [| for n in a do
              if n > 12 then yield n + 10 |]

Это по существу то же самое, что и списки обработки - там вы должны использовать функции списка [ ... ] и функции обработки списка, такие как List.map и т.д. Разница действительно появляется только при инициализации списка/массива.

Ответ 4

F # затрудняет работу с массивами

F # предоставляет множество функций, которые упрощают работу с массивами, чем на других языках, включая литералы массивов, шаблоны массивов и функции более высокого порядка.

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

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

Итак, почему дизайнеры F # предпочитают списки?

F # унаследовал некоторые возможности, связанные с списком, от OCaml, которые унаследовали их от Standard ML и ML, потому что одиночные связанные неизменные списки очень полезны в контексте их области приложения (метапрограммирование), но я бы не сказал, что дизайнеры F # предпочитают списки.

В чем принципиальное отличие неизменяемой среды между списком и массивом?

В F # списки обеспечивают O (1) добавление и добавление и O (n) случайный доступ, тогда как массивы обеспечивают O (n) добавление и добавление и O (1) случайный доступ. Массивы могут быть мутированы, но списки не могут.

Что мне не хватает?

Базовые знания чисто функциональных структур данных. Прочитайте Окасаки.

Являются ли списки в F # действительно связанными списками?

Да. В частности, односвязные неизменные списки. Фактически, в некоторых MLs тип list может быть определен как:

type 'a list =
  | ([])
  | (::) of 'a * 'a list

Вот почему оператор :: является конструктором, а не функцией, поэтому вы не можете писать (::), как вы можете, например, (+).

Ответ 5

Список F # больше похож на следующую структуру данных - единственный связанный список:

public class List<T> {

    public List(T item, List<T> prev) { /*...*/ }

    public T Item { get; }
    public List<T> Prev { get; }
}

Итак, когда создается новый список, он фактически создает единственный node со ссылкой на первый элемент предыдущего списка, а не копирует весь массив.