Daniel Prager wrote on 07/28/2017 01:03 AM:
> `first` and `rest` need to check if the input is a list.
Why is that?
When Racket/Scheme/Lisp people speak of checking whether something is a
list, I think they usually mean in the sense of the predicate `list?`
(or `listp`), which is usually an O(n) test for whether a value is a
properly-formed list of pairs (or cons cells) terminated by a null.
One reason people sometimes do the expensive list check is because it
can be good practice (to have your procedure check its arguments at
entry, so it can say the bug is not its fault, as early as possible).
Teaching languages are one place I don't think anyone would question
whether this is good practice.
Another possible reason is that, unless the cost of `list?` has
previously been pointed out to you, it's easy to just use it without
even considering whether it might be expensive. Even once I knew this,
I still did this at least once, myself.
When writing list-processing code that has to deal with potentially
large lists, if you're not using a type system that avoids the expensive
`list?` cost, IMHO, it's usually OK for an initial argument type check
to use a `pair?`/`null?` in lieu of `list?`, or possibly do no initial
check at all. If you want to provide better exceptions on improper
lists, you can check for list correctness as you proceed with your
algorithm, and raise an exception yourself (such as including the
original argument value, which info would not be in the exception if,
say, `cdr` raised it).
BTW, if you want to be professional about list-processing code you write
for use with potentially arbitrary lists, it's good to remember that
lists can have cycles, and... uh, you can usually just document that
"behavior is undefined" for lists with cycles. :) Especially since today
you're usually dealing with immutable pairs, in modern Racket, where
cycles are much less likely than they were when we used `set-cdr!`.
(Or, if you can't afford to hang in an infinite loop on cycles that are
reasonably plausible, and you don't mind slowing down and complicating
things a little, and you don't mind having a maximum list size for your
procedure, you can keep a counter during what could otherwise be an
infinite loop in your algorithm, which you can then keep checking, to
decide whether to raise an exception. Or you can do it a harder way,
like one of "https://en.wikipedia.org/wiki/Cycle_detection".[1] Or you
could use a less-basic language/platform facility, and raise an
exception if some limit of compute resource or time is reached for that
procedure call.)
[1] Tangential story about school and industry. The first time that I
hit a speed bump in a software development interview was a long time
ago, when some CS student co-founder of a video game startup asked me
how to detect whether a linked list had cycles. So, having some
schooling and experience by that time, but not recalling this problem
from when I took Data Structures & Algorithms years earlier, I started
working through the problem, while trying to ignore distracting social
cues that the interviewer might not have realized he was making-- Then
the interviewer tells me he'd recently given the same question to a CS
student from his school, who'd immediately named "the" algorithm, and
who'd then proceeded to derive a proof of it on the whiteboard. Then
the interviewer vetoed me as a hire, despite the CS systems cred for
which his co-founder recruited me in the first place, not that I'm still
bitter. :) So, if you didn't know/remember that there are off-the-shelf
algorithms for cycle detection, now you do, and, when you someday
interview others, consider not being a punk about it. :)
--
You received this message because you are subscribed to the Google Groups "Racket
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
