This is readable and just fine if you are handing it in for a class.
The benefit of the pascal triangle is that through a simple number triangle you can find binomial coefficients. It has since been redefined as the binomial coefficient. But historically it was interesting because it could provide binomial coefficients through simpler math than n choose k.
If you have to calculate the whole triangle, then I would probably recursively define it and calculate it that way. (Pascal's formula shows that each subsequent row is obtained by adding the two entries diagonally above) Instead of constantly calculating it at each position with n choose k.
I guess you could use the binomial coefficient definition and memoize the choose and factorial. Memoization alone is what is saving you here. Luckily arc provides this functionality.
Anyways, this is a fun problem. Much easier to solve elegant and efficiently in arc, thanks to memoize. Try this in an imperative language and you'll definitely have to fall back on the recursive definition because all those factorials and chooses will kill the performance. There is one other benefit to using the recursive definition - you won't use any extra memory memoizing factorials. Instead you'll just have the chooses appearing in the tree.
A bit nit picky, but memoization alone won't make the solution optimal, since you are dealing with very large numbers. n! has O(n log n) digits, so in the limit it will take O(n log n) time just to calculate n! from n * (n-1)!.
But I don't know about your big-O estimate. Since the triangle is constructive and you are memoizing calculating n! from n * (n - 1)! will take O(1). It'll be the cached (n - 1)! value times n.
Doing a single multiplication is not O(1) when the numbers have more than a constant number of digits. I'm not precisely sure how long multiplying large numbers takes, but it's at least linear in the number of digits involved. And (n-1)! has O(n log n) digits.
No prob. Sorry if I go on at too much length here ;-)
So a useful formula for counting digits is, a positive integer x has floor(log10(x)) + 1 digits. You can figure this out yourself by thinking, where does the digit-counting function bump up a notch? At 10, 100, 1000, etc. So asymptotically the number of digits in x is O(log x).
So n! has O(log n!) digits. The trickier part is figuring out or knowing that O(n log n) = O(log n!). Using log ab = log a + log b you can expand out the factorial:
In case the last step isn't clear, you can do this splitting-in-half bounding trick. Since each element in the sum is less than log n you can bound from above with
log n + log (n-1) + ... + log 2 + log 1 < n log n
And if you just take the larger half of the list you can bound from below with
Usually, it seems to be either (n log n) or (n log n) - 1 digits.
And usually in this case I would leave of the O, as that usually refers to the performance of an algorithm in time or space. I suppose you could construe the number of digits to be "space" but multiplying O(n) numbers doesn't make that much sense.
You just need to properly set up an IDE. Personally I use emacs and slime. Though there are other options. I have autocomplete that works better than intellisense (visual studio). My experience is intellisense in VS2008 schools eclipse.
It's doable you just have to put in some time to learn emacs / slime or a similar lisp IDE.
Is there a list of the syntax sugar we have so far?
I remember being told about table!key being equivalent to (table key), and : is used to string functions together (although I keep forgetting it works from inside out).
I'm not sure what . offers, except that you can do *(3 . + . 5) with it. The example of foo.bar being equal to (foo bar) isn't helping much either ;)
Note that you can also use : to compose multiple functions.
The Anarki also has, if you include "ssyntaxes.arc":
11. x..y, which is the same as (range x y), and x..y..z, which is the same as (range x y z) (a range from x to y with step size z).
12. f//g, which is the same as (orf f g); this returns a function where ((orf f g) x y ...) is equivalent to (or (f x y ...) (g x y ...)). This can be used with as many functions as you want.
13. f&&g, which is like f//g but uses andf instead of orf, so the function is equivalent to (and (f x y ...) ...).
14. typ?, which returns the function (fn (x) (isa x 'typ)).
15. User-definable ssyntax, so you can add your own!
Also, note that ssyntax only works with variables and integers, not with literal lists or function calls.
And your example of using . for infix is actually a holdover from mzscheme, and not used anywhere particularly; its existence in Arc seems to be accidental.
There is no doubt that you'll be able to get arc to do it with enough time and energy. But this use of variables seems un-functional. Or otherwise not in the spirit of lisp. Have you considered a hash table where the key is the variable name?
This is coming from someone that writes VB.NET and C# at work. I understand the need for variables. But, I also know that I use very few when writing lisp.
It's risky to say "you should do X" or "you shouldn't use Y" when talking about using programming languages, because they don't look at the problem being solved. Using variables may be a very natural way to approach problem A, while they'd be very clunky for problem B.
I am asking because it is a common mistake when moving from an imperative language to a functional language. I know I made the mistake of trying to use many variables when I first started writing functional code. I was asking so that I could help out.
I never said "you shound do ..." or "you shouldn't use ...".
I have no problem with people using whatever style or approach that they want. If you want to write arc with gotos and a bunch of variables, go for it. I just wanted to help this arc coder out.
That's not quite true. You would not see Lisp code written as though it were assembly, full of gotos and working with a finite number of registers, to take an extreme example. Lisp is a multiparadigm language, but it is heavily functional. As such, writing imperative code is not generally advisable ("not in the spirit of Lisp"), but is possible. Similarly, code with such a heavy use of variables is likely unfunctional, and thus would similarly be outside the "spirit of Lisp". Yes, you can do anything you want in Lisp (cf. the Church-Turing thesis), but it may not be advisable ("in the spirit of Lisp"). Again, for instance, if you want to work in a stack-based manner, it would probably be advisable to either (1) rework your code, or (2) switch to a stack-based language like Factor.
This is not unique to Lisp: if you want to write a tail-recursive, functional, list-based program in C, that's probably not a good idea. You can, but since C is optimized for iteration (with many implementations not even supporting tail call elimination) and for imperative programming (it lacks closures and anonymous functions), and since memory management in C is…clunky…you would be better off (1) reworking your code, or (2) switching to a more functional language with lists and tail call elimination, such as a Lisp.
In short, yes, as a Turing-complete language, Lisp can do anything. And as a multi-paradigm language (with macros), it can do a good job at performing a given task in any way. But it has strengths, inclinations, and intentions, which together do comprise what could be called a "spirit of Lisp".
