; General Sexp Tree Manipulation
; ==============================
;
;  These view sexps as trees as follows:
;
;    list:     list of child trees
;    non-list: data leaf
;
;    Some implications:
;
;      - empty list has no children and no data
;      - lists can't be data
;
;    Also, the interpretation/behaviour of improper lists is unspecified
;     except where indicated.

(module sexp-tree mzscheme
  (provide sexp->list-of-subtree-sexps
           maximal-subtree-sexps
           maximal-subtree-sexps-replace)

;  All subtrees
;  ============
;
;  (sexp->list-of-subtree-sexps s) -> list of all subtrees of s
;   ---------------------------
;
;    I.e. return a list containing: s, elements of s, elements of elements of s, etc.
;    - doesn't enter improper lists.
;
;    Compared with flatten: includes intermediate expressions, not just leaves/atoms.
;
(define (sexp->list-of-subtree-sexps s)
  `(,s ,@(if (list? s) (apply append (map sexp->list-of-subtree-sexps s)) '())))

;  Maximal subtrees wrt a property
;  ===============================
;
;  Maximal: not contained in a larger tree satisfying the property.
;    I.e. in a preorder traversal, skip children when test? is satisfied.
;
;  (maximal-subtree-sexps test? s) -> list of all maximal subtrees satisfying test?.
;   ---------------------
;
;  (maximal-subtree-sexps-replace test? replacer s) ->
;   -----------------------------
;    s with maximal subtrees satisfying test? replaced by calling replacer on them.
;
(define (maximal-subtree-sexps test? s)
  (let m-s-s ((s s))
    (cond ((test? s) `(,s))
          ((list? s) (apply append (map m-s-s s)))
          (#t '()))))
;
(define (maximal-subtree-sexps-replace test? replacer s)
  (let m-s-s ((s s))
    (cond ((test? s) (replacer s))
          ((list? s) (map m-s-s s))
          (#t s))))

)