recursion over list of characters in scheme

Question

I have found a recursive problem in one page that says the following:

If a person enter a string with two consecutive letters that are the same, it should put a 5 between them. For example if I enter "hello"

it should print "hel5lo"

I have done the following program in Scheme:

(define (function listT)
  (if (empty? listT)
      '()
      (begin
        (if (eq? (car listT) (car (cdr listT)))
            (display 5)
            (display (car listT))
        )))
  (function (cdr listT)))

and tested with:

(function'( 'h 'e 'l 'l 'o))

and the problem I got is

car: contract violation
  expected: pair?
  given: ()

I suppose that is because at one moment (car (cdr listT)) will face an empty list, have tried with a conditional before, but still with some issues.

Is it possible to do it only using recursion over the list of characters with cdr and car? I mean not with new variables, strings, using reverse or loops?

Any help?

Thanks

Answer 1

Here is a straightforward function from a list to a list:

(define (add5s s)
    (cond ((null? s) s)
        ((null? (cdr s)) s)
        ((equal? (car s) (cadr s)) (cons (car s) (cons 5 (add5s (cdr s)))))
        (else (cons (car s) (add5s (cdr s))))
    )
)

A list either:

1. is null
2. has one element
3. begins with two equal elements
4. begins with two unequal elements

A list with a 5 put between consecutive equal elements is respectively:

1. the list
2. the list
3. the first element followed by a 5 followed by the rest of it with a 5 put between consecutive equal elements
4. the first element followed by the rest of it with a 5 put between consecutive equal elements

A Scheme string is not a list of characters or a list of symbols. If you want to input and output strings then you should use the corresponding string operators. Or write a function that defines this one, calls it with string->list of an input string and outputs list->string of this one's result list. Or a function like this one but that branches on string->list of its input string and outputs list->string of what this one returns.

(It is really not clear what code is to be written. You say "enters a string", but your "tested" code is a function that takes a list as argument, rather than reading from a port. And you say "put a 5" but you print argument list elements or a 5 via display to a port, rather than returning a value of the type of the argument. And you give an example passing an argument that is a list of quoted symbols rather than just symbols let alone characters. (If you want to pass a list of symbols then use '(h e l l o) or (list 'h 'e 'l 'l 'o).) Say exactly what is to be produced, eg, a function with what arguments, return value and effect on ports.)

Answer 2

Here's a solution including just one, top-level recursive function:

(define (insert list item)
  (if (< (length list) 2)                    ;; not enough elements to compare?
      list                                   ;; then just return the input
      (let ((first (car list))               ;; capture the first element,
            (second (cadr list))             ;; the second element,
            (rest (insert (cdr list) item))) ;; and the recursively processed tail
          (cons first                        ;; construct a list with the first element
                (if (eq? first second)       ;; compare the first two and return either
                    (cons item rest)         ;; the item before the rest
                    rest)))))                ;; or just the rest

It takes as input a list and an item to be inserted between each two consecutive identical elements. It does not display anything, but rather returns another list with the result of the insertion. For example,

(insert '(1 2 2 3 3 3 2 2 1) 0)

results in

(1 2 0 2 3 0 3 0 3 2 0 2 1)

This hopefully solves your problem and seeds further experimentation.

Answer 3

This happens when there is only one character left in the list; (cdr listT) will be the empty list '() and the car of the empty list is undefined.

So you either need to check that the cdr isn't empty, for example:

(define (f str)
  (let loop ((lst (string->list str)) (res '()))
    (if (null? lst)
        (list->string (reverse res))
        (let ((c (car lst)))
          (loop (cdr lst) 
                (cons c
                      (if (and (not (null? res)) (char=? c (car res)))
                          (cons #\5 res)
                          res)))))))

or, instead of looking one character ahead, turn around your logic and keep track of the last character, which is initialised to some value that will be different in every case (not as elegant as the first solution though IMO):

(define (f str)
  (list->string
   (let loop ((prev #f) (lst (string->list str)))
     (if (null? lst)
         '()
         (let ((c (car lst)))
           (if (equal? c prev)
               (cons #\5 (cons c (loop c (cdr lst))))
               (cons c (loop c (cdr lst)))))))))

[EDIT alternatively, with an explicit inner procedure:

(define (f str)
  (define (inner prev lst)
    (if (null? lst)
        '()
        (let ((c (car lst)))
          (if (equal? c prev)
              (cons #\5 (cons c (inner c (cdr lst))))
              (cons c (inner c (cdr lst)))))))
  (list->string (inner #f (string->list str))))

]

Testing:

> (f  "hello")
"hel5lo"
> (f "helo")
"helo"
> (f "heloo")
"helo5o"

---

Side note: don't double quote:

> '('h 'e 'l 'l 'o)
'('h 'e 'l 'l 'o)
> (car '('h 'e 'l 'l 'o))
''h

This is probably not what you expected. Instead:

> '(h e l l o)
'(h e l l o)
> (car '(h e l l o))
'h

or

> (list 'h 'e 'l 'l 'o)
'(h e l l o)
> (car (list 'h 'e 'l 'l 'o))
'h

---

Also note that these are symbols, whereas, since you start from a string, you want characters:

> (string->list "hello")
'(#\h #\e #\l #\l #\o)

---

EDIT 2

I see you are still struggling with my answer. Here's a solution that should be as minimal as you requested, I hope this is it:

(define (f lst (prev #f))
  (unless (null? lst)
    (when (equal? (car lst) prev) (display "5"))
    (display (car lst))
    (f (cdr lst) (car lst))))

or even

(define (f lst)
  (unless (null? lst)
    (display (car lst))
    (when (and (not (null? (cdr lst))) (equal? (car lst) (cadr lst)))
      (display "5"))
    (f (cdr lst))))

Testing:

> (f '(h e l l o))
hel5lo
> (f '(h e l o))
helo
> (f '(h e l o o))
helo5o

Answer 4

I have found a solution:

(define (func lisT)
  (if (empty? (cdr lisT))
      (display (car lisT))
      (begin
        (if (eq? (car lisT) (car (cdr lisT)))
            (begin
              (display (car lisT))
              (display 5)
             )
            (display (car lisT))
        )
        (func (cdr lisT))
        )
  ))