[racket] From tree to lists : imperative or functionnal language ?

From: David Delfieu (david.delfieu at univ-nantes.fr)
Date: Wed Jun 20 06:35:53 EDT 2012


I am in difficulty with a recursive algorithm which build lists. Vn build a tree (lp) where all the suites of a list (l) where elements are either +2 either +3 from previous. 

#lang scheme
(define (maxi l)
  (- (length l) 1))

(define (Union l1 l2)
  (if (empty? l2) l1 
      (list l1 l2)))

(define (U1n n l)
  (if (>= (- (maxi l) n) 2)
      (cons (list-ref l (+ n 2)) (Vn (+ n 2) l))

(define (U2n n l)
  (if (>= (- (maxi l) n) 3)
      (cons (list-ref l (+ n 3)) (Vn (+ n 3) l))

(define (Vn n l)
  (if (>= (- (maxi l) n) 1)
      (Union (U1n n l) (U2n n l))

(define l (list 'e_1 'e_2 'e_3 'e_4 'e_5 'e_6 'e_7 'e_8 'e_9 'e_10 'e_11))

(define lp (cons (first l) (Vn 0 l)))

; lp is (e_1 (e_3 (e_5 (e_7 (e_9 e_11) (e_10)) (e_8 (e_10) (e_11))) (e_6 (e_8 (e_10) (e_11)) (e_9 e_11))) (e_4 (e_6 (e_8 (e_10) (e_11)) (e_9 e_11)) (e_7 (e_9 e_11) (e_10))))

; I would like to unflat this tree and to have all the paths of the tree and to obtain :

; ((e_1 e_3 e_5 e_7 e_9 e_11) (e_1 e_3 e_5 e_7 e_10) (e_1 e_3 e_5 e_8 e_10) (e_1 e_3 e_5 e_8 e_11) (e_1 e_3 e_6 e_8 e_10) (e_1 e_3 e_6 e_8 e_11) (e_1 e_3 e_6 e_9 e_11) (e_1 e_4 e_6 e_8 e_10)
;(e_1 e_4 e_6 e_8 e_11) (e_1 e_4 e_6 e_9 e_11) (e_1 e_4 e_7 e_9 e_11) (e_1 e_4 e_7 e_10))

; I am trying, without any success (since 3 weeks), to obtain this list of lists, perhaps because i need a local list under building which change when a leave is reached

My poor and un-complete solution is
(define (1? l)
  (equal? (length l) 1))

(define (simple-list? l)
  (or (1? l)
  (for/and ( [e l]) (not (list? e)))))

(define (flat r g d)
   [(simple-list? g) (cons r g)]
   [(simple-list? d) (cons r d)]
   [else (list (cons r (flat (car g) (second g) (third g)))
         (cons r (flat (car d) (second d) (third d))))]))

(flat (car lp) (second lp) (third lp))

; which gives the un-complete solution ((e_1 (e_3 (e_5 e_7 e_9 e_11) (e_5 e_8 e_10)) (e_3 e_6 e_9 e_11)) (e_1 (e_4 e_6 e_9 e_11) (e_4 e_7 e_9 e_11)))

I could easily solve this problem in imperative language (C).
Do you think it could exist an elegant solution ? 
I am doubting of a good solution in fonctionnal language as Racket.


David Delfieu, tel : 02 40 90 50 45			
EC à Polytech'Nantes - Département Génie Électrique 
Site de Gavy, 44603 Saint Nazaire Cedex		
Chercheur à L'IRCCyN						

Posted on the users mailing list.