re: Q&A on relations as sets, quotation, mapping over set elements (Tom Gruber)
Date: Mon, 6 Jun 94 20:15:37 PDT
From: (Tom Gruber)
Message-id: <9406070315.AA01640@hpp-ssc-1.Stanford.EDU.ksl>
To: ontolingua@HPP.Stanford.EDU
Subject: re: Q&A on relations as sets, quotation, mapping over set elements
Reply-To: gruber@HPP.Stanford.EDU
In-reply-to: <199406022159.OAA28025@HPP.Stanford.EDU>

A colleague pointed out a bug in one of the definitions I proposed in an
earlier message <199406022159.OAA28025@HPP.Stanford.EDU>.

I claimed this:

> So if you want to count up the fractions in the second element of each
> tuple in a binary relation R,

> (define-function range-cardinality (?R) :-> ?n
>   := (apply + (all-instances (exact-range ?R))))

First, this is a misleading name for the function.  It should be called
something like sum-of-range-elements.  The cardinality of a range would be the
number of range elements.
Second, it doesn't mean what the text says it means.

> Here's the problem:
> This works if exact-range isn't a set but a list. The documentation
> says it is a set. So if it is and the relation to which it is applied
> is something like:
> { < A , 0.4 >, < B , 0.4 >, < C , 0.2 > }
> then range-cardinality delivers 0.6 rather than 1 because the second
> 0.4 is thrown out. 

Right.  APPLY wants a list as a second argument, and ALL-INSTANCES returns a
set.  EXACT-RANGE returns a list of singleton tuples (i.e., a unary relation).
The correct function would be 

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

which is the way one would do it in Lisp, treating the ?R argument as a list
of tuples and forgetting that it is meant as a binary relation (there's a
deeper issue exposed here, which I'll leave to the reader to ponder).

For context, here are the definitions of the supporting functions.

>From my original message:

(define-function SECOND-ELEMENT (?list)
  := (first (rest ?list)))

>From the KIF-relations ontology:

(define-function MAP (?f ?list)
  := (if (null ?list)
         (cons (value ?f (first ?list))
               (map ?f (rest ?list)))))

(define-function APPLY (?f ?list)
  := (if (and (function ?f) (= ?list (listof @args)))
              (value ?f @args)))

>From the kif-lists ontology:

(define-function FIRST (?list)
  := (if (exists @items 
            (= (listof ?x @items) ?list)) ?x))

(define-function REST (?list) :-> ?rest-list
  :iff-def (or (and (null ?list)
                    (= ?rest-list ?list))
               (exists (?x @items)
                 (and (= ?list (listof ?x @items))
                      (= ?rest-list (listof @items))))))