CODEWITHSUNDEEP
performancelistrecursionschemeracket
Ray Sun
Ray Sun

Reputation: 21

make a list in scheme with high efficiency

I want to use the Scheme language to create a special list with high efficiency. E.g.:

Function name: make-list
parameter: max
(make-list max) -> (1 2 3 4 5 6 7 ... max)

I can complete this task by using recursion method. 

#lang racket

(define (make-list max)
(define lst '())
(define count 1) 
(make-list-helper lst max count))

(define (make-list-helper lst max count) 
 (cond  
 [(> count max) lst]
 [else 
  (set! lst (append lst (list count))) 
  (make-list-helper lst max (add1 count)]))

However, this method can be considered to be low. I have no idea how to improve its efficiency of making a list. Can anybody help me out?

Upvotes: 0

Views: 395

Answers (3)

Óscar López
Óscar López

Reputation: 236004

Another definition of "efficiency" might be: writing the procedure with the least amount of code. With that in mind, the shortest solution for the question would be to use an existing procedure to solve the problem; for example if max = 10:

(define (make-list max-val)
  (build-list max-val add1))

(make-list 10)
=> '(1 2 3 4 5 6 7 8 9 10)

The above makes use of the build-list procedure that's part of Racket:

Creates a list of n elements by applying proc to the integers from 0 to (sub1 n) in order. If lst is the resulting list, then (list-ref lst i) is the value produced by (proc i).

Yet another option, also for Racket, would be to use iterations and comprehensions:

(define (make-list max-val)
  (for/list ([i (in-range 1 (add1 max-val))]) i))

(make-list 10)
=> '(1 2 3 4 5 6 7 8 9 10)

Either way, given that the procedures are part of the language's core libraries, you can be sure that their performance is quite good, no need to worry about that unless a profiler indicates that they're a bottleneck.

Upvotes: 1

leppie
leppie

Reputation: 117220

(define (make-list max)
  (let f ((i max)(a '()))
    (if (zero? i)
        a
        (f (- i 1) (cons i a)))))

This seems to be a simple exercise for iteration.

The above is as simple as it gets, and you will use it every where in Scheme.

Make sure you understand how the entire snippet works.

Upvotes: 2

Anton Kovalenko
Anton Kovalenko

Reputation: 21507

The key principle is to avoid Schlemiel the Painter's algorithm, which you don't: using append repeatedly takes more and more as the list becomes longer. Prepending the element is O(1), while appending is O(length of list); so make the innermost make-list-helper return a singular list (max), and use cons to prepend elements on recursion.

(I would prefer iterative solution, but I'm a common lisper, so I'd better avoid insisting on anything for scheme).

No code included to avoid spoiling you the fun of learning.

Upvotes: 2

Related Questions