We often process a list into another one in LISP.
For example:
(define (filter-a l)
(if (null? l) '()
(let ((n (car l))
(r (filter-a (cdr l))))
(if (> n 10) r (cons n r)))))
The procedure above can choose the items in 'l' which is
less than or equal ten, then put them in a new list,
and return the new list.
Lists in LISP are very simple structures and they have a
big disadvantage - it's not easy to append a new element
to the tail of the list.Some programmers would push them
into the top of the list, then reverse the list to get
the final result.But I like recursing very much, so I
usually use recursion to collect the result list.
But in my opinion, both of the two ways are not good.
I think my way is wasting stack - local variables use
stack, but only the last pair of the list being
collected is useful(we use it to connect to next pair).
To reverse the list after collecting it is wasting time
- why not collect it at once but do a twice processing?
I have invented a way to solve this problem.My algorithm
is similar to the implement of queue in SLIB.
Here is my new way to do filtering:
(define (filter-a l)
(letrec ((result '())
(last-pair '())
(grow (lambda (x)
(let ((tmp (list x)))
(set! result tmp)
(set! last-pair tmp))
(set! grow (lambda (x)
(let ((tmp (list x)))
(set-cdr! last-pair tmp)
(set! last-pair tmp)))))))
(let growing ()
(if (null? l) result
(let ((first (car l)))
(if (<= first 10)
(grow first))
(set! l (cdr l))
(growing))))))
It's a little complex, but it can save a lot of space
especially when collecting much data.
But maybe my way could slow the collecting, because
to make a closure need some time.
Which way is good?
I am a schoolboy from China.I have a lot of friends
who would say "Microsoft has monopolized all." while
using Dev-C++.They would prefer Python or C# rather
than LISP or other old languages.So I need your help.
Sorry for some mistakes in my mail due to my terrible
English.
