first and rest were introduced in the teaching languages first when we decided
it was about principles of design and cadadar was cute but nobody should have
care.
first and rest are about lists in other languages and the names say so. car and
cdr are about pairs (not that their names say so) and should be called left and
right.
first and rest were applied to immutable cons-es in *SL, so we knew that no
checks were needed.
first and rest migrated to racket but we wanted them to be like those in *SL.
So we checked. Fortunately, lists became immutable so
list? is essentially O(1) and has negligible cost.
> On Jul 28, 2017, at 6:40 AM, Robby Findler <ro...@eecs.northwestern.edu>
> wrote:
>
> It could have been. I am not sure why (but it probably had something to do
> with better checking for the teaching languages, Matthias may recall more).
>
> Robby
>
> On Fri, Jul 28, 2017 at 4:19 AM Daniel Prager <daniel.a.pra...@gmail.com
> <mailto:daniel.a.pra...@gmail.com>> wrote:
> Interesting stuff, but if I may probe a little deeper into scheme history,
> why couldn't first have simply been defined as a synonym for car (i.e. first
> item in a pair) and rest a synonym for cdr?
>
> Dan
>
>
> On Fri, Jul 28, 2017 at 6:09 PM, Neil Van Dyke <n...@neilvandyke.org
> <mailto:n...@neilvandyke.org>> wrote:
> 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
> <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
> <mailto:racket-users%2bunsubscr...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
>
> --
> 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
> <mailto:racket-users+unsubscr...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
>
> --
> 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
> <mailto:racket-users+unsubscr...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
--
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.
