CODEWITHSUNDEEP
prologscheme
Student_2017
Student_2017

Reputation: 101

Counting adjacent duplicates in scheme and prolog

I am new to scheme and prolog and have done only a few basic problems. I need to write a function in scheme and prolog for counting adjacent recurrences in a list.

Example: (Count '(1, 1, 1, 2, 3, 3, 1)) gives ((3 1) (1 2) (2 3) (1 1))

I do not want the code as this is homework but any hints or how to think about this problem would be appreciated as I don't know where to start.

Upvotes: 0

Views: 146

Answers (1)

soegaard
soegaard

Reputation: 31145

Let's look at a hypothetical function loop:

(loop todo done)

that rewrites the list in todo to you wanted format and done contains the part already handled.

(loop '(1 1 1 2 3 3 1) '())
(loop   '(1 1 2 3 3 1) '((1 1))
(loop     '(1 2 3 3 1) '((1 2))
(loop       '(2 3 3 1) '((1 3))
(loop         '(3 3 1) '((2 1) (1 3))
(loop           '(3 1) '((3 1) (2 1) (1 3))
(loop             '(1) '((3 2) (2 1) (1 3))
(loop              '() '((1 1) (3 2) (2 1) (1 3))
'((1 1) (3 2) (2 1) (1 3)

Given such a function loop you can write 

(define (count xs) 
    (reverse loop xs '())

Now in order to implement loop you need to consider these cases:

1) todo is empty
2) done is empty
3) the first element of todo is different from the first element of done
3) the first element of todo is the same as the first element of done

Upvotes: 1

Related Questions