Re: cheap-list

[Aaron Hill]

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