Prolog- Mappings (Associative Arrays)

5
votes

I am studying prolog and was wondering if anybody give me guidance on how to go about doing this question, It's the first of many in this area and knowing how to do this question will really help me progress. Thank-you in advance.

Using Prolog define a predicate mapof(K, M, V) such that, when invoked with K instantiated to a key, and M instantiated to a mapping, mapof will instantiate the variable V to the value (or one of the values) associated with K in mapping M. The predicate should fail if K does not appear as a key in mapping M.

2
listprolog
It is definitely not OK to destructively edit a question. Read the guidelines. - user1812457

2 Answers

4
votes

It really depends how you want to represent your "mapping". In Prolog, a table of facts is the most obvious approach. For two mappings m and n:

m(a, 1).
m(b, 2).
m(c, 3). % and so on

n(a, foo).
n(b, bar).
n(c, baz). % and so on

Then, your mapof would be something along the lines of:

mapof(K, m, V) :- m(K, V).
mapof(K, n, V) :- n(K, V).

or maybe:

mapof(K, M, V) :- call(M, K, V).

A list can be used to represent a mapping, as shown by @Yasel, but a list [a, b, c] in Prolog is a nested term like .(a, .(b, .(c, []))). You don't usually represent an associative array as a singly linked list, right?

In SWI-Prolog there is a library that is better than using a simple list for a backtrackable associative array represented as a Prolog term: library(assoc). With it, you can do:

mapof(K, M, V) :- gen_assoc(K, M, V).

This library represents the associative array as an AVL tree. You can find in the SWI-Prolog code source two more associative array implementations: one using RB-trees, and one that uses non-backtrackable RB-trees.

All three libraries mentioned here are probably more efficient than a simple list of key-value pairs [k1-v1, k2-v2...] if your associative array has more than say around 100 key-value pairs in it. This doesn't mean that using a list of pairs and doing member(Key-Value, List_of_pairs) is wrong; it is the cheapest solution for simple cases.

2
votes

Using the built-in predicate member/2 you can build your predicate mapof/3 like this:

mapof(K, M, V):- member((K,V), M).

Consult: 

?- mapof(k1, [(k, a),(k1,b),(k2,c),(k1,d)], V).
V = b ;
V = d.