Re: StackOverflowError in a specialized map

[Damien Mattei <damien dot mattei at gmail dot com>]

Hi Chaw,

thank for your message,
i have posted an answer friday unfortunately it does not correctly the
mailins list due to copy-carbon i think, i have not the text of my
answer here but i  will be able to repost it on monday.

basically it works now in kawa without use of --tail-calls option,
the only penality is that i need in my solution ,as of yours to use a
_reverse_ call ,
but there is nothing else to do unfortunately ,except use some
iteration and set-cdr! because in LisP and Scheme lists are "linked"
in only one way from begin to tail (end)  ,and you cannot explore the
list in reverse starting from tail (end) to begin , because CAR is
pointing to element and CDR to rest of the list,when you have a PAIR
you can find the CDR but with the CDR you cannot get the previous
PAIR, so in LisP and Scheme you cannot find such a recursive function
to do this without at least at the end reversing the list.

here is my last version:

;; map-nil-iter-optim-tail-calls : 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-tail-calls + '() '((1 2 3) (4 5 6)))  -> '(9 7 5)
;; (map-nil-iter-optim-tail-calls (lambda (a b) (if (= a 2) '() (+ a
b))) '() '((1 2 3) (4 5 6))) -> '(9 5)
(define map-nil-iter-optim-tail-calls

  (lambda (function result 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.

      (if (some? null? lists)

      result

      (let* ((funct-result (apply function (map car lists))))

        (if (null? funct-result)

        (map-nil-iter-optim-tail-calls function result (map cdr lists))

        (map-nil-iter-optim-tail-calls
         function
         (cons funct-result result) ;; cons now create a reversed result list
         (map cdr lists))))))))


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


regards,

Damien

On Sat, Mar 25, 2017 at 11:56 PM, Sudarshan S Chawathe <chaw@eip10.org> wrote:
>> From: Damien MATTEI <Damien.Mattei@unice.fr>
>> Date: Tue, 21 Mar 2017 15:00:57 +0100
>>
>> yes, thank you, but i try to stay in a functional programming style
>> and avo= id "loop" that make code unreadable and hard to debug,
>
> I suspect I may be misunderstanding your quest, but I don't see a
> significant difference between a 'named let' and a nested function
> definition (with respect to being functional programming).  Perhaps I
> should have used a name 'recur' instead of 'loop' in my earlier version.
>
> For example, if we wish to avoid named let altogether for some reason,
> we could use the following variant of my earlier implementation.
>
> (define (map/remove-nulls-1 proc . lsts)
>   (define (f lsts result)
>     (if (any null? lsts)
>         (reverse result)
>         (f (map cdr lsts)
>            (let ((proc-result (apply proc
>                                      (map car lsts))))
>              (if (null? proc-result)
>                  result
>                  (cons proc-result
>                        result))))))
>   (f lsts '()))
>
> Or, going another way, we could use fold:
>
> (define (map/remove-nulls-2 proc . lsts)
>   (reverse (apply fold
>                   (lambda fargs
>                     (let ((accum (last fargs))
>                           (pargs (drop-right fargs 1)))
>                       (let ((r (apply proc pargs)))
>                         (if (null? r)
>                             accum
>                             (cons r accum)))))
>                   '()
>                   lsts)))
>
> As before, I'm using some SRFI 1 procedures for convenience; they can be
> avoided easily: any, fold, last, drop-right.
>
> Both the above versions, like the one I posted earlier, work without
> problems in Kawa without needing the --full-tailcalls option (i.e., Kawa
> properly detects and eliminates and simple cases of tail calls they
> use).  The slight awkwardness of last/drop-right is due to the
>
> But, as I noted before, perhaps I'm missing the main point of the
> original question.
>
> Regards,
>
> -chaw
>
>