Scheme - number of occureences function

Author

number of occureences function

isaac2004

2006-04-18, 7:07 pm

how could i make a function that takes in set and counts the number of
occureences of an element to avoid redundncy. i cant figure where to
start i need to make a counter of some sort.

Pascal Bourguignon

2006-04-18, 10:02 pm

"isaac2004" <isaac_2004@yahoo.com> writes:

> how could i make a function that takes in set and counts the number of
> occureences of an element to avoid redundncy. i cant figure where to
> start i need to make a counter of some sort.

You need to read a good tutorial about scheme programming.
I'd avise you: http://www.htdp.org/2003-09-26/Book/

Jumping into the water to see if you can learn to swim can give good
results, but in your case, I've got the feeling you're drowning. So
don't be in a hurry, just learn programming step by step, reading this
"How to Design Programs" book.

--
__Pascal Bourguignon__ http://www.informatimago.com/

"I have challenged the entire quality assurance team to a Bat-Leth
contest. They will not concern us again."

isaac2004

2006-04-18, 10:03 pm

"isaac2004" <isaac_2...@yahoo.com> writes:
> how could i make a function that takes in set and counts the number of
> occureences of an element to avoid redundncy. i cant figure where to
> start i need to make a counter of some sort.

>You need to read a good tutorial about scheme programming.
>I'd avise you: http://www.htdp.org/2003-09-26/Book/

>Jumping into the water to see if you can learn to swim can give good
>results, but in your case, I've got the feeling you're drowning. So
>don't be in a hurry, just learn programming step by step, reading this
>"How to Design Programs" book.

the thing is that i can program in ada and c++ but i cant the recursion
of scheme down, any pointers could help and will read the book

Pascal Bourguignon

2006-04-18, 10:03 pm

"isaac2004" <isaac_2004@yahoo.com> writes:

> "isaac2004" <isaac_2...@yahoo.com> writes:
>
>
>
>
> the thing is that i can program in ada and c++ but i cant the recursion
> of scheme down, any pointers could help and will read the book

Ok. It's not that different, you know. You could define the cons
data type in ada or C++, and implement similar versions of these
functions.

typedef struct cons_s {
object* car;
object* cdr; } cons_t ;

typedef struct object_s {
int type;
union {
int integer;
float real;
char character;
symbol_t* symbol;
string_t* string;
cons_t* cons;
} value;
} object_t;

cons_t* cons(object_t* car,object_t* cdr){
cons_t* result=malloc(sizeof(cons_t);
result->car=car;
result->cdr=cdr;
return(result);
}

// etc

then you can write:

int count_occurences(object_t* object,object_t* list){
...
}

// and:

count_occurences(find_symbol("A"),
cons(intern("A"),
cons(intern("B"),
cons(intern("A"),
cons(intern("B"),
cons(intern("A"),intern("NIL")))))));

Now, for this question of counter, you could indeed write a loop and
increment a counter, but if you try to think at a higher level, you
may notice that:

(count-occurences 'a '()) = 0
(count-occurences 'a '(a ...)) = (+ 1 (count-occurences 'a '(...)))
(count-occurences 'a '(x ...)) = (count-occurences 'a '(...))

and this is all the cases there are.

So you can easily write count-occurences without thinking more of
counter or loop or anything low-level like that.

(define (count-occurences object list)
(cond ((null? list) 0)
((eqv? object (car list)) (+ 1 (count-occurences object (cdr list))))
(else (count-occurences object (cdr list)))))

One thing to note with this procedure, is that the first recursive
call is not a tail call (we need to call + on its result). So it will
use O(n) stack space, n being the occurence count.

You could avoid it transforming it like this:

(define (count-occurences-1 object list count)
(cond
((null? list) count)
((eqv? object (car list)) (count-occurences-1 object (cdr list) (+ 1 count)))
(else (count-occurences-1 object (cdr list) count))))

; and define a stub function to hide it:
(define (count-occurences object list)
(count-occurences-1 object list 0))

Here, all recursive calls of count-occurences-1 are tail calls so they
can be optimized and the stack usage is O(1): we have an iterative solution.

--
__Pascal Bourguignon__ http://www.informatimago.com/

"Indentation! -- I will show you how to indent when I indent your skull!"

2006-04-18, 10:03 pm

>
> the thing is that i can program in ada and c++ but i cant the recursion
> of scheme down, any pointers could help and will read the book

The first question should be: can you write this procedure if it's just
counting all of the elements in a list, without the predicate
condition? If not, start there. What should the base case be? What
should happen happen with each loop? If you don't know the answer to
these questions, guess, and we'll help you out.

Also, if you're just learning recursion, you might want to try CS3
webcasts, from Berkeley, which devote 6 classes (6 hours) to how to
think about recursion for newbies:
http://wla.berkeley.edu/main.php?course=cs3
You want classes 6 through 11.

Sponsored Links