Постоянны ли списки F #?

Question

Я разработчик C #, плохо знакомый с F #, я понимаю, что в .net строки неизменяемы.Другими словами, каждый раз, когда вы изменяете строку, вы получаете новый экземпляр строки.

Для не функционального ума, подобного моему, первым вопросом будет эффективность, и я понимаю, что изменяемые объекты C # не являются постоянными.так как манипулирование строками обычно тривиально в большинстве приложений.

Мой вопрос такой: относится ли это также к спискам F #? Клонирует ли F # каждый список при изменении?Как, например, при фильтрации списка создать новый список с меньшим количеством элементов?

Обновление : я не сравниваю строку .net и списки.Я назвал строку как пример неизменяемого объекта и хочу узнать, предоставляет ли F # какую-либо специальную обработку для его списка.

Это то, что я имею в виду под " persistent ".

Answer 1

Я думаю Введение Дастина Кэмпбелла делает удивительную работу по объяснению неизменности списка.

В функциональном мире списки неизменны. Это означает, что совместное использование узла возможно, потому что исходные списки никогда не изменятся. Поскольку первый список заканчивается пустым списком, его узлы должны быть скопированы, чтобы указать свой последний узел на второй список. После операции добавления наши списки выглядят так:

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

Нет проблем.

Используя знание того, что списки F # являются рекурсивными, мы можем получить последняя половина комбинированного (внутренний список начинается с 4), взяв хвост, хвоста, хвоста. List.tl это функция, которая F # обеспечивает извлечение хвоста списка.

> let lastHalf = List.tl (List.tl (List.tl combined));;

val lastHalf : int list

> lastHalf;;

val it : int list = [4; 5; 6]

Наконец, поскольку F # является первоклассным гражданином .NET Framework, мы иметь полный доступ ко всем библиотекам базовых классов. Итак, мы можем использовать Object.ReferenceEquals метод для проверки, является ли lastHalf а второй действительно один и тот же экземпляр.

> System.Object.ReferenceEquals(lastHalf, second);;

val it : bool = true

И вот оно у вас. Хотите верьте, хотите нет, добавляя два неизменных списки могут быть быстрее и эффективнее, чем добавление изменяемые списки, потому что нужно копировать меньше узлов.

Answer 2

Я думаю, что рекомендации Дэна и Брайана должны прямо ответить на ваш вопрос. Если вы хотите узнать больше, вы также можете посмотреть следующие материалы (опубликованные на этой неделе на MSDN), которые были написаны для объяснения F # и функциональных концепций для разработчиков .NET:

• Учебное пособие: работа с функциональными списками представляет списки F # и показывает, как реализовать ту же концепцию в C #, что является отличным способом понять, как работают списки (и какие операции эффективны).

• Обзор: Работа с неизменяемыми данными дает дополнительную справочную информацию об неизменности в F # - он не дает прямого ответа на ваш вопрос, но может быть также полезным ресурсом.

Answer 3

F # списки неизменны.Не существует API для «модификации» списка F #, поэтому клонирование не требуется.Такие операции, как List.filter, действительно создают новый список (который может иметь некоторую структуру с оригиналом, если это возможно).

(Я думаю, именно так работают все неизменяемые объекты на любом языке.)

См., Например,

http://en.wikipedia.org/wiki/Persistent_data_structure

для хорошего описанияс фотографиями, которые показывают, как работает обмен.

Answer 4

Лучший способ понять списки на функциональных языках, чтобы понять Cons Cells

Answer 5

F # списки являются связанными списками. Поэтому, когда вы создаете новый список, он просто добавляет элемент в существующий список и указывает на заголовок, который содержит новый элемент. Исходный список по-прежнему указывает на элемент, который был заголовком на момент создания списка. Другими словами, все они указывают на один и тот же список в разных местах списка.