Индуктивный тип данных - это просто тот, который определяется в терминах самого себя. Простым примером будет список, который мы можем определить как:
type List<'a> =
| Empty
| List of 'a * List<'a>
Итак, список либо пуст, либо имеет головной узел и хвост, который сам по себе является списком. Это позволяет нам определить список очень простым способом, не имея других встроенных структур данных (кроме типа кортежа, но мы могли бы сделать это без этого, это просто упрощает пример).
Затем мы можем создать простую функцию для добавления в список, например:
let add item = function
| Empty -> List (item, Empty)
| List (head, tail) -> List (item, (List (head, tail)))
Принимает элемент и список в качестве входных данных и возвращает новый список. Если входной список пуст, он возвращает список с элементом в качестве заголовка и пустой список в качестве хвоста. Если список не пустой, он возвращает новый список с элементом в качестве заголовка и исходным списком в качестве хвоста.
Мы можем использовать эту функцию для создания списка любого типа. Для целых чисел это будет выглядеть примерно так:
Empty
|> add 1
|> add 2
|> add 3
Где |> - оператор, который принимает предыдущее значение и передает его в качестве последнего параметра следующей функции. Это дает нам список:
List<int> = List (3,List (2,List (1,Empty)))
Что касается случаев, когда их не следует использовать, то существуют некоторые сценарии, в которых рекурсивно определенная структура данных может повлечь за собой снижение производительности или памяти по сравнению, например, с массивом изменяемого состояния. Часто это происходит из-за того, что базовая реализация системы основана на структурах, которые более точно отражаются массивами. Однако в зависимости от варианта использования поддержание массива изменяемого состояния может повлечь за собой другие штрафы, такие как управление блокировками в параллельном приложении. Если вы заинтересованы в более подробном анализе, я настоятельно рекомендую книгу Чисто функциональные структуры данных .