Implementing last-non-zero without continuations-CodePudding

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)) (return (lnz (cdr ls)))) ;; to jump out when we get to last 0.
                (else (cons (car ls) (lnz (cdr ls))))))))
        (lnz ls)))))

CodePudding user response：

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)

CodePudding user response：

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)))))