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

Question

Я пытаюсь перевести идею, которая у меня была, из концепций ООП в концепции ФП, но я не совсем уверен, как лучше всего это сделать. Я хочу иметь несколько коллекций записей, но отдельные записи должны быть связаны между собой. В C # я, вероятно, использовал бы несколько объектов Dictionary со специфичным для Entity ID в качестве общего ключа, чтобы при любом наборе словарей метод мог извлекать конкретную Entity, используя его ID / Name.

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

Я подумал, что это, может быть, три или патриция, но мне не нужен очень глубокий поиск по имени, и у меня больше шансов получить одну или две вещи и много других. Это идея игрового дизайна, так что, например, у вас будет только один «Игрок», но может быть множество «Враг1», «Враг2» и т. Д.

Существует ли действительно хорошая структура данных для быстрого поиска по ключевым словам в FP, или мне просто придерживаться Dictionary / Hashmaps?

Answer 1

Обычной функциональной структурой данных для представления словарей, доступной в F #, является Map (как указано larsmans).Под прикрытием это реализовано в виде сбалансированного двоичного дерева, поэтому сложность поиска составляет O (log N) для дерева, содержащего N элементов.Это медленнее, чем словарь на основе хеша (который имеет O (1) для хороших ключей хеширования), но он позволяет добавлять и удалять элементы без копирования всей коллекции - необходимо изменить только часть дерева.

Из вашего описания у меня сложилось впечатление, что вы будете создавать структуру данных только один раз, а затем использовать ее в течение длительного времени без ее изменения.В этом случае вы можете реализовать простой неизменяемый тип-обертку, который использует Dictionary<_, _> под обложкой, но принимает все элементы как последовательность в конструкторе и не допускает изменений:

type ImmutableMap<'K, 'V when 'K : equality>(data:seq<'K * 'V>) =  // '
  // Store data passed in constructor in hash-based dictionary
  let dict = new System.Collections.Generic.Dictionary<_, _>()
  do for k, v in data do dict.Add(k, v)
  // Provide read-only access
  member x.Item with get(k) = dict.[k]

let f = new ImmutableMap<_,_ >( [1, "Hello"; 2, "Ahoj" ])  
let str = f.[1]

Это должно бытьбыстрее, чем использование F # Map, если вам не нужно изменять коллекцию (или, точнее, создавать копии с добавленными / удаленными элементами).

Answer 2

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

Попытки сложно программировать, и в основном они полезны в специализированных приложениях, таких как индексация поисковых систем, где они обычно используются в качестве вторичного хранилища поверх массива / базы данных / и т.д. Не используйте их, если не знаете, что вам нужно.