Finding the longest sub-list in list of lists (Racket/Scheme)

Admin 1
Viewed 473

I wrote this Racket code to find and display the longest sublist in a list of lists, but if the lengths of multiple sublists are equal and all the longest, I want it to return the last sublist having the longest length. 

(define longest '())
;returns longest sublist in a list of lists
(define (longestSub losl)
  (set! longest (car losl))
   (for ([x (- (length losl) 1)])
    (if (>= (length (list-ref losl x)) (length longest))
        (set! longest (list-ref losl x))
        (void losl)))
  (display longest))

For example, if "losl" is ((1 2) (3 4 5) (6 7 8)), I want it to return (6 7 8), but right now it would return (3 4 5). Can anyone tell me what I'm doing wrong?

racket list
2 Answers

Can anyone tell me what I'm doing wrong?

With (for ([x (- (length losl) 1)]) ;... the loop does not iterate to the end of the input list. With the given input, (length losl) is 3; so the loop clause is equivalent to (for ([x 2]) ;..., which is similar to (for ([x (in-range 2)]) ;.... This generates the values 0 and 1 for x, but 2 is never reached, hence the last list is never checked. To correct this problem, change to:

(define (longestSub losl)
  (set! longest (car losl))
  (for ([x (length losl)])
    (if (>= (length (list-ref losl x)) (length longest))
        (set! longest (list-ref losl x))
        (void losl)))
  (display longest))

Incidentally, you could get rid of the (void losl) by using when instead of if:

(define (longestSub losl)
  (set! longest (car losl))
  (for ([x (length losl)])
    (when (>= (length (list-ref losl x)) (length longest))
      (set! longest (list-ref losl x))))
  (display longest))

Using a loop and set! for this may not be the most idiomatic solution. Another approach would be to use recursion, and a helper function that passes the current longest sublist:

(define (longest-sublist losl)
  (define (lsl-helper losl longest)
    (cond [(empty? losl)
           longest]
          [(>= (length (first losl)) (length longest))
           (lsl-helper (rest losl) (first losl))]
          [else (lsl-helper (rest losl) longest)]))
  (lsl-helper losl '()))

Both solutions will work, but there are a couple of differences. The OP solution will fail with a runtime error in the event of an empty list for input: (longestSub '()). But this recursive solution will return the empty list for the same input instead of failing. Which behavior is preferred is up to OP. The other difference is that this recursive solution returns the longest sublist, while the OP solution merely prints it.

user_68798260

We kick out smaller element or left element.

(define (longest  lst)
  (foldr (λ (a b) (if (> (length a) (length b)) a b))
         '()
         lst))

;;; TEST
(longest '((1 2) (3 4 5) (6 7 8)))
user_114791580
Related