I wrote this function for converting numbers in base-N to decimal.
(defun in-decimal-base (n base) (let ((tmp 0) (digit 0) (result 0)) (do ((i 0 (1+ i))) ((<= n 0)) (setf tmp (mod n (expt 10 (1+ i)))) (setf digit (/ tmp (expt 10 i))) (setf result (+ result (* digit (expt base i)))) (setf n (- n tmp))) result))
And you use it as:
> (in-decimal-base 1020 7) 357
> (in-decimal-base 10110 2) 22
etc.
Not being a LISP guru, can't think of a "tail recursive" version immediately--assuming it'd be any better in this case. Still, it feels so... imperative and inelegant -- those stacked "setfs" look awful. (Please, no wisecracks like "what makes you think 'imperative => inelegant'?" etc.)
Aside: if you write low-level code you might as well get rid of the exponentiation, since it's unnecessarily expensive (hint: (expt 10 i) at loop iteration i = (* 10 the-same-expression-one-iteration-before)).
> (setf result (+ result (* digit (expt base i)))) > (setf n (- n tmp))) > result))
> And you use it as:
> > (in-decimal-base 1020 7) > 357
> > (in-decimal-base 10110 2) > 22
> etc.
> Not being a LISP guru, can't think of a "tail recursive" version > immediately
Don't worry about it (at least not for the moment) -- a loop rewritten as a tail recursion is still a loop and not necessarily better for it (no matter what people will try to brain wash you into). Real improvements in conceptual elegance come from replacing loops with higher order constructs.
> --assuming it'd be any better in this case. Still, it feels > so... imperative and inelegant -- those stacked "setfs" look awful. > (Please, no wisecracks like "what makes you think 'imperative => > inelegant'?" etc.)
> Any suggestions for improvement?
I think the following is a good way to conceptualize what's going on (doesn't necessarily make for an efficient implementation, but you can always rewrite for speed when needed later):
Operators in boxes are REDUCE's those without are MAPCAR's. The first -> is an UNFOLD (not predefined in common lisp and the opposite of a reduction, if you want), but you can forget about that for the moment -- reductions and mappings are more important.
Some more hints (lower-case functions you have to write yourself):
(1 0 2 0) = (decimal-digits 1020) ; first implement it however you like, then ; google unfold (3 2 1 0) = (REVERSE (iota (LENGTH '(1 0 2 0))))
cheers
'as
p.s. You might get better answers to common lisp related questions in comp.lang.lisp, however there tends to be a strong anti-functional bias there. You could also switch to scheme and ask in comp.lang.scheme -- scheme is of even more dubious practical value than common lisp, but if you want to learn functional programming paradigms with a lispy language, it has some social and technical advantages. You might also want to google SICP.
p.p.s. If you're not familiar with reductions, it's really easy:
(reduce '+ (list a b c d)) == a + b + c + d ; insert operator between list elements (reduce '+ ()) == 0 ; neutral element of operator
You're right, Alex. I knew there was something too long-winded about it. I think this should do:
(defun in-decimal-base (n base) (let ((result 0)) (do ((exp 1 (* base exp))) ((<= n 0)) (setf result (+ result (* (mod n 10) exp))) (setf n (truncate n 10))) result))
One could make this recursive--one being yours truly, just to see how it can be done.
(defun in-decimal (n base) (in-decimal-helper n base 0))
(defun in-decimal-helper (n base i) (if (= n 0) 0 (+ (* (mod n 10) (expt base i)) (in-decimal-helper (truncate n 10) base (1+ i)))))
But I guess a solution based on your suggestion is the most LISP-like:
(defun digits (n) (if (= n 0) nil (cons (mod n 10) (digits (truncate n 10)))))
(I couldn't find IOTA in my CL implementation so I grabbed one from Google Code search, and I chose to name this last version in George Costanza (of Seinfeld) fashion. :-D)
BTW I looked up "unfold," but after about half an hour on Google, the world started to unfold before my eyes without any results. If you know any implementation, please do quote its code here, and I'll have a look how this can be coded with it.
--
I know this function is pretty trivial, and--more importantly--to get the value of 1020 in 7 base, all I have to do is use "#7r1020" in CL. But that's not the point. I'm just trying to map my imperative mind to the paradigmatic thinking of LISP.
> I wrote this function for converting numbers in base-N to decimal.
> (defun in-decimal-base (n base)
> [snip]
> Not being a LISP guru, can't think of a "tail recursive" version > immediately--assuming it'd be any better in this case. Still, it feels > so... imperative and inelegant -- those stacked "setfs" look awful. > (Please, no wisecracks like "what makes you think 'imperative => > inelegant'?" etc.)
> Any suggestions for improvement?
> -- Ken
Tail recursion isn't terribly difficult to do: in fact, you don't even need to understand the problem in order to translate code into that form. The above is a perfectly acceptable imperative approach (though certainly not optimized). Higher order constructs have already been mentioned, and fold/unfold is a very attractive method for doing this. So I'll just offer a very direct translation into a tail-recursive call.
(defun in-decimal-base (n base) (labels ((recurser (result i n) (if (> n 0) (let ((tmp (mod n (expt 10 (1+ i))))) (recurser (+ result (* (/ tmp (expt 10 i)) (expt base i))) (1+ i) (- n tmp))) result))) (recurser 0 0 n)))
What this does is define a recurser function. The trick is that everything required for the next step of the computation is passed as a parameter to this function. The variable "digit" vanished, because it was only an intermediate step in calculating the next result: it's computation has been inserted directly into the code for result. "tmp" remains only because it's computation would have to be performed twice without.
It doesn't actually require an understanding of how the algorithm works in order to translate most imperative loops into tail-recursive constructs: just take every value needed for the next stage of the computation and make it a parameter to the recurser.
> You're right, Alex. I knew there was something too long-winded about it. I > think this should do:
> (defun in-decimal-base (n base) > (let ((result 0)) > (do ((exp 1 (* base exp))) > ((<= n 0)) > (setf result (+ result (* (mod n 10) exp))) > (setf n (truncate n 10))) > result))
> One could make this recursive--one being yours truly, just to see how it > can be done.
> (defun in-decimal (n base) > (in-decimal-helper n base 0))
> (defun in-decimal-helper (n base i)
You can use LABELS for helper functions (it has the advantage that you won't need to pass BASE and that it keeps the global namespace clean -- it has the disadvantage that it makes testing and debugging them harder).
> (if (= n 0) > 0 > (+ (* (mod n 10) (expt base i)) > (in-decimal-helper (truncate n 10) base (1+ i)))))
> But I guess a solution based on your suggestion is the most LISP-like:
> (defun digits (n) > (if (= n 0) > nil > (cons (mod n 10) (digits (truncate n 10)))))
APPEND should always set off your warning bells. This code is very inefficient -- quadratic rather than linear in x. This is a typical newbie mistake (I'm suprised you found this code in a search) -- the standard idiom is to use CONS and finally (N)REVERSE instead (or LOOP's COLLECT).
This doesn't work -- it might appear to, but the consequences of the code above are really undefined (and what it will do in most implementations is not what you likely expect, although it appears to work the variables will be global and lexically scoped). You need to define a variable with LET (or DEFVAR etc.) before you can SETF it. The idiomatic way to write this is just:
> (reduce '+ (mapcar #'(lambda (x i) (* x (expt base i))) digs exps)))
As an aside, whilst the #' can essentially always be safely omitted in front of (lambda ...) (no change in meaning), it is generally better to write (reduce #'fun ...) rather then (reduce 'fun ...) -- you need not worry what the difference is at this stage, #' will always do what you want and ' might not.
> (I couldn't find IOTA in my CL implementation so I grabbed one from Google > Code search, and I chose to name this last version in George Costanza (of > Seinfeld) fashion. :-D)
> BTW I looked up "unfold," but after about half an hour on Google, the > world started to unfold before my eyes without any results. > If you know any implementation, please do quote its code here, and I'll have > a look how this can be coded with it.
Try this:
(defun unfoldl (seed next collect till &optional (tail '())) (cond ((funcall till seed) tail) (:else (unfoldl (funcall next seed) next collect till (cons (funcall collect seed) tail)))))
