Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Count occurrence of element in a list in Scheme?

Tags:

scheme

This is extremely easy if I can use an array in imperative language or map (tree-structure) in C++ for example. In scheme, I have no idea how to start this idea? Can anyone help me on this?

Thanks,

like image 745
Chan Avatar asked Apr 21 '11 06:04

Chan


People also ask

How do you count occurrences of an item in a list?

Using the count() Function The "standard" way (no external libraries) to get the count of word occurrences in a list is by using the list object's count() function. The count() method is a built-in function that takes an element as its only argument and returns the number of times that element appears in the list.

How do you count occurrences of an item in a list Python?

The easiest way to count the number of occurrences in a Python list of a given item is to use the Python . count() method. The method is applied to a given list and takes a single argument. The argument passed into the method is counted and the number of occurrences of that item in the list is returned.

How can I count the occurrences of a list item C#?

Use the list. count() method of the built-in list class to get the number of occurrences of an item in the given list.

How do I count multiple elements in a list Python?

If you want to count multiple items in a list, you can call count() in a loop. This approach, however, requires a separate pass over the list for every count() call; which can be catastrophic for performance. Use couter() method from class collections , instead.


2 Answers

Your question wasn't very specific about what's being counted. I will presume you want to create some sort of frequency table of the elements. There are several ways to go about this. (If you're using Racket, scroll down to the bottom for my preferred solution.)

Portable, pure-functional, but verbose and slow

This approach uses an association list (alist) to hold the elements and their counts. For each item in the incoming list, it looks up the item in the alist, and increments the value of it exists, or initialises it to 1 if it doesn't.

(define (bagify lst)
  (define (exclude alist key)
    (fold (lambda (ass result)
            (if (equal? (car ass) key)
                result
                (cons ass result)))
          '() alist))
  (fold (lambda (key bag)
          (cond ((assoc key bag)
                 => (lambda (old)
                      (let ((new (cons key (+ (cdr old) 1))))
                        (cons new (exclude bag key)))))
                (else (let ((new (cons key 1)))
                        (cons new bag)))))
        '() lst))

The incrementing is the interesting part. In order to be pure-functional, we can't actually change any element of the alist, but instead have to exclude the association being changed, then add that association (with the new value) to the result. For example, if you had the following alist:

((foo . 1) (bar . 2) (baz . 2))

and wanted to add 1 to baz's value, you create a new alist that excludes baz:

((foo . 1) (bar . 2))

then add baz's new value back on:

((baz . 3) (foo . 1) (bar . 2))

The second step is what the exclude function does, and is probably the most complicated part of the function.

Portable, succinct, fast, but non-functional

A much more straightforward way is to use a hash table (from SRFI 69), then update it piecemeal for each element of the list. Since we're updating the hash table directly, it's not pure-functional.

(define (bagify lst)
  (let ((ht (make-hash-table)))
    (define (process key)
      (hash-table-update/default! ht key (lambda (x) (+ x 1)) 0))
    (for-each process lst)
    (hash-table->alist ht)))

Pure-functional, succinct, fast, but non-portable

This approach uses Racket-specific hash tables (which are different from SRFI 69's ones), which do support a pure-functional workflow. As another benefit, this version is also the most succinct of the three.

(define (bagify lst)
  (foldl (lambda (key ht)
           (hash-update ht key add1 0))
         #hash() lst))

You can even use a for comprehension for this:

(define (bagify lst)
  (for/fold ((ht #hash()))
            ((key (in-list lst)))
    (hash-update ht key add1 0)))

This is more a sign of the shortcomings of the portable SRFI 69 hashing library, than any particular failing of Scheme for doing pure-functional tasks. With the right library, this task can be implemented easily and functionally.

like image 99
Chris Jester-Young Avatar answered Sep 28 '22 05:09

Chris Jester-Young


In Racket, you could do

(count even? '(1 2 3 4))

But more seriously, doing this with lists in Scheme is much easier that what you mention. A list is either empty, or a pair holding the first item and the rest. Follow that definition in code and you'll get it to "write itself out".

Here's a hint for a start, based on HtDP (which is a good book to go through to learn about these things). Start with just the function "header" -- it should receive a predicate and a list:

(define (count what list)
  ...)

Add the types for the inputs -- what is some value, and list is a list of stuff:

;; count : Any List -> Int
(define (count what list)
  ...)

Now, given the type of list, and the definition of list as either an empty list or a pair of two things, we need to check which kind of list it is:

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ...]))

The first case should be obvious: how many what items are in the empty list?

For the second case, you know that it's a non-empty list, therefore you have two pieces of information: its head (which you get using first or car) and its tail (which you get with rest or cdr):

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ... (first list) ...
              ... (rest list) ...]))

All you need now is to figure out how to combine these two pieces of information to get the code. One last bit of information that makes it very straightforward is: since the tail of a (non-empty) list is itself a list, then you can use count to count stuff in it. Therefore, you can further conclude that you should use (count what (rest list)) in there.

like image 27
Eli Barzilay Avatar answered Sep 28 '22 05:09

Eli Barzilay