Q&A mapping over set elements

vet@cs.utwente.nl (Paul van der Vet)
Date: Mon, 13 Jun 94 17:03:18 +0200
From: vet@cs.utwente.nl (Paul van der Vet)
Message-id: <9406131503.AA23685@apollo.cs.utwente.nl>
To: ontolingua@HPP.Stanford.EDU
Subject: Q&A mapping over set elements

Two weeks ago, I asked for a function written in Ontolingua/KIF that
would deliver the sum of the second members of elements of a relation.
I.e., if the relation is defined extensionally as 

R =Df { < A , 0.4 > , < B , 0.4 > , < C , 0.2 > }

the function is required to deliver 1. On Monday, June 6, Tom Gruber
has proposed the function SUM-OF-RANGE-ELEMENTS as follows:

(define-function SUM-OF-RANGE-ELEMENTS (?R) :-> ?n
  := (apply + (map second-element ?R)))

with an explanation to the effect that the function works by having
Lisp treat ?R as a list, `forgetting' that it is a set rather than a
list. Although I haven't had time to check it, I'm confident that it

However, it is esthetically not very pleasing to mix up sets and lists
this way. I have tried to formalise the idea in first-order predicate
logic, but my experience in Lisp/KIF/Ontolingua is so small that I
haven't yet written the thing in Ontolingua.

I propose to define the desired function recursively. The idea can be
explained for the simple example of a set Y that consists of numbers
that can be added. (In principle, every set with elements for which
you can define something called "+" will do, but that isn't the point
here.) Then the predicate SET-SUM(X,Y) (read: X is the sum of elements
of Y) can be defined as follows:

SET-SUM(X,Y) <=> [ (Z in Y) => SET-SUM(X minus Z, Y setminus {Z}) ]

where all variables X, Y and Z are universally quantified; <=> stands
for equivalence; => stands for implication; "in" stands for "is
element of", "minus" stands for arithmetical difference; "setminus"
stands for asymmetric set difference; and "{Z}" stands for the
singleton set consisting of element Z.

Recursion "bottoms out" through a zero-point convention, here
obviously the requirement that SET-SUM is zero for the empty set.

The extension to have the sum of second elements of ordered pairs is

  [ (<V,W> in Y) => PAIR-RANGE-SUM( X minus W, Y setminus {<V,W>}) ]

with the same zero-point convention.

Paul van der Vet.

Paul van der Vet                   Phone +31 53 89 36 94 / 36 90
Knowledge-Based Systems Group      Fax   +31 53 33 96 05
Dept. of Computer Science          Email vet@cs.utwente.nl
University of Twente
P.O. Box 217
7500 AE  Enschede
The Netherlands