Re: cheap-list

[Freeman Gilmore]

Aaron:

That helps but I do not know how to use it.    For now that is OK    I
found the places in “Notation Reference” where cheap-list was
mentioned, that is why I asked.

Thank you, ƒg


On Thu, May 7, 2020 at 9:09 PM Aaron Hill <address@hidden> wrote:
>
> 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