srfi-1 map!

srfi-1 map!

[Kevin Ryde]

[-- Attachment #1: Type: text/plain, Size: 194 bytes --]

I've been finding it a bit annoying that map can handle long lists but
map! can't.

        * srfi-1.scm (map!): Define as an alias for map, previous definition
        was not tail-recursive.


[-- Attachment #2: srfi-1.scm.mapx.diff --]
[-- Type: text/plain, Size: 702 bytes --]

--- srfi-1.scm.~1.29.~	1970-01-01 10:00:01.000000000 +1000
+++ srfi-1.scm	2003-11-11 10:28:35.000000000 +1000
@@ -572,22 +572,8 @@
 	'()
 	(append! (apply f (map1 car l)) (lp (map1 cdr l)))))))
 
-(define (map! f list1 . rest)
-  (if (null? rest)
-    (let lp ((l list1))
-      (if (null? l)
-	'()
-	(begin
-	  (set-car! l (f (car l)))
-	  (set-cdr! l (lp (cdr l)))
-	  l)))
-    (let lp ((l (cons list1 rest)) (res list1))
-      (if (any1 null? l)
-	'()
-	(begin
-	  (set-car! res (apply f (map1 car l)))
-	  (set-cdr! res (lp (map1 cdr l) (cdr res)))
-	  res)))))
+;; OPTIMIZE-ME: Re-use cons cells of given list(s)
+(define map! map)
 
 (define (pair-for-each f clist1 . rest)
   (if (null? rest)

[-- Attachment #3: Type: text/plain, Size: 142 bytes --]

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

a circular dilemma . #0# (was Re: srfi-1 map!)

[Stephen Compall]

Kevin Ryde <user42@zip.com.au> writes:

> I've been finding it a bit annoying that map can handle long lists
> but map! can't.

You're right, that is annoying.  So annoying, I wrote a new version,
and ran into some problems with circular lists.

Here is the first version.  I suppose I should have used any1 instead
of the two hand-rollings, but I saw it too late.  On the same note,
you have to bring map1, an internal from srfi-1.scm, into scope.

;;see if any list in LISTLIST has only one element
(define (any-alone? listlist)
  (cond
   ((null? listlist) #f)
   ((null? (cdar listlist)) #t)
   (else (any-alone? (cdr listlist)))))

(define (s11-map! f list1 . rest)
  ;; First, make sure list1 is not empty, and rest contains no empty
  ;; lists.
  (if (or (null? list1)
          (let lp ((lists rest))
            (cond
             ((null? lists) #f)
             ((null? (car lists)) #t)
             (else (lp (cdr lists))))))
      ;; BTW, I'm going to return list1.
      (set! list1 '())
    ;; OK, all cars are conses, with real elements to callback with
    (let nextelem ((clist1 list1) (crest rest))
      (set-car! clist1 (apply f (car clist1) (map1 car crest)))
      ;; Will that be true on the next round?
      (if (or (null? (cdr clist1)) (any-alone? crest))
          ;; If not, cut the list off here
          (set-cdr! clist1 '())
        (nextelem (cdr clist1) (map1 cdr crest)))))
  list1)

Which worked wonderfully for all sorts, even with circulars in REST,
until I started setting circulars to LIST1 with "longer" (that is,
those with more cons cells) but proper lists.

guile> (define mylist (circular-list 1 2 3 4))
guile> mylist
(1 2 3 4 . #0#)
guile> (map + mylist '(0 0 0 0 0 0))
(1 2 3 4 1 2)
guile> (s11-map! + mylist '(0 0 0 0 0 0))
(1 2)

The problem is, of course, even larger when your function returns
something other than its first argument.

So I modified it like so:

(define (s11-map! f list1 . rest)
  ;; First, make sure LIST1 is not empty, and rest contains no empty
  ;; lists.
  (if (or (null? list1)
          (let lp ((lists rest))
            (cond
             ((null? lists) #f)
             ((null? (car lists)) #t)
             (else (lp (cdr lists))))))
      ;; BTW, I'm going to return LIST1.
      (set! list1 '())
    ;; OK, all cars are conses, with real elements to callback with
    (let nextelem ((clist1 list1) (crest rest))
      (set-car! clist1 (apply f (car clist1) (map1 car crest)))
      (cond
       ;; circular LIST1...append new cells instead
       ((eq? (cdr clist1) list1)
        (set-cdr! clist1 (apply map f list1 (map1 cdr crest))))
       ;; rest of system handles circulars in REST just fine
       ;; If no more elements, cut LIST1 off here
       ((or (null? (cdr clist1)) (any-alone? crest))
        (set-cdr! clist1 '()))
       (else
        (nextelem (cdr clist1) (map1 cdr crest))))))
  list1)

Of course, this doesn't compensate for the circular list being a
sublist of LIST1 (e.g. (cons* -1 0 (circular-list 1 2 3 4))), but at
least produces a list of the proper length.

guile> mylist
(1 2 3 4 . #0#)
guile> (s11-map! + mylist '(0 0 0 0 0 0))
(1 2 3 4 1 2)
guile> mylist
(1 2 3 4 1 2)

But the values!

guile> (set! mylist (circular-list 1 2 3 4))
guile> (s11-map! + mylist '(1 1 1 1 1 1))
(2 3 4 5 3 4)
guile> (map + (circular-list 1 2 3 4) '(1 1 1 1 1 1))
(2 3 4 5 2 3)

Well, that isn't good!  And of course:

guile> (set! mylist (cons* 1 2 (circular-list 3 4 5 6)))
guile> (map + mylist '(1 1 1 1 1 1 1 1))
(2 3 4 5 6 7 4 5)
guile> (s11-map! + mylist '(1 1 1 1 1 1 1 1))
(2 3 5 6)

Which is the same problem the original had.

So, is there any way out of this problem, other than to dump the
second version (which is needlessly more complicated, I now think),
and shunt any call where LIST1 doesn't meet list? to map?  Or just
live with "undefined behavior" given by the silly (IMHO) case of
having a circular as LIST1 where a list in REST has more cells?  Or
what?

Did I mention I like [my] original version better?  Yeah.

--
Stephen Compall or s11 or sirian

Logic is a pretty flower that smells bad.

SCUD missile cybercash Kosovo Ermes New World Order ASPIC KGB
government munitions satellite imagery investigation csystems
fissionable e-cash MIT-LL


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: a circular dilemma . #0# (was Re: srfi-1 map!)

[Kevin Ryde]

Stephen Compall <s11@member.fsf.org> writes:
>
> (define (s11-map! f list1 . rest)

If you want to write some code, copying and adapting the current C
code would probably be much better.

> Or just
> live with "undefined behavior" given by the silly (IMHO) case of
> having a circular as LIST1 where a list in REST has more cells?

I see the spec calls for list2 etc to have at least as many elements
as list1.  Which I guess means list1 is finite (ie. non-circular) and
can be used to construct the return without further checking.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: a circular dilemma . #0# (was Re: srfi-1 map!)

[Stephen Compall]

Kevin Ryde <user42@zip.com.au> writes:

> If you want to write some code, copying and adapting the current C
> code would probably be much better.

Would this be added to libguile-srfi-srfi-1.so?  I just wrote it in
Scheme to go with the context; it was a function eliminated from
srfi-1.scm, eh?

> I see the spec calls for list2 etc to have at least as many elements
> as list1.  Which I guess means list1 is finite (ie. non-circular)
> and can be used to construct the return without further checking.

Ah, I misinterpreted this.  This makes my life much easier, now that I
know I am not pathetic and weak.  Thanks. :)

--
Stephen Compall or s11 or sirian

My method is to take the utmost trouble to find the right thing to say.
And then say it with the utmost levity.
		-- G.B. Shaw

chameleon man INSCOM Mantis Mena Geraldton Rule Psix offensive
information warfare North Korea Skipjack Aldergrove Rubin Echelon
Leuken-Baden counter intelligence bullion


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: a circular dilemma . #0# (was Re: srfi-1 map!)

[Kevin Ryde]

Stephen Compall <s11@member.fsf.org> writes:
>
> Would this be added to libguile-srfi-srfi-1.so?

srfi-1.c, which is where the current map lives.  Making aliases or
easy things may as well be done in the .scm.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel