(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^
  ((open sequence^)
   append))

(define-signature double-ended-sequence^
  ((open sequence^)
   insert-first
   insert-last   
   remove-first
   remove-last))

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

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

(define-signature catenable-list^
  ((open list^)
   (open catenable-sequce^)))
  
(define-signature double-ended-list^    
  ; also called output restricted deque
  ((open double-ended-sequence^ (- remove-last))  ; The (- ...) is not legal syntax
   (open list^)
   snoc       ; = insert-last
   ))

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

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

(define-signature deque^    
  ((open double-ended-sequence^)
   (open list^)
   (open queue^)))

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