CODEWITHSUNDEEP
listfunctional-programmingschemeflatten
sudhirc
sudhirc

Reputation: 125

Scheme: advise on implementation of flatten

My implementation of flatten looks like this:

(define flatten
  (lambda (lst)
    (if (null? lst)
        lst
        (append
          (rtn-lst (car lst))
          (flatten (cdr lst))))))

(define rtn-lst
  (lambda (lst)
    (cond 
      ((null? lst) 
        empty)
      ((atom? lst)
        (list lst))
      (else 
        (flatten lst)))))

While standard implementation is:

(define (flatten lst)
  (cond 
    ((null? list)
      empty)
    ((list? (car lst))
      (append (flatten (car lst)) (flatten (cdr lst))))
    (else
      (cons (car lst) (flatten (cdr lst))))))

Apart from the obvious verboseness, what else is wrong with my code?

Upvotes: 0

Views: 4088

Answers (4)

陈君尧
陈君尧

Reputation: 1

How about something like this:

(define (flatten x y)
    (if (null? x)
        y
        (if (list? (car x))
            (flatten (append (car x) (cdr x)) y)
            (flatten (cdr x) (append y (list (car x)))))))
(define (flat x)     
    (flatten x '()))

> (flat '(1(2(3(4(5)6)7)8)9))
(1 2 3 4 5 6 7 8 9)

and closure version:

(define (flatten x)  
        (define (flatten x y)
            (if (null? x)
                y
                (if (list? (car x))
                    (flatten (append (car x) (cdr x)) y)
                    (flatten (cdr x) (append y (list (car x)))))))
        (flatten x '()))

> (flatten '(1(2(3(4(5)6)7)8)9))
(1 2 3 4 5 6 7 8 9)

Upvotes: 0

Mayer Goldberg
Mayer Goldberg

Reputation: 1438

How about something like this:

(define foo
  (lambda (e)
    (cond ((pair? e) `(,@(foo (car e)) ,@(foo (cdr e))))
          ((null? e) '())
          (else (list e)))))

Where for example:

> (foo '(((2 3) (4 . 5) 8)))
(2 3 4 5 8)

Does this do what you want?

Upvotes: 0

Yasir Arsanukayev
Yasir Arsanukayev

Reputation: 9676

I'd try this:

(define rtn-lst
  (lambda (lst)
    (cond 
      ((list? lst)
        (if (null? lst)
            empty
            (flatten-list lst)))
      ((atom? lst)
        (list lst))
      (else 
        (flatten-list lst)))))

Probably we have different implementations of Scheme.

EDIT:

With modified else branch:

(define rtn-lst
  (lambda (lst)
    (cond 
      ((list? lst)
        (if (null? lst)
            empty
            (flatten-list lst)))
      (else 
        (list lst)))))

Upvotes: 1

knivil
knivil

Reputation: 906

I would consider atom? to be wrong. You want to know if the lst is a list, so use list?. atom? can return false on vector or string for some implementations. But i do not know for sure. The rest is quit good.

Upvotes: 1

Related Questions