CODEWITHSUNDEEP
schemefind-occurrences
HARUN SASMAZ
HARUN SASMAZ

Reputation: 609

How can I count occurence of a list in another list in Scheme

I am trying to count occurence of a list in another one but I am stuck. I don't know if there any function to do that however here is my code. It actually finds the first occurence and return to 1. How can I continue to count?

    (define *test* '(a b c a b a b a b c  b c b c a b c))

    (define match
      (lambda (pattern text) (cond ((null? pattern) 1)
                                   ((null? text) 0)
                                   ((eq? (car text) (car pattern)) 
                                      (match (cdr pattern) (cdr text)))
                                   (else (match pattern (cdr text))))
    ))

Upvotes: 0

Views: 153

Answers (1)

IFcoltransG
IFcoltransG

Reputation: 111

Your code checks positions in the list until it finds a match, and if it does, it returns that it found a match. You want to check each position in the list and add up the ones that contain the pattern, but since your code looks ahead to find the pattern, it's difficult to control which part of the list it operates on. I couldn't 'fix' the problem in your code, so I decided to write something from scratch. Hopefully it makes sense:

(define begins-with (lambda (starter-list full-list)
  (cond ((null? starter-list) #t)
        ((eq? (car starter-list) (car full-list)) (begins-with (cdr starter-list) (cdr full-list)))
        (else #f)
  )))

(define count-matches
  (lambda (pattern lst)
    (cond ((null? lst) 0)
          ((begins-with pattern lst) (+ 1 (count-matches pattern (cdr lst))))
          (else (count-matches pattern (cdr lst)))

The first function, begins-with, doesn't check the whole string for the pattern, it just checks if it "begins with" the pattern. That allows us to use the other function, count-matches, to count the number of suffixes which begin with the pattern, in other words, the number of times the pattern appears in the string.

Note that the code I wrote above will count overlapping sequences, for example '(a b a) appears twice in '(a b a b a).

Upvotes: 1

Related Questions