Почему F# предпочитает списки массивам?
Я пытаюсь выучить F# и смотрю видео, когда что-то странное (по крайней мере, для меня) подошло. Это видео находится здесь, и соответствующая часть начинается в 2:30 для тех, кто заинтересован. Но, по сути, парень говорит, что F# делает работу с массивами неудобной и что дизайнеры сделали это специально, потому что списки легче "готовить и добавлять".
Вопрос, который сразу всплыл в голову: разве не легко предсказать и добавить что-то, что следует отвергать на неизменном языке? В частности, я думаю о списках C#, где вы можете сделать что-то вроде List.Add(obj); и мутировать список. С массивом вам нужно было бы создать совершенно новый массив, но это также должно происходить на неизменном языке.
Так почему же дизайнеры F# предпочитают списки? В чем принципиальное отличие неизменяемой среды между списком и массивом? Что мне не хватает? Действительно ли списки в F# связаны между собой?
5 ответов
В функциональных языках списки обычно представляют собой односвязные списки. Т.е. не нужно копировать полный список. Вместо этого предваривание (часто называемое 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 первоначально построенного списка и может двигаться только вперед, а поскольку элементы списка, на которые он указывает, не могут быть видоизменены, независимо от того, что у разделяет узлы с ним.
Прежде всего, массивы - это довольно низкоуровневая структура данных, и они действительно полезны, только если вы знаете длину массива при его создании. Это не часто так, и это причина, почему программисты на 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 и т.д. Разница действительно появляется только при инициализации списка / массива.
F# делает работу с массивами неудобной
F# предоставляет множество функций, облегчающих работу с массивами, чем в других языках, включая литералы массивов, шаблоны массивов и функции высшего порядка.
Вопрос, который сразу всплыл в голову: разве не легко предсказать и добавить что-то, что следует отвергать на неизменном языке?
Я полагаю, вы неправильно поняли, что означает это утверждение. Когда люди говорят о добавлении и добавлении в контексте чисто функциональных структур данных, они имеют в виду создание новой коллекции, которая является производной (и разделяет большинство ее внутренних компонентов) с существующей коллекцией.
Так почему же дизайнеры F# предпочитают списки?
F# унаследовал некоторые связанные со списком возможности от OCaml, который унаследовал их от Standard ML и ML, потому что односвязные неизменяемые списки очень полезны в контексте их предметной области (метапрограммирование), но я бы не сказал, что разработчики F# предпочитают списки.
В чем принципиальное отличие неизменяемой среды между списком и массивом?
В F# списки обеспечивают O(1) предварительное добавление и добавление и O(n) произвольный доступ, тогда как массивы обеспечивают O(n) предварительное добавление и добавление и O(1) произвольный доступ. Массивы могут быть видоизменены, но списки не могут.
Что мне не хватает?
Базовые знания чисто функциональных структур данных. Прочитайте Окасаки.
Действительно ли списки в F# связаны между собой?
Да. В частности, односвязные неизменяемые списки. На самом деле, в некоторых ОД 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; }
}
Поэтому, когда создается новый список, он фактически создает отдельный узел со ссылкой на первый элемент предыдущего списка, а не копирует весь массив.