[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

FOLD/UNFOLD inconsistency?

This page is part of the web mail archives of SRFI 1 from before July 7th, 2015. The new archives for SRFI 1 contain all messages, not just those from before July 7th, 2015.

Hi Olin:

I looked over SRFI-1 one more time (!) and found an inconsistency
in FOLD/UNFOLD section:

- although right version of FOLD is more "natural" of the two
  (homomorphism), it has long name while less "natural" has
  short name  (I don't think that "natural" here is just a matter of
  my personal preferences; SICP book uses the right version 
  throughout the "sequences as conventional interfaces" chapter, 
  while left version is only mentioned in exercises)

- UNFOLD can be considered an "inverse" of the right version of
  fold, but its name suggests relation with the short (left) version:

  given operations knull?, kar, kdr, kons, knil satisfying
  (kons (kar x) (kdr x)) == x  and (knull? knil) == #t
  we have:
   (FOLD-RIGHT kons knil (UNFOLD knull? kar kdr x)) == x
   (UNFOLD knull? kar kdr (FOLD-RIGHT kons knil x)) == x

- iterative variant of UNFOLD ("inverse" of FOLD-LEFT) is missing

My suggestions are: 

1) add "left" (iterative) version of UNFOLD:

(define (unfold-left p f g seed)
  (check-arg procedure? p unfold)
  (check-arg procedure? f unfold)
  (check-arg procedure? g unfold)
  (let lp ((seed seed) (lis '()))
    (if (p seed) lis
      (lp (g seed) (cons (f seed) lis)))))


2) either name them FOLD, FOLD-LEFT, UNFOLD, and UNFOLD-LEFT
Personally, I prefer the first variant.

Sorry for late comments,