CODEWITHSUNDEEP
schemeracket
ads27
ads27

Reputation: 71

scheme string-append? recursion to replicate a string

Design a program called string-dup that consumes a String s and a Number n and returns a String that is the concatenation of s n times with spaces between each instance of s, i.e.,

(string-dup "a" 3) => "a a a" Without using replicate but i guess we can use string-append.

So far i got

(define (string-dup s n)
(cond 
  [(zero? n) ""]
  [else
   (cond
     [(= n 1 ) s]
     [(> n 1 )(string-dup (string-append s " ") (sub1 n))])]))

However, this only allows me to have one string "a". I know when in the list case you can do

(cons s (string-cp s (sub1 n)))

but how to apply in this case? Thanks.

Upvotes: 2

Views: 2711

Answers (2)

ben rudgers
ben rudgers

Reputation: 3669

When performance matters (e.g. n is large), working with lists of characters directly may increase speed significantly. The function faster-string-dup below:

  • Lines 1-5 perform basic conditional branching as in the accepted answer.

  • Line 6 begins a closure over two local values in the else clause.

  • Lines 7-8 define s1 which is string converted to a list of characters appended to a list containing a single character, #\space.

  • Lines 9-14 define a tail recursive function next. It takes two parameters: an integer n and a list of characters acc and returns a list of characters.

  • Line 15 is the trampoline for the else clause. It:

    1. Begins the recursive call on the list of characters.
    2. Converts the list of characters returned by the recursive call back to a string.
    3. Appends the original string. This allows s1 to end with a space rather than begin with one. This is more consistent with our intuitive understanding of the problem - that we add the string and a space for each duplication.
1:  (define (faster-string-dup s n)

2:   (cond

3:     [(< n 1) ""]

4:     [(= n 1) s]

5:     [else

6:      (letrec

7:          ((s1 (append (string->list s)   

8:                       (list #\space)))

9:           (next (lambda (n acc)

10:                  (if (> n 2)

11:

12:                  (next (sub1 n)

13:                            (append s1 acc))

14:                      acc))))

15:         (string-append (list->string (next n s1)) s))]))

Time comparisons using Racket 6.1 from the command line where:

  • string-dup is the accepted answer

  • duplications is 10,000

  • dump is just some mutable variable that prevents lots of screen printing.

Show significantly faster execution compared with the accepted answer.

-->(time (set! dump (string-dup "string" duplications)))
cpu time: 1125 real time: 1129 gc time: 262
-->(time (set! dump (faster-string-dup "string" duplications)))
cpu time: 3 real time: 2 gc time: 0

The power that Scheme and other Lisps provide by facilitating higher level programming sometimes obscures the fact that Lisps were originally replacements for machine code and can be tuned to run closer to the metal.

Upvotes: 1

uselpa
uselpa

Reputation: 18917

The recursive call to string-dup needs to be a parameter to string-append, not the other way round. Here's a corrected (and refactored) version:

(define (string-dup s n)
  (cond 
    [(< n 1) ""]
    [(= n 1) s]
    [else    (string-append s " " (string-dup s (sub1 n)))]))

Upvotes: 2

Related Questions