College Work - Scheme

2
votes

So I am going through some past papers for my Programming Languages module and I came across this question and I have no idea how to go about it.

Q: "Define a Scheme function reverse-with-count which takes two lists, the second of which is a list of non-negative integers the same length as the first list, and returns a list of elements from the first list, in reverse order, each repeated a number of times as specified by the corresponding element of the second list."

Examples:

(reverse-with-count '(a b c) '(1 2 3)) => (c c c b b a)
(reverse-with-count '(d c b a) '(3 0 0 1)) => (a d d d)

Thanks :)

Edit:

(define (repeat n s)
  (if (= n 0)
      '()
      (append s
              (repeat (- n 1) s))))

Using:

 (repeat 10 '(test)) => '(test test test test test test test test test test)
3
schemeracket
Can you write a function which takes a symbol S, a number N a produce a list with N times the S element? Please provide at least an attempt. - coredump
@coredump see above.. - Manus Gallagher
With cons instead of append, you can call the function with (repeat 10 'test). Also, be careful about possible negative n in inputs, you should probably use <= instead of =. But this is great. Now, What if you called (map repeat numbers symbols), where numbers and symbols are your lists of numbers and symbols? You would obtain a list of lists. Next, reverse that list, and concatenate all its elements with a (foldr append () ...). - coredump

3 Answers

2
votes

I think this should work:

(define (multi-element element n)
  (map (lambda (x) element) (range n)))

(define (range-list xs ys)
  (map (lambda (x y) (multi-element x y)) xs ys))

(define (reverse-with-count xs ys)
  (reverse (flatten (range-list xs ys))))

Output:

> (reverse-with-count '(a b c) '(1 2 3))
(c c c b b a)
> (reverse-with-count '(d c b a) '(3 0 0 1))
(a d d d)
> (reverse-with-count '(x baz y z bar g t foo) '(0 1 0 0 1 0 0 1))
(foo bar baz)
0
votes

An accumulator-based approach is efficient here:

(define (repeat n s (result '()))
  (if (positive? n)
      (repeat (- n 1) s (cons s result))
      result))

used with or without an initial value result:

> (repeat 10 'a)
'(a a a a a a a a a a)
> (repeat 10 'a '(initial))
'(a a a a a a a a a a initial)

then the second procedure in the same manner:

(define (reverse-with-count elts cnts (result '()))
  (if (or (null? elts) (null? cnts))
      result
      (reverse-with-count (cdr elts)
                          (cdr cnts)
                          (repeat (car cnts) (car elts) result))))

testing:

> (reverse-with-count '(a b c) '(1 2 3)) 
'(c c c b b a)
> (reverse-with-count '(a b c) '(1 2 3))
'(c c c b b a)
> (reverse-with-count '(d c b a) '(3 0 0 1))
'(a d d d)
> (reverse-with-count '(x baz y z bar g t foo) '(0 1 0 0 1 0 0 1))
'(foo bar baz)
0
votes

Following version uses for/list twice to create a list of lists, which is then flattened and reversed: 

(define (f l k)
  (reverse
   (flatten
    (for/list ((i k)(n (length k)))
      (for/list ((x i))
        (list-ref l n))))))

One can also use general and highly flexible 'named let' method for looping. Reversing is not needed as 'cons' produces a reversed list:

(define (f1 l k)
  (let loop ((ol '())
             (l l)
             (k k))
    (if (null? l) 
        (flatten ol)
        (loop (cons
               (for/list ((i (first k)))
                 (first l))
               ol)
              (rest l)
              (rest k)))))