Quantifiers

Hi everyone

I'm trying to write a very simple module with a handful of quantifiers and
similar set-theoretic constructs, and I'm trying to figure out how one can
do this best with Objective-C.

Functional languages make this very easy. For example, with Q, you can
write...

> any (<0) [5,6,9,-3]
true

> all (<>-3) [5,6,9,-3]
false

The predicate(s) ("<0", "<>-3") are nicely applied to each of the members,
and as the quantifiers are [most probably] defined with a "reduce"
function
as...

any 	= reduce (or) false;
all 	= reduce (and) true;

...you get the result with very elegant code.

(NB: "Elegant" stands NOT for "fa****onably smart-dressed" but for
"ingenuously simple and effective." <End of insulting fellow coders'
intellect.>)

However, the tricky parts here are

- the curried syntax of the predicate(s);
- the type-generality of their application domain

...neither of which are sup****ted by Objective-C. (Ok, maybe "id" can be
used for the second but that's not a type derived from say a protocol like
-- to use a Java/Eiffel analogy -- "Comparable"; it's probably a "(void
*)"
or something. <End of Objective-C-ignorant remark.>)

I'm a novice to Objective-C, so I first tried this with integers as
follows.

I used a function pointer called "Predicate" to define the simple
relations of equal, less than, greater than, etc.

// "Predicate.h"

typedef BOOL (*Predicate)(int lhs, int rhs);

BOOL eq (int lhs, int rhs)  { return (lhs == rhs); }
BOOL lt (int lhs, int rhs)  { return (lhs <  rhs); }
BOOL gt (int lhs, int rhs)  { return (lhs >  rhs); }
BOOL le (int lhs, int rhs)  { return (lhs <= rhs); }
BOOL ge (int lhs, int rhs)  { return (lhs >= rhs); }
BOOL ne (int lhs, int rhs)  { return (lhs != rhs); }


// These macros are only for convenience, to save the
// client from having to use the address-of op '&'.

#define equalTo             &eq
#define lessThan            &lt
#define greaterThan         &gt
#define lessThanEqualTo     &le
#define greaterThanEqualTo  &ge
#define notEqualTo          &ne


Then I used a category named "Quantifying" on the NSSet type (since I
expect these to be used primarily on sets) (the implementations are just
the first trials and some are naive in algorithm):

// "Quantifying.h"

#im****t <Foundation/Foundation.h>
#im****t "Predicate.h"

@[EMAIL PROTECTED]
 NSSet (Quantifying);
-(BOOL) any: (Predicate) pred : (int) rhs;
-(BOOL) all: (Predicate) pred : (int) rhs;
-(BOOL) none: (Predicate) pred : (int) rhs;
-(BOOL) most: (Predicate) pred : (int) rhs;
-(BOOL) few: (Predicate) pred : (int) rhs;
@[EMAIL PROTECTED]
 NSSet (Quantifying);

// Could be implemented with binary search to speed up
-(BOOL) any: (Predicate) pred : (int) rhs
{
    int i = [self count]-1;
    NSEnumerator *ns = [self objectEnumerator];

    while ((i >= 0) && ! pred([[ns nextObject] intValue], rhs))
        i--;

    return (i > 0);
}

-(BOOL) all: (Predicate) pred : (int) rhs
{
    int i = [self count]-1;
    NSEnumerator *ns = [self objectEnumerator];

    while ((i >= 0) && pred([[ns nextObject] intValue], rhs))
        i--;

    return (i < 0);
}

-(BOOL) none: (Predicate) pred : (int) rhs
{
    int i = [self count]-1;
    NSEnumerator *ns = [self objectEnumerator];

    while ((i >= 0) && ! pred([[ns nextObject] intValue], rhs))
        i--;

    return (i < 0);
}

// Could exit once it determines 1 item more than half
// of the set fulfills the predicate
-(BOOL) most: (Predicate) pred : (int) rhs
{
    int i = [self count]-1;
    int q = i/2, r = i%2, e = 0;

    NSEnumerator *ns = [self objectEnumerator];

    while (i >= 0) {
        if (! pred([[ns nextObject] intValue], rhs))
            e++;
        i--;
    }

    return (e < q+r);
}

// Likewise, could exit once it determines more than
// half of the items fail to fulfill the predicate
-(BOOL) few: (Predicate) pred : (int) rhs
{
    int i = [self count]-1;
    int q = i/2, r = i%2, e = 0;

    NSEnumerator *ns = [self objectEnumerator];

    while (i >= 0) {
        if (! pred([[ns nextObject] intValue], rhs))
            e++;
        i--;
    }

    return (e > q+r);
}

@[EMAIL PROTECTED]
 may ask "what exactly are the 'none', 'most', and 'few' dudes doing
there?" but never mind that. They are just for convenience -- I can
imagine problems where they could come in handy (with which you're free to
disagree, but that's a different topic :)).

And then a very simple workout:

// "main.m"

#im****t <Foundation/Foundation.h>
#im****t "Quantifying.h"

#define _I(v)   [NSNumber numberWithInt: v]


int main(int argc, char *argv[])
{
    NSAutoreleasePool *pool = [NSAutoreleasePool new];
    NSSet *ns = [NSSet setWithObjects: _I(5), _I(6), _I(9), _I(-3), nil];

    printf("ns = { 5, 6, 9, -3 } :\n" \
        "  any  <   0 = %c\n" \
        "  all  != -3 = %c\n" \
        "  none == -4 = %c\n" \
        "  most >   0 = %c\n" \
        "  few  >=  9 = %c\n\n",
        [ns any:  lessThan            :  0] ? 'Y' : 'N',
        [ns all:  notEqualTo          : -3] ? 'Y' : 'N',
        [ns none: equalTo             : -4] ? 'Y' : 'N',
        [ns most: greaterThan         :  0] ? 'Y' : 'N',
        [ns few:  greaterThanEqualTo  :  9] ? 'Y' : 'N'
        );

    [pool release];

    return 0;
}


(NB: This was compiled on a Windows MinGW environment using the GNUstep
implementation of the Foundation cl*****.)

Here's the output (the compile file is "qntf"):

$ qntf
ns = { 5, 6, 9, -3 } :
  any  <   0 = Y
  all  != -3 = N
  none == -4 = Y
  most >   0 = Y
  few  >=  9 = Y

--

Now, my question(s):

- Do you know a more concise and/or elegant way of doing this?
- How would you code this so that I could send not only integers but any
kind of data (chars, strings, complex numbers) to it?

When you're replying, please make sure you...

- do NOT provide the full text of the solution you suggest (I'd like to
solve this myself);
- do NOT reply with "you dufus, module/type X of library A already
provides this";
- if possible, rather than suggesting something yourself, direct me to a
resource that may inspire that idea;
- preferably only discuss, or hint at, the characteristic principles of
Objective-C coding that I should ponder on when I'm trying to find the
solution.

Thanks for reading this long-winded message (my server doesn't allow me to
attach files, so I had to include the code in the message), and thanks in
advance for your reply.


Cheers
-- K


--
Message posted using
http://www.talkaboutprogramming.com/group/comp.lang.objective-c/
More information at http://www.talkaboutprogramming.com/faq.html