Specifically, as Robby said earlier, `list?` is memoized, so e.g. (first (rest (build-list 10 values))) only pays this price once. And `list?` rejects pairs that have cycles.
-Philip On Fri, Jul 28, 2017 at 5:51 AM, Matthias Felleisen <matth...@ccs.neu.edu> wrote: > > 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> > 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> >> 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".[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. >>> >> >> -- >> 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. >> > > -- > 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. > > > -- > 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. > -- 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.
