From address@hidden Wed Jan 24 00:20:26 2001
Date: Thu, 8 Jun 2000 02:54:17 +0200 (MEST)
From: Dirk Herrmann <address@hidden>
To: Peter C. Norton <address@hidden>
Cc: Guile Mailing List <address@hidden>
Subject: readdir

Hello!

When I was looking at perls readdir implementation:

  opendir(DIR,".");
  @files = sort grep(!/^\./, readdir(DIR));
  closedir(DIR);

and the implementation for guile

  (define files '())

  (let* ((dport (opendir "."))
         (regexp (make-regexp "^\\."))
         (entry (readdir dport)))
    (while (not (eof-object? entry))
           (if (not (regexp-exec regexp entry))
               (set! files (cons entry files)))
           (set! entry (readdir dport)))
    (set! files (sort files string<?))
    (closedir dport))

I felt that guile users might be disappointed because of the seemingly
enormous efforts in order to achieve something that perl does in three
lines of code.  Thus, I took a different approach and wrote a more
tutorial style thingy about how to arrive at a point where you could
simply write the following line in guile:

  (sort (grep "^[^.]" (directory->list ".")) string<?)

It's not comparable to your approach, because it is less focused on a
special problem.  However, maybe it makes a good extension to your
example, in the sense of "and if you want to learn how to do it in a more
general way, read on".

If you like it, you are free to do with it whatever you like.  While
writing it I realized that I was not sure about how much explanation
certain schemey things needed, thus it is a mixture of assuming the reader
knows something about scheme and assuming the reader doesn't know very
much about it yet.  And, it's not guaranteed to be bug free.  (Put the
usual GPL style ABSOLUTELY NO WARRANTY disclaimer here :-)

Best regards
Dirk




;;
;; From a given list of objects, select those objects that fulfill a given
;; predicate.  Return these selected objects in a new list.  This function can
;; be seen as a filter:  It filters interesting things out of a larger list.
;;
;; Examples:  
;;   (filter odd?  '(0 1 2 3 4 5 7 9)) --> (1 3 5 7 9)
;;   (filter even? '(0 1 2 3 4 5 7 9)) --> (0 2 4)
;;

;;
;; Below is a first solution.  It works, but has a slight disadvantage:  If
;; the list of objects is very long, it will use a lot of stack space.  The
;; reason is, that in order to perform the 'cons' command, the recursive call
;; to filter must have taken place and delivered a result.  You can think of
;; the 'cons' as if it is "waiting" on the stack for the delivery of its
;; parameter.  Another problem of this first solution is, that the predicate,
;; which is constant during the filtering, has always to be passed as a
;; parameter.
;;
(define (filter pred? objs)
  (cond ((null? objs) '())
	((pred? (car objs)) (cons (car objs) (filter pred? (cdr objs))))
	(else (filter pred? (cdr objs)))))

;;
;; The second solution below avoids to pass the predicate with every recursive
;; call.  The trick is, that the 'let loop' creates a function called 'loop'
;; within the function 'filter'.  Then, 'loop' is called instead of 'filter'
;; and the predicate of the surrounding scope can be used within the loop.
;; This is an improvement, but may still use a lot of stack space.
;;
(define (filter pred? objects)
  (let loop ((objs objects))
    (cond ((null? objs) '())
	  ((pred? (car objs)) (cons (car objs) (loop (cdr objs))))
	  (else (loop (cdr objs))))))

;;
;; The third solution below reduces the stack usage by making use of scheme's
;; tail call elimination rule which I will try to explain:  With the two
;; examples above we had the situation, that the results of the recursive call
;; were still needed by the function 'cons'.  Thus, for every recursive call
;; there was a 'cons' "waiting" on the stack for the desired parameter.  The
;; solution below avoids this by introduction of an additional parameter
;; 'results'.  With the help of this parameter it is possible to rewrite the
;; function in a way that there is no need to wait for the result of the
;; recursive call any more, i. e. the only thing that has to be done with the
;; result of the recursive call is to return it to the caller.  Fortunately,
;; this situation allows to get completely rid of the recursion stack:
;; Instead of "waiting" on the stack just to return the result of some
;; function call, the caller says to the callee:  "Hey, I just want your
;; return value in order to return it as my own result.  Please, pass your
;; result directly to my caller."  (Actually, this is not the way tail call
;; elimination is implemented, but this explains why it works.)  Due to the
;; restructuring, the list 'result' contains the elements in the wrong order,
;; which is the reason for the call to 'reverse!' before returning the
;; result.
;;
(define (filter pred? objects)
  (let loop ((objs objects)
	     (result '()))
    (cond ((null? objs) (reverse! result))
	  ((pred? (car objs)) (loop (cdr objs) (cons (car objs) result)))
	  (else (loop (cdr objs) result)))))

;;
;; Since you can provide any predicate to filter, it is an extremely powerful
;; function.  The following example shows how to implement a function with a
;; 'grep' like behaviour.  While the UN*X 'grep' command works on input lines,
;; the grep below works on a list of strings.  In the implementation of 'grep'
;; below, a temporary predicate is created using 'lambda'.  (You can
;; understand lambda better if you think of it as 'make-function'.)
;;
;; Examples:  
;;   (grep "^[0-9].*" '("0a" "b" "6" "c" "0d")) --> ("0a" "6" "0d")
;;   (grep "^[^0-9].*" '("0a" "b" "6" "c" "0d")) --> ("b" "c")
;;   (grep "[^0-9].*" '("0a" "b" "6" "c" "0d")) --> ("0a" "b" "c" "0d")
;;
(define (grep rx strings)
  (let ((r (make-regexp rx)))
    (filter (lambda (x) (regexp-exec r x)) strings)))

;;
;; The following code reads the entries of a directory (given as a string)
;; into a list of strings.  Again, we use scheme's tail call elimination rule
;; to reduce stack usage in case of large directories.
;;
(define (directory->list dir)
  (let ((dport (opendir dir)))
    (let loop ((entry (readdir dport))
	       (files '()))
      (if (not (eof-object? entry))
	  (loop (readdir dport) (cons entry files))
	  (begin
	    (closedir dport)
	    (reverse! files))))))

;;
;; Putting the pieces together, we can now easily provide a sorted list of all
;; files except dot files in the current directory.
;;
(sort (grep "^[^.]" (directory->list ".")) string<?)