16 octombrie 2014

Exercițiu în Scheme: numărarea simbolurilor (numSym)

Define a Scheme procedure "numberSym"
numberSym:  S-List -> N-List
Example:
 (numberSym '(b () (a d) a c a)) => (0 ()  (1 2) 1 3 1)
-----------------------------------------------------------------
Traversarea simplă a unei liste:

(define traversal2 
  (lambda (myList)
    (if (null? myList) 
        '()
        (let ((c (car myList)))
          (cons (if (list? c) (traversal2 c) 'x)
                (traversal2 (cdr myList)))))))

-------------------------------------------

Traversare cu numărare:

; returns a list with the same structure as myList and with symbols replaced by index 
; numbers. Also returns the list with all distinct symbols found
(define traversal 
  (lambda (myList distinctList)
    (if (null? myList) 
        (list '() distinctList)
        ; else
        (let ((c (car myList)))
          (if (list? c)
              (letrec ((resultC (traversal c distinctList))
                    (resultR (traversal (cdr myList) (cdr resultC))))
                (list (cons (car resultC) (car resultR)) (cdr resultR)))
              ; else if c is a symbol
              (letrec ((position (getIndexList c distinctList))
                       (resultR (traversal (cdr myList) (cdr position))))
                  (list (cons (car position) (car resultR)) (cdr resultR))))))))

(define numberSym (lambda (myList)
                    (car (traversal myList '()))))

---- funcție auxiliară

; returns the index of element in simpleList (after updating it) AND 
; the updated list with appending element if it's new in simpleList
(define posInList (lambda (element simpleList originalList seed)
  (if (null? simpleList) (list (length originalList) (append originalList (list element)))
      (if (eq? element (car simpleList)) (list seed originalList)
          (posInList element (cdr simpleList) originalList (+ 1 seed))))))

(define getIndexList (lambda (element aList)
     (let ((flatList (flatten aList)))
        (posInList element flatList flatList 0))))

---- teste

(display (numberSym '(b b h b a b a))) ; ((0 0 1 0 2 0 2)
(display "\n")
(display (numberSym '((x m b m y) b))) ; ((0 1 2 1 3) 2)
(display "\n")
(display (numberSym '((f) h () (r t b) (x m b m y) b (c (d))))) ; ((0) 1 () (2 3 4) (5 6 4 6 7) 4 (8 (9)))
(display "\n")

Niciun comentariu: