CODEWITHSUNDEEP
schemeracket
nwelch
nwelch

Reputation: 89

Scheme - Return list of N Repetitions of said list

First off, this is a homework question so just looking for guidance and not an answer.

Write a function named (cycle ALIST N) that accepts a list of elements ALIST and an integer N. This function returns a list containing N repetitions of the elements of ALIST. If N is non-positive, this function returns the empty list.

I will be honest in that I'm not sure how to begin solving this problem. I've been thinking of writing a helper function then using cons calling this n times but just looking if I'm on the correct track here.

Upvotes: 0

Views: 464

Answers (2)

Sylwester
Sylwester

Reputation: 48745

You have different strategies you can make. The simplest is probably not the most effiecent but the one that produces less code: 

(require srfi/26) ; cut
(define (cycle lst n)
  (define dup-lst (map (cut make-list n <>) lst)) 
  (foldr append '() dup-lst))

So what this does is that the map creates a list of lists where each is n elements of each. The foldr flattens it by using append.

With more hands on you can make it more efficient. I'm thinking roll your own recursion consing the elements from end to beginning in an accumulator:

(define (cycle lst n)
  (let helper ((lst (reverse lst)) (c n) (acc '()))
    (cond ((null? lst) acc)
          ((<= c 0) (helper ...))
          (else (helper ...)))))

I've left out the recursive parts. What this does is a base case on the empty list, a reset recur with a c reset to n and the cdr when c is zero and the default case keeping lst while reducing c and cons-ing the first element of lst to acc. This is a O(n) solution.

Upvotes: 0

law-of-fives
law-of-fives

Reputation: 643

One of the more common ways to tackle recursive problems is to begin thinking about it at the end. In other words, under what conditions should you stop? —When are you done? If you can write this base case down, then you only need to ask, what do I do when I am one step away from stopping? This is the recursive step, and for relatively simple recursive problems you are done as the whole problem is either "continue" to do the same thing or "stop."

Knowing the base case usually tells you what kind of extra information you may need to carry around, if any.

In the case of scheme and racket, which support tail call optimization, you may end up with different kinds of recursion. For example:

(define (normal-factorial n)
  (if (zero? n)
      1
      (* n (normal-factorial (- n 1)))))

(define (tail-factorial n)
  (letrec ((tf (lambda (product index)
                 (if (zero? index)
                     product
                     (tf (* product index) (- index 1))))))
    (tf n (- n 1))))

In the first case, we build up a product without ever multiplying until the very end, while in the second we multiply as soon as possible and carry around this temporary product the whole time.

Not all problems easily lend themselves to one kind of recursion or the other.

Upvotes: 0

Related Questions