Interesting problem for me

[Lutz]

The fast methods 9,3,2,5,6 all work the list sequentially and assemble the new list sequentially.



The destructive methods 8,4,1 all do indexed access in the list using indexing, which gets slower the more they have to count into the list in the (lst $idx) expressions.



I could imagine the only way to do it destructively fast is using some form of 'replace', which works the list sequentially and changes the found element directly in place as it goes.



The difference will be smaller or can be neglected when dealing only with a few dozen elements, or when using arrays in 8,4,1.

[Kazimir Majorinc]

Now recursive algorithms are not used since they could cause serious problems to the stack area.

Only relatively small set of recursive functions can be tail-call optimized. Typically, recursive call can be eliminated only by introduction of a new data - some kind of stack. So, efficiency is about the same, just it is much harder to write non-recursive version. Fibonacci

f(0) = f(1) = 1

f(n) = f(n-1) + f(n-2)[/list]can be rewritten on non-recursive way easily. But with only slight change, for example,

f(x) = 1  for  -1<x<1

f(y) = f(y-1-|sin y|) + f(y-1-|cos y|)
[/list]recursive version is still easy, but non-recursive version is much more complicated, and probably only for a constant factor more efficient.

[newdep]

just to fillup the solutions...





This topic got me thinking the whole week actualy because i also had the

same though once, doing it all functional,... The result is not always a

charming clean code line...The results from this topic are very nice and

creactive.. (the use of 'bits and the use of replace..nice ;-)



The original statement of doing this without a loop but only functional is

not matching the procedure ;-) This can only be solved with at least 1

loop...(as map dolist etc are macro loops)



The old fasioned 'for..not listed here but yet actualy the fastest..irrc..





(setq L '("string 1" "string 2" "string 3" "string 4" "string 5" "string 6"))



(for (l 0 (dec (length L)) 2) (setf (L l) (upper-case (L l))))



("STRING 1" "string 2" "STRING 3" "string 4" "STRING 5" "string 6")



Replacing the 0 with 1 or 2 indicates the start position.. with a step 2..







I tried playing with 'index 'filter 'clean and ref-all but they all get very

bigish in code.. Yes I must admit..'for is not the nicest loop on the block

but its an effective one..we should not neglect it ;-)

[ale870]

@newdep your observation is a good point, since in every other algorithm we are obliged to check every value,m then we need to take/eliminate a condition.

In the FOR...STEP statement, we really by-pass the conditions, and we made only the half of the checks.

It seems very strange that a  procedural algorithm can manage this in a way not that cannot be implemented in a functional way.

I think we could avoid to use FOR..NEXT only if we could implement a kind of index, example:

Code Select Expand

(setq i 1)
(inc i 2)


This could be a good way without using real for/loops statements.

[newdep]

here it is ->



(map (fn(x) (setf (Q x) (upper-case (Q x)))) (index = (map (fn(x) (% x 2)) (index != Q))))



assuming Q is a string based list...



("a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o" "p" "q" "r" "s" "t"

 "u" "v" "w" "x" "y" "z")



would result in ->



("A" "b" "C" "d" "E" "f" "G" "h" "I" "j" "K" "l" "M" "n" "O" "p" "Q" "r" "S" "t"

 "U" "v" "W" "x" "Y" "z")

[ale870]

Good solution newDep!

I love this topic, since I found how flexible is newLisp!

[Lutz]

how about this one:

Code Select Expand

(let (flag) (map (fn (x) (if (setq flag (not flag)) (upper-case x) x)) Q))

[newdep]

Aaaa smooth one Lutz!



Even 1 lambda less ;-)

[Lutz]

Last not least the classic full functional, recursive solution to this problem. Slow as hell, but no side effects when flipping the flag!

Code Select Expand

(define (foo lst flag)
  (if (empty? lst) lst
    (cons (if flag (upper-case (first lst)) (first lst))
          (foo (rest lst) (not flag)))))

you call it with either (foo Q) for starting with ods or (foo Q true) for stating with evens.

[ale870]

Lutz, you cracked my mind!!!

[Kazimir Majorinc]

The main reason it is slow is not in recursion itself, but in its combination with rest function that returns copy in Newlisp.

[ale870]

The main reason it is slow is not in recursion itself, but in its combination with rest function that returns copy in Newlisp.

Is there a way to work like Rebol? It can return a "pointer" of a list, but it is referenced to the original list. In fact if you "navigate" in the list using that "pointer", you can find all list values.



I say this because new newLisp version 10 was optimized to work/return many pointers, instead the copy.

So REST function could return a reference to the second element of the list, not its copy.

[newdep]

No newlisp does not use indexes like rebol does, which I sometimes like and sometimes dislike..

..So you have to create you own indexing regarding counting..

[ale870]

But newLisp could get a function, similar to rest, but returning a reference to the second element:

Code Select Expand


(define (rest-ref argList)
    (1 argList) )


But in this way it works with a copy... see here:

Code Select Expand


> (push 'Z (rest-ref a))
(Z 8 7 6 5)
> a
(9 8 7 6 5)


I think we need a way (using setf?) to return a reference.

[Lutz]

Currently things works like this:

Code Select Expand

(set 'a '(9 8 7 6 5))
(push 'Z (rest a)) => (Z 8 7 6 5)

With 'a' unchanged. If we could push on (rest a) as a reference the result would be:

Code Select Expand

a => (9 Z 8 7 6 5)

Which is not (Z 8 7 6 5). if this is what you want, do this:

Code Select Expand

(push 'Z a 1) => (9 Z 8 7 6 5)

and have 'a' changed.