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
works.
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
easy:
PAIR-RANGE-SUM(X,Y) <=>
[ (<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
---------------------------------------------------------------------