Page 1 of 1

Deep-map-iter

Posted: Sun Mar 01, 2009 2:59 am
by hoven
Hi.Im supposed to program function Deep-map whitch goes thru list apllying funcion given to it by argument and keeping the list structure.Both iterativly/recursivly. Recrsively it was really easy but i cant find the way to revrite it to iterative function :? . I could really apreciate help. this is how it should work (deep-map #'oddp '(1 2 (((3) 4)))) -> (T NIL (((T) NIL))). Thx for any help.

Re: Deep-map-iter

Posted: Sun Mar 01, 2009 2:08 pm
by Jasper
Hi. Firstly, many of us here prefer full sentences and typo-checked writing. Secondly, some might feel that you're asking us do do your homework. I guess the latter isn't so, because it is only help you are asking.

If you already have the non-recursive part, maybe you should post it so we can comment on it.

As for the non-recursive part, you will need a list to play stack. This stack is usually handled by common lisp itself, but you will have to make it yourself if you want it non-recursively. Every time you go down a list, your stack gets an extra layer. Note that lisp does not create a stack every time the function itself is called from a function, sometimes it can do optimization, like tail recursion. Basically we do tail recursion manually when we write the (partially recursive, partially iterative) function:

Code: Select all

(defun deep-map (fun list)
  (loop for el in list collect (if (listp el) (deep-map fun el) (funcall fun el)))
In order to do this iteratively you will have to do the stack stuff whenever is deep-map is called inside the loop there. (You could do the loop with do, dolist too, of course.)

Re: Deep-map-iter

Posted: Fri Mar 13, 2009 11:19 am
by Wodin
Jasper wrote:Hi. Firstly, many of us here prefer full sentences and typo-checked writing. Secondly, some might feel that you're asking us do do your homework.
Have you heard of Muphry's Law ;)

Re: Deep-map-iter

Posted: Fri Mar 13, 2009 5:16 pm
by Exolon
Wodin wrote:
Jasper wrote:Hi. Firstly, many of us here prefer full sentences and typo-checked writing. Secondly, some might feel that you're asking us do do your homework.
Have you heard of Muphry's Law ;)
Hah, that's good! At first I thought you'd typoed "Murphy" and expected to see a Wikipedia-style 404 :D