Как создать функцию в ML используя Рекурсивный Тип данных

Question

Учитывая типы данных:

datatype bunch = One of int 
       | Group of bunch list; 
datatype 'ex bunch = NIL 
        | One of 'ex 
        | Group of 'ex * 'ex bunch; 

Как я могу создать функцию, например, вернуть сумму этого рекурсивной функции. Я понимаю, как определить рекурсивную функцию и немного ее использовать, но я не могу найти указание на то, как «ex» меняет тип данных в Интернете или какие-либо другие ссылки.

Answer 1

Ваше второе определение делает структуру данных bunchполиморфной, то есть может содержать данные любого типа. Например, Group (3, One 2) является int bunch, а Group ("three", One "two") является string bunch. Значение NIL имеет тип 'a bunch, где 'a обозначает любой тип (т. Е. NIL имеет тип int bunch и тип string bunch и ...).

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

Следующая функция вычисляет сумму целых чисел в int bunch. Как вы можете видеть, введя его в интерпретатор ML, его тип равен int bunch -> int, то есть он может действовать только на пучки целых чисел (в противном случае оператор + не имеет смысла).

fun bunch_sum NIL = 0 
    | bunch_sum (One x) = x 
    | bunch_sum (Group (x, b)) = x + bunch_sum b; 

Следующая функция вычисляет количество элементов в связке с любым типом элемента (как показано по его типу 'a bunch -> int). Причина, по которой вы можете определить такую ​​полиморфную функцию, заключается в том, что ей не нужно заглядывать внутрь элементов сгустка: параметрически полиморфный.

fun bunch_count NIL = 0 
    | bunch_count (One x) = 1 
    | bunch_count (Group (x, b)) = 1 + bunch_count b; 

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

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