Interesting problem for me

[ale870]

Hello,
I'm sorry for the bad subject, but I could not find anything better.

Some times ago I was talking with a friend of mine, and we compared newLisp vs other imperative languages (object pascal, generic basic, and java).

We tried to make small programs to get an input and produce same output, but using the best of each sector ("imperative" concepts and "functional" ones).

Well, I'm working in newLisp but I come from many years programming with imperative languages. So sometimes is difficult for me using advance functional algorithms since I tend to use "imperative" concepts to solve problems in newLisp.

(sorry for this long introduction!)

This is the "trivial" problem:

I have a list of strings, and I want to convert only some strings to upper-case. The strings are: first string, third string, 5th string, etc...
So... I have:
("string 1" "string 2" "string 3" "string 4" "string 5" "string 6")

I want to obtain:
("STRING 1" "string 2" "STRING 3" "string 4" "STRING 5" "string 6")

In an "imperative algorithm" I could use a loop and a "step". For example:

Code: Select all

dim myList$(6)

myList$(1) = "string 1"
myList$(2) = "string 2"
myList$(3) = "string 3"
myList$(4) = "string 4"
myList$(5) = "string 5"
myList$(6) = "string 6"

for i=1 to 6 step 2
  myList$(i) = uppercase(myList$(i))
next

How can I do in newLisp without using loops, but using "functional" concepts (e.g. using "map")?

How many possibilities/alternatives do I have to accomplish it?

(I wish to insert the results of this topic even in my blog, since I think this discussion could be interesting even for many other guys).

Thank you!

[newdep]

(MAIN)-> (setq L '("string 1" "string 2" "string 3" "string 4" "string 5" "string 6"))
("string 1" "string 2" "string 3" "string 4" "string 5" "string 6")
(MAIN)-> (map (fn(x) (setf (L x) (upper-case (L x)))) '(1 3 5))
("STRING 2" "STRING 4" "STRING 6")
(MAIN)-> L
("string 1" "STRING 2" "string 3" "STRING 4" "string 5" "STRING 6")

[unixtechie]

Here's an example from documentation which looks like a helpful hint to me:

Code: Select all

 (map if '(true nil true nil true) '(1 2 3 4 5) '(6 7 8 9 10))
    --> '(1 7 3 9 5) 

From alphabetical section on functions in User Manual

[ale870]

@newdep immediately uses newLisp 10 features! ;-)
I like that solution!

@unixtechie I found that hint, but I cannot grab final solution using it. I don't know if that one is a good way.

I think the "problem" is map function takes a single argument (else one must pass two or more lists).
I don't know if there is a function tomake something like this (meta-code):

Code: Select all

(map-2 (fn (x y) (upper-case x) y) '("s1" "s2" "s3" ....))

In this way I could get two values per step. So I could obtain:
("S1" "s2" "S3" "s4" ... )

Maybe there is a better way than using MAP (but... how?)

[ale870]

Code: Select all

(map (fn (x y) (if (= (/ x 2) (div x 2) ) y (upper-case y) ) )  (sequence 1 5) '("a" "b" "c" "d" "e") )

Or better (more flexible):

Code: Select all

(setq f '("a" "b" "c" "d" "e" "f" "g") )
(map (fn (x y) (if (= (/ x 2) (div x 2) ) y (upper-case y) ))  (sequence 1 (length f) ) f )

[xytroxon]

Code: Select all

(define (odd? num)((bits num true) 0))
(define (even? num)(not ((bits num true) 0)))

(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (odd? $idx) (setf (f $idx) (upper-case (f $idx)))))
(println f)
; ("a" "B" "c" "D" "e" "F" "g")

(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case (f $idx)))))
(println f)
; ("A" "b" "C" "d" "E" "f" "G")
(exit)

Q.E.D. ;)

-- xytroxon

P.S. And six months later, at a glance, I can tell what this code does!

[Lutz]

In self-referential 'setf' statements you can also use the system variable '$it':

Code: Select all

(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it)))

ps: congratulations for using new 'bits' with extra flag ;-)

[xytroxon]

In self-referential 'setf' statements you can also use the system variable '$it':

Code: Select all

(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it)))

ps: congratulations for using new 'bits' with extra flag ;-)

I think you mean:
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it))) ) ;<- missing paren

Code: Select all

(define (odd? num)((bits num true) 0))
(define (even? num)(not ((bits num true) 0)))

(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (odd? $idx) (setf (f $idx) (upper-case $it))))
(println f)
; ("a" "B" "c" "D" "e" "F" "g")

(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it))))
(println f)
; ("A" "b" "C" "d" "E" "f" "G")
(exit)

Yes, much better now!

-- xytroxon

[cormullion]

How about:

Code: Select all

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

; or 

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

I suppose this is also 'functional' in that the initial list is unchanged...

[Lutz]

Nice solution because without the need for 'odd?' and 'even?' functions!

But here another one using 'map' and also using the system variable '$idx', which also gets updated during 'map':

Code: Select all

(map (fn (x) (if (even? $idx) (upper-case x) x)) f)

[DrDave]

You guys get carried away, but it's interesting to see so many ways to arrive at usable solutions.

I had done basically what xytroxon did but created a new list. Easier for a casual programmer such as myself to understand at some later date.

Code: Select all

(set 'myList (list "string 1" "string 2" "string 3" "string 4" "string 5"))
(dolist (this-string myList) (if (even? $idx)
                                 (push (upper-case this-string) newList -1)
                                 (push this-string newList -1)
                             )
)
--> "STRING 5"
newList
--> "STRING 1" "string 2" "STRING 3" "string 4" "STRING 5"
myList
--> ("string 1" "string 2" "string 3" "string 4" "string 5")

[xytroxon]

After lunch, I simplified odd? and even? with bit?.

Code: Select all

; test bit position in number for 1 or 0
(define (bit? pos num) (bits num true) pos)

(define (odd? num) (bit? 0 num))

(define (even? num) (not (bit? 0 num)))

Bit operations on integers can be useful on packed data and working on data sent to and from hardware registers via dll, etc.

Other proposed bit functions to be developed:

Code: Select all

(bit0 pos num) ; set bit position in number to 0  "clear bit"

(bit1 pos num) ; set bit position in number to 1 "set bit"

(bit~ pos num) ; toggle bit position in number 0 -> 1 , 1 -> 0

Any others?

And I propose adding at least odd? and even? pedicate functions to a future version of newlisp...

This code sprint was fun, I learned a few things and it helped to clean up some of my code too.
(Now I can make checkerboard colored html tables! Woo Hoo!)

-- xytroxon

[ale870]

I was delighted from these solutions!
I learnt so many things!
@cormullion you killed me with that solution! I'm still studying it to better understand your solution!

Thank you even for odd and even optimizations! I think in future newLisp versions they should be really included ;-)

I started this topic saying I wanted to prepare an article, but now... I think I will prepare more than one!!!

[cormullion]

There's an interesting aspect of this thread that hasn't so far been mentioned: performance. Although I generally agree with DrDave's signature ("make programs efficient only if really needed"), I'm always fascinated by the interplay between simplicity, elegance, performance, and readability that newLISP allows us to explore.

Which of these algorithms are faster? Is the full-speed ahead iteration of dolist the fastest way, or will map be able to drill those lists quickly enough? Or will secret agent match be able to snoop and scan its way to victory?

I put the different algorithms head to head on a 60000 word list. Some are an order of magnitude slower than another. It might matter some day... :)

[ale870]

Good point of view @cormullion.
I found another interesting solution for this problem just studying Erlang language.
In fact, I think sometimes we forget that newLisp is a functional language, and some items should be solved in a functional way.
If you start to use languages like Erlang, where some functional aspects are very strong (e.g. variables are immutable, recursive algorithms are a great resource to solve problems, etc...) you will see our problem in a different point-of-view.
Now I'm at work, but at home I want to write another possibility only using function call. Example (pseudo-code):

Code: Select all

MY_FUNC(string_list, final_list):
get_first_string:
   is it odd?
      YES->convert to uppercase and add it to final list.
      NO -> add it to final list as is.
call MY_FUNC(remaining_strings, final_list)

I hope my concept is clear.
This is a clear example about functional programming:
@cormullion I add another important point to your list: code must be safe and error-free. So... in the previous code...

1) variables are immutable.
2) usage of real functional-programming aspects.

[DrDave]

I put the different algorithms head to head on a 60000 word list. Some are an order of magnitude slower than another. It might matter some day... :)

And you're just leaving us hanging??

[xytroxon]

There's an interesting aspect of this thread that hasn't so far been mentioned: performance.

Yes. odd? and even? need to be implimented in C for best performance.

Try these changes to odd? and even? using "bitwise and" &.

Code: Select all

;corrected 12/12/2008 
(define (odd? num) (= (& num 1) 1))
(define (even? num) (= (& num 1) 0))
(dolist (x f) (if (odd? $idx) (setf (f $idx) (upper-case $it))))
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it))))

And then try putting them "inline":

Code: Select all

(dolist (x f) (if (= (& $idx 1) 1) (setf (f $idx) (upper-case $it)))) ; odd
(dolist (x f) (if (= (& $idx 1) 0) (setf (f $idx) (upper-case $it)))) ; even

-- xytroxon

[DrDave]

Good point of view @cormullion.
I want to write another possibility only using function call. Example (pseudo-code):

Code: Select all

MY_FUNC(string_list, final_list):
get_first_string:
   is it odd?
      YES->convert to uppercase and add it to final list.
      NO -> add it to final list as is.
call MY_FUNC(remaining_strings, final_list)

I hope my concept is clear.

I see you want to recursively call your function and have it walk the list until out of strings. But how does 'dolist' handle it? Does it make recursive calls to itself or just traverses the list? (Personally, I think recursion is over rated. It certainly has some very good places where it gives simple, readable code compared to a non-recursive solution. But I don't see that it is a major tool in my toolbox.)

[DrDave]

There's an interesting aspect of this thread that hasn't so far been mentioned: performance.

-- xytroxon

Rather than go through all that code, I made a similar comparison of the time it takes to evaluate the predicate form versus the inline form for determining if a number is odd. I get a ratio of about 53:30 (inline faster).

[DrDave]

And while we're talking optimization now, in my version I built the second list on-the-fly by pushing each string to the end of a second list. Would it be faster to start off by copying the entire first list and then pushing only the changed string to its proper location (according to $idx) because it makes only half as many pushes?

Does pushing to an index location require traversing the list from the start? And if pushed to either the first or last position, would those always be "instantly" located?

[ale870]

I made some tests for recursive functions. But it seems some "instruments" are missing to "emulate" Erlang functioning.
So I think recursive way is better for newLisp.

@Curmullion can you give us the results you obtained about performance?

[Lutz]

And if pushed to either the first or last position, would those always be "instantly" located?

Yes, the first location is accessed instantly and access to the last location is optimized with no need to traverse the list. This is true not only for 'push' and 'pop' but also other indexed access with 0 or -1 and via the functions 'first' and 'last'.

Lists in newLISP are forward-single-linked lists, but a pointer to the last element is stored in the header/envelope of the list and updated whenever possible.

[xytroxon]

Correction, swap the 1 and 0 for odd and even like this. (Lunchtime programmer error. ;)

Code: Select all

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

Another "case" to consider is to use case inline:

Code: Select all

(println "case 1 odd")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (case (& $idx 1)(1 (setf (f $idx) (upper-case $it)))))
(println f)
(println "case 0 even")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (case (& $idx 1)(0 (setf (f $idx) (upper-case $it)))))
(println f)
(exit)

Much faster!

-- xytroxon, now going to dinner. Without a computer...

[Kazimir Majorinc]

One "functional" contribution to the discussion.

Code: Select all

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

(set 'alt-case-starting-with 
     (lambda(L first-case)
            (if (empty? L) (list)
                           (cons (first-case (first L))
                                 (alt-case-starting-with (rest L) 
                                                         (other-one first-case
                                                                    lower-case 
                                                                    upper-case))))))


(println (alt-case-starting-with '("str1" "str2" "str3" "str4") upper-case))
(exit)

[ale870]

Good exercise @Kazimir!
Your approach hightlight a potential "problem" in newLisp (maybe it could be completed with a specific function): newLisp does not apply "tail recursive" method. This is one of the biggest problems of imperative languages, and this is one of the reasons because recursive functions are not so much used.
I think, if newLisp could contain a function like (tail-recursive (...) ) we could extend the real power of newLisp language. In fact it contains many functions that could be used in such cases, like first, rest, last, cons, etc...
Now recursive algorithms are not used since they could cause serious problems to the stack area.
@Lutz, I think you need to evaluate this function implementation (tail-recursive). In fact I don't think you could implement at compile-level (but I'm still a newbie in functional programming so I do not know all the concepts in detail).