bugGuile - Bugs: bug #30071, unfold isn't tail-recursive

 
 

bug #30071: unfold isn't tail-recursive

Submitted by:  Szavai Gyula <szgyg>
Submitted on:  Mon 07 Jun 2010 06:30:34 PM UTC  
 
Category: NoneSeverity: 3 - Normal
Item Group: NoneStatus: Fixed
Privacy: PublicAssigned to: Ludovic Courtès <civodul>
Open/Closed: Closed

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Fri 08 Oct 2010 02:28:05 PM UTC, comment #3:

Fixed along these lines:

http://git.savannah.gnu.org/cgit/guile.git/commit/?id=07076c1e61ab05b62979ee01a5220edb308b0750

Thanks!

Ludo'.

Ludovic Courtès <civodul>
Project AdministratorIn charge of this item.
Thu 10 Jun 2010 03:57:38 PM UTC, comment #2:

; I mean the simple implementation

(define* (unfold p f g s #:optional (t (lambda (x) '())))
(let loop ((s s) (a '()))
(if (p s)
(rev-append a (t s))
(loop (g s) (cons (f s) a)))))

(define (rev-append xs ys)
(if (null? xs)
ys
(rev-append (cdr xs) (cons (car xs) ys))))

Szavai Gyula <szgyg>
Tue 08 Jun 2010 09:47:56 PM UTC, comment #1:

Hello,

Doesn't the TAIL-GEN argument prevent it from being implemented in a tail-recursive fashion?

(When TAIL-GEN is omitted it can be tail-recursive.)

Thanks,
Ludo'.

Ludovic Courtès <civodul>
Project AdministratorIn charge of this item.
Mon 07 Jun 2010 06:30:34 PM UTC, original submission:

(use-modules (srfi srfi-1))

(write
(false-if-exception
(let ((stack (* 0.05 (cadr (member 'stack (debug-options))))))
(unfold (lambda (x) (> x stack)) identity 1+ 0)
#t)))

Szavai Gyula <szgyg>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by civodul (Posted a comment)
  • -unavailable- added by szgyg (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 08 Oct 2010 02:28:05 PM UTCcivodulStatusNone=>Fixed
      Open/ClosedOpen=>Closed
    Thu 17 Jun 2010 01:07:24 PM UTCcivodulAssigned toNone=>civodul

    Back to the top


    Powered by Savane 3.1-cleanup1