Comment créer une fonction ML à l'aide d'un récursive type de données

Question

Compte tenu des types de données:

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

Comment puis-je concevoir une fonction, par exemple, le retour la somme de cette fonction récursive. Je comprends comment définir une fonction récursive et légèrement comment l'utiliser, mais je ne trouve pas d'indication sur la façon dont l'ex change le type de données en ligne, ou l'une de mes autres références.

Answer 1

Votre seconde définition rend la structure de données bunchpolymorphe, c'est-à-dire qu'elle peut contenir des données de n'importe quel type. Par exemple Group (3, One 2) est un int bunch et Group ("three", One "two") est un string bunch. La valeur NIL a le type 'a bunch où 'a représente n'importe quel type (par exemple NIL a le type int bunch et le type string bunch et ...).

Votre objectif de "retourner la somme de cette fonction récursive" n'a pas de sens: vous n'avez pas de fonction récursive. Si vous vouliez dire «retourner la somme de cette structure de données inductive», vous ne savez toujours pas ce que vous voulez, vous devez être plus précis sur ce que vous entendez par somme pour une structure de données qui n'est pas une collection de nombres.

La fonction suivante calcule la somme des entiers dans un int bunch. Comme vous pouvez le voir en le tapant dans un interpréteur ML, son type est int bunch -> int, c'est-à-dire qu'il ne peut agir que sur des paquets d'entiers (sinon l'opérateur + n'aurait pas de sens).

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

La fonction suivante calcule le nombre d'éléments dans un groupe avec tout type d'élément (comme représenté par son type 'a bunch -> int). La raison pour laquelle vous pouvez définir une telle fonction polymorphe est qu'il n'a pas besoin de regarder à l'intérieur des éléments du groupe pour fonctionner: il est paramétriquement polymorphe.

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

(Dans un programme de production, ces fonctions doivent être écrites dans une moins claire, mais de manière moins gourmand en ressources, en utilisant un algorithme récursif de la queue.)

Comme le type de groupe est presque isomorphe à des listes, Vous pouvez vous inspirer de la source de la bibliothèque de listes standard de votre implémentation.