Как создать функцию в ML с использованием рекурсивного типа данных - PullRequest
Новая
       14

Как создать функцию в ML с использованием рекурсивного типа данных

1 голос
/ 28 сентября 2010

С учетом типов данных: 

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

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

1 Ответ

0 голосов
/ 10 октября 2010

Ваше второе определение делает структуру данных 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;

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

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

...