On 2020-05-07 4:52 pm, Freeman Gilmore wrote:
Aaron, thank you; but i do not have a clue. Were can I read about
this? Google is no help.
Seeing as cheap-list? in this context is a LilyPond invention, it is
unsurprising there is little information online. I use DuckDuckGo, but
a search for "scheme cheap-list? predicate" only yields relevant results
that point to the LilyPond documentation. And aside from the source
code itself, the only documentation on cheap-list? is the comment in the
Notation Reference regarding its improved performance over the standard
list? predicate.
Understanding why cheap-list? works requires recalling how lists are
defined and represented in Scheme. A list is either a special value
known as the empty list (which can be tested for with null?) or a pair
whose second part ("cdr") is itself a list. That means list? would have
the following recursive implementation:
;;;;
(define (list? x)
(or (null? x)
(and (pair? x)
(list? (cdr x)))))
;;;;
Compare that to cheap-list? which does not recur:
;;;;
(define (cheap-list? x)
(or (null? x)
(pair? x)))
;;;;
If a list being tested has many elements, cheap-list? can return success
much faster than list? would. However, cheap-list? does not assert the
value tested is, in fact, a proper list:
;;;;
(list? '(1 . 2))
=> #f
(cheap-list? '(1 . 2))
=> #t
;;;;
-- Aaron Hill
