import math,itertools as i
def f(k,p):
while(len(p)>k):
m=()
for r in i.combinations(p,2):
d=math.sqrt(sum(map(lambda x,y:(x-y)**2,*r)))
if d<m:m=d;x,y=r
t=p.remove;t(x);t(y);p+=[map(lambda g,h:(g+h)/2,x,y)]
print p
To discuss your specific issues, I prefer '+ to 'join for lists. I don't particularly have an opinion on how it looks in infix, because I don't like infix. Certainly
('(1 2 3) + '(4 5))
does look pretty ugly, but I like infix for basically everything. Your heuristic seems quite reasonable, though. What do you do about math? Do you still hold to it? For example, how would you write y(x) = mx+b:
(def y (x)
(+ (* m x)
b))
(def y (x)
(+ (m * x)
b)
(def y (x)
(m * x
+ b))
Or something else? I prefer the first one, but I know not everyone does.
I don't know if you saw the thread about infix in wart[1], but I can say:
def (y x)
(m*x + b)
All operators have the same precedence, but operators without whitespace have precedence over operators with whitespace:
(n * n-1)
The major drawback is, of course, that you can no longer use '* or '- in symbols. I use capitalization for globals and underscores in long names, and have been mulling camelCase.
(Wait, didn't someone check the pitchforks at the door?)
On a slightly different topic, I find '+ vs 'join really weird. They are only superficially similar; '+ actually reaches inside its arguments to muck with the cons cells:
(originally written up by me at http://zck.me/golf). 'mappend uses '+, so it's also weird. This behavior seems insane to me, and was the cause of some hard-to-track-down bugs in the code at the above link.
Interesting... doing that test in Arc/Nu returns "t" in both cases. I wasn't even aware of that issue but apparently "fixed" it accidentally.
By comparing Arc to Arc/Nu, it seems that the problem is that Arc returns a new list that is 'nil terminated, whereas Arc/Nu uses () for 'nil, so it doesn't have to do any conversion.
It took me a while to understand why this should be. cartesian calls mem which calls testify, and testify uses is.
(def testify (x)
(if (isa x 'fn) x [is _ x]))
I think it should use iso. Can y'all think of any reasons that's a bad idea?
If we make that change, I'm not too concerned about whether + is like join. A caller of either shouldn't typically care whether they create new conses or not.
There'll totally be places where it matters whether something conses or not. But that should reflect in the (longer) name, IMO. cons-minimal-append, mayhap?
Yeah, definitely. The reason for the bug is because the Arc compiler uses Racket's "append" to do the join, which means it first needs to convert the Arc list to a Racket list, do the append, then convert back to an Arc list.
So there's two ways to fix this:
1) Change Arc to be like Arc/Nu, so that it doesn't need to do the conversion. I don't expect this to be too hard.
2) Write + in Arc, and have it call "join" when the first argument is a list. Then there's no discrepency between the two.
I actually dislike how the overloaded + is written in Arc, so I think having it call join instead would be great.
If the language used immutable conses, it still shouldn't have to change every cons. The issue here arises not because the list you pass in has different conses than the list returned, but because the elements of the list you pass in have different conses than the elements of the list returned.
Let's say we call (+ '((1) (2))). I'll draw the list this way:
To my brain, there are two "kinds" of conses in the list: those that make up the top-level list itself, and those that make up the elements.
top-level ( , . , )
conses | `-------> ( , . nil)
| |
| |
| |
element v v
conses (1 . nil) (2 . nil)
And here's what I think should happen in the call to +
these conses ( , . , )
can change | `-------> ( , . nil)
| |
| |
| |
these conses v v
shouldn't (1 . nil) (2 . nil)
Similarly, if you call
(+ (list (obj 1 2)))
Would you expect the hash table to have its elements copied into a new hash table? No, the same hashtable should be shared between the calling list and the returned list, even if the list itself has different conses. And indeed, this is the case (thanks again, evanrmurphy, for tryarc):
So the first of your element conses has to change too.
But you are right that not all the conses need to change. I finally understood Pauan's diagnosis, that it was arc copying nil vs () terminated lists. I've been against that 'feature' for a long time. My private fork just stays with () terminated lists: http://github.com/akkartik/arc
Sorry, I think we've both managed to confuse each other. + and join on a single arg is just the identity function, right? Aren't these the cases we care about?
arc> (+ '(1 2) '(3 4))
(1 2 3 4)
My argument was that in the presence of mutable conses all the conses would have to change. After your response I'm correcting that to "all the outer conses (except in the last arg)".
Does this seem right? I was reading your previous comment without one wrapping set of parens.
Yes, the outer conses all have to change, except for the last one. But the inner conses don't, and they are changed right now. That, specifically, is my problem with '+ . If you call (+ '(((((((1))))))) '(((((((2)))))))) , you shouldn't have to change fifteen conses, just one or two.
akkartik: "I finally understood Pauan's diagnosis, that it was arc copying nil vs () terminated lists. I've been against that 'feature' for a long time."
Yes, but Arc/Nu manages to implement that Arc feature without conversion, so I don't consider it a problem with the feature, but a problem with the implementation.
---
akkartik: "+ and join on a single arg is just the identity function, right?"
Yes, but Arc does the conversion even if you pass in a single argument. So another possible solution to the problem is to change Arc to return the first argument unchanged when passed in a single argument.
---
zck: "If you call (+ '(((((((1))))))) '(((((((2)))))))) , you shouldn't have to change fifteen conses, just one or two."
Yes, you shouldn't have to. Arc uses ar-nil-terminate and ac-niltree to do the Arc->Racket->Arc conversion. ar-nil-terminate does a shallow copy, but ac-niltree does a deep copy. Simply changing ac-niltree wouldn't work, because I'm pretty sure other stuff depends on the deep copy.
However, the Arc compiler could be changed so that + uses a shallow version of ac-niltree. That's an interesting idea: how much stuff in the Arc compiler is currently using the deep ac-niltree when it could instead use a shallow ac-niltree?
"Arc uses ar-nil-terminate and ac-niltree to do the Arc->Racket->Arc conversion. ar-nil-terminate does a shallow copy, but ac-niltree does a deep copy.
However, the Arc compiler could be changed so that + uses a shallow version of ac-niltree."
That's the essence of the bug, as I see it. This fix is much shallower than the other fixes discussed, so this fix would make the most sense in a minimally updated variant of pg's Arc.
Should Anarki go for shallow or deep improvement? I've advocated shallow in the past, but now I'm thinking Arc oughta follow through on its promise to "break all your code," which of course means the entire network of hacks, libraries, help resources, and alternate language implementations we've built up so far. It would be nice to see Anarki become a fork of Arc/Nu and undergo deep improvements, without losing the Arc flavor.
"I feel uneasy about the shallow change to +; I'm sure the same bug exists in some other functions since deep niltree is the default."
From what I can see, there are only three places in the pg-Arc code where 'ac-niltree traverses too far, and they're all in ac.scm. Two are the definitions of + and ar-+2, and one is a misleading comment:
; Arc primitives written in Scheme should look like:
; (xdef foo (lambda (lst)
; (ac-niltree (scheme-foo (ar-nil-terminate lst)))))
; That is, Arc lists are NIL-terminated. When calling a Scheme
; function that treats an argument as a list, call ar-nil-terminate
; to change NIL to '(). When returning any data created by Scheme
; to Arc, call ac-niltree to turn all '() into NIL.
; (hash-table-get doesn't use its argument as a list, so it doesn't
; need ar-nil-terminate).
From another point of view, there are only a few places where 'ac-niltree probably needs to be recursive. Those are in the definitions of 'ac-call, 'ac-mac-call, and 'ac-macex, where they deal with quotation and macroexpansion, the two ways literal code is made available to Arc programs.
The other uses of 'ac-niltree are in 'ar-coerce (string to cons), 'dir, and 'timedate, where the lists are flat anyway.
I only looked for uses in pg-Arc, not any code that's been derived from it.
"Confusing that you're using deep/shallow with two meanings in the same comment :)"
Whoops! My comment was originally going to stand on its own, but I adapted it into a reply when Pauan got to what I wanted to say first. :) I didn't notice the word overlap.
Arc/Nu manages to implement that Arc feature without conversion
Hmm, can you elaborate on how it manages this? Is it just printing nil, but otherwise leaving the actual cons cells ()-terminated? (That option has probably been discussed multiple times: http://arclanguage.org/item?id=3094. I'm sure I mentioned it too at some point.)
"Hmm, can you elaborate on how it manages this? Is it just printing nil, but otherwise leaving the actual cons cells ()-terminated? (That option has probably been discussed multiple times: http://arclanguage.org/item?id=3094. I'm sure I mentioned it too at some point.)"
Yes. And then "nil" is a global variable that is bound to (). I also have to do a few other things like changing quote so that it changes the symbol "nil" to (), but overall it isn't that hard to have perfect Arc compatibility, even without doing the conversion.
16 lines total. Probably less than it would have taken to do the 'nil -> () conversion. But Arc can't tell the difference, unless I've overlooked something.
"I also just noticed: It is _utterly_ insane that niltree converts () to nil, while nil-terminate does the opposite."
It's called "tree" because it recurses on the car. In other words, it traverses sublists. As for why it's called "nil", well, I guess that's because you can't use () in the name without using || quotes. I'd call them "nil->null" and "null->nil". Or perhaps "arc->racket" and "racket->arc".
Sometimes I feel like I'm the only person who actually prefers parentheses. They just seem so much more useful than having to mentally parse indentation, or what kind of parens are there, or whether there's a space between the function name and its arg list.
Some of these suggestions are to get people to kneejerk less when they see Lisp code, but some parts are presented as being better for existing Lisp coders.
I can relate with wanting to be more accessible to non-lispers, but I primarily want to search for better ways to write programs. I'm not in the education business. I'm in the invention business.
Parsing indentation is a muscle just like parsing parentheses. Some programmers have experience with one, some have trained their visual cortex with the other. Whichever side you're on, it's good to leave one's comfort zone. Otherwise we risk being ruled by our languages and tools.
---
Checking for the space between function name and its arglist is a (minor) burden for the writer, but it seems painless for the reader. I think that's the right kind of decision. I'm happy to put the writer through some hoops if it makes reading easier.
The primary problem with Java's verbosity isn't that it's too much trouble to type. It is that it leaves readers to sip at the codebase through a straw.
Again, I'm not a fan of readable's specific approach. But I am totally on board with the general idea of looking to improve on s-expressions. I'm sure there can be new features out there that are better for existing Lisp coders.
I do agree that s-expressions shouldn't be set in stone. But I'm not sure that these specific suggestions are useful. Maybe I'm being a Luddite in regards to change.
I guess I'm on board with the curly-infix expressions for math. Maybe. I do hate having to mentally parse through lines like
{{1 * 2} + {3 / 4}}
To get "oh, this is adding two things together". But ok. Maybe. But the minute I have to distinguish between the form
... fun(arg1 arg2 arg3) ...
and
... fun (arg1 arg2 arg3) ...
I'm done. Granted, I haven't actually used neoteric expressions -- and I should try them -- but until I do, this style looks much less readable to me. I disagree that it's painless; it seems actually quite painful to me. It sure is closer to Algol-style coding, but it's just asking you to confuse the two. And that's easily done.
Fair enough. You don't typically see the no space style in lisp, so it stands out for me. But you're right that it's not as cut and dried as I thought.
Whenever I see things like the linked presentation (turns out I've seen it before), I can't help but think it's a solution in search of a problem. Simple parsing & evaluation models lead to expressive languages, and (I intuit) that's why their notations stick around despite people's efforts. For time immemorial, projects like these try to take a simple, consistent notation and pile on an abominable number of special cases with line noise more offensive than just parentheses [1]. It's not only unfitting for Lisps, but it's limiting for language design. There's only so much you can do with abbreviations, but soon enough there's feature-creep. I see that in his estimation (http://sourceforge.net/p/readable/wiki/Retort/), the special cases are sparing. But really? He needs three kaleidoscoping levels of syntax, knee-jerks to using the different brace types to supply soothing Algol-isms, introduces an indentation scheme that needs clarification regarding edge-cases with traditional syntax, and still finds a way to need special characters with special rules for "advanced" features. I guess we can agree to disagree...
In the end, I think it's a mistake trying to make Lisp notation something it's not. Much better is trying to improve what you've got within the structure of the language, like Arc turning
(let ((a 1) (b 2))
(+ a b))
into
(with (a 1 b 2)
(+ a b))
People are drawn to the idea of finally making Lisp "accessible" (I guess fixing society's use of infix notation is harder :P) while still retaining homoiconicity. Yet most seem to forget that homoiconicity requires simplicity, not Lisp syntax. People get stuck thinking inside the Lisp box, but again, simple parsing & evaluation models lead to expressive languages. For instance, combine a stack machine model (http://docs.factorcode.org/content/article-evaluator.html) with a simple parsing algorithm (http://docs.factorcode.org/content/article-parser-algorithm....) and you get a homoiconic language. Of course, it's a postfix language, so its math is unparsable to mere mortals...
[1] I admit he has a point about existing abbreviations that I'm simply used to, like quote/quasiquote/comma/splice and dotted lists. I think where those notations have stood the test of time is that they're subtle. I can use the quote family and the code still looks like Lisp, instead of looking like Lisp trying to look like C.
shader, fallintothis, will you email me? Email in profile. I'm going to post my solution to infix :) in a few days or weeks, and I would like to ping y'all to make sure I can get your criticisms.
(I'm not sure if you come here often or go periods without visiting.)
I think some moderate use of parentheses is okay, but I don't really like using them everywhere. Though, I wouldn't really mind an Arc dialect that had good syntax for functions and a Nulan-style type system, even if it did use parens.
I believe this is a "real" qsort. It's way more verbose than I expected, but I did code it on two nights hours after I should have gone to bed. I'm sure I could name some things better. Maybe I will later.
Corn in rows; OO? I'm here, aren't I?; emacs is the piece of software I love the most.
Unfortunately, I'm not enough of a math person to understand everything Tilly was saying (even though one of my majors for my Bachelor's degree was math), so I don't know which I am, nor can I really guess. I hated my Real & Complex Analysis class, but it was intended as the hardest course in the major, if I remember correctly. Perhaps it's more accurate to say I struggled with it.
To take a minor point and nitpick it, I wonder if he didn't get Emacs and vim reversed: one of the points of vim -- as I understand it; I've only gone through a bit of vimtutor -- is that the same blocks can be composed in separate ways. If you know that 3j means "move down three lines", then d3j means "delete the next three lines". That seems more like algebra than analysis.
I'm not an expert in making large-sized functional programs, but it seems to me that needing to update variables in functional code is a code smell. Wouldn't you be better off recursing or calling a different function at that point?
