#lang racket

; Example of threading state through a recursively decomposed problem.

; Problem: go through a list (utimately an expression to be transformed)
; and sequentially number each token encountered in the left to right
; depth-first traversal of the list.
; 
; For example:
; (walk-over '( (a b ( c d ) e ) f ( g h (i ( j k ( l m ) ) ) ) n ) )
; geneates this result:
; ((a-0 b-1 (c-2 d-3) e-4) f-5 (g-6 h-7 (i-8 (j-9 k-10 (l-11 m-12)))) n-13)

; The recursor takes state-in (a list) and an expression and returns
; a list (state-out result)
; 
; (walk-over-expression-r state-in expr) -> (state-out result)

; The state is very simple, consisting of a 1-element list, where the 
; element is the sequence number for the next symbol.

(define walk-over-r
  (lambda (state-in expr)
    (cond  
      ( (not (list? expr)) 
        ; handle simple atomic term here, use new symbol number and update
        ; the next symbol number
        (list (list (+ 1 (first state-in)))
              (string->symbol (string-append  (symbol->string expr) "-" 
                       (number->string (first state-in)) ) ))
       )
      (#t 
       ; handle list here, use fold to thread previous results 
        (foldl 
         ; e is the current element to be processed
         ; fold-state is a list (state-in current-fold-results)
         
         (lambda (e fold-state) 
           (let ( [ e-result (walk-over-r (first fold-state) e) ] )
             ; now construct new fold state to pass along consisting of
             ; updated state and appending modified expression to the 
             ; current-fold-results
             (list (first e-result) 
                   (append (second fold-state) (list (second e-result)))
              )
           )
           )
         
         (list state-in '()) ; initial state and result
         expr
        )
       )
      )
    )
    )

(define walk-over
  (lambda (expr)
    (second (walk-over-r '(0) expr))
    
    ; To see what the final state is, use this variant
    ; (walk-over-r '(0) expr)
    ))



(walk-over '())
(walk-over 'a)
(walk-over '(a b c))
(walk-over '(lambda () x))
(walk-over '(lambda (x) x))
(walk-over '(lambda (x y) x))
(walk-over '(lambda (x) (lambda (y) x y)))
(walk-over '(lambda (x) (lambda (y) x y (lambda (z) (lambda (y) x y)))))
(walk-over '( (a b ( c d ) e ) f ( g h (i ( j k ( l m ) ) ) ) n ) )