Next: Group Up: Programming Concepts Previous: Sum Contents Index

Subsections

Merge

Description

The merge concept is used when we want to match corresponding entries in two lists. We sort both lists on the same key, and then scan them in parallel, always discarding the entry with the smallest key first.

We can use this concept to combine information from the two lists, to find differences between lists quickly, or to lookup information from the second list for all elements of the first list.

Parameters

L: a list
K: a list

Schema

:-mode merge(+,+).
merge(L,K):-
        sort_on_key(L,L1),
        sort_on_key(K,K1),
        merge_lp(L1,K1).

merge_lp([],_):-
        !.
merge_lp([_|_],[]):-
        !.
merge_lp([A|A1],[B|B1]):-
        merge_compare(A,B,Op),
        merge_cont(Op,A,A1,B,B1).

merge_cont(<,A,A1,B,B1):-
        merge_lp(A1,[B|B1]).
merge_cont(=,A,A1,B,B1):-
        merge_op(A,B),
        merge_lp(A1,[B|B1]).
merge_cont(>,A,A1,B,B1):-
        merge_lp([A|A1],B1).

Comments

The cuts in merge_lp are used to remove choicepoints left by the compiler^5.1.

The schema looks quite complex, but its performance is nearly always significantly better than a simple lookup in the second list.

Example

The example takes data from two different sources and merges it. The first argument is a list of interface_topology terms, the second a list of ndi_interface structures. For matching Node-Interface pairs, we copy information from the first structure into the second. If the Node-Interface pairs do not match, then we don't do anything.

Also note the use of compare/3 to obtain a lexicographical ordering of Node-Interface pairs.

:-mode insert_topology(+,+).
insert_topology([],_):-
        !.
insert_topology([_|_],[]):-
        !.
insert_topology([A|A1],[B|B1]):-
        compare_index_interface(A,B,Op),
        insert_topology_op(Op,A,B,A1,B1).

compare_index_interface(interface_topology(_,Router1,
                                           Index1,_,_),
                  ndi_interface with [router:Router2,
                                      index:Index2],Op):-
        compare(Op,Router1-Index1,Router2-Index2).

insert_topology_op(<,A,B,A1,B1):-
        insert_topology(A1,[B|B1]).
insert_topology_op(=,A,B,A1,B1):-
        insert_one_topology(A,B),
        insert_topology(A1,B1).
insert_topology_op(>,A,_B,A1,B1):-
        insert_topology([A|A1],B1).

insert_one_topology(interface_topology(_,_,_,Ip,Mask),
                    ndi_interface with [ip_address:Ip,
                                    subnet_mask:Mask,
                                    subnet:Subnet]):-
        subnet(Ip,Mask,Subnet).

Next: Group Up: Programming Concepts Previous: Sum Contents Index

Warwick Harvey
2004-08-07