(dolist) enhancement

[Fanda]

Hello!
I like the (dolist) in the newLISP - it is similar to TCL's 'foreach', but 'foreach' has more freedom how to iterate through the list(s).

Here is the example from TCL manual:

Code: Select all

foreach - Iterate over all elements in one or more lists

foreach varname list body
foreach varlist1 list1 ?varlist2 list2 ...? body

1) The following loop uses i and j as loop variables to iterate over pairs of elements of a single list.

set x {}
foreach {i j} {a b c d e f} {
    lappend x $j $i
}
# The value of x is "b a d c f e"
# There are 3 iterations of the loop.

2) The next loop uses i and j to iterate over two lists in parallel.

set x {}
foreach i {a b c} j {d e f g} {
    lappend x $i $j
}
# The value of x is "a d b e c f {} g"
# There are 4 iterations of the loop.

3) The two forms are combined in the following example.

set x {}
foreach i {a b c} {j k} {d e f g} {
    lappend x $i $j $k
}
# The value of x is "a d e b f g c {} {}"
# There are 3 iterations of the loop.

It would add lots of power to newLISP, if we could write something like:

Code: Select all

(dolist ((x y) '(x1 y1 x2 y2)) (use x y))
(dolist ((name age) '("John" 32 "Richard" 41 "Lucy" 37)) (use name age))

(dolist (a '(a1 a2 a3) b '(b1 b2 b3)) (use a b))

(dolist (p '((1 2) (3 4) (5 6)))
  (dolist ((x y) p)
    (use x y)))

It is VERY READABLE and EASY to do. I AM FOR IT!

Fanda ;-)

[Lutz]

An intriguing idea, let me investigate this

Lutz

[nigelbrown]

I think most of the functionality you're suggesting for dolist is in map and apply, particularly if more of a list of lists approach is taken with data rather than a flat list.
Some egs to consider from your examples:
I've defined use as
> (define (use x y) (string "Params:" x "," y))
(lambda (x y) (string "Params:" x "," y))
> (use x y)
"Params:nil,nil"
>

yours: (dolist ((x y) '(x1 y1 x2 y2)) (use x y))
if x y are really a pair treat them that way by storing as a list of pairs then map apply over that
eg:
> (map (lambda (z) (apply use z)) '((x1 y1) (x2 y2)))
("Params:x1,y1" "Params:x2,y2")
>

yours: (dolist ((name age) '("John" 32 "Richard" 41 "Lucy" 37)) (use name age))
similarly
> (map (lambda (x) (apply use x)) '(("John" 32) ("Richard" 41) ("Lucy" 37)))
("Params:John,32" "Params:Richard,41" "Params:Lucy,37")
>

yours: (dolist (a '(a1 a2 a3) b '(b1 b2 b3)) (use a b))
using map alone
> (map use '(a1 a2 a3) '(b1 b2 b3))
("Params:a1,b1" "Params:a2,b2" "Params:a3,b3")
>

yours:
(dolist (p '((1 2) (3 4) (5 6)))
(dolist ((x y) p)
(use x y)))

can be:
> (map (lambda (x) (apply use x)) '((1 2) (3 4) (5 6)))
("Params:1,2" "Params:3,4" "Params:5,6")
>
The success of the above may depend on the details of use as apply doesn't evaluate the args before applying eg
> (define (use x y) (+ x y))
(lambda (x y) (+ x y))
> (use 2 3)
5
> (setq x1 2 x2 3)
3
> (use x1 x2)
5
> (apply use '(x1 x2))

value expected in function + : x

> (apply use '(2 3))
5
>


I find an advantage of lisp is 'map'ing rather 'do'ing (very FORTRAN77).
however, map is more about collecting the results into a list of results while dolist is applying the function for its side effects and only returning the last value.

Nigel

PS not knocking FORTRAN, just used as a canonical style example.

PPS always wanted to find an opportunity to use 'canonical' so took the opportunity to slip it in - hope I used it properly.

[Fanda]

Few comments:
- Thanks for rewriting it to LISP ;-) I am new to LISP and I know about map and apply, just haven't used to them much.

- Yes, you are right that it is more imperative style of programming than functional. I just don't know, how to deal with flat lists - you have to make the pairs first and only after that you can use map or apply. (If you create your own list, you can do it in pairs.)

- I tried all your examples. Apply doesn't evaluate the args before applying, so we can do it by ourselves:
(apply use (map eval '(x1 x2)))

There are reasons to use enhanced dolist:
1) flat lists - need to be converted to list with pairs
2) when (use x y) isn't a simple function, but more complicated code - as it is usually with dolist. (Actually I used (use x y) only as a symbolic example.)

Lutz has the last word :-)

Fanda

[Fanda]

OK, I will add something more :-)

Right now, I am learning how to do conversions between different lists. For example - I want to iterate on points, when I have a list of lines:

point P = (x y)
line L = (P1 P2)
list = (L1 L2 ...)

Code: Select all

(setq N '(((1 2) (3 4)) ((5 6) (7 8)) ((9 10) (11 12))))

I tried different ways:
1)

Code: Select all

(setq r '())
(map (lambda (X) (map (lambda (Y) (push Y r -1)) X)) N)
(println "map:    " r)
; => map:    ((1 2) (3 4) (5 6) (7 8) (9 10) (11 12))

2)

Code: Select all

(setq s '())
(dolist (x N)
  (dolist (y x)
    (push y s -1)))
(println "dolist: " s)
; => dolist: ((1 2) (3 4) (5 6) (7 8) (9 10) (11 12))

Now I can use map or dolist again to iterate on points.

Version 1 is hard to read (at least for me). I can do this, it helps reading a little bit:

Code: Select all

(setq r '())
(map (lambda (X)
  (map (lambda (Y)
    (push Y r -1))
  X))
N)

Version 2 is easier to read and also 2x faster. If you go one level down to 'x' and 'y' it is 3-4x faster.

Fanda

[Fanda]

Just adding:

With new 'dolist' we could do

Code: Select all

(dolist ((x y) (flat N)) (use x y))

OR

Code: Select all

(dolist (l N)
  (dolist ((p1 p2) l)
    (use p1 p2)))

If you know the other way, please let me know.

Thank you, Fanda

[Dmi]

Possible, good function for grouping and disposing of lists will be good support.
I.e., something like:

Code: Select all

(set 'n '(1 2 3 4 5 6 7))
(group 3 n) => ((1 2 3) (4 5 6) (7))
(set 'm '(7 6 5 4 3 2 1))
(dispose m n) => ((7 1) (6 2) (5 3) (4 4)....)

so we could write then:

Code: Select all

(dolist (a (group 3 n)) (use (a 0) (a 1) (a 2)))

"Tips and tricks" section has an example of pairing function trough conversion to an array and using integer divisoin of an index.
Anybody knows, is it efficient?

PS.
BTW possibility to assign a list of values to list of symbols can be useful (imho).
I.e., something like (not exact of course ;-)

Code: Select all

(set '(a b c) (1 2 3))

will result: a=1 b=2 c=3 - and similar in dolist etc.

[nigelbrown]

How about mapping slice across an index list generated by sequence
as
> (slice '(1 2 3 4 5 6) 0 2)
(1 2)
eg
> (setq p '(1 2 3 4 5 6))
(1 2 3 4 5 6)
the definition:
> (define (dispose m n) (map (lambda (i) (slice m i n)) (sequence 0 (sub (length m) 1) n)))
(lambda (m n) (map (lambda (i) (slice m i n)) (sequence 0 (sub (length
m) 1) n)))
test it:
> (dispose p 2)
((1 2) (3 4) (5 6))
> (dispose p 3)
((1 2 3) (4 5 6))
>
It doesn't check for correct length (but could) so
> (dispose p 4)
((1 2 3 4) (5 6))
>

Nigel

[Lutz]

Here is a function from http://newlisp.org/index.cgi?page=Code_Snippets to 'group' elements in a flat list:

Code: Select all

;; pair - put members of a list into pairs 
;; 
;; (pair '(a b c d e f)) => ((a b) (c d) (e f))
;;
(define (pair lst)
  (array-list (array (/ (length lst) 2) 2 lst)))

The function can easily be rewritten for numbers other than 2 with an additional parameter and you have the 'group' function suggested by DMI.

Also, use:

Code: Select all

(map set '(a b c) '(1 2 3))

For the list set suggested.

Lutz

[nigelbrown]

Lutz,

Much cleaner using your array approach.

Nigel

[Dmi]

Cool! I Like it :-)

[Fanda]

Dmi:

(dolist (a (group 3 n)) (use (a 0) (a 1) (a 2)))

This is why I would like to have an enhanced 'dolist'. Then you could just do:

Code: Select all

(dolist ((x y z) n) (use x y z))

Grouping and indexing is done inside the 'dolist'.


Nigel: Your (dispose m n) is in fact a grouping function. (It works great, I like it! :-). Dmi meant by (dispose) the function that merges two lists together.


Lutz: (pair) function needs to have a good length of the list, otherwise it looses a part of the list (good or bad?):
> (pair '(1 2 3 4 5))
((1 2) (3 4))


Yes, I am learning, I am learning :-)

Fanda

ps: Just let me know, if I bug you ;-)

[nigelbrown]

Yes my 'dispose' is group - I made the classic mistake of not reading the question properly.

Here is a dispose that is just a wrapper around the builtin newLISP function transpose.
using args lets you accept any number of lists
viz

> (define (dispose) (transpose (args)))
(lambda () (transpose (args)))
> (dispose '(1 2 3) '(4 5 6))
((1 4) (2 5) (3 6))
> (dispose '(1 2 3) '(4 5 6) '(7 8 9))
((1 4 7) (2 5 8) (3 6 9))
> (setq m '(1 2 3 4 5 6 7))
(1 2 3 4 5 6 7)
> (setq n '(7 6 5 4 3 2 1))
(7 6 5 4 3 2 1)
> (dispose m n)
((1 7) (2 6) (3 5) (4 4) (5 3) (6 2) (7 1))
>

Nigel

[Fanda]

Nigel: Thanks for showing me that function.
I was doing:
> (setq L '((1 2) (3 4) (5 6)))
((1 2) (3 4) (5 6))
> (map (lambda (x) (nth 0 x)) L)
(1 3 5)

And now I can also do:
((transpose L) 0)
(1 3 5)

[ 'dolist' version: ]
(setq r '())
(dolist (x L)
(push (x 0) r -1))

For 1000000 times the function 'time' returns:
map/transpose/dolist - 2047,672,1266

Transpose is the winner, but 'dolist' is still 1.6x faster than 'map'. That's one of the reasons why use it.

Lutz: If I can ask - what is your comment on the enhanced 'dolist'? Have you done any tests with it? I think it could be useful (e.g. recursive functions), more readable (many times nested lists) and faster. Sorry, if I bother you too much.

Thank you all, Fanda

[nigelbrown]

The apparent slowness for map is in the function you chose to map from my timings.
Instead of (lambda (x) (nth 0 x)) just use 'first'
eg for
> L
((1 2) (3 4) (5 6))
>
we have
> (map first L)
(1 3 5)

Here are my timings:

> (time (dotimes (i 100000) (map first L)))
331
> (time (dotimes (i 100000) (map (lambda (x) (nth 0 x)) L)))
843
> (time (dotimes (i 100000) (setq r '())(dolist (x L)(push (x 0) r -1))))
519

dolisting first without collecting results is the same as map:
> (time (dotimes (i 100000) (dolist (x L) (first x))))
334
>
Which suggests the preference for either map or dolist doesn't hinge on time performance - unless you do need to collect results in which case map is more efficient.

Nigel
PS let me know if I've overlooked something in my timings

[Lutz]

I have been looking into an enhanced (dolist ((x y ... ) L) ...) and actually started coding something, the speed performance impact though seems to big. I also think, that in most cases where a need for a multiparameter 'dolist' is perceived it would be better to structure the iteration list and do something like this:

Code: Select all

(dolist (p '((a 1) (b 2) (c 3)))
    ... (p 0) ...   ; access the first member of the p sublist
    ... (p 1) ...   ; access the second member of the p sublist
)

Nested lists are good for structuring information and should be used in this way. Then use implicit indexing to access sub members.

But still, after having made this argument I agree, a multi parameter 'dolist' is a good idea and there are cases where it comes in very handy. I may give it another shot.

Lutz

[Fanda]

Nigel: Silly me - I used 2 different functions and compared the speed ;-)

I tried it and it seems more complicated. For simple lists:
> (setq L '((1 2) (3 4) (5 6)))
((1 2) (3 4) (5 6))

# dolist faster
> (time (dotimes (i 100000) (map (lambda (x) (x 0)) L)))
203
> (time (dotimes (i 100000) (setq r '())(dolist (x L)(push (x 0) r -1))))
125

# map faster
> (time (dotimes (i 100000) (map first L)))
78
> (time (dotimes (i 100000) (setq r '())(dolist (x L) (push (first x) r -1))))
125

I guess - if you have lambda inside the map - you get slow down.

I tried nested lists:
> (setq M '(((1 2) (3 4)) ((5 6) (7 8))))
(((1 2) (3 4)) ((5 6) (7 8)))
> (map (lambda (x) (map first x)) M)
((1 3) (5 7))

> (setq r '())(dolist (x M) (dolist (y x) (push (first y) r -1)))
()7
> r
(1 3 5 7)

You don't get the same results, but algorithm is pretty much the same.

> (time (dotimes (i 100000) (map (lambda (x) (map first x)) M)))
313
> (time (dotimes (i 100000) (setq r '())(dolist (x M) (dolist (y x) (push (first y) r -1)))))
266

So, I would say:
- map is pretty fast for simple functions
- dolist is good for complicated functions and nested lists (try to nest it 3x, 4x times)


Lutz: If it would mean slow down for current 'dolist', I guess you might give it another name...

My idea of algorithm was to fill in empty lists at the end and then just iterate through it:
(dolist ((x y) '(1 2 3 4 5)) ...)
-> (dolist ((x y) '(1 2 3 4 5 ())) ...)
(dolist (x '(1 2 3 4) n '(a b)) ...)
-> (dolist (x '(1 2 3 4) n '(a b () ())) ...)

Also:
(dolist (x '(1 2 3 4) n '(a b)) ...)
can be written like:
(dolist ((x n) '(1 2 3 4) '(a b)) ...)
so all the variables are in the first list

Hm... but that would lead to nested lists:
(dolist ((x y) '(1 2 3 4) (w z) '(5 6 7 8)) ...)
rewritten:
(dolist (((x y) (w z)) '(1 2 3 4) '(5 6 7 8)) ...)


Fanda

[nigelbrown]

Nigel: Silly me - I used 2 different functions and compared the speed ;-)
...
So, I would say:
- map is pretty fast for simple functions
- dolist is good for complicated functions and nested lists (try to nest it 3x, 4x times)

Fanda

Hi Fanda,
I think you are still letting dolist off tooooo lightly.
In your comparison the outer dolist had only to iterate, rather than iterate and collect, so the result was not the same as for the map code. Adding a collection step to the outer dolist so the codes give the same output gives about the same times - consider:
> (time (dotimes (i 100000) (setq r1 '())(dolist (x M) (setq r '())(dolist (y x) (push (first y) r -1)) (push r r1 -1))))
1359
> r1
((1 3) (5 7))
> (time (dotimes (i 100000) (map (lambda (x) (map first x)) M)))
1257
> (map (lambda (x) (map first x)) M)
((1 3) (5 7))
>

map is slightly ahead (essentially the same).

Nigel

[Fanda]

Oh, oh, oh!
You are right!
I overlooked difference between 'iterating' and 'iterating and collecting'!

Look, what I tried:
> (time (dotimes (i 100000) (setq r '())(map (lambda (x) (map (lambda (y) (push (first y) r -1)) x)) M)))
594
> r
(1 3 5 7)

> (time (dotimes (i 100000) (setq r '())(dolist (x M) (dolist (y x) (push (first y) r -1)))))
250
> r
(1 3 5 7)

This code is what was making me to say, that 'map' is slow. But it's not really true, because the nature of map is to iterate and also collect results. It means, that in the first example, I iterate, but both maps also return lists which are not being used at all!

> (map (lambda (x) (map (lambda (y) (push (first y) r -1)) x)) M)
((1 3) (5 7))

The inside map collects and returns (1 3) and (5 7) and outside map collects that and returns ((1 3) (5 7)). None of it is being used!
=> !!! That's why it is slower !!!

Ok, I leave the 'map' alone, now ;-))))

Fanda

[Jeremy Dunn]

Here is a version of the group function that I wrote that gives you a few more options. I tend to like the enhanced dolist suggestion simply because I can more easily see what is going on. I know it can be done other ways but I am not always as abstract as I would like to be.

Code: Select all

;; This function performs a multiple slice on a given list
;; One supplies a list and an integer n. The list is broken into a list of sublists of
;; length n. If n is negative the list items are collected going from the end of the list
;; to the beginning. If the optional bool argument is supplied then remaining elements are
;; included in the result.
;; (group '(1 2 3 4 5 6 7) 3)       -> ((1 2 3)(4 5 6))
;; (group '(1 2 3 4 5 6 7) 3 true)  -> ((1 2 3)(4 5 6)(7))
;; (group '(1 2 3 4 5 6 7) -3 true) -> ((1)(2 3 4)(5 6 7))
(define (group lst n bool , len num rep rem start)
  (setq num (abs n))
  (if (< n 0)
      (reverse (map reverse (group (reverse lst) num bool)))
      (= n 0)
      nil
      (begin
        (setq len   (length lst)
              rep   (/ len num)
              rem   (% len num)
              start '()
        )
        (if (< num len)
            (begin
              (dotimes (x rep)
                (setq start (cons (slice lst (* x num) num) start)))
              (if (and bool (> rem 0))
                  (setq start (cons (slice lst (* num rep) rem) start)))
              (reverse start))
            (list lst)))))

[Dmi]

I'm slightly busy now, so I cant flame here with full power :-( ;-)
But checking some code, I found some unexpectance:

Code: Select all

newLISP v.8.6.1 on linux, execute 'newlisp -h' for more info.

> (array 0 1 '(1 2 3))

Command terminated

....newlisp exits here

Possible zero-length dimension checking must to be in (array) function.

[Lutz]

Thanks for catching this, its fixed in 8.6.5

Lutz