CODEWITHSUNDEEP
recursionschemelispracket
Silverfin
Silverfin

Reputation: 495

Effective method for replicating length function

I am replicating racket's length function using just car & cdr to compare then length of two lists and return the shorter of the two.

The length function simply put is:

(define length
 (lambda (list)
    (if (null? list)
        0
        (+ 1 (length (cdr list))))))

and when used in comparison of two lists

(define short
  (lambda (list1 list2)
    (if (<= (length list1) (length list2))
        list1
        list2)))

> (short '(a b c) '(1 2 3 4 5 6 7))

will return '(a b c).

However this method is ineffective especially when one list is much longer than the other, as it will iterate through both lists before returning the shorter.

I have a more effective method below. However I was wondering if there was a more efficient/alternate method to getting the shorter length without checking to the end of both lists. Perhaps by recursively going through the lists simultaneously with car/cdr, until the shorter list reaches its end first.

(define shorter?
  (lambda (list1 list2)
    (and (not (null? list2))
         (or (null? list1)
             (shorter? (cdr list1) (cdr list2)))))) 

(define shorter
  (lambda (list1 list2)
    (if (shorter? list2 list1)
        list2
        list1)))

Upvotes: 2

Views: 105

Answers (3)

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

Your shorter? procedure is already as efficient as possible - both the and and or special forms short-circuit and will stop when the value of any of the evaluated expressions is true (for the or special form) or false (for the and special form). So as soon as one of the lists reaches null, the recursion stops. Your shorter? implementation is equivalent to, and as efficient as this:

(define shorter?
  (lambda (list1 list2)
    (cond ((null? list2) #f)
          ((null? list1) #t)
          (else (shorter? (cdr list1) (cdr list2))))))

If you want a more compact solution you can put both procedures inside a single procedure, using a named let (as demonstrated in the other answer) or an inner helper procedure, both are equivalent. I'll demonstrate the later approach:

(define (shorter lst1 lst2)
  (define (shorter-list list1 list2)
    (cond ((null? list2) lst2)
          ((null? list1) lst1)
          (else (shorter-list (cdr list1) (cdr list2)))))
  (shorter-list lst1 lst2))

Upvotes: 2

rnso
rnso

Reputation: 24545

The 'named let' method provides easily understable code. The comments provide the explanation: 

(define (shorter l1 l2)
  (let loop ((al l2)         ; start with both full lists
             (bl l2))
    (cond
      [(empty? al) l1]       ; if al finishes, return l1 and end; 
      [(empty? bl) l2]       ; if bl finishes, return l2 and end;
      [else
       (loop (cdr al) (cdr bl))] ; else loop again with cdr of lists;
    )))

This function will end when shorer list finishes and will not needlessly continue till end of longer list.

Upvotes: 2

user7487664
user7487664

Reputation: 24

I recommend starting like this:

(define (shorter list-1 list-2) (shorter-loop list-1 list-2 list-1 list-2))

then

(define (shorter-loop list-1 list-2 result-1 result-2)
  ;;
  )

where the helper function shorter-loop recurses down list-1 and list-2 simultaneously. If list-1 becomes null it returns result-1, if list-2 returns null it returns result-2.

Upvotes: -1

Related Questions