Deep-map-iter

Discussion of Common Lisp
Post Reply
hoven

Deep-map-iter

Post by hoven » Sun Mar 01, 2009 2:59 am

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.

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

Re: Deep-map-iter

Post by Jasper » Sun Mar 01, 2009 2:08 pm

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.)

Wodin
Posts: 56
Joined: Sun Jun 29, 2008 8:16 am

Re: Deep-map-iter

Post by Wodin » Fri Mar 13, 2009 11:19 am

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 ;)

Exolon
Posts: 49
Joined: Sat Jun 28, 2008 12:53 pm
Location: Ireland
Contact:

Re: Deep-map-iter

Post by Exolon » Fri Mar 13, 2009 5:16 pm

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

Post Reply