[racket] Building an indexing function for lists-of-lists

#lang racket 

;; guess: 
;; S-expr is one of: 
;; -- '()
;; -- (cons Atom S-expr)
;; -- (cons S-expr S-expr)
;; Atom is one of: 
;; -- Number
;; -- Symbol 


(module+ test
  (require rackunit))

;; fix 1: encapsulate the function via a local definition 
;; because you rarely want to expose the accumulator function 

; S-expr -> S-expr 
; this function is to convert one list into a list of indices 

(module+ test 
  (check-equal? (index-s-expr '(+ .3 (- .1 x))) '(1 2 (3 4 5)))
  (check-equal? (index-s-expr '(+ (- .1 .2) .3)) '(1 (2 3 4) 5)))

(define (index-s-expr.v1 s-exp0)
  ;; S-expr Nat -> S-expr 
  ;; replace atoms with their index according to a leftmost traversal 
  ;; accumulator: index is the number of atoms seen so far 
  (define (index-s-exp s-exp index)
    (cond [(empty? s-exp) empty]
          [(atom? (first s-exp))
           (cons index (index-s-exp (rest s-exp) (add1 index)))]
          [else 
           (cons (index-s-exp (first s-exp) index)
                 (index-s-exp (rest s-exp) (add1 index)))]))
  ;; -- IN -- 
  (index-s-exp s-exp0 1))

;; the real fix: you need to return the transformed expression 
;; WITH the index consumed so far 

(define (index-s-expr s-exp0)
  ;; S-expr Nat -> S-expr Nat 
  ;; replace atoms with their index according to a leftmost traversal 
  ;; accumulator: index is the number of atoms seen so far 
  ;; store: the returned index is the number of atoms replaced 
  ;; during the traversal of the first argument -- [see diff between atom and cons clause]
  (define (index-s-exp s-exp index)
    (cond [(empty? s-exp) (values empty index)]
          [(atom? (first s-exp))
           (define-values (rst rst-index) (index-s-exp (rest s-exp) (add1 index)))
           (values (cons index rst) rst-index)]
          [else 
           (define-values (fst fst-index) (index-s-exp (first s-exp) index))
           (define-values (rst rst-index) (index-s-exp (rest s-exp) fst-index))
           (values (cons fst rst) rst-index)]))
  ;; -- IN -- 
  (define-values (result _) (index-s-exp s-exp0 1))
  result)
  
(define (atom? x) (or (number? x) (symbol? x)))


On Jan 13, 2014, at 6:06 PM, Rian Shams <rian.shams at gmail.com> wrote:

> I am trying to build the following indexing function:
> 
> ;list-of-lists beginning-index-number -> list-of-lists
> ;The purpose of this function is to convert one list into another list of incremental numbers, while at the same time, maintaining the structure of the original list. To basically number each point/node in a given list, and return the new numbered list in the same form as the original.
> 
> Here is what I have so far which works in some instances, but not in others:
> 
> (define (index-s-exp s-exp index)
>   (cond [(empty? s-exp) empty]
>            [(atom? (first s-exp))
>             (cons index 
>                      (index-s-exp (rest s-exp) (add1 index)))]
>            [else 
>             (cons (index-s-exp (first s-exp) index)
>                      (index-s-exp (rest s-exp) (add1 index)))])) 
> 
> 
> >(index-s-exp '(+ .3 (- .1 x))  1)
> '(1 2 (3 4 5))  
> this works (I think because the redex is always in tail-position and therefore matches Racket's evaluation scheme)
> 
> >(index-s-exp '(+ (- .1 .2) .3)  1)
> '(1 (2 3 4) 3) 
> This doesn't work, desired result is '(1 (2 3 4) 5)
> 
> I was wondering how I might be able to modify this function so that it works in both cases, as well as if there are any built-in functions that I can take advantage of to make this function cleaner?
> 
> Thanks,
> -- 
> Rian
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users