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

Question

Я пытаюсь выучить F # и смотрел видео, когда появилось что-то странное (по крайней мере, для меня).Речь идет о здесь , а соответствующая часть начинается в 2:30 для тех, кто заинтересован.Но, по сути, парень говорит, что F # делает работу с массивами неудобной и что дизайнеры сделали это специально, потому что списки легче «готовить и добавлять».

Вопрос, который сразу же возник в голове: isn 'Легко ли придумывать и добавлять что-то, на что следует осуждать неизменным языком?В частности, я имею в виду списки C #, где вы можете сделать что-то вроде List.Add(obj); и изменить список.С массивом вам нужно было бы создать совершенно новый массив, но это также должно происходить на неизменном языке.

Так почему же разработчики F # предпочитают списки?В чем принципиальное отличие неизменяемой среды между списком и массивом?Что мне не хватает?Действительно ли списки в F # связаны между собой?

Answer 1

Я бы не согласился с тем, что "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 первоначально сконструированного списка и может двигаться только вперед, а поскольку элементы списка, на которые он указывает, не могут быть изменены, это не независимо от того, что у разделяет узлы с ним.

Answer 2

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

Answer 3

Прежде всего, массивы - это довольно низкоуровневая структура данных, и они действительно полезны, только если вы знаете длину массива при его создании. Это не часто случается, и это причина, почему программисты C # используют 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 и т. Д. Разница действительно появляется только при инициализации списка / массива.

Answer 4

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

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

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

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

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

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

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

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

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

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

Действительно ли списки в F # связаны между собой?

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

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

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

Answer 5

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

public class List<T> {

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

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

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