Page 1 of 1
Helpful function: first-that
Posted: Wed May 30, 2007 1:07 pm
by 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))))
Posted: Wed May 30, 2007 1:16 pm
by Fanda
There is a function called 'exists' that should be able to do the same.
Fanda
Posted: Wed May 30, 2007 2:16 pm
by Jeff
Thanks, I was looking for that ;)
Posted: Wed May 30, 2007 5:19 pm
by 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 ;-)
Posted: Wed May 30, 2007 6:19 pm
by 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 :)
Posted: Thu May 31, 2007 3:12 am
by 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!
Posted: Thu May 31, 2007 12:39 pm
by 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.
Posted: Thu May 31, 2007 3:01 pm
by rickyboy
Here's why the base case (which checks for the end of list) is needed:
So, something like
(first-that string? '(a-symbol 42)) will cause a stack overflow.
Posted: Thu May 31, 2007 3:07 pm
by 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.