Re: StackOverflowError in a specialized map

[Damien MATTEI <Damien dot Mattei at unice dot fr>]

yes, thank you, but i try to stay in a functional programming style and avoid "loop"
 that make code unreadable and hard to debug,
 i agree that append should be forbide too as it is require to explore the whole list to append a list
at the tail at each new element, so i rewrite it with "cons" , and i have then only a single reverse 
 on the whole list :

;; map-nil-iter-optim : a map version that exclude nil results
;; the same as map-with-lambdas but will exclude from the result list the '() result of function
;;
;; (map-nil-iter-optim + '() '(1 2 3) '(4 5 6))  -> '(5 7 9)
;; (map-nil-iter-optim (lambda (a b) (if (= a 2) '() (+ a b))) '() '(1 2 3) '(4 5 6)) -> '(5 9)
(define map-nil-iter-optim
  
  (lambda (function result list1 . more-lists)

    (letrec ((some?
	      (lambda (fct list)
		;; returns #t if (function x) returns #t for 
		;; some x in the list
		(and (pair? list)
		     (or
		      (fct (car list))
		      (some? fct (cdr list)))))))

      
      ;; variadic map implementation terminates
      ;; when any of the argument lists is empty.
      (let ((lists (cons list1 more-lists)))

	(if (some? null? lists)
	    result
	    (let* ((funct-result (apply function (map car lists))))

	      (if (null? funct-result)
		  (apply map-nil-iter-optim function result (map cdr lists))
		  (apply
		   map-nil-iter-optim
		   function
		   (cons funct-result result) ;; cons now create a reversed result list
		   (map cdr lists)))))))))



;; (map-nil-iter-optim-call +  '(1 2 3) '(4 5 6))  -> '(5 7 9)
;; (map-nil-iter-optim-call (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6))  -> '(5 9)
(define map-nil-iter-optim-call
  (lambda (function list1 . more-lists)
    (reverse  ;; cons had created a reversed result list
     (apply map-nil-iter-optim function '() (cons list1 more-lists)))))

i'm still searching a fastest way to do that...
perheaps some funfamental routines as map* should be written with set-cdr! and loops and never touch them again.... and build functional programming on top of those low level routines...
i do not know.

Damien

Le Friday 17 March 2017 15:07:03 Sudarshan S Chawathe, vous avez écrit :
> I wrote the following, which seems to work as desired (if I understand
> the original motivation correctly) and seems simpler and more idiomatic
> to me.
> 
> It also avoids the use of 'append', which would lead to quadratic
> running time.  It also does not need the --full-tailcalls option to Kawa
> (which figures out the simple case of tail call used).  It uses SRFI 1
> for the 'any' procedure, but that dependency is easy to remove if
> desired.
> 
> (import (srfi 1))
> 
> (define (map/remove-nulls proc . lsts)
>   (let loop ((lsts lsts)
>              (result '()))
>     (if (any null? lsts)
>         (reverse result)
>         (loop (map cdr lsts)
>               (let ((proc-result (apply proc
>                                         (map car lsts))))
>                 (if (null? proc-result)
>                     result
>                     (cons proc-result
>                           result)))))))
> 
> ;; a few tests
> 
> (map/remove-nulls +  '(1 2 3) '(4 5 6))
> 
> (map/remove-nulls (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6))
> 
> (length (map/remove-nulls (lambda (i j)
>                             (if (even? i)
>                                 '()
>                                 j))
>                           (iota (expt 10 6))
>                           (iota (expt 10 7))))
> 
> Regards,
> 
> -chaw
> 
> 
> > From: Damien MATTEI <Damien.Mattei@unice.fr>
> > To: kawa@sourceware.org
> > Subject: Re: StackOverflowError in a specialized map
> > Date: Fri, 17 Mar 2017 12:38:40 +0100
> > 
> > this and only this version works and WITH --full-tailcalls:
> > 
> > Le Thursday 16 March 2017 11:54:48 Damien MATTEI, vous avez =E9crit=A0:
> > > really hard to solve, in a recursive way....
> > >=20
> > > i have  rewrite the function with as much possible of tail recursion but =
> > it fails again:
> > >=20
> > > ;; map-nil-iter : a map version that exclude nil results
> > > ;; the same as map-with-lambdas but will exclude from the result list the=
> >  '() result of function
> > > ;;
> > > ;; (map-nil-iter + '() '(1 2 3) '(4 5 6))  -> '(5 7 9)
> > > ;; (map-nil-iter (lambda (a b) (if (=3D a 2) '() (+ a b))) '() '(1 2 3) '=
> > (4 5 6)) -> '(5 9)
> > > (define map-nil-iter
> > >=20=20=20
> > >   (lambda (function result list1 . more-lists)
> > >=20
> > >     (letrec ((some?
> > > 	      (lambda (fct list)
> > > 		;; returns #t if (function x) returns #t for=20
> > > 		;; some x in the list
> > > 		(and (pair? list)
> > > 		     (or
> > > 		      (fct (car list))
> > > 		      (some? fct (cdr list)))))))
> > >=20
> > >=20=20=20=20=20=20=20
> > >       ;; variadic map implementation terminates
> > >       ;; when any of the argument lists is empty.
> > >       (let ((lists (cons list1 more-lists)))
> > > 	(if (some? null? lists)
> > > 	    result
> > > 	    (let ((funct-result (apply function (map car lists))))
> > > 	      (if (null? funct-result)
> > > 		  (apply map-nil-iter function result (map cdr lists))
> > > 		  (apply
> > > 		   map-nil-iter
> > > 		   function
> > > 		   (append result (list funct-result))
> > > 		   (map cdr lists)))))))))
> > >=20
> > >=20
> > > ;; (map-nil-iter-call +  '(1 2 3) '(4 5 6))  -> '(5 7 9)
> > > ;; (map-nil-iter-call (lambda (a b) (if (=3D a 2) '() (+ a b))) '(1 2 3) =
> > '(4 5 6))  -> '(5 9)
> > > (define map-nil-iter-call
> > >   (lambda (function list1 . more-lists)
> > >     (apply map-nil-iter function '() (cons list1 more-lists))))
> > >=20
> > > the recursive call of map-nil-iter are no more encapsuled
> > >=20
> > > have not try the --full-tailcalls options, will do it later....
> > 
> > tested and it works=20
> > 
> > great!
> > 
> > got the idea from university course and i reread the chapter at page 27 of =
> > second edition of
> > SICP Structure and Interpretation of Computer Program (Abelson  adn Sussman=
> > )about tail recursion .... explaining how to transform a recursion in an it=
> > erative form using an accumulator to pass result on the factorial example...
> > perhaps the first time i really read this strange old book i bought 25 year=
> > s ago ...
> > 
> > hope it will works with other scheme too, seems in Scheme norm to transform=
> >  tail call in iterations automatically when possible.
> > damien
> > >=20
> > > Damien
> > >=20
> > >=20
> > > Le Wednesday 15 March 2017 17:22:50 Per Bothner, vous avez =E9crit=A0:
> > > > On 03/15/2017 08:08 AM, Damien MATTEI wrote:
> > > > > Hello,
> > > > >
> > > > > i have a custom definition of map ( https://github.com/damien-mattei/=
> > LOGIKI/blob/master/lib/map.scm at  line 392):
> > > > >
> > > > > ;; map-nil : a map version that exclude nil results
> > > > > ;; the same as map-with-lambdas but will exclude from the result list=
> >  the '() result of function
> > > > > ;;
> > > > > ;; (map-nil + '(1 2 3) '(4 5 6)) -> '(5 7 9)
> > > > > (define map-nil
> > > > >   (lambda (function list1 . more-lists)
> > > > >     (letrec ((some? (lambda (fct list)
> > > > > 		      ;; returns #f if (function x) returns #t for
> > > > > 		      ;; some x in the list
> > > > > 		      (and (pair? list)
> > > > > 			   (or (fct (car list))
> > > > > 			       (some? fct (cdr list)))))))
> > > > >
> > > > >       ;; variadic map implementation terminates
> > > > >       ;; when any of the argument lists is empty.
> > > > >       (let ((lists (cons list1 more-lists)))
> > > > > 	(if (some? null? lists)
> > > > > 	    '()
> > > > > 	    (let ((funct-result (apply function (map car lists))))
> > > > > 	      (if (null? funct-result)
> > > > > 		  (apply map-nil function (map cdr lists))
> > > > > 		  (cons funct-result
> > > > > 			(apply map-nil function (map cdr lists))))))))))
> > > > >
> > > > > i use it in various project since many years and this times it create=
> > s a java StackOverflowError on a big list (22527 elements),
> > > >=20
> > > > Not unexpected - you're recursing on a big list.
> > > >=20
> > > > > i'm not sure if it's only in kawa and java that the problem occur so
> > > > > i'm near to code this function differently,
> > > >=20
> > > > Try compiling map-nil with --full-tailcalls.   That might do it.
> > > >=20
> > > > However, if the stack overflow is in the final apply, that won't be eno=
> > ugh,
> > > > because that apply is not a tail-call (because of the cons of the resul=
> > t).
> > > >=20
> > > > You can also try replacing:
> > > >=20=20=20=20=20
> > > >      (apply map-nil function (map XXX))
> > > >=20
> > > > by splice-notation:
> > > >=20
> > > >      (map-nil function @(map XXX))
> > > >=20
> > > > However, I don't think that would be enough for Kawa to be able to inli=
> > ne the tailcalls.
> > > > That would require the splice argument to match up with the more-lists =
> > rest argument,
> > > > which it doesn't.
> > > >=20
> > > > If you don't mind using set-cdr! that would be a relatively simple and =
> > efficient solution:
> > > >=20
> > > >    (if (not (null? funct-result))
> > > >       (let ((new-cons (cons funct-result '()))
> > > >           (if (null? last-pair)
> > > >               (set! result new-cons)
> > > >               (set-cdr! last-pair new-pair))
> > > >           (set! last-pair new-cons))))
> > > >=20
> > > > Instead of using map, put the above snippet inside a for-each.
> > > >=20
> > > > (The list1 parameter seems strange, as it isn't used, as far as i can t=
> > ell.)
> > >=20
> > >=20
> > >=20
> > 
> > 
> > 
> > --=20
> > Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS
> > 
> 



-- 
Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS