Recursion on nested list in Scheme

Question

Can someone show my the error in this code please? I haven't been familiar with recursion so that I don't really understand whats wrong with the code below.

(define (counting lst)  
    (if (null? lst)
        '()
        (string-append (number->string (car (car lst))) 
                       ", " 
                       (number->string (length (cdr (car lst)))) 
                       (counting (cdr lst)))))

Input: '((2 b a) (1 f e c) (0 m))

output expected from the code: "2, 2\n1, 3\n0, 1\n"

Actual output from the code above:

string-append: contract violation
  expected: string?
  given: '()
  argument position: 4th
  other arguments...:
   "0"
   ", "
   "1"

As I understand,

Base case: if length of the list nested = 0, or null, it is '()

Inductive case: append the first number in the list nested with "," and the length of the rest of the list nested.

Is my idea correct? If not, where I'm wrong ?? Thank in advance!

Thank you for mentioning the expected output, but what was the actual output? Presumably you got some kind of error since you were calling string-append with an empty list as an argument? The error message that got, when copied into your question, will help future users with the same problem find the solution. — Joshua Taylor
– Joshua Taylor, Commented Nov 7, 2013 at 2:50

Scott Hunter · Accepted Answer · 2013-11-06 17:05:42Z

2

For one thing, the result should be a string; in your base base, it is not.

For another, you never add the newline character.

answered Nov 6, 2013 at 17:05

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

uselpa · Accepted Answer · 2013-11-06 18:18:37Z

1

Your base case should return "", not '(), since it is used in a recursive call with string-append:

(define (counting lst)  
  (if (null? lst)
      "" ; <===
      (string-append (number->string (car (car lst))) 
                     ", " 
                     (number->string (length (cdr (car lst)))) 
                     "\n" ; <===
                     (counting (cdr lst)))))

such as

(counting '((2 b a) (1 f e c) (0 m)))
=> "2, 2\n1, 3\n0, 1\n"

EDIT

A more elegant solution would be to use the built-in functions string-join, map and format:

(define (counting lst)
  (string-join 
   (map (lambda (s) (format "~a, ~a" (car s) (length (cdr s)))) lst)
   "\n"))

edited Nov 6, 2013 at 18:18

answered Nov 6, 2013 at 17:06

uselpa

19k2 gold badges36 silver badges53 bronze badges

3 Comments

Trung Bún Over a year ago

yes, I forgot the newline character :) but basically now i understand the recursion in list!!!! Thank you!!!

uselpa Over a year ago

If recursion if OK for you now, have a look at the alternative solution I have added, it's very useful to know the standard procedures which help you avoid programming your own loops.

Trung Bún Over a year ago

Cheers, i have done this by using the map procedure, but my previous solution doesnt print out a string, which i want the output is a string. But string join seem to be very nice :)

Collectives™ on Stack Overflow

Recursion on nested list in Scheme

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related