Re: StackOverflowError in a specialized map

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

part of the answer that did not reached the mailing list was here:

https://groups.google.com/forum/#!msg/comp.lang.scheme/40wwKHG43Uw/wq71EH4nCQAJ


Damien

On Sun, Mar 26, 2017 at 11:49 AM, Damien Mattei <damien.mattei@gmail.com> wrote:
> 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
>>
>>