Re: Why cannot "last" be fast on vector?
I promised I won't post more on this thread. But Rich is here and I think I can grant myself an excuse to post just one more. End of it, I promise. :-) First, although Rich does not think so, I myself feel this topic is very important as it is not just about "last", It touches some fundamental design principles. Then, please see my comments embedded in Rich's original message. And my comments are not long as I already said most of what I want to say before. Thank you. On Sunday, July 1, 2012 2:17:07 PM UTC-4, Rich Hickey wrote: > > Wow, this thread was exhausting :) This reply is not to anyone in > particular, just tagging on at the end (hint). > > It is quite easy to come up to some part of Clojure, with some need, and > some current perspective, and find it unsatisfying. It certainly is not > perfect. But a good presumption is that there might be more context, more > constraints, or more issues in play than one might recognize at first > glance. > > True, but this applies both ways. So it is also possible to be satisfied with our current design with our current context and find out it does not fit later. > Mark was most correct in identifying that the algorithmic complexity > dominates this decision. As far as the functions being defined in terms of > abstractions: while true, the abstractions are still something that could > be refactored. They are a means, not an end. > > History: 'last' is a Lisp function. In Common Lisp it operates on lists > only. It is a function that, there, advertises slowness by its mere > presence. Code using it has a presumption it will only be used on short > lists, and in fact it generally is; in macros and things that process code. > People reading that code can presume the same. > > I do think that, in general, it is bad to have a single polymorphic > function that, depending on the target arguments, transitions between > different algorithmic complexity categories (N.B. that is not equivalent to > using polymorphism to get better performance by leveraging some > implementation specifics, it is a specific subset). 'nth' for seqs is a > counterexample, was requested by the community, and I still think is > somewhat of a mistake. At least, it would be good to also have an 'elt' > with specific non-linear complexity (for the reasons I give below). > > Usually, there is a 'fast' function and someone wants it to work on > something that would be in a slower category. This case is the opposite, > 'last' is slow and people want it to be faster where possible. The end > result is the same. > > Why not just be as polymorphic as possible? In Common Lisp, there is a set > of functions that lets you use lists as associative maps. The performance > is not good as things get larger (i.e the sky falls). While this made sense > at one point in time (when there were only lists), is it still a good idea > now? Should we have functions that expect maps accept lists? > > In my experience, having everything work on/with lists made it really easy > to get a system together that worked on small data sets, only to have it > crash and burn on larger ones. And then, making it perform well was > extremely challenging. Some of that was because of the lack of > interface-conforming implementations of e.g. hashmaps to swap in. but > another category of problem was not being able to see what calls mattered > for performance, when lists would still be ok etc. Thus Clojure 'forces' > you to make some of these decisions earlier, and make them explicit. Even > so, it is still highly polymorphic. > > In "list as map" example of Common Lisp, that in my view is not the fault of polymorphic design, that is because as you said a lack of it. (... because of the lack of interface-conforming implementations ...). If the polymorphic design were done right, then we should be able to swap in an efficient map implementation. I think we should learn the *right* lesson here. > At the moment, I'm not sure it would be bad to have 'last' behave better > for vectors et al while still promising in documentation to be not > necessarily better than linear. But I do know this - it is seriously > unimportant. We all have much better things to do, I hope, than argue over > things like this. > > There is a perfectly adequate and well documented way to get the last > element of a vector quickly, and code for which that matters can (and > should, *even if last were made faster*) use it. Code for which it doesn't > matter can use 'last' on vectors because - ipso facto *it doesn't matter*! > People reading either code will know what is and isn't important, and that > seems to matter most. > > Rich > > As a middle ground, maybe we can keep both type specific and polymorphic functions? For people who absolutely need to squeeze out the last drop of performance, the type specific function will save them some dispatching cost. But I myself would rather to
Re: Why cannot "last" be fast on vector?
Wow, this thread was exhausting :) This reply is not to anyone in particular, just tagging on at the end (hint). It is quite easy to come up to some part of Clojure, with some need, and some current perspective, and find it unsatisfying. It certainly is not perfect. But a good presumption is that there might be more context, more constraints, or more issues in play than one might recognize at first glance. Mark was most correct in identifying that the algorithmic complexity dominates this decision. As far as the functions being defined in terms of abstractions: while true, the abstractions are still something that could be refactored. They are a means, not an end. History: 'last' is a Lisp function. In Common Lisp it operates on lists only. It is a function that, there, advertises slowness by its mere presence. Code using it has a presumption it will only be used on short lists, and in fact it generally is; in macros and things that process code. People reading that code can presume the same. I do think that, in general, it is bad to have a single polymorphic function that, depending on the target arguments, transitions between different algorithmic complexity categories (N.B. that is not equivalent to using polymorphism to get better performance by leveraging some implementation specifics, it is a specific subset). 'nth' for seqs is a counterexample, was requested by the community, and I still think is somewhat of a mistake. At least, it would be good to also have an 'elt' with specific non-linear complexity (for the reasons I give below). Usually, there is a 'fast' function and someone wants it to work on something that would be in a slower category. This case is the opposite, 'last' is slow and people want it to be faster where possible. The end result is the same. Why not just be as polymorphic as possible? In Common Lisp, there is a set of functions that lets you use lists as associative maps. The performance is not good as things get larger (i.e the sky falls). While this made sense at one point in time (when there were only lists), is it still a good idea now? Should we have functions that expect maps accept lists? In my experience, having everything work on/with lists made it really easy to get a system together that worked on small data sets, only to have it crash and burn on larger ones. And then, making it perform well was extremely challenging. Some of that was because of the lack of interface-conforming implementations of e.g. hashmaps to swap in. but another category of problem was not being able to see what calls mattered for performance, when lists would still be ok etc. Thus Clojure 'forces' you to make some of these decisions earlier, and make them explicit. Even so, it is still highly polymorphic. At the moment, I'm not sure it would be bad to have 'last' behave better for vectors et al while still promising in documentation to be not necessarily better than linear. But I do know this - it is seriously unimportant. We all have much better things to do, I hope, than argue over things like this. There is a perfectly adequate and well documented way to get the last element of a vector quickly, and code for which that matters can (and should, *even if last were made faster*) use it. Code for which it doesn't matter can use 'last' on vectors because - ipso facto *it doesn't matter*! People reading either code will know what is and isn't important, and that seems to matter most. Rich -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
I fully support Warren's point of view. I'm also unhappy with current behaviour of sequence functions (more accurate: I think it can be made even better). In my mind, protocols (interfaces?) based, polymorphic core functions is just what we need. Moreover, similar request has been done already (e.g. see CLJ-803) for reasons completely unrelated to the topic of this thread. I think some parts of clojure can be considered "broken", quoting from doc-strings for deftype, defrecord, extend: "Alpha - subject to change", "It is TBD how to specify which impl to use". I believe Warren has provided some constructive criticism of the language and rised important problems. It's a good idea to create corresponding wiki page on JIRA. This thread was definitely useful for me, and I find the discussion interesting and worthy too. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Sat, Jun 30, 2012 at 10:24 AM, Warren Lynn wrote: > I think some people agree with me something is broken here (puzzler, for > example. Please correct me is I am wrong as I don't want to hijack other > people's opinion). > One really nice thing about the Clojure community is that from the very beginning, Rich instilled a value that we should generally avoid talking in terms of a "sky is falling" mentality, and avoid using terms like "broken". Generally speaking, the community has been trained to avoid engaging with people who make such exaggerated claims. This has a couple of beneficial effects: first, it helps keep criticisms grounded and constructive, second, it tends to limit the destructive potential of people who are just trolling. As a result of this community ethic, you'll find that if you keep calling Clojure broken, people will just tune you out. So no, I don't agree that last is "broken". I claimed that last *could* be made polymorphic, and that if, it were up to me, I *would* make it polymorphic because I think there's little downside and it's generally better to make functions behave in an intuitive way; I believe that the name last implies fast access for data structures which offer fast access to the last element. However, I, like most of the others here, don't regard this as a big deal. The first time I read through the docs, I noted that last wasn't a particularly useful function because of its linear time bound. So I just don't use it. If I need fast access to the last element, I use a vector, and I use the peek function. It's not the way I would design things, but it's not a big deal, either. There are a number of aspects of Clojure I feel that way about, and it doesn't stop me from wanting to use it. Now I *do* find this discussion interesting, particularly because of things that David has said about protocols and ClojureScript, and the limitations that this may place on design. Ever since protocols were introduced, I have been very intrigued to see how they would play out in practice. I would like to discuss this issue further, but I will start a new thread to do so... -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Sat, Jun 30, 2012 at 7:09 AM, Warren Lynn wrote: > As I mentioned before, the issue here is not just a fast "last". The issue > here is I find the design of Clojure "wrong", or confusing. That really > shakes my confidence in the whole system. Some of Clojure's design decisions take a while to really internalize. Several folks here have explained them but you're still not satisfied. I don't think there's much more they can do at this point. > According to the book "Clojure Programming" by Chas, one of the Clojure's > principles is to "build on abstractions" and to separate abstractions from > concrete types. Now I have a little deeper contact with Clojure and my > impression is that is not the reality. But it is the abstractions specifically that lead to the situation you are in, with last operating the way it does, as several folks have explained. Some have suggested you read through and understand the implementation of Clojure. That may help you understand the abstractions better (it may not). But, as has been stated (repeatedly) in this thread, Clojure is this way for a (good) reason. I actually think Stu's post was one of the clearest explanations... -- Sean A Corfield -- (904) 302-SEAN An Architect's View -- http://corfield.org/ World Singles, LLC. -- http://worldsingles.com/ "Perfection is the enemy of the good." -- Gustave Flaubert, French realist novelist (1821-1880) -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Saturday, June 30, 2012 1:03:04 PM UTC-4, Las wrote: > > Warren, > > I think the issue is this: > > You claim there is sg. broken in clojure while admitting that you know > little about how the design decision was made. > > People that know clojure's implementation and the history of design > decisions inside-out offered advice why they think it is not broken, they > took time to explain the rationale for decision and even offerred advice > how to "fix it" for yourself should you insist on your view of the matter. > > It seems to me you > a) need to reread these arguments to perhaps get a better grasp > b) have chosen to ignore them. > > While you have right to do either of them, if it's b) not even the > "clojure gods" can really help you unless you actually spend some time with > the internals of clojure. ;-). > > Las > > > First, this will be my last post on this thread, so I will be absolved from "attention seeking". But really, as you have pointed out, things are getting in a kind of circle and we may just need to sit back and think for a while. I think some people agree with me something is broken here (puzzler, for example. Please correct me is I am wrong as I don't want to hijack other people's opinion). For the other people who don't agree with me, I am not really ignoring their argument (I tried hard to reply to each of them), it is just, I am not really convinced. No I don't know the language inside-out, and I don't know much about the implementation. But I was trying to keep my discussion on the high-level abstraction. If somebody told me "Warren, I agree with you that the abstractions and design principles need some fixing, but man it is very hard to do now, take my word for it", even nothing changed I will feel better using Clojure because at least people admit there is a problem and there is a chance it will get fixed in the future (on on another host language). So far I have not get that kind of feedback. We all choose what we think is right for us, so there is no imposing anything on anybody. I appreciate the fact at least there is the language Clojure we can talk about. Thanks you all for the participation. And I will much more comfortalbe Of course in the end -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Warren, I think the issue is this: You claim there is sg. broken in clojure while admitting that you know little about how the design decision was made. People that know clojure's implementation and the history of design decisions inside-out offered advice why they think it is not broken, they took time to explain the rationale for decision and even offerred advice how to "fix it" for yourself should you insist on your view of the matter. It seems to me you a) need to reread these arguments to perhaps get a better grasp b) have chosen to ignore them. While you have right to do either of them, if it's b) not even the "clojure gods" can really help you unless you actually spend some time with the internals of clojure. ;-). Las 2012/6/30 Warren Lynn > Craig: > > If the dominant community attitude is "before you know everything about > Clojure, you have no right to comment", then that itself will be the reason > not to use Clojure. But I think that is just you, not the community. > > Although I am glad some people paid attention to this post, I have far > more important things to do than seeking some attention from strangers. I > hope I stimulated some thinking here. I am a lisp lover, and I feel Clojure > has a good potential of being a great and practical language, but it has > its broken parts too and I wish they get fixed, so I will have a better > experience using it. That is my goal (obvious I hope). > > > On Saturday, June 30, 2012 12:17:39 PM UTC-4, Craig Brozefsky wrote: >> >> Warren Lynn writes: >> >> >As I mentioned before, the issue here is not just a fast "last". The >> >issue here is I find the design of Clojure "wrong", or confusing. >> That >> >really shakes my confidence in the whole system. >> >> To say stuff like this, then be demure about digging into the code and >> understanding how things work, followed by asking for others to be do >> the coding and be and advocate for your rather vague feeling of unease, >> strikes me as passive-aggressive attention seeking. To do such while >> top posting, well, it's just too much for me. 8^) >> >> -- >> Craig Brozefsky >> Premature reification is the root of all evil >> > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > -- László Török -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Craig: If the dominant community attitude is "before you know everything about Clojure, you have no right to comment", then that itself will be the reason not to use Clojure. But I think that is just you, not the community. Although I am glad some people paid attention to this post, I have far more important things to do than seeking some attention from strangers. I hope I stimulated some thinking here. I am a lisp lover, and I feel Clojure has a good potential of being a great and practical language, but it has its broken parts too and I wish they get fixed, so I will have a better experience using it. That is my goal (obvious I hope). On Saturday, June 30, 2012 12:17:39 PM UTC-4, Craig Brozefsky wrote: > > Warren Lynn writes: > > >As I mentioned before, the issue here is not just a fast "last". The > >issue here is I find the design of Clojure "wrong", or confusing. > That > >really shakes my confidence in the whole system. > > To say stuff like this, then be demure about digging into the code and > understanding how things work, followed by asking for others to be do > the coding and be and advocate for your rather vague feeling of unease, > strikes me as passive-aggressive attention seeking. To do such while > top posting, well, it's just too much for me. 8^) > > -- > Craig Brozefsky > Premature reification is the root of all evil > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Warren Lynn writes: >As I mentioned before, the issue here is not just a fast "last". The >issue here is I find the design of Clojure "wrong", or confusing. That >really shakes my confidence in the whole system. To say stuff like this, then be demure about digging into the code and understanding how things work, followed by asking for others to be do the coding and be and advocate for your rather vague feeling of unease, strikes me as passive-aggressive attention seeking. To do such while top posting, well, it's just too much for me. 8^) -- Craig Brozefsky Premature reification is the root of all evil -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Saturday, June 30, 2012 9:51:56 AM UTC-4, stuart@gmail.com wrote: > > Having separate "peek" and "last", with documented performance > characteristics, makes it straightforward to reason about how code is > likely to perform, a point that Mark made earlier. > > As I said before, I strongly feel mixing abstraction and speed path is the wrong direction to take. Let me elaborate a little bit more: 1. What's the purpose of high level language and dynamic typing? To abstract so we can be more efficient in writing code (Note: code itself my not run fast) and the code is easier to read and maintain. Statically typed language has less abstraction power (although it still tries hard with things like C++ templates), but faster. Dynamic language has higher abstraction power but slower performance. So it is wrong to me to throw away the strength of abstraction of a dynamic language in pursuit of performance. Performance is of course important, but not at the expense of broken abstraction. Maybe that can be done on rare cases that may have a huge impact of performance on the whole system, but it seems wrong to do it as a "design choice". 2. The argument that if a function takes its pre-designated speed characteristics, even when its possible to be faster on a particular type, will encourage better code performance or performance analysis, is a very convoluted one. If you say: by making "last" slow on vectors, it will force people to use "peek", then why not make it even slower on vectors? (how about putting a "sleep" there for vectors?). If you say "no, no, sometimes people may still use "last" on vectors and we still want the best performance in that case", then why not make it as fast as we can? 3. Maybe we don't have one now, but we will have a profiler in the future if the language will be put into serious use. With a profiler you can see where the performance bottleneck is, and a programmer can reason "Ah, this part is slow because I used "last" on a large list", give we already documented that "last" will take linear time on lists. So he can choose the right data type instead of switching functions. If the abstraction is done right, switching a data type should not be difficult. It is a fundamental design principle of Clojure that, when given two > approaches, A and B, make primitive the one that could be used to build the > other. Clojure's "peek" and "last" might be useful to somebody building > the "last" that Warren wants. Warren's "last" is *useless* for building > the "peek" and "last" that Clojure already has. > > > Not arguing against having Warren's "last". Just saying that c.c/last > ain't broken, and is simpler. > > I don't understand the argument that because a higher level function cannot be used to build a lower level function, so it is not worth working on or fixing. We can build Clojure with Java but Clojure cannot be used to build Java, so we don't need to work on Clojure? Keeping both type specific low level functions and abstraction level function is less of a problem to me, but I would avoid it if possible. Stu > > > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
As I mentioned before, the issue here is not just a fast "last". The issue here is I find the design of Clojure "wrong", or confusing. That really shakes my confidence in the whole system. I am also not talking about implementations, which is a separate issue that I don't know much yet According to the book "Clojure Programming" by Chas, one of the Clojure's principles is to "build on abstractions" and to separate abstractions from concrete types. Now I have a little deeper contact with Clojure and my impression is that is not the reality. On Saturday, June 30, 2012 3:47:58 AM UTC-4, Craig Brozefsky wrote: > > Warren Lynn writes: > > >Although I have not yet looked at any of Clojure's internals yet, I > >suspect the change won't be too difficult (for the right person). So > I > >hope/wish someone with enough knowledge, skills and influence will > >agree with me and advocate a review of the design ("last" may not be > >the only one with issues) and fix some of those things before things > >get too messy down the road. > > Err, I don't think this is an issue of "design" let alone something > worthy of getting a bit weepy about Clojure failing to be worthy of use > in your production system as implied by your previous posts. > > Here is a version of last for clojure.core that will use peek on > vectors. > > (def > ^{:arglists '([coll]) >:doc "Return the last item in coll." >:added "1.0" >:static true} > last (fn ^:static last [s] > (if (vector? s) > (peek s) > (if (next s) > (recur (next s)) > (first s) > > If the intent of specifying "in linear time" in the docstring was to > guarantee the user that we would be looping over a sequence using > first/next, then it should explicitely say so and not just imply it by > mentioning linear time. Otherwise, I see the phrase as a warning, and > not as a guarantee. > > David Nolen asked about drop-last and take-last and but-last. > > drop-last is defined as returning lazy sequences. A > change to them that returned a vector with it's tail peeked off would be > a change to the language. I am not so keen on that. > > take-last returns a seq, and it's not obvious after a whiskey just how > to rewrite it to be more efficient for vectors and not just end up > making it linear scaling on n for vectors. > > However, butlast is documented as returning a seq, so changing pop on a > vector might have some performance advantage, and not change the > outcomes of the function. Here is what that would look like. > > (def > ^{:arglists '([coll]) >:doc "Return a seq of all but the last item in coll, in linear time" >:added "1.0" >:static true} > butlast (fn ^:static butlast [s] >(if (and (not (empty? s)) > (vector? s)) > (pop s) > (loop [ret [] s s] >(if (next s) > (recur (conj ret (first s)) (next s)) > (seq ret)) > > These changes don't really bring any new entanglement between > clojure.core and the clojure.lang java objects -- because the language > defines explicitely how vector conj/peek. However, going thru > clojure.core and optimizing it based on knowledge of implementation in > clojure.lang would be complecting - thus punishable by exile to the > bitcoin mines. > > > -- > Craig Brozefsky > Premature reification is the root of all evil > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Why cannot "last" be fast on vector?
On Friday, June 29, 2012, Mark Engelberg wrote: > On Fri, Jun 29, 2012 at 4:50 PM, David Nolen wrote: > >> ISeq *is* an interface on Clojure JVM. But ideally it would be >> protocol as in ClojureScript. But then all ISeq implementing types >> must also implement this new protocol you are suggesting to get these >> basic *generic* sequence operations we enjoy today. >> >> > I see, you're not saying it can't be done in Clojure, you're saying it > wouldn't work on ClojureScript. It seems to me that's a limitation of > either ClojureScript, or protocols, or both. My guess is that it's a > limitation of ClojureScript, because my understanding is that in Clojure, > every protocol generates a Java interface, so I can't think of any reason > why you couldn't list that generated interface as a "type" in another > protocol (although I haven't tried it). > It is a host detail one can take advantage of in Clojure. But it is not a feature of protocols. In fact using protocols this way will fail. You have to go under the hood to the generated interface. And even then doesn't work for extend-typed things. As far as whether this is a problem for large software I don't share you concerns. ClojureScript is getting towards 7000 lines of standard library. Not problems yet. core.logic is approaching 40 protocols and 3000 lines of code. No problems encountered and none foreseen when the full functionality is ported to ClojureScript. Why does this seem to scale? Because Clojure's interfaces were already written in a protocol style. Inheritance doesn't matter much, and they only define 2-3 methods on average. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Having separate "peek" and "last", with documented performance characteristics, makes it straightforward to reason about how code is likely to perform, a point that Mark made earlier. It is a fundamental design principle of Clojure that, when given two approaches, A and B, make primitive the one that could be used to build the other. Clojure's "peek" and "last" might be useful to somebody building the "last" that Warren wants. Warren's "last" is *useless* for building the "peek" and "last" that Clojure already has. Not arguing against having Warren's "last". Just saying that c.c/last ain't broken, and is simpler. Stu > Even not a single action is taken because of this thread, I still would not > consider the thread fruitless. It helped me (and maybe others) understand the > issue better. > > My point was: you need a clear documentation on a coherent, consistent > abstraction, and let the programmer to understand. Just clear documentation > is not enough. You can document a very messy system in clear documentation > (maybe the US tax code?). > > Here, we are having both "peek" and "last", which is not coherent to me. > consider the documentation on an alternative design: > > last: get the last element from an ordered collection. for queues and linked > lists, it takes linear time. for vectors, it takes constant time. > > and get rid of "peek" (we already have "first" for linked list and queues, > right?) > > Which one is cleaner? > > > On Friday, June 29, 2012 3:27:57 PM UTC-4, Sean Corfield wrote: > On Fri, Jun 29, 2012 at 7:51 AM, Warren Lynn wrote: > > 1. Put good documentations on the functions, and the programmer needs to > > have some idea what data structure is fast/slow for what use. > > At the risk of continuing what is quickly becoming a rather fruitless > thread, I figured I'd quote the docstrings from last and peek: > > last: Return the last item in coll, in linear time > > peek: For a list or queue, same as first, for a vector, same as, but > much more efficient than, last. If the collection is empty, returns > nil. > > That seems like pretty good documentation to me. (last my-vector) is > documented to be a linear operation. (peek my-vector) is documented to > be "much more efficient". last is not dependent on the type of its > argument, peek is. > -- > Sean A Corfield -- (904) 302-SEAN > An Architect's View -- http://corfield.org/ > World Singles, LLC. -- http://worldsingles.com/ > > "Perfection is the enemy of the good." > -- Gustave Flaubert, French realist novelist (1821-1880) > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with your > first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en Stuart Halloway Clojure/core http://clojure.com -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Sam Ritchie writes: >Perhaps place them inside a protocol, where core supplies I don't think a protocol is needed to identify a performance characteristic, which as far as I can tell really is limited to vectors. The definition of vector? itself is sufficient. Also, consider that last is defined as part of the very base of core, before protocols get loaded, and even before defn is available. Using a protocol to optimize at that level is gonna get dirty dirty. See my reply to Warren my proposed change to core. Those defs can be dropped into clojurescript too, btw. -- Craig Brozefsky Premature reification is the root of all evil -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Warren Lynn writes: >Although I have not yet looked at any of Clojure's internals yet, I >suspect the change won't be too difficult (for the right person). So I >hope/wish someone with enough knowledge, skills and influence will >agree with me and advocate a review of the design ("last" may not be >the only one with issues) and fix some of those things before things >get too messy down the road. Err, I don't think this is an issue of "design" let alone something worthy of getting a bit weepy about Clojure failing to be worthy of use in your production system as implied by your previous posts. Here is a version of last for clojure.core that will use peek on vectors. (def ^{:arglists '([coll]) :doc "Return the last item in coll." :added "1.0" :static true} last (fn ^:static last [s] (if (vector? s) (peek s) (if (next s) (recur (next s)) (first s) If the intent of specifying "in linear time" in the docstring was to guarantee the user that we would be looping over a sequence using first/next, then it should explicitely say so and not just imply it by mentioning linear time. Otherwise, I see the phrase as a warning, and not as a guarantee. David Nolen asked about drop-last and take-last and but-last. drop-last is defined as returning lazy sequences. A change to them that returned a vector with it's tail peeked off would be a change to the language. I am not so keen on that. take-last returns a seq, and it's not obvious after a whiskey just how to rewrite it to be more efficient for vectors and not just end up making it linear scaling on n for vectors. However, butlast is documented as returning a seq, so changing pop on a vector might have some performance advantage, and not change the outcomes of the function. Here is what that would look like. (def ^{:arglists '([coll]) :doc "Return a seq of all but the last item in coll, in linear time" :added "1.0" :static true} butlast (fn ^:static butlast [s] (if (and (not (empty? s)) (vector? s)) (pop s) (loop [ret [] s s] (if (next s) (recur (conj ret (first s)) (next s)) (seq ret)) These changes don't really bring any new entanglement between clojure.core and the clojure.lang java objects -- because the language defines explicitely how vector conj/peek. However, going thru clojure.core and optimizing it based on knowledge of implementation in clojure.lang would be complecting - thus punishable by exile to the bitcoin mines. -- Craig Brozefsky Premature reification is the root of all evil -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 8:55 PM, Mark Engelberg wrote: > my understanding is that in Clojure, every protocol generates a Java > interface, so I can't think of any reason why you couldn't list that > generated interface as a "type" in another protocol (although I haven't > tried it). > > Hmmm, thinking more about this, I wonder: is the problem that unless the protocol is implemented inline in the defrecord/deftype, it doesn't officially "implement" the corresponding the interface? -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 4:50 PM, David Nolen wrote: > ISeq *is* an interface on Clojure JVM. But ideally it would be > protocol as in ClojureScript. But then all ISeq implementing types > must also implement this new protocol you are suggesting to get these > basic *generic* sequence operations we enjoy today. > > I see, you're not saying it can't be done in Clojure, you're saying it wouldn't work on ClojureScript. It seems to me that's a limitation of either ClojureScript, or protocols, or both. My guess is that it's a limitation of ClojureScript, because my understanding is that in Clojure, every protocol generates a Java interface, so I can't think of any reason why you couldn't list that generated interface as a "type" in another protocol (although I haven't tried it). If that doesn't work, then this merits more discussion, I think, because it points to a real issue about building large systems with protocols. The issue of "thin" vs "fat" interfaces is a tricky one in many languages, and one of the most reasonable solutions is to give the fat interface an implementation in terms of the thin one, so that implementers are only required to implement the thin interface, but can override the default implementation of the fat interface if need be. If this can't be done in Clojure, it would be good to figure out an alternative that will work. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
ISeq is a interface on Clojure JVM. So that will work. In ClojureScript it won't as ISeq is a protocol. On Friday, June 29, 2012, Mark Engelberg wrote: > On Fri, Jun 29, 2012 at 5:17 PM, David Nolen > > > wrote: > >> As I said, if ISeq and ILast are both protocols that won't work. No >> protocol inheritance. >> >> > I don't see how inheritance factors into this. This works just fine in > Clojure 1.3. What am I missing?: > > (defprotocol Last > (better-last [s])) > > (extend-protocol Last > nil > (better-last [s] (last s)) > Object > (better-last [s] (last s)) > clojure.lang.ISeq > (better-last [s] (last s)) > clojure.lang.Reversible > (better-last [s] (first (rseq s))) > java.lang.String > (better-last [s] (nth s (dec (count s > clojure.lang.IPersistentVector > (better-last [s] (peek s))) > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to > clojure@googlegroups.com 'clojure@googlegroups.com');> > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com 'clojure%2bunsubscr...@googlegroups.com');> > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Bobby: Thanks for confirming my sanity here. But I have a different opinion on the "attractive nuisance" label on "last" function. Sure if you call "last" on an infinite sequence that will not work (the program will get stuck?), but it is no more dangerous than other dynamic part of the language. Think about a higher order function, a function that takes another function as an argument, isn't that much more dangerous? I mean, you don't even know what kind of function people may throw into it, and the damage could be bigger (for example, it may even wipe out you hard drive). As a dynamic language gives high level of freedom and abstraction power, the programmer needs to take certain responsibilities too, because the compiler will catch much less errors than a statically typed language. So I still think "last" is a very useful function and worth fixing. Ideally, if a sequence can be checked if it is infinite or not so "last" can throw an exception when not applicable, but that may not be feasible with lazy sequences. And again I feel the responsibility should be more on the programmer's side. On Friday, June 29, 2012 9:23:09 PM UTC-4, Bobby Eickhoff wrote: > > Warren, you're on the right track with your alternative design: > Intuitively and ideally, "last" should return the last element of a finite, > ordered collection. But Clojure's "last" operates on sequences, not > collections. This is problematic because sequences can be (effectively) > infinite. Calling "last" on an arbitrary sequence is, therefore, dubious > at best. It's what Doug Crockford might call an attractive nuisance: > sometimes useful, but dangerous. So "last" isn't a function I would spend > alot of time trying to fix. > > There is historical precedent for Clojure's "last" function. For example, > see Haskell's "last" function in Data.List. Historical precedent doesn't > justify the design, but it helps explain how we got here. > > Bobby > > On Friday, June 29, 2012 4:34:04 PM UTC-4, Warren Lynn wrote: >> >> Even not a single action is taken because of this thread, I still would >> not consider the thread fruitless. It helped me (and maybe others) >> understand the issue better. >> >> My point was: you need a clear documentation on a coherent, consistent >> abstraction, and let the programmer to understand. Just clear documentation >> is not enough. You can document a very messy system in clear documentation >> (maybe the US tax code?). >> >> Here, we are having both "peek" and "last", which is not coherent to me. >> consider the documentation on an alternative design: >> >> last: get the last element from an ordered collection. for queues and >> linked lists, it takes linear time. for vectors, it takes constant time. >> >> and get rid of "peek" (we already have "first" for linked list and >> queues, right?) >> >> Which one is cleaner? >> > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 5:17 PM, David Nolen wrote: > As I said, if ISeq and ILast are both protocols that won't work. No > protocol inheritance. > > I don't see how inheritance factors into this. This works just fine in Clojure 1.3. What am I missing?: (defprotocol Last (better-last [s])) (extend-protocol Last nil (better-last [s] (last s)) Object (better-last [s] (last s)) clojure.lang.ISeq (better-last [s] (last s)) clojure.lang.Reversible (better-last [s] (first (rseq s))) java.lang.String (better-last [s] (nth s (dec (count s clojure.lang.IPersistentVector (better-last [s] (peek s))) -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Warren, you're on the right track with your alternative design: Intuitively and ideally, "last" should return the last element of a finite, ordered collection. But Clojure's "last" operates on sequences, not collections. This is problematic because sequences can be (effectively) infinite. Calling "last" on an arbitrary sequence is, therefore, dubious at best. It's what Doug Crockford might call an attractive nuisance: sometimes useful, but dangerous. So "last" isn't a function I would spend alot of time trying to fix. There is historical precedent for Clojure's "last" function. For example, see Haskell's "last" function in Data.List. Historical precedent doesn't justify the design, but it helps explain how we got here. Bobby On Friday, June 29, 2012 4:34:04 PM UTC-4, Warren Lynn wrote: > > Even not a single action is taken because of this thread, I still would > not consider the thread fruitless. It helped me (and maybe others) > understand the issue better. > > My point was: you need a clear documentation on a coherent, consistent > abstraction, and let the programmer to understand. Just clear documentation > is not enough. You can document a very messy system in clear documentation > (maybe the US tax code?). > > Here, we are having both "peek" and "last", which is not coherent to me. > consider the documentation on an alternative design: > > last: get the last element from an ordered collection. for queues and > linked lists, it takes linear time. for vectors, it takes constant time. > > and get rid of "peek" (we already have "first" for linked list and queues, > right?) > > Which one is cleaner? > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 8:02 PM, Mark Engelberg wrote: > I think the suggestion is to create a protocol for each function that could > potentially gain speed improvements for specialized types. So for example, > ILast could be a protocol. extend ILast to have an implementation for ISeq > (using the current code). As I said, if ISeq and ILast are both protocols that won't work. No protocol inheritance. At this point I think some of the basic challenges are clear. Would love to see someone actually build these ideas out purely on top of protocols instead of making this thread any longer. A good Clojure implementation via ClojureScript would make the arguments more convincing ;) David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Again, I don't know the internal details. If you are saying because of the current implementation, the change is difficult, then we will be talking about the implementation, not about the abstraction design. I have very little to say about that. On Friday, June 29, 2012 7:50:56 PM UTC-4, David Nolen wrote: > > On Fri, Jun 29, 2012 at 7:28 PM, Sam Ritchie > wrote: > > Perhaps place them inside a protocol, where core supplies > implementations > > for ISeq only? This would make it easier to extend efficient behavior to > > other types without placing a big burden on core. > > ISeq *is* an interface on Clojure JVM. But ideally it would be > protocol as in ClojureScript. But then all ISeq implementing types > must also implement this new protocol you are suggesting to get these > basic *generic* sequence operations we enjoy today. > > David > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 4:50 PM, David Nolen wrote: > On Fri, Jun 29, 2012 at 7:28 PM, Sam Ritchie wrote: > > Perhaps place them inside a protocol, where core supplies implementations > > for ISeq only? This would make it easier to extend efficient behavior to > > other types without placing a big burden on core. > > ISeq *is* an interface on Clojure JVM. But ideally it would be > protocol as in ClojureScript. But then all ISeq implementing types > must also implement this new protocol you are suggesting to get these > basic *generic* sequence operations we enjoy today. > > I think the suggestion is to create a protocol for each function that could potentially gain speed improvements for specialized types. So for example, ILast could be a protocol. extend ILast to have an implementation for ISeq (using the current code). Then, there's no burden on implementers of new data types that implement ISeq to do any additional work, but those who want to create custom implementations of last for other data types are free to do so. Win-win. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
I really don't know, as I know very little about how these things are implemented. My point is, we maintain a coherent abstraction and get the best speed we can. To recap, what I don't like about current "last" is it makes writing generic code difficult. Currently, I need to use "peek" for vector and "last" for sequence. That defeats the very purpose of abstraction. On Friday, June 29, 2012 7:42:14 PM UTC-4, David Nolen wrote: > > On Fri, Jun 29, 2012 at 6:49 PM, Warren Lynn wrote: > > The same? If internally it can be faster, be faster. If not, don't > change. > > For which types do you think they can be made faster? > > David > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
vectors and sorted collections, for sure. On Fri, Jun 29, 2012 at 4:42 PM, David Nolen wrote: > On Fri, Jun 29, 2012 at 6:49 PM, Warren Lynn wrote: > > The same? If internally it can be faster, be faster. If not, don't > change. > > For which types do you think they can be made faster? > > David > > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 7:28 PM, Sam Ritchie wrote: > Perhaps place them inside a protocol, where core supplies implementations > for ISeq only? This would make it easier to extend efficient behavior to > other types without placing a big burden on core. ISeq *is* an interface on Clojure JVM. But ideally it would be protocol as in ClojureScript. But then all ISeq implementing types must also implement this new protocol you are suggesting to get these basic *generic* sequence operations we enjoy today. David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 6:49 PM, Warren Lynn wrote: > The same? If internally it can be faster, be faster. If not, don't change. For which types do you think they can be made faster? David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Perhaps place them inside a protocol, where core supplies implementations for ISeq only? This would make it easier to extend efficient behavior to other types without placing a big burden on core. On Fri, Jun 29, 2012 at 3:05 PM, David Nolen wrote: > On Fri, Jun 29, 2012 at 5:17 PM, Mark Engelberg > wrote: > > It is clear that some collections *could* support a more efficient last. > > Anything with random access. Anything that supports rseq (e.g., sorted > > collections). > > And what does overloading last in this way mean for drop-last, > take-last, but-last? All sequence functions. > > David > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > -- Sam Ritchie, Twitter Inc 703.662.1337 @sritchie09 (Too brief? Here's why! http://emailcharter.org) -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
The same? If internally it can be faster, be faster. If not, don't change. On Friday, June 29, 2012 6:05:37 PM UTC-4, David Nolen wrote: > > On Fri, Jun 29, 2012 at 5:17 PM, Mark Engelberg > wrote: > > It is clear that some collections *could* support a more efficient last. > > Anything with random access. Anything that supports rseq (e.g., sorted > > collections). > > And what does overloading last in this way mean for drop-last, > take-last, but-last? All sequence functions. > > David > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 5:17 PM, Mark Engelberg wrote: > It is clear that some collections *could* support a more efficient last. > Anything with random access. Anything that supports rseq (e.g., sorted > collections). And what does overloading last in this way mean for drop-last, take-last, but-last? All sequence functions. David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Although I have not yet looked at any of Clojure's internals yet, I suspect the change won't be too difficult (for the right person). So I hope/wish someone with enough knowledge, skills and influence will agree with me and advocate a review of the design ("last" may not be the only one with issues) and fix some of those things before things get too messy down the road. Looking "peek" from your point of view (actually from another abstraction point of view), it seems useful. Thank you. On Friday, June 29, 2012 5:17:53 PM UTC-4, puzzler wrote: > > It is clear that some collections *could* support a more efficient last. > Anything with random access. Anything that supports rseq (e.g., sorted > collections). > > There are multiple ways to accomplish this; I presume a protocol would do > the trick. > > Perhaps the original design decision is easily justified in terms of the > original way the collections were factored into various interfaces, but now > that it is so easy to make functions polymorphic over different types via > protocols, I can't imagine this would be a difficult change if anyone cared > to do it. > > I don't think anyone is arguing that the current semantics aren't well > documented; the claim is that it violates the "Principle of Least Surprise" > in the sense that most people expect a built-in core function to be > implemented efficiently for the cases when it can be implemented > efficiently. Everyone knows that a vector, for example, is designed to > provide very fast access to the last element, so it is counterintuitive > that a function called "last" ignores this capability and just treats > vector as a generic sequence, searching through the items one-by-one to get > to the last element. > > BTW, I disagree with Warren's comment about how a better last would > eliminate the need for peek. Even if you have last, peek is a very useful > way of guaranteeing consistent stack semantics for a wide variety of > collection types. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
It is clear that some collections *could* support a more efficient last. Anything with random access. Anything that supports rseq (e.g., sorted collections). There are multiple ways to accomplish this; I presume a protocol would do the trick. Perhaps the original design decision is easily justified in terms of the original way the collections were factored into various interfaces, but now that it is so easy to make functions polymorphic over different types via protocols, I can't imagine this would be a difficult change if anyone cared to do it. I don't think anyone is arguing that the current semantics aren't well documented; the claim is that it violates the "Principle of Least Surprise" in the sense that most people expect a built-in core function to be implemented efficiently for the cases when it can be implemented efficiently. Everyone knows that a vector, for example, is designed to provide very fast access to the last element, so it is counterintuitive that a function called "last" ignores this capability and just treats vector as a generic sequence, searching through the items one-by-one to get to the last element. BTW, I disagree with Warren's comment about how a better last would eliminate the need for peek. Even if you have last, peek is a very useful way of guaranteeing consistent stack semantics for a wide variety of collection types. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
You are right, clojure.lang.ISeq is public and I can see it from "user" namespace. But that is not what I meant, the "ordered collection" is a language level abstraction, clojure.lang.ISeq is an exposed interface. With regard to "last", clojure.lang.ISeq is still implementation level, even if it is exposed. In other words, the "ordered collection" abstraction is like (or maybe the same as) the "clojure.lang.Seqable". And vectors belongs to it: (isa? clojure.lang.PersistentVector clojure.lang.Seqable) => true On Friday, June 29, 2012 4:41:59 PM UTC-4, David Nolen wrote: > > On Fri, Jun 29, 2012 at 4:25 PM, Warren Lynn wrote: > > My understanding here is "ISeq" is an INTERNAL, implementation level > > interface/abstraction, not the user/language level abstraction (which in > > this case should be "ordered collection", as somebody called) > > It is not internal. It is a user/language level abstraction. > > David > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 4:25 PM, Warren Lynn wrote: > My understanding here is "ISeq" is an INTERNAL, implementation level > interface/abstraction, not the user/language level abstraction (which in > this case should be "ordered collection", as somebody called) It is not internal. It is a user/language level abstraction. David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Even not a single action is taken because of this thread, I still would not consider the thread fruitless. It helped me (and maybe others) understand the issue better. My point was: you need a clear documentation on a coherent, consistent abstraction, and let the programmer to understand. Just clear documentation is not enough. You can document a very messy system in clear documentation (maybe the US tax code?). Here, we are having both "peek" and "last", which is not coherent to me. consider the documentation on an alternative design: last: get the last element from an ordered collection. for queues and linked lists, it takes linear time. for vectors, it takes constant time. and get rid of "peek" (we already have "first" for linked list and queues, right?) Which one is cleaner? On Friday, June 29, 2012 3:27:57 PM UTC-4, Sean Corfield wrote: > > On Fri, Jun 29, 2012 at 7:51 AM, Warren Lynn wrote: > > 1. Put good documentations on the functions, and the programmer needs to > > have some idea what data structure is fast/slow for what use. > > At the risk of continuing what is quickly becoming a rather fruitless > thread, I figured I'd quote the docstrings from last and peek: > > last: Return the last item in coll, in linear time > > peek: For a list or queue, same as first, for a vector, same as, but > much more efficient than, last. If the collection is empty, returns > nil. > > That seems like pretty good documentation to me. (last my-vector) is > documented to be a linear operation. (peek my-vector) is documented to > be "much more efficient". last is not dependent on the type of its > argument, peek is. > -- > Sean A Corfield -- (904) 302-SEAN > An Architect's View -- http://corfield.org/ > World Singles, LLC. -- http://worldsingles.com/ > > "Perfection is the enemy of the good." > -- Gustave Flaubert, French realist novelist (1821-1880) > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Thanks for clarifying more on the rationale behind the design. Also a note on the tone: I never thought insisting on a view is offensive. Insisting our views are the essence of a debate. But we need to insist based on reasons and acknowledge when we are wrong. Also, I realize that sometimes debating on a forum is different from face-to-face debating and offense is easier to make. I hope nobody took any offense. Here actually I am not only trying to ask for a faster "last". I am trying to understand some of the designs here (and along the way insisting on my own "right" one), because I have this regretful feeling that Clojure has some really nice LISP features but failed on some basic stuff, and I am seriously doubting whether I should invest more on it (possibly on a production system). I will be more than glad to be convinced that the design is sound, but I will need enlightenment. My understanding here is "ISeq" is an INTERNAL, implementation level interface/abstraction, not the user/language level abstraction (which in this case should be "ordered collection", as somebody called), so whether "last" is part of "ISeq" is irrelevant. In my view, at the user/language level, last should work on all ordered collections as fast as it can without EXPOSING whatever internal implementation is on. I know there is a lot of exciting projects going on with Clojure. But a good review of the design does not conflict with that, and may be beneficial for future exciting projects. I am still insisting on my view, but I hope its based on reasons. On Friday, June 29, 2012 2:45:53 PM UTC-4, Nicolas wrote: > > I would say we can have different ways of designing things. > > A way is to design abstractions and provide services on top on theses > abstractions. The abstraction here is ISeq. That is sequences. Last > is not part of the ISeq abstraction and just work on top of it. There > is no way to access last element directly from something that is just > a an ISeq. So last can't use it. > > If last was part of ISeq abstraction, you would not need a separate > last function at all. But this would also mean that all ISeq > implementations would need to implement last. This would be sure > conveniant, but this is not the same abstraction. It is also heavier > (more code, more maintenance...). And for some implementation like > networks streams, this would be anoying than anything as it would > provide no added value. > > Seq abstraction is exactly that: a very basic (yet powerfull) > abstraction for accessing streams, linked list and other specialized > structures that are sequential in essence. > > Clojure team could have designed last to work on any possible type > where it make sense and so have better performance for each possible > type. An efficient implementation would use a protocol to do so. > Making last its own abstraction. This is indeed possible, but was not > the choice here. > > Fact is others abstractions already allow you to have the last element > directly like Indexed if this important to you. > > So yes we could have a better last, promoting it to a full > abstraction. Like clojure could be many more things. Is this REALLY a > priority for the future of clojure? Not at least for clojure core > team. I tend to share their views. You have the right to disagree. > > On my side, I'am far more interrested to see progress in > clojurescript, IDEs, tooling, maybe even grid computing. > > You care about last. This is your right... And well why not implement > your own last in contrib or private lib and use if it is important? > Like other members of the community implemented code matching their > own interrest. > > It is logical you ask for it, but there is no need to insist or maybe > be a little offensive if others don't share your views. > > Regards, > > Nicolas Bousquet. > > On 29 juin, 01:32, Warren Lynn wrote: > > This is an off-shoot subject from my last post "General subsequence > > function". > > > > I found people had similar questions before (one year ago): > http://groups.google.com/group/clojure/browse_thread/thread/712711f04... > > > > As of Clojure 1.4, seems nothing changed, as "source" show here: > > > > user> (source last) > > (def > > ^{:arglists '([coll]) > >:doc "Return the last item in coll, in linear time" > >:added "1.0" > >:static true} > > last (fn ^:static last [s] > > (if (next s) > > (recur (next s)) > > (first s > > > > Any reason for that? Thanks. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 7:51 AM, Warren Lynn wrote: > 1. Put good documentations on the functions, and the programmer needs to > have some idea what data structure is fast/slow for what use. At the risk of continuing what is quickly becoming a rather fruitless thread, I figured I'd quote the docstrings from last and peek: last: Return the last item in coll, in linear time peek: For a list or queue, same as first, for a vector, same as, but much more efficient than, last. If the collection is empty, returns nil. That seems like pretty good documentation to me. (last my-vector) is documented to be a linear operation. (peek my-vector) is documented to be "much more efficient". last is not dependent on the type of its argument, peek is. -- Sean A Corfield -- (904) 302-SEAN An Architect's View -- http://corfield.org/ World Singles, LLC. -- http://worldsingles.com/ "Perfection is the enemy of the good." -- Gustave Flaubert, French realist novelist (1821-1880) -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
I would say we can have different ways of designing things. A way is to design abstractions and provide services on top on theses abstractions. The abstraction here is ISeq. That is sequences. Last is not part of the ISeq abstraction and just work on top of it. There is no way to access last element directly from something that is just a an ISeq. So last can't use it. If last was part of ISeq abstraction, you would not need a separate last function at all. But this would also mean that all ISeq implementations would need to implement last. This would be sure conveniant, but this is not the same abstraction. It is also heavier (more code, more maintenance...). And for some implementation like networks streams, this would be anoying than anything as it would provide no added value. Seq abstraction is exactly that: a very basic (yet powerfull) abstraction for accessing streams, linked list and other specialized structures that are sequential in essence. Clojure team could have designed last to work on any possible type where it make sense and so have better performance for each possible type. An efficient implementation would use a protocol to do so. Making last its own abstraction. This is indeed possible, but was not the choice here. Fact is others abstractions already allow you to have the last element directly like Indexed if this important to you. So yes we could have a better last, promoting it to a full abstraction. Like clojure could be many more things. Is this REALLY a priority for the future of clojure? Not at least for clojure core team. I tend to share their views. You have the right to disagree. On my side, I'am far more interrested to see progress in clojurescript, IDEs, tooling, maybe even grid computing. You care about last. This is your right... And well why not implement your own last in contrib or private lib and use if it is important? Like other members of the community implemented code matching their own interrest. It is logical you ask for it, but there is no need to insist or maybe be a little offensive if others don't share your views. Regards, Nicolas Bousquet. On 29 juin, 01:32, Warren Lynn wrote: > This is an off-shoot subject from my last post "General subsequence > function". > > I found people had similar questions before (one year > ago):http://groups.google.com/group/clojure/browse_thread/thread/712711f04... > > As of Clojure 1.4, seems nothing changed, as "source" show here: > > user> (source last) > (def > ^{:arglists '([coll]) > :doc "Return the last item in coll, in linear time" > :added "1.0" > :static true} > last (fn ^:static last [s] > (if (next s) > (recur (next s)) > (first s > > Any reason for that? Thanks. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 12:30 PM, Weber, Martin S wrote: > I'm sorry to say, but IMHO you failed to communicate the critical point to > your audience. If your audience keeps failing to grasp the point, and > communicates this failure back by asking the same question.. Perhaps we differ on the matter of audience participation? :) The functions found in the standard library fall out of Clojure's well considered protocol / interface partitions. Don't take my word for it as I already said - examine the protocol / interface partitions yourself. In the end you'll be left with a discussion about *names* (peek vs. last) - not performance, concrete types or anything else. At which point we'll probably agree that it's water under the bridge and it's not going to change. David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
I'm sorry to say, but IMHO you failed to communicate the critical point to your audience. If your audience keeps failing to grasp the point, and communicates this failure back by asking the same question.. I do understand the distinction between a collection and a sequence and something being a collection or a sequence operation. That doesn't stop certain sequences from being capable of doing certain things in a better way. I simply do not understand the reason of clojure/rich/whoever throwing away a potential performance increase because "this operation does not operate on the correct level to be performant. If you expect this to be performant, rewrite it on a lower level." That stance seems surprisingly patronizing. Also, it seems of course clojure itself is inconsistent with regard to that design choice. At least looking at Timothy Baldridge's reply to "possible bug in reducer code" makes me think so. I mean come on, a high level operation being optimized on certain types? Heresy! Regards, -Martin -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 12:13 PM, Warren Lynn wrote: > If the design choice has nothing to do with speed path, Could you let us > know why we cannot get free speed improvements on vectors? I already have. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
> The design choice has nothing to do with speed, it has nothing to do > with concrete types like lists and vectors either, no matter what > might have been said before by others. > > David > If the design choice has nothing to do with speed path, Could you let us know why we cannot get free speed improvements on vectors? -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Surely nobody can restrict/enforce anything on anybody, and I can always have my own "mycore" ns. In theory, I could even create my own language without the need to persuade anybody (or just fork from Clojure and have my own private copy). That will be the ultimate "Libertarian", but some people (including myself) may call me "savage" in doing so, unless you can attract enough people to form a new society around you, like Rich has done. :-) On Thursday, June 28, 2012 11:26:07 PM UTC-4, tbc++ wrote: > > > Nevertheless, I hope I've clarified the reasoning behind the current > > design. Early Clojure design decisions have a lot of inertia, so as > David > > pointed out, this is very unlikely to change. > > Well put. > > I would argue as well, that many functional languages I've come across > take this stance: the language is opensource, you have namespaces, so > feel free to make a namespace called mycore, that includes all you > special versions of functions that you need, and then use that library > for your projects. It doesn't take very long to define these special > case functions and if they work for you, then just use them. For > instance, one such function I wrote tonight is called every-other > (returns '(1 3 5) if you hand it (1 2 3 4 5)) > > Does this function exist in clojure.core...not that I saw off-hand. > Does it really matter though? Not really. I'll copy and paste these > functions when I need them and go happily on my way. One of the > biggest strengths of functional programming is that we can build up > snippets of functions like this, and when we use then in our programs > we can't tell that they weren't included by default. > > As Gerald Sussman said at the last Strange Loop conference: be a > Libertarian when it comes to programming. Don't restrict others to > your view of programming, liberty to you and to me and to everyone. > You can code in your style, I'll code in mine, and Clojure (or Lisp in > the case of the quote), shouldn't constrain me to its view of the > world. > > Timothy > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Sorry, I should have addressed my last post to "puzzler". On Friday, June 29, 2012 10:51:44 AM UTC-4, Warren Lynn wrote: > > > Tamreen: > > Thank you. Your posts really explained why it is so. I understand the > reasons now, but I can hardly agree those reasons are good ones (not > arguing with you, as you pointed out, the reasons are weak for this case). > > As I pointed out before in my other post ("General subsequence function"), > mixing abstraction with speed path is really a bad idea, and might be a > classical example of what Rich called "complecting". In practice, it did > not achieve what it tries to achieve either (one of the big complaints I > read from the Web about Clojure is it is really hard to know the speed > performance). For speed, the classical solution is: > > 1. Put good documentations on the functions, and the programmer needs to > have some idea what data structure is fast/slow for what use. If the > programmer does not have a clue, why would making "last" artificially slow > on vectors help? Plus, whether one data structure is slower than the other > for certain operations can also be an implementation detail that may change. > 2. Use a profiler, so you can keep optimizing on the current hot spots. > > The above solution has no interference with abstraction. > > On Thursday, June 28, 2012 11:08:35 PM UTC-4, puzzler wrote: >> >> On Thu, Jun 28, 2012 at 6:59 PM, Tamreen Khan wrote: >> >>> Here's a somewhat old but still generally useful article on how Clojure >>> vectors are implemented: >>> http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ >>> >>> >>> Vectors are optimized for random access, whereas lists are optimized for >>> going through from the beginning to the end, which is exactly what the last >>> function does. >>> >>> >>> >> This doesn't really address the underlying question. >> >> nth is a good example of a function that is fast for vectors, strings, >> and arrays, and only for lists uses the slower sequential implementation. >> >> There's no technical reason that last couldn't do the same, dispatching >> on the underlying type to have a more efficient implementation for data >> types that support it. >> >> The real reason is this: With the glaring exception of nth, Clojure tends >> to eschew functions with a fast path and a slow path, because programmers >> shouldn't have to do deep semantic analysis of their code to figure out >> which will get chosen. In this case, however, we're talking about a >> function that is currently always slow. Surely it would be a win to make >> it have a faster path in a large number of cases, right? Well, the >> argument against that is eventually people would start to rely on it being >> fast for so many collection types, and then get burned when somehow their >> collection accidentally gets turned into a seq before last is called on >> it. The theory is that it's better to force people to use a different >> function call, namely peek, to retrieve the last element quickly from a >> vector. >> >> Honestly though, despite David Nolen's claim that this design decision >> will be obvious if you've coded enough Clojure, I've been programming in it >> for around 3-1/2 years, and I think the argument behind this design >> decision is a relatively weak one, so you are not making an unreasonable >> request. In fact, the more I code in Clojure, the more I see that there >> are a number of core functions that require significant semantic analysis >> of the surrounding context to know how they will behave. Either Clojure >> trusts that programmers can make determinations about the types of their >> collections or it doesn't. Which is it? Well, I'd argue there's a large >> body of evidence that under Clojure's current design, it's clear that you >> better know what you're doing. If that's the case, why not go ahead and >> make last fast when it can be fast? >> >> Nevertheless, I hope I've clarified the reasoning behind the current >> design. Early Clojure design decisions have a lot of inertia, so as David >> pointed out, this is very unlikely to change. >> > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Fri, Jun 29, 2012 at 10:51 AM, Warren Lynn wrote: > 1. Put good documentations on the functions, and the programmer needs to > have some idea what data structure is fast/slow for what use. If the > programmer does not have a clue, why would making "last" artificially slow > on vectors help? Plus, whether one data structure is slower than the other > for certain operations can also be an implementation detail that may change. The design choice has nothing to do with speed, it has nothing to do with concrete types like lists and vectors either, no matter what might have been said before by others. David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Tamreen: Thank you. Your posts really explained why it is so. I understand the reasons now, but I can hardly agree those reasons are good ones (not arguing with you, as you pointed out, the reasons are weak for this case). As I pointed out before in my other post ("General subsequence function"), mixing abstraction with speed path is really a bad idea, and might be a classical example of what Rich called "complecting". In practice, it did not achieve what it tries to achieve either (one of the big complaints I read from the Web about Clojure is it is really hard to know the speed performance). For speed, the classical solution is: 1. Put good documentations on the functions, and the programmer needs to have some idea what data structure is fast/slow for what use. If the programmer does not have a clue, why would making "last" artificially slow on vectors help? Plus, whether one data structure is slower than the other for certain operations can also be an implementation detail that may change. 2. Use a profiler, so you can keep optimizing on the current hot spots. The above solution has no interference with abstraction. On Thursday, June 28, 2012 11:08:35 PM UTC-4, puzzler wrote: > > On Thu, Jun 28, 2012 at 6:59 PM, Tamreen Khan wrote: > >> Here's a somewhat old but still generally useful article on how Clojure >> vectors are implemented: >> http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ >> >> >> Vectors are optimized for random access, whereas lists are optimized for >> going through from the beginning to the end, which is exactly what the last >> function does. >> >> >> > This doesn't really address the underlying question. > > nth is a good example of a function that is fast for vectors, strings, and > arrays, and only for lists uses the slower sequential implementation. > > There's no technical reason that last couldn't do the same, dispatching on > the underlying type to have a more efficient implementation for data types > that support it. > > The real reason is this: With the glaring exception of nth, Clojure tends > to eschew functions with a fast path and a slow path, because programmers > shouldn't have to do deep semantic analysis of their code to figure out > which will get chosen. In this case, however, we're talking about a > function that is currently always slow. Surely it would be a win to make > it have a faster path in a large number of cases, right? Well, the > argument against that is eventually people would start to rely on it being > fast for so many collection types, and then get burned when somehow their > collection accidentally gets turned into a seq before last is called on > it. The theory is that it's better to force people to use a different > function call, namely peek, to retrieve the last element quickly from a > vector. > > Honestly though, despite David Nolen's claim that this design decision > will be obvious if you've coded enough Clojure, I've been programming in it > for around 3-1/2 years, and I think the argument behind this design > decision is a relatively weak one, so you are not making an unreasonable > request. In fact, the more I code in Clojure, the more I see that there > are a number of core functions that require significant semantic analysis > of the surrounding context to know how they will behave. Either Clojure > trusts that programmers can make determinations about the types of their > collections or it doesn't. Which is it? Well, I'd argue there's a large > body of evidence that under Clojure's current design, it's clear that you > better know what you're doing. If that's the case, why not go ahead and > make last fast when it can be fast? > > Nevertheless, I hope I've clarified the reasoning behind the current > design. Early Clojure design decisions have a lot of inertia, so as David > pointed out, this is very unlikely to change. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Hi, Am Freitag, 29. Juni 2012 05:26:07 UTC+2 schrieb tbc++: For instance, one such function I wrote tonight is called every-other > (returns '(1 3 5) if you hand it (1 2 3 4 5)) > user=> (take-nth 2 [1 2 3 4 5]) (1 3 5) Kind regards Meikel -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
So you recommend that "last" should be only function that accepts IPersistentStack *and* ISeqable and does the appopiate thing? Or are there others? On Thursday, June 28, 2012, Mark Engelberg wrote: > On Thu, Jun 28, 2012 at 6:59 PM, Tamreen Khan > > > wrote: > >> Here's a somewhat old but still generally useful article on how Clojure >> vectors are implemented: >> http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ >> >> >> Vectors are optimized for random access, whereas lists are optimized for >> going through from the beginning to the end, which is exactly what the last >> function does. >> >> >> > This doesn't really address the underlying question. > > nth is a good example of a function that is fast for vectors, strings, and > arrays, and only for lists uses the slower sequential implementation. > > There's no technical reason that last couldn't do the same, dispatching on > the underlying type to have a more efficient implementation for data types > that support it. > > The real reason is this: With the glaring exception of nth, Clojure tends > to eschew functions with a fast path and a slow path, because programmers > shouldn't have to do deep semantic analysis of their code to figure out > which will get chosen. In this case, however, we're talking about a > function that is currently always slow. Surely it would be a win to make > it have a faster path in a large number of cases, right? Well, the > argument against that is eventually people would start to rely on it being > fast for so many collection types, and then get burned when somehow their > collection accidentally gets turned into a seq before last is called on > it. The theory is that it's better to force people to use a different > function call, namely peek, to retrieve the last element quickly from a > vector. > > Honestly though, despite David Nolen's claim that this design decision > will be obvious if you've coded enough Clojure, I've been programming in it > for around 3-1/2 years, and I think the argument behind this design > decision is a relatively weak one, so you are not making an unreasonable > request. In fact, the more I code in Clojure, the more I see that there > are a number of core functions that require significant semantic analysis > of the surrounding context to know how they will behave. Either Clojure > trusts that programmers can make determinations about the types of their > collections or it doesn't. Which is it? Well, I'd argue there's a large > body of evidence that under Clojure's current design, it's clear that you > better know what you're doing. If that's the case, why not go ahead and > make last fast when it can be fast? > > Nevertheless, I hope I've clarified the reasoning behind the current > design. Early Clojure design decisions have a lot of inertia, so as David > pointed out, this is very unlikely to change. > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to > clojure@googlegroups.com 'clojure@googlegroups.com');> > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com 'clojure%2bunsubscr...@googlegroups.com');> > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
> Nevertheless, I hope I've clarified the reasoning behind the current > design. Early Clojure design decisions have a lot of inertia, so as David > pointed out, this is very unlikely to change. Well put. I would argue as well, that many functional languages I've come across take this stance: the language is opensource, you have namespaces, so feel free to make a namespace called mycore, that includes all you special versions of functions that you need, and then use that library for your projects. It doesn't take very long to define these special case functions and if they work for you, then just use them. For instance, one such function I wrote tonight is called every-other (returns '(1 3 5) if you hand it (1 2 3 4 5)) Does this function exist in clojure.core...not that I saw off-hand. Does it really matter though? Not really. I'll copy and paste these functions when I need them and go happily on my way. One of the biggest strengths of functional programming is that we can build up snippets of functions like this, and when we use then in our programs we can't tell that they weren't included by default. As Gerald Sussman said at the last Strange Loop conference: be a Libertarian when it comes to programming. Don't restrict others to your view of programming, liberty to you and to me and to everyone. You can code in your style, I'll code in mine, and Clojure (or Lisp in the case of the quote), shouldn't constrain me to its view of the world. Timothy -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Thu, Jun 28, 2012 at 6:59 PM, Tamreen Khan wrote: > Here's a somewhat old but still generally useful article on how Clojure > vectors are implemented: > http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ > > > Vectors are optimized for random access, whereas lists are optimized for > going through from the beginning to the end, which is exactly what the last > function does. > > > This doesn't really address the underlying question. nth is a good example of a function that is fast for vectors, strings, and arrays, and only for lists uses the slower sequential implementation. There's no technical reason that last couldn't do the same, dispatching on the underlying type to have a more efficient implementation for data types that support it. The real reason is this: With the glaring exception of nth, Clojure tends to eschew functions with a fast path and a slow path, because programmers shouldn't have to do deep semantic analysis of their code to figure out which will get chosen. In this case, however, we're talking about a function that is currently always slow. Surely it would be a win to make it have a faster path in a large number of cases, right? Well, the argument against that is eventually people would start to rely on it being fast for so many collection types, and then get burned when somehow their collection accidentally gets turned into a seq before last is called on it. The theory is that it's better to force people to use a different function call, namely peek, to retrieve the last element quickly from a vector. Honestly though, despite David Nolen's claim that this design decision will be obvious if you've coded enough Clojure, I've been programming in it for around 3-1/2 years, and I think the argument behind this design decision is a relatively weak one, so you are not making an unreasonable request. In fact, the more I code in Clojure, the more I see that there are a number of core functions that require significant semantic analysis of the surrounding context to know how they will behave. Either Clojure trusts that programmers can make determinations about the types of their collections or it doesn't. Which is it? Well, I'd argue there's a large body of evidence that under Clojure's current design, it's clear that you better know what you're doing. If that's the case, why not go ahead and make last fast when it can be fast? Nevertheless, I hope I've clarified the reasoning behind the current design. Early Clojure design decisions have a lot of inertia, so as David pointed out, this is very unlikely to change. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
Here's a somewhat old but still generally useful article on how Clojure vectors are implemented: http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/ Vectors are optimized for random access, whereas lists are optimized for going through from the beginning to the end, which is exactly what the last function does. On Thu, Jun 28, 2012 at 7:36 PM, David Nolen wrote: > On Thu, Jun 28, 2012 at 7:32 PM, Warren Lynn wrote: > >> This is an off-shoot subject from my last post "General subsequence >> function". >> >> I found people had similar questions before (one year ago): >> >> http://groups.google.com/group/clojure/browse_thread/thread/712711f049507c63/aea7cf438aa22922 >> >> As of Clojure 1.4, seems nothing changed, as "source" show here: >> >> user> (source last) >> (def >> ^{:arglists '([coll]) >>:doc "Return the last item in coll, in linear time" >>:added "1.0" >>:static true} >> last (fn ^:static last [s] >> (if (next s) >> (recur (next s)) >> (first s >> >> Any reason for that? Thanks. > > > Don't hold your breath. Assume that the language was designed after much > consideration. last is a sequence operation, not a collection operation. If > the distinction doesn't make sense, I suggest you explore the design > decision by writing some non-trivial Clojure code so you can arrive at your > own satisfying answer why this was done. Otherwise you'll just listen to > people repeat the same answer without hearing what is being said. > > David > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: Why cannot "last" be fast on vector?
On Thu, Jun 28, 2012 at 7:32 PM, Warren Lynn wrote: > This is an off-shoot subject from my last post "General subsequence > function". > > I found people had similar questions before (one year ago): > > http://groups.google.com/group/clojure/browse_thread/thread/712711f049507c63/aea7cf438aa22922 > > As of Clojure 1.4, seems nothing changed, as "source" show here: > > user> (source last) > (def > ^{:arglists '([coll]) >:doc "Return the last item in coll, in linear time" >:added "1.0" >:static true} > last (fn ^:static last [s] > (if (next s) > (recur (next s)) > (first s > > Any reason for that? Thanks. Don't hold your breath. Assume that the language was designed after much consideration. last is a sequence operation, not a collection operation. If the distinction doesn't make sense, I suggest you explore the design decision by writing some non-trivial Clojure code so you can arrive at your own satisfying answer why this was done. Otherwise you'll just listen to people repeat the same answer without hearing what is being said. David -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Why cannot "last" be fast on vector?
This is an off-shoot subject from my last post "General subsequence function". I found people had similar questions before (one year ago): http://groups.google.com/group/clojure/browse_thread/thread/712711f049507c63/aea7cf438aa22922 As of Clojure 1.4, seems nothing changed, as "source" show here: user> (source last) (def ^{:arglists '([coll]) :doc "Return the last item in coll, in linear time" :added "1.0" :static true} last (fn ^:static last [s] (if (next s) (recur (next s)) (first s Any reason for that? Thanks. -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en