Return a predecessor for a given value and given list

Question

I'm familiar with recursion procedures, but somehow I cannot solve this problem: I want to return a predecessor value for a given list.

(define (pred value lst)
    ...)

(pred 3 (list 8 3 7 3)) should return 8
(pred 2 (list 1 2 2 2 2)) should return 1

Note that I only want to return the "first" occurrence of a predecessor, therefore in this first example the number 7 does not have to be returned.

I'm currently stuck because I "loose information" about the predecessor value, once I call a recursion by (pred value (rest lst)) ... I don't know to "store" this information in e.g. a list.

Thanks for any help! I'm already trying for hours...

Can you show us your work? What did you try and where did you got stuck? It's hard yo help you, when we don't know what your problem actually is. — rsm
Note that this function really needs to return three values: the predecessor, was there a predecessor? did we run out of list? You could fold the second two into one, but there's no real need I think. — user5920214
@tfb Just like car and + needs to return 2 values in case they are given bad data? The extra mile would be to use (error 'not-found "element not found") instead of it getting a type error on (). Deciding a value when it's not found is also OK as long as it's underspecified but (pred 'test '(#f test)) might return the same as (pred 'test2 '(#f test)) — Sylwester
@Sylwester: no, not like, for instance + at all: (+ 1 'a) is an error, but (pred 'a '(a b) isn't: it should have a way of saying 'there is no predecessor', just like gethash can in CL. That's what multiple values are for in many cases: providing some extra information you may care about without going through the vast overhead of signalling an error. Even if Racket, at least, is so fussy about multiple values as to make them almost useless in practice. — user5920214
@Sylwester: Oh, yes, I had not understood your idea for car: I'd be fine with a Lisp where (car x) returned two values: the car (or nil) and false if x is (), true otherwise, so long as it continued to signal an error if x was not either a cons or (). (But only in a language like CL where additional values can be ignored.) I think I can't easily describe my issue with the function here without giving examples of implementations of it, and I don't want to do that here for obvious reasons. — user5920214

Sylwester Sylwester · Accepted Answer · 2019-11-18T23:13:42

So here is how to fix this. You make a helper that takes additional arguments. One of those can be the previous element. eg.

(define (iterate-pred value last lst)
  ...)

(pred 3 '(1 2 3 4))         ; ==> 
(iterate-pred 3 1 '(2 3 4)) ; ==> 
(iterate-pred 3 2 '(3 4))   ; ==> 
; ==> 2

So to update the variables you just call the same procedure again with the new values. It is just as easy as iterating the list to begin with, which uses the same strategy.

You can implement these as internal procedure either with define/letrec or you can use named let. Then you can omit value in the helper since you have access to it through the scope.

Good luck!

Return a predecessor for a given value and given list

1 Answers