J'écris une fonction OCAML où j'ai besoin de fusionner deux cartes. Je n'ai pas pu comprendre la sémantique de la fonction fourni par le fonctionnement En outre, les deux cartes que je dois fusionner ont des propriétés intéressantes: les clés ont le même type ( map.make (trouvé dans la version 3.12.0 de OCAML). Quelqu'un pourrait-il me fournir une explication plus détaillée que le manuel OCAML? Un exemple suffisait probablement pour moi de le comprendre.
int , en fait) et leur domaine est disjoint. Y aurait-il une approche plus efficace que la routine de fusion?
3 Réponses :
Exemple: P> fusion code> prend une fonction et deux cartes. Pour chaque clé présente dans l'une ou l'autre carte, la fonction sera appelée. Si la clé n'est présente que dans l'une des cartes, la valeur de l'autre sera transmise comme aucune (c'est pourquoi les arguments sont des options). Si les fonctions renvoient certains x code>, la nouvelle carte aura la valeur x code> pour la clé en question. Sinon, la clé ne sera pas présente. let map3 = merge (fun k xo yo -> match xo,yo with
| Some x, Some y -> Some (x+y)
| None, yo -> yo
| xo, None -> xo
) map1 map2;;
Juste quelques éclaircissements que je pensais être utile dans la définition de fusion: fusion itérera f à toutes les touches de M1 ou M2, mais ne gardera que celles pour lesquelles le retour la valeur n'est pas aucune.
basé sur la première réponse et compte tenu de la question supplémentaire (fusions de fusion dans le cas des domaines disjoints), je proposerais ensuite la routine de fusion générique suivante:
let merge_disjoint m1 m2 =
IntMap.merge
(fun k x0 y0 ->
match x0, y0 with
None, None -> None
| None, Some v | Some v, None -> Some v
| _, _ -> invalid_arg "merge_disjoint: maps are not disjoint")
m1 m2
Ce serait une bonne map.Union fonction. Pour moi, l'idée de fusionner des cartes permet d'appliquer une fonction non seulement dans le cas de clés identiques, mais même avec des clés dans une carte. Par exemple, peut-être que l'on voudrait carte.merge (amusant _ x y -> (x, y))
Étant donné que vos cartes sont disjointes, vous pouvez simplement utiliser la carte plus petite et insérer dans le plus grand: dans le cas où vous utilisez une version plus ancienne d'OCAML qui ne fait pas Inclure la fonction qui itière essentiellement à travers tous les éléments une carte et appelle une fonction qui prend une clé, une valeur et une autre variable de type Edit: Vous ferez mieux de faire: P> cardinal code> Vous pouvez simplement choisir une carte pour toujours parcourir. Quant à ce que le code ci-dessus est utilisé, est-il utilisé: p> 'B code> et renvoie quelque chose de ce type (' B code>). Dans notre cas, nous passons la fonction intmap.add code> et cette autre variable est notre deuxième carte. Donc, il comporte à travers tous les éléments et les ajoute à l'autre carte. P> let disjoint_merge = IntMap.fold IntMap.add;;
Lorsque le type de clé est
int et que vous êtes intéressé par la fusion (disjoint ou non) des cartes, il convient de vérifier si les cartes représentées comme des arbres de Patricia sont adaptées à vos besoins. Voici une implémentation: Lri.fr/~filliatr/ftp /ocaml/ds/ptmap.ml.htmlAu fait, si l'une des réponses a résolu votre problème, vous devez le marquer comme accepté.