CODEWITHSUNDEEP
recursionfunctional-programmingschemeracketcontinuations
Hermann
Hermann

Reputation: 55

Implementing last-non-zero without continuations

last-non-zero takes a list of numbers and return the last cdr whose car is 0.

So, I can implement it using continuations, but how do I do this with natural recursion.

(define last-non-zero
  (lambda (ls)
    (let/cc return
      (letrec
          ((lnz
            (lambda (ls)
              (cond
                ((null? ls) '())
                ((zero? (car ls))      ;; jump out when we get to last 0.
                   (return (lnz (cdr ls))))
                (else 
                   (cons (car ls) (lnz (cdr ls))))))))
        (lnz ls)))))

Upvotes: 2

Views: 110

Answers (6)

Gwang-Jin Kim
Gwang-Jin Kim

Reputation: 9930

Also possible, to use foldr:

(define (last-non-zero l)
  (reverse (foldl (lambda (e res) (if (zero? e) '() (cons e res))) 0 l)))

Or use recursion:

(define (last-non-zero l (res '()))
  (cond ((empty? l) res)
        ((zero? (car l)) (last-non-zero (cdr l) (cdr l)))
        (else (last-non-zero (cdr l) res))))

Upvotes: 0

alinsoar
alinsoar

Reputation: 15803

(define last-non-zero
  (lambda (l)
    ((lambda (s) (s s l (lambda (x) x)))
     (lambda (s l* ret)
       (if (null? l*)
           (ret '())
           (let ((a (car l*))
                 (r (cdr l*)))
             (if (zero? a)
                 (s s r (lambda (x) x))
                 (s s r
                    (lambda (r)
                      (ret (cons a r)))))))))))

Upvotes: 0

Sylwester
Sylwester

Reputation: 48765

Using your implementation where you return the argument in the event there are no zero you can just have a variable to keep the value you think has no zero values until you hit it and then update both:

(define (last-non-zero lst)
  (let loop ((lst lst) (result lst))
    (cond ((null? lst) result)
          ((zero? (car lst)) (loop (cdr lst) (cdr lst)))
          (else (loop (cdr lst) result)))))


(last-non-zero '())          ; ==> ()
(last-non-zero '(2 3))       ; ==> (2 3)
(last-non-zero '(2 3 0))     ; ==> ()
(last-non-zero '(2 3 0 1 2)) ; ==> (1 2)

Upvotes: 0

ignis volens
ignis volens

Reputation: 9282

Here's an obvious version which is not tail-recursive:

(define (last-non-zero l)
  ;; Return the last cdr of l which does not contain zero
  ;; or #f if there is none
  (cond
    ((null? l)
     #f)
    ((zero? (car l))
     (let ((lnzc (last-non-zero (cdr l))))
       ;; This is (or lnzc (cdr l)) but that makes me feel bad
       (if lnzc
           lnzc
           (cdr l))))
    (else
     (last-non-zero (cdr l)))))

Here is that version turned into a tail-recursive equivalent with also the zero test moved around a bit.

(define (last-non-zero l)
  (let lnzl ([lt l]
             [r #f])
    (if (null? lt)
        r
      (lnzl (cdr lt) (if (zero? (car lt)) (cdr lt) r)))))

It's much clearer in this last version that the list is traversed exactly once.

Upvotes: 1

Shawn
Shawn

Reputation: 52539

Racket's takef-right can do it:

> (takef-right '(1 2 0 3 4 0 5 6 7) (lambda (n) (not (zero? n))))
'(5 6 7)

But assuming you have an assignment where you're supposed to write the logic yourself instead of just using a built in function, one easy if not very efficient approach is to reverse the list, build a new list out of everything up to the first zero, and return that. Something like:

(define (last-non-zero ls)
  (let loop ([res '()]
             [ls (reverse ls)])
    (if (or (null? ls) (zero? (car ls)))
        res
        (loop (cons (car ls) res) (cdr ls)))))

Upvotes: 1

Francis King
Francis King

Reputation: 1732

Please indicate if I have correctly understood the problem:

#lang scheme

; returns cdr after last zero in lst
(define (last-non-zero lst)

  ; a helper function with 'saved' holding progress
  (define (lnz-iter lst saved)
     (if (null? lst)
        saved
        (if (zero? (car lst))
            (lnz-iter (cdr lst) (cdr lst))
            (lnz-iter (cdr lst) saved))))

  (lnz-iter lst '()))

  (last-non-zero '(1 2 3 0 7 9)) ; result (7 9)

Upvotes: 1

Related Questions