Interesting problem for me

[cormullion]

Well, I wasn't originally going to post this, but I'm off sick today ... if you forgive me mangling your code, guys, just to make it fit my approach, and don't for a moment think that this is rigourous or scrupulously fair...

Code: Select all

(set 'source-list .... your list of strings goes here... 

(define (method1 lst)
    (map (fn (x) (setf (lst x) (upper-case (lst x))))  
         (sequence 0 (- (length lst) 1) 2))
    lst)
         
(define (method2 lst)
  (map (fn (x y) (if (= (/ x 2) (div x 2)) y (upper-case y))) 
    (sequence 0 (- (length lst) 1)) 
    lst))

(define (odd? num) (= "1" (last (bits num))))
(define (odd? num) (= (& num 1) 1))

(define (method3 lst)
  (map (fn (x) (if (odd? $idx) (upper-case x) x)) lst))

(define (method4 lst)
  (dolist (x lst) (if (odd? $idx) (setf (lst $idx) (upper-case $it))))
  lst)

(define (method5 lst)
  (flat (replace '(+) (explode lst 2 true) (list (upper-case (first $it)) (last $it)) match)))

(define (method6 lst)
  (apply append (map (fn (l) (list (upper-case (first l)) (last l))) (explode lst 2 true))))

(set 'other-one (lambda (x y z) 
                        (cond ((= x y) z) 
                              ((= x z) y)))) 

(define (method7 lst (first-case upper-case))
    (if (empty? lst) (list)
        (cons (first-case (first lst))
            (method7 (rest lst)
                 (other-one first-case
                  lower-case
                  upper-case)))))

(define (method8 lst)
  (dolist (x lst) (case (& $idx 1) (0 (setf (lst $idx) (upper-case $it)))))
  lst)

(define (method9 lst)
  (dolist (this-string lst) 
    (if (odd? $idx) 
        (push (upper-case this-string) newList -1) 
        (push this-string newList -1)))
  newList) 

(push (list (time (method1 source-list)) "method1") results)
(push (list (time (method2 source-list)) "method2") results)
(push (list (time (method3 source-list)) "method3") results)
(push (list (time (method4 source-list)) "method4") results)
(push (list (time (method5 source-list)) "method5") results)
(push (list (time (method6 source-list)) "method6") results)
(push (list (time (method7 source-list)) "method7") results)
(push (list (time (method8 source-list)) "method8") results)
(push (list (time (method9 source-list)) "method9") results)

(map println (sort results))

These don't give exactly the same answer (odd/even) but I was only looking to make a quick comparison - not proper testing methodology... :)

Note that method7 requires a larger stack for longer lists.

[Lutz]

The topic of tail-recursion came up in this thread and has come up earlier. Here my thoughts about it:

As somebody else said already in this thread: "recursion is overrated"

It may be interesting from a theoretical point of view to reduce iteration to tail-recursive function calls, but from a practical point of view I don't see much sense in it. First of all, its inefficient, it took the Scheme designers a long time to implement continuations with more or less acceptable but not stellar performance.

Don't get me wrong I am all for recursion where an algorithm is elegantly expressed this way, and newLISP supports recursion. But often I see that people in traditional Lisp texts try to force recursion on naturally linear, iterative problems. Remember that only the tail-recursive part in an recursive algorithm can be optimized. But why optimize something into iteration if it was expressed more naturally iterative in the first place?

Generations of programmers have been taught by their CS professors that recursion is the holy grail of algorithm design. I think its just not true, its an important part among other important techniques, nothing else. I agree, that it has a special place in functional programming theory, but it is not special in a practical, applications oriented, multi-paradigm scripting Lisp.

Use recursion where appropriate, i.e. processing and generating tree like structures, but where the problem is linear don't force it into a recursive perspective to satisfy some theoretical purity of solving all control patterns in computer programming with recursive function calls.

newLISP has a wide selection of iterator functions to make iteration comfortable: 'dotimes, dolist, for, while, until, do-while, do-until'; more than most other scripting languages.

Most recursive algorithm will suffice with the default stack depth of 2028 in newLISP. You can bump it up to whatever number you need using the -s command line switch. Most recursive programs running into stack problems are better solved using an iterative algorithm. Again remember: only the tail-recursive part can be optimized (translated into iteration) anyway.

To make a long story short: there will never be tail-recursion optimization in newLISP ;-)

[ale870]

Ok Lutz, I didn't want to oblige you to implement tail-recursion!
As you said, recursion is a way to apply an algorithm (so it has advantages and weakness as any other algorithm).
I proposed to insert a such function so the users will have another important instrument in their toolbox.
In other languages recursion is a must (for example to by-pass the problem related to immutable variables), but newLisp, as many other languages, offer "rewritable" variables, so recursion becomes simply another tool.

Finally, I simply think that...
If I have a tool I can decide if use it or not (flexibility); if I haven't a tool I cannot decide anything...

Thank you.

[Lutz]

Finally, I simply think that...
If I have a tool I can decide if use it or not (flexibility); if I haven't a tool I cannot decide anything...

I totally agree on that point and newLISP prides itself to often offer different styles and solutions to the same problem, which is all the fun we are having in this thread. A big part of the joy of programming is to express your own style.

Unfortunately there is no way to implement tail-recursion optimization or some helper function like 'recur' with little code and no impact on performance, the way newLISP's VM is architectured.

[DrDave]

After some minor tweaking, I ran the code that Cormullion was nice enough to post. I used a source list of length 81920. Initally, I ran the versions one at a time and discoverd that method7 never completed, even after 40 minutes. So, when I ran the whole group, it was omitted.

I implemented only this version of odd?

Code: Select all

(define (odd? num) (= (& num 1) 1)) 

newLISP 10.0.0 WIN32 (Windows XP pro)

Here are typical results, time in milliseconds
(468 "method9")
(515 "method3")
(546 "method2")
(609 "method5")
(781 "method6")
(25781 "method8")
(29234 "method4")
(103562 "method1")
( never completes "method7")

I was actually surprised to see that method9 turned in the best performance.
Also note that the results clearly fall into three groups: {9, 3, 2, 5, 6}; {8, 4}; {1}. And I suppose we could add a fourth gorup {7} also out there by itself.

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

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

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 all

(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 all

(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 all

(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 all

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

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

Code: Select all

> (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 all

(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 all

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 all

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

and have 'a' changed.

[ale870]

Lutz, is there any way (generally speaking) to make a function that return a reference to an element of a list (like in the example before) instead returning a copy? Can I do that using contexts?

[Lutz]

Not for user-defined functions without using contexts, but for built-in functions, indexed parts return the reference:

Code: Select all

(set 'L (set 'L '(a b (c d e) f g))

(push 'Z (L 2)) => (Z c d e)

L => (a b (Z c d e) f g)

You can achieve similar in a user-defined function by packing the L in a namespace/context:

Code: Select all

(define L:L '(a b (c d e) f g))

(define (my-push lst offset)
	(push 'Z (lst offset)))

(my-push L 2) => (Z c d e)

L:L => (a b (Z c d e) f g)

[ale870]

Your explanation is very clear, thank you Lutz!

just for information: in my blog I just started to write some workshops to "put all together" about my experience acquired in this topic (I want even to highlight the new things I learnt). Even if they are in italian language there is an "automatic" translator using google. I'm very happy if you read and correct/comment/etc... my workshops.
First workshop is at:

ORIGINAL (ITALIAN):
http://newlisp.wordpress.com/2008/12/15 ... orkshop-1/

TRANSLATION:
http://translate.google.com/translate?h ... orkshop-1/

Thank you!

[itistoday]

I thought it'd be fun to implement this using streams...

Results:

Code: Select all

> (print-stream (upper-other-case (stream-from-list '("a" "b" "c" "d" "e" "f" "g"))))
A b C d E f G "done"

The upper-other-case function which does this:

Code: Select all

(define (upper-other-case s)
	(join-streams
		(every-other-stream (map-stream upper-case s))
		(every-other-stream (tail s))
	)
)

Other functions used by upper-other-case:

Code: Select all

(define (join-streams s1 s2)
	(if (empty-stream? s1)
		s2
		(empty-stream? s2)
		s1
		(letex (a (head s1)
				b (tail s1)
				c s2)
			(cons-stream a (join-streams 'c 'b)))
	)
)

(define (stream-from-list l)
	(if (empty? l)
		the-empty-stream
		; underscore hack, newlisp namespace problem with:
		; (stream-from-list '(a b c)) b/c of usage of vars a & b
		(letex (_a (first l) _b (rest l))
			(cons-stream '_a (stream-from-list '_b)))
	)
)

(define (every-other-stream s)
	(if (empty-stream? s)
		the-empty-stream
		(empty-stream? (tail s))
		(letex (a (head s))
			(cons-stream a (every-other-stream '())))
		(letex (a (head s) b (tail (tail s)))
			(cons-stream a (every-other-stream 'b)))
	)
)

For the rest of the functions you can read: Streams in newLISP

[DrDave]

To pass the time while awaiting my turn at the medical center, I thought about how to take some of the information from this thread to produce a very fast method. Method9 was previously the fastest, so I included only method9 and my latest endeavor, method11; it smokes method9. I wanted to have a list large enough to give a run time of at least half a second. This required 16 iterations to construct source-list, resulting in length of 327680.

I think method11 still has code that is clear, easy to maintain, and efficient, assuming ending with an output list the same size as the source list is acceptable.

Code: Select all

;; Generate the source list
;; To try out the really slow methods, reduce iterations to 2 or 3 and work your way up

(set 'source-list "a")  ;after generating source-list the first time, can comment out this line
(set 'iterations 16)  ; for new methods, use a small value like 3 to start

(if (< (length source-list) 4)
    (silent   ;;silent to supresses output of list generation. Use begin to see output
       (set 'source-list '("a" "b" "c" "d" "e"))
       (for (zz 1 iterations)  (push source-list source-list -1))
       (set 'source-list (flat source-list))
    )
)

(println (length source-list))

;; Need to reset these in case running the code several times in succession
(set 'newList nil 'results nil 'myeven? nil)

(define (method9 lst) 
  (dolist (this-string lst) 
    (if (odd? $idx) 
        (push (upper-case this-string) newList -1) 
        (push this-string newList -1))) 
  newList) 

(define (method11 lst)
   (while lst 
     (set 'myeven? (not myeven?))
     (if (= myeven? true)
         (push (upper-case (first lst)) newList -1)
         (push (first lst) newList -1)
     )
     (pop lst)
   )
)

(push (list (time (method9 source-list)) "method9") results) 
(push (list (time (method11 source-list)) "method11") results) 

(println "======")
(map println (sort results)) 

Here are typical results on my system: newLISP 10.0.0. WIN32, Windows XP pro

(531 "method11")
(3343 "method9")

EDIT-- and here is the version of odd? I used

Code: Select all

(define (odd? num) (= (& num 1) 1)) 

Also, I actually prefer to use some intermediate functions rather than inlinng the code, like below. But there is quite a speed penalty to call the functions, if speed is the goal.

Code: Select all

(define (process-even-members)
        (push (upper-case (first lst)) newList -1)
)

(define (process-odd-members)
        (push (first lst) newList -1)
)

(define (method11 lst)
  (while lst 
   (set 'myeven? (not myeven?))
   (if (= myeven? true)
       (process-even-members)
       (process-odd-members)
   )
   (pop lst)
  )
)