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 Expand


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 Expand

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

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

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


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


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

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

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


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

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

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

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


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


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

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.