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

On Wed, Jun 20, 2012 at 12:35 PM, David Delfieu <
david.delfieu at univ-nantes.fr> wrote:
[...]

> (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)
>  (cond
>   [(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))))]))
>
> lp
> (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.
>

Couldn't resist the troll...

You mean something like this?

#lang racket

; lp is
(define lp
  '(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 :
(define lres
'((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)))


(define (flat-list? l)
  (and (list? l) (not (ormap list? l))))
#|
> (flat-list? '(a b e))
#t
> (flat-list? '(a b (e)))
#f
> (flat-list? '(a b (e) f))
#f
|#

(define (comp tree)
  (cond [(empty? tree) '()]
        [(flat-list? tree) (list tree)]
        [(list? tree)
         (let ([sublists (append-map comp (rest tree))])
           (for/list ([sl sublists])
             (cons (first tree) sl)))]
        ))

(equal? lres (comp lp)) ; #t

(most probably not optimal, and only little tested; use with caution)
Laurent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120620/0811ca0c/attachment-0001.html>