Helpful function: first-that

[Jeff]

Returns the first item that satisfies a predicate. Unlike find and ref, this returns the entire element, rather than its index.

Code: Select all

(define (first-that lambda-p lst)
  "Returns first item in list that satisfies lambda-p."
  (if (lambda-p (first lst))
    (first lst)
    (first-that lambda-p (rest lst))))

[Fanda]

There is a function called 'exists' that should be able to do the same.

Fanda

[Jeff]

Thanks, I was looking for that ;)

[Lutz]

Beyond the fact Fanda mentioned that the built-in 'exists' does the same functionality, I wanted to make some other comments about this code:

Code: Select all

(define (first-that lambda-p lst) 
  "Returns first item in list that satisfies lambda-p." 
  (if (lambda-p (first lst)) 
    (first lst) 
    (first-that lambda-p (rest lst))))

This is the kind of algorithm people use who have learned Scheme or have been teached other older LISP dialects favouring recursion and trying to avoid iteration.

The principle used here is iterating through a list by applying an operation to the first element and then recursing the function with the rest of the list.

newLISP has many built-in function to make this type of problem easier to code and much faster in execution:

Code: Select all

(define (first-that lambda-p lst)
	(first (filter lambda-p lst)))

or to retrieve all for that lambda-p is not true:

Code: Select all

(define (first-that-not lambda-p lst)
	(first (clean lambda-p lst)))

Lutz

ps: this is not to criticize Jeff's code but to point out differences between programming in newLISP versus what is normally teached when learning Lisp ;-)

[Jeff]

Good point, Lutz. I do tend toward recursion and older lispy techniques. And we should always try the existing solution first before writing our own.

I did not use filter because (filter lambda-p lst) first expands by applying lambda-p to each item in lst. My solution short-circuits when it hits the first non-nil evaluation.

I did not imagine that filter would be faster since it is applying a lambda as well and does not short-circuit. Is there a fault in that logic?

PS I of course don't take offense Lutz. Code doesn't get better if it doesn't get comments :)

[rickyboy]

Jeff,
Love the recursion! ;-) It's missing the base case, but looks beautiful anyway.

Lutz,
Your version, of course, doesn't need a base case, but Jeff is right about the short-circuiting logic. If he rewrote his short-circuiting version iteratively, it would probably be the most efficient lambda implementation. Your version would be pretty much be the most efficient way to implement it, if newLISP's evaluator was non-eager; then filter would only need to return its output's head to first, and not bother to process the rest of its input -- like UNIX pipelines, naturally short-circuiting!

[Jeff]

Rickyboy,

The base case is nil because it is technically a predicate. If nothing in the list evaluates as t, it should simply not return any elements - an empty list.

[rickyboy]

Here's why the base case (which checks for the end of list) is needed:

Code: Select all

> (rest '())
()
> (first '())
nil

So, something like (first-that string? '(a-symbol 42)) will cause a stack overflow.

[Jeff]

Ah, I assumed that it would return nil. I wasn't thinking and got sloppy :). I should have done:

Code: Select all

(if (rest lst) (first-that lambda-p (rest lst)) nil)

or something on the last line there.