Я пытаюсь узнать F # и смотрел видео, когда что-то странное (по крайней мере, для меня) подошло. Видео, о котором идет речь, здесь, и соответствующая часть начинается в 2:30 для желающих. Но в основном, парень говорит, что F # делает неудобным работу с массивами и что дизайнеры сделали это специально, потому что списки легче "добавлять и добавлять".
Вопрос, который сразу же возник в голове: нелегко добавить и добавить что-то, на что надо наговорить на неизменном языке? В частности, я думаю о списках С#, где вы можете сделать что-то вроде List.Add(obj); и мутировать список. С массивом вам нужно будет создать совершенно новый массив, но также и то, что должно произойти на неизменном языке.
Так почему дизайнеры F # предпочитают списки? В чем принципиальное отличие в неизменяемой среде между списком и массивом? Что мне не хватает? Являются ли списки в F # действительно связанными списками?
В списках функциональных языков обычно есть односвязные списки. То есть нет необходимости копировать полный список. Вместо этого добавление (часто называемое cons) является операцией O (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 из первоначально построенного списка и может двигаться только вперед, и поскольку элементы списка, на которые он указывает, не могут быть мутированы, это не что y делится с ним узлами.
Прежде всего, массивы представляют собой довольно низкоуровневую структуру данных, и они действительно полезны, если вы знаете длину массива при его создании. Это не часто случается и что причина, по которой программисты С# используют 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 и т.д. Разница действительно появляется только при инициализации списка/массива.
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
Вот почему оператор :: является конструктором, а не функцией, поэтому вы не можете писать (::), как вы можете, например, (+).
Список F # больше похож на следующую структуру данных - единственный связанный список:
public class List<T> {
public List(T item, List<T> prev) { /*...*/ }
public T Item { get; }
public List<T> Prev { get; }
}
Итак, когда создается новый список, он фактически создает единственный node со ссылкой на первый элемент предыдущего списка, а не копирует весь массив.