srfi-1.scm

MSYS在windows下模拟了一个类unix的终端

;;; srfi-1.scm --- List Library

;; 	Copyright (C) 2001, 2002 Free Software Foundation, Inc.
;;
;; This program is free software; you can redistribute it and/or
;; modify it under the terms of the GNU General Public License as
;; published by the Free Software Foundation; either version 2, or
;; (at your option) any later version.
;;
;; This program is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
;; General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with this software; see the file COPYING.  If not, write to
;; the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
;; Boston, MA 02111-1307 USA
;;
;; As a special exception, the Free Software Foundation gives permission
;; for additional uses of the text contained in its release of GUILE.
;;
;; The exception is that, if you link the GUILE library with other files
;; to produce an executable, this does not by itself cause the
;; resulting executable to be covered by the GNU General Public License.
;; Your use of that executable is in no way restricted on account of
;; linking the GUILE library code into it.
;;
;; This exception does not however invalidate any other reasons why
;; the executable file might be covered by the GNU General Public License.
;;
;; This exception applies only to the code released by the
;; Free Software Foundation under the name GUILE.  If you copy
;; code from other Free Software Foundation releases into a copy of
;; GUILE, as the General Public License permits, the exception does
;; not apply to the code that you add in this way.  To avoid misleading
;; anyone as to the status of such modified files, you must delete
;; this exception notice from them.
;;
;; If you write modifications of your own for GUILE, it is your choice
;; whether to permit this exception to apply to your modifications.
;; If you do not wish that, delete this exception notice.

;;; Author: Martin Grabmueller <[e-mail]>
;;; Date: 2001-06-06

;;; Commentary:

;; This is an implementation of SRFI-1 (List Library).
;;
;; All procedures defined in SRFI-1, which are not already defined in
;; the Guile core library, are exported.  The procedures in this
;; implementation work, but they have not been tuned for speed or
;; memory usage.
;;
;; This module is fully documented in the Guile Reference Manual.

;;; Code:

(define-module (srfi srfi-1)
  :use-module (ice-9 session)
  :use-module (ice-9 receive))

(begin-deprecated
 ;; Prevent `export' from re-exporting core bindings.  This behaviour
 ;; of `export' is deprecated and will disappear in one of the next
 ;; releases.
 (define iota #f)
 (define map #f)
 (define map-in-order #f)
 (define for-each #f)
 (define list-index #f)
 (define member #f)
 (define delete #f)
 (define delete! #f)
 (define assoc #f))

(export
;;; Constructors
 ;; cons				<= in the core
 ;; list				<= in the core
 xcons
 ;; cons*				<= in the core
 ;; make-list				<= in the core
 list-tabulate
 ;; list-copy				<= in the core
 circular-list
 iota					; Extended.

;;; Predicates
 proper-list?
 circular-list?
 dotted-list?
 ;; pair?				<= in the core
 ;; null?				<= in the core
 null-list?
 not-pair?
 list=

;;; Selectors
 ;; car					<= in the core
 ;; cdr					<= in the core
 ;; caar				<= in the core
 ;; cadr				<= in the core
 ;; cdar				<= in the core
 ;; cddr				<= in the core
 ;; caaar				<= in the core
 ;; caadr				<= in the core
 ;; cadar				<= in the core
 ;; caddr				<= in the core
 ;; cdaar				<= in the core
 ;; cdadr				<= in the core
 ;; cddar				<= in the core
 ;; cdddr				<= in the core
 ;; caaaar				<= in the core
 ;; caaadr				<= in the core
 ;; caadar				<= in the core
 ;; caaddr				<= in the core
 ;; cadaar				<= in the core
 ;; cadadr				<= in the core
 ;; caddar				<= in the core
 ;; cadddr				<= in the core
 ;; cdaaar				<= in the core
 ;; cdaadr				<= in the core
 ;; cdadar				<= in the core
 ;; cdaddr				<= in the core
 ;; cddaar				<= in the core
 ;; cddadr				<= in the core
 ;; cdddar				<= in the core
 ;; cddddr				<= in the core
 ;; list-ref				<= in the core
 first
 second
 third
 fourth
 fifth
 sixth
 seventh
 eighth
 ninth
 tenth
 car+cdr
 take
 drop
 take-right
 drop-right
 take!
 drop-right!
 split-at
 split-at!
 last
 ;; last-pair				<= in the core

;;; Miscelleneous: length, append, concatenate, reverse, zip & count
 ;; length				<= in the core
 length+
 ;; append				<= in the core
 ;; append!				<= in the core
 concatenate
 concatenate!
 ;; reverse				<= in the core
 ;; reverse!				<= in the core
 append-reverse
 append-reverse!
 zip
 unzip1
 unzip2
 unzip3
 unzip4
 unzip5
 count

;;; Fold, unfold & map
 fold
 fold-right
 pair-fold
 pair-fold-right
 reduce
 reduce-right
 unfold
 unfold-right
 map					; Extended.
 for-each				; Extended.
 append-map
 append-map!
 map!
 map-in-order				; Extended.
 pair-for-each
 filter-map

;;; Filtering & partitioning
 filter
 partition
 remove
 filter!
 partition!
 remove!

;;; Searching
 find
 find-tail
 take-while
 take-while!
 drop-while
 span
 span!
 break
 break!
 any
 every
 list-index				; Extended.
 member					; Extended.
 ;; memq				<= in the core
 ;; memv				<= in the core

;;; Deletion
 delete					; Extended.
 delete!				; Extended.
 delete-duplicates
 delete-duplicates!

;;; Association lists
 assoc					; Extended.
 ;; assq				<= in the core
 ;; assv				<= in the core
 alist-cons
 alist-copy
 alist-delete
 alist-delete!

;;; Set operations on lists
 lset<=
 lset=
 lset-adjoin
 lset-union
 lset-intersection
 lset-difference
 lset-xor
 lset-diff+intersection
 lset-union!
 lset-intersection!
 lset-difference!
 lset-xor!
 lset-diff+intersection!

;;; Primitive side-effects
 ;; set-car!				<= in the core
 ;; set-cdr!				<= in the core
 )

(cond-expand-provide (current-module) '(srfi-1))

;;; Constructors

(define (xcons d a)
  (cons a d))

;; internal helper, similar to (scsh utilities) check-arg.
(define (check-arg-type pred arg caller)
  (if (pred arg)
      arg
      (scm-error 'wrong-type-arg caller
		 "Wrong type argument: ~S" (list arg) '())))

;; the srfi spec doesn't seem to forbid inexact integers.
(define (non-negative-integer? x) (and (integer? x) (>= x 0)))

(define (list-tabulate n init-proc)
  (check-arg-type non-negative-integer? n "list-tabulate")
  (let lp ((n n) (acc '()))
    (if (<= n 0)
      acc
      (lp (- n 1) (cons (init-proc (- n 1)) acc)))))

(define (circular-list elt1 . rest)
  (let ((start (cons elt1 '())))
    (let lp ((r rest) (p start))
      (if (null? r)
	(begin
	  (set-cdr! p start)
	  start)
	(begin
	  (set-cdr! p (cons (car r) '()))
	  (lp (cdr r) (cdr p)))))))

(define (iota count . rest)
  (check-arg-type non-negative-integer? count "iota")
  (let ((start (if (pair? rest) (car rest) 0))
	(step (if (and (pair? rest) (pair? (cdr rest))) (cadr rest) 1)))
    (let lp ((n 0) (acc '()))
      (if (= n count)
	(reverse! acc)
	(lp (+ n 1) (cons (+ start (* n step)) acc))))))

;;; Predicates

(define (proper-list? x)
  (list? x))

(define (circular-list? x)
  (if (not-pair? x)
    #f
    (let lp ((hare (cdr x)) (tortoise x))
      (if (not-pair? hare)
	#f
	(let ((hare (cdr hare)))
	  (if (not-pair? hare)
	    #f
	    (if (eq? hare tortoise)
	      #t
	      (lp (cdr hare) (cdr tortoise)))))))))

(define (dotted-list? x)
  (cond
    ((null? x) #f)
    ((not-pair? x) #t)
    (else
     (let lp ((hare (cdr x)) (tortoise x))
       (cond
	 ((null? hare) #f)
	 ((not-pair? hare) #t)
	 (else
	  (let ((hare (cdr hare)))
	    (cond
	      ((null? hare) #f)
	      ((not-pair? hare) #t)
	      ((eq? hare tortoise) #f)
	      (else
	       (lp (cdr hare) (cdr tortoise)))))))))))

(define (null-list? x)
  (cond
    ((proper-list? x)
     (null? x))
    ((circular-list? x)
     #f)
    (else
     (error "not a proper list in null-list?"))))

(define (not-pair? x)
  (not (pair? x)))

(define (list= elt= . rest)
  (define (lists-equal a b)
    (let lp ((a a) (b b))
      (cond ((null? a)
	     (null? b))
	    ((null? b)
	     #f)
	    (else
	     (and (elt= (car a) (car b))
		  (lp (cdr a) (cdr b)))))))
  (or (null? rest)
      (let ((first (car rest)))
	(let lp ((lists rest))
	  (or (null? lists)
	      (and (lists-equal first (car lists))
		   (lp (cdr lists))))))))

;;; Selectors

(define first car)
(define second cadr)
(define third caddr)
(define fourth cadddr)
(define (fifth x) (car (cddddr x)))
(define (sixth x) (cadr (cddddr x)))
(define (seventh x) (caddr (cddddr x)))
(define (eighth x) (cadddr (cddddr x)))
(define (ninth x) (car (cddddr (cddddr x))))
(define (tenth x) (cadr (cddddr (cddddr x))))

(define (car+cdr x) (values (car x) (cdr x)))

(define (take x i)
  (let lp ((n i) (l x) (acc '()))
    (if (<= n 0)
      (reverse! acc)
      (lp (- n 1) (cdr l) (cons (car l) acc)))))
(define (drop x i)
  (let lp ((n i) (l x))
    (if (<= n 0)
      l
      (lp (- n 1) (cdr l)))))
(define (take-right flist i)
  (let lp ((n i) (l flist))
    (if (<= n 0)
      (let lp0 ((s flist) (l l))
	(if (null? l)
	  s
	  (lp0 (cdr s) (cdr l))))
      (lp (- n 1) (cdr l)))))

(define (drop-right flist i)
  (let lp ((n i) (l flist))
    (if (<= n 0)
      (let lp0 ((s flist) (l l) (acc '()))
	(if (null? l)
	  (reverse! acc)
	  (lp0 (cdr s) (cdr l) (cons (car s) acc))))
      (lp (- n 1) (cdr l)))))

(define (take! x i)
  (if (<= i 0)
    '()
    (let lp ((n (- i 1)) (l x))
      (if (<= n 0)
	(begin
	  (set-cdr! l '())
	  x)
	(lp (- n 1) (cdr l))))))

(define (drop-right! flist i)
  (if (<= i 0)
    flist
    (let lp ((n (+ i 1)) (l flist))
      (if (<= n 0)
	(let lp0 ((s flist) (l l))
	  (if (null? l)
	    (begin
	      (set-cdr! s '())
	      flist)
	    (lp0 (cdr s) (cdr l))))
	(if (null? l)
	  '()
	  (lp (- n 1) (cdr l)))))))

(define (split-at x i)
  (let lp ((l x) (n i) (acc '()))
    (if (<= n 0)
      (values (reverse! acc) l)
      (lp (cdr l) (- n 1) (cons (car l) acc)))))

(define (split-at! x i)
  (if (<= i 0)
    (values '() x)
    (let lp ((l x) (n (- i 1)))
      (if (<= n 0)
	(let ((tmp (cdr l)))
	  (set-cdr! l '())
	  (values x tmp))
	(lp (cdr l) (- n 1))))))

(define (last pair)
  (car (last-pair pair)))

;;; Miscelleneous: length, append, concatenate, reverse, zip & count

(define (length+ clist)
  (if (null? clist)
    0
    (let lp ((hare (cdr clist)) (tortoise clist) (l 1))
      (if (null? hare)
	l
	(let ((hare (cdr hare)))
	  (if (null? hare)
	    (+ l 1)
	    (if (eq? hare tortoise)
	      #f
	      (lp (cdr hare) (cdr tortoise) (+ l 2)))))))))

(define (concatenate l-o-l)
  (let lp ((l l-o-l) (acc '()))
    (if (null? l)
      (reverse! acc)
      (let lp0 ((ll (car l)) (acc acc))
	(if (null? ll)
	  (lp (cdr l) acc)
	  (lp0 (cdr ll) (cons (car ll) acc)))))))

(define (concatenate! l-o-l)
  (let lp0 ((l-o-l l-o-l))
    (cond
      ((null? l-o-l)
       '())
      ((null? (car l-o-l))
       (lp0 (cdr l-o-l)))
      (else
       (let ((result (car l-o-l)) (tail (last-pair (car l-o-l))))
	 (let lp ((l (cdr l-o-l)) (ntail tail))
	   (if (null? l)
	     result
	     (begin
	       (set-cdr! ntail (car l))
	       (lp (cdr l) (last-pair ntail))))))))))


(define (append-reverse rev-head tail)
  (let lp ((l rev-head) (acc tail))
    (if (null? l)
      acc
      (lp (cdr l) (cons (car l) acc)))))

(define (append-reverse! rev-head tail)
  (append-reverse rev-head tail))	; XXX:optimize

(define (zip clist1 . rest)
  (let lp ((l (cons clist1 rest)) (acc '()))
    (if (any null? l)
      (reverse! acc)
      (lp (map1 cdr l) (cons (map1 car l) acc)))))


(define (unzip1 l)
  (map1 first l))
(define (unzip2 l)
  (values (map1 first l) (map1 second l)))
(define (unzip3 l)
  (values (map1 first l) (map1 second l) (map1 third l)))
(define (unzip4 l)
  (values (map1 first l) (map1 second l) (map1 third l) (map1 fourth l)))
(define (unzip5 l)
  (values (map1 first l) (map1 second l) (map1 third l) (map1 fourth l)
	  (map1 fifth l)))

(define (count pred clist1 . rest)
  (if (null? rest)
      (count1 pred clist1)
      (let lp ((lists (cons clist1 rest)))
	(cond ((any1 null? lists)
	       0)
	      (else
	       (if (apply pred (map1 car lists))
		 (+ 1 (lp (map1 cdr lists)))
		 (lp (map1 cdr lists))))))))

(define (count1 pred clist)
  (let lp ((result 0) (rest clist))
    (if (null? rest)
	result
	(if (pred (car rest))
	    (lp (+ 1 result) (cdr rest))
	    (lp result (cdr rest))))))

;;; Fold, unfold & map