(define-signature sequence^
  (empty
   empty?
   insert   ; the "natural" insertion of the particular sequence
   remove   ; the "natural" removal of the particular sequence
   first
   fold
   fold/exit
   ))

(define-signature +catenable-sequence^
  (append))

(define-signature catenable-sequence^
  ((open sequence^)
   (open +catenable-sequence^)))

(define-signature +output-restricted-double-ended-sequence^   ; due to (- ...) not legal in open
  (insert-first
   insert-last   
   remove-first))

(define-signature +double-ended-sequence^
  ((open +output-restricted-double-ended-sequence^)
   remove-last))

(define-signature double-ended-sequence^
  ((open sequence^)
   (open +double-ended-sequence^)))

(define-signature catenable-double-ended-sequence^
  ((open sequence^)
   (open +double-ended-sequence^)
   (open +catenable-sequence^)))

(define-signature +list^
  (; sequence names
   insert-first  ; = insert
   remove-first  ; = remove
   ; list names
   cons       ; = insert-first
   rest cdr   ; = remove-first
   car        ; = first
   ))

(define-signature list^    
  ((open sequence^)
   (open +list^)))

(define-signature catenable-list^
  ((open list^)
   (open +catenable-sequence^)))
  
(define-signature double-ended-list^    
  ; also called output restricted deque
  ((open list^)
   (open +output-restricted-double-ended-sequence^)
   snoc       ; = insert-last
   ))

(define-signature catenable-double-ended-list^    
  ((open double-ended-list^)
   (open +catenable-sequence^)))

(define-signature +queue^
  ((open sequence^)
   ; sequence names
   insert-last    ; = insert
   remove-first   ; = remove
   ; queue names
   enqueue  ;  = insert-last 
   dequeue  ;  = remove-first
   ))

(define-signature queue^    
  ((open sequence^)
   (open +queue^)))

; this doesn't work: remove-first is in 
; both +list^ and +queue^
(define-signature deque^    
  ((open double-ended-sequence^)
   (open +list^)
   (open +queue^)))

(define-signature catenable-deque^
  ((open deque^)
   (open +catenable-sequence^)))