Scheme: reduce & filter (please rate).

[netytan]

I don't know if anyone here uses Scheme but Scheme doesn't include a reduce or filter function, so I set about writing some for fun and in any case it's a good way to learn :).

Code Select Expand

(define filter
  (lambda (fn values)
    "This function is a tail recursive implementation of the filter function
    found in other Lisp dialect."
    (let loop ((v values)
               (rest '()))
     
      (let ((item (car v))
            (next (cdr v)))               ; Saves car and cdr for efficiency.

        (if (fn item)
          ;; Add the current 'item to 'rest if 'fn returned #t, then continue
          ;; though the list. Return 'this AND 'rest revsered.
          (if (pair? next)
            (loop next (cons item rest))
            (reverse (cons item rest)))
           
          ;; Don't add the 'item to the 'rest list but continue on though the
          ;; list.
          (if (pair? next)
            (loop next rest)
            (reverse rest)))))))

Code Select Expand

> (filter even? '(1 2 3 4 5 6 7))
(2 4 6)

The function is tail-recursive, which happy about but I wonder if it can be done in a better way in any Lisp dialect (inc. newLisp). My intend here was to gain more experience with recursive techniques so that's the only limit there, I know I could do it with map but that's not what I want here :).



Any tips or insight you could give would be more welcome than you know.



I'm currently thinking about how to do reduce but I'm not so sure how it works to he honest, it's not something I've used much before recently.



EDIT: Please forgive the text-wrapping on the comments.



Thanks in advance,



Mark.

[eddier]

If you are using drscheme, you can look into collects folder and find the scheme source code for filter, reduce, fold, foldr, unfold, zip, filter-map, etc,...



When you get ready to write some serious code, I would use the libraries provided instead of rewriting them all. For Instance,



(require (lib "list.ss" "srfi" "1"))



above the spot you want to use filter, reduce, foldr, unfold, etc,...



There are many, many libraries with all sorts of goodies for handeling lists, strings, and the what nots. I really dig using different versions of scheme.



Don't you just love the named let?



Eddie

[Sammo]

Being unfamiliar with Scheme's named let, it's hard for me to read the Scheme code. Here is my straightforward newLisp solution which is, I think, tail recursive.

Code Select Expand

;;  recursive version
;;
(define (myfilter pred? items)
  (reverse (myfilter-aux pred? items '())) )

(define (myfilter-aux pred? items result)
  (if (empty? items)
    result
    (myfilter-aux
          pred?
          (rest items)
          (if (pred? (first items)) (cons (first items) result) result ))))
And, for completeness, here is another version using map.

Code Select Expand

;;  map version
;;
(define (myfilter pred? items)
  (let
    ( keep '()
      keep-if-true (fn (p item) (if p (push item keep -1)))
    )
  ;body of let
    (map keep-if-true (map pred? items) items)
    keep ))

[cormullion]

I've been struggling to learn this stuff too, although I realise that it's probably only an academic exercise, since there are usually better ways of doing things. However, I managed to cobble this newLISP together, which looks very like Sammo's:

Code Select Expand


(define (my-filter f lst r)
(cond ((= (length lst) 1)  ; the basic situation
r )
(true
(if (f (first lst))
(push (first lst) r -1))
(my-filter f (rest lst) r ))))

(println (my-filter float? '(1 2.1 3.00001 4.1 5 6 7 3.2 8)))


I've no idea whether this is valid tail-recursion or not. The book I've been referring to occasionally for old-fashioned Lisp-y stuff says this:

Because a 'tail-recursive' procedure does nothing to the value returned by the recursive call, it need not remember anything.

which didn't really help me either way. :-)

[eddier]

That is one gripe I have against scheme and what I do like about newLISP, the looonnnnggg definition names. For example, (string-append , (string-drop-right ,or (call-with-input-file , etc...  It gets hard to read a long line strung out with intervening spaces, words, and white space. To make it readable you have to keep breaking them to the next line and indenting. Actually, short identifiers, even if cryptic, helps a bunch.



There is a good explanation of tail call optimization at http://en.wikipedia.org/wiki/Tail_recursion">http://en.wikipedia.org/wiki/Tail_recursion



Eddie

[Lutz]

The interesting thing about tail-recursion is:



If the function is tail recursive an iterative solution is obvious and many times easier to understand and faster.



The elegant recursive solutions are the ones, whch are not tail recursive and therefore cannot be optimized. Mnay times they are also more complex to rebuild iteratively.



Lutz

[netytan]

Thanks for all your posts guys they helped a lot, just having similar Lisp code to read lets me find new techniques to use :).



Eddie: Scheme, including Dr. Scheme doesn't have those functions in list.ss, filter is available although it uses some tricks because of weaknesses in the implementation (according to one comment).



If you have them in your version could you please most the code for reduce?



I really enjoy Scheme, it's clean and minimal and there are a lot of different tools for it, named let is way better than the CL labels which ends up looking messy no matter what you do :(.



I agree with you about the long names however one of the joys of Lisp is that you can always change it, if you don't like the long names give them another, or write a macro to do things your way :D.



Lutz: tail-recursion is very functional, using iterative styling you'd more likely use a lot of set!'s where this way everything kind of flows, or thats how i see it anyway.



Iteration does make some things simpler but then we have map etc. to accomplish these things too. I just find recursion to be interesting, I haven't used it a lot in the past so it's a challenge.



Heres what I came up with in the end, it's not dissimilar to either of yours :D. There are a few good examples of tail-recursion I've seen around the web, if i find any good ones again I'll post a link for you but wikipedia has a nice explanation of what happens :).

Code Select Expand

(define filter
  (lambda (fn values)
    "This function is a tail recursive implementation of the filter
    function found in other Lisp dialect."
    (let loop ((v values)
               (rest '()))

      ;;; If there are items in v then CAR and CDR are saved; return
      ;;; rest after reversing.
      ;;;
      ;;;   Checks if fn  => #t  -> add item to rest & repeat.
      ;;;                 => #f  -> loop without adding item.
      (if (pair? v)
        (let ((item (car v))
              (next (cdr v)))
          (if (fn item)
            (loop next (cons item rest))
            (loop next rest)))
          (reverse rest)))))

Thanks again,



Mark.

[eddier]

netytan,



Make sure at the top of the source you use all of



(require (lib "list.ss" "srfi" "1"))



because



(require (lib "list.ss"))



is a different package! I was a bit confussed the first time trying to include the functionality to. I found the code to reduce and reduce-right in the file "fold.ss" under  the "/usr/plt/collects/srfi/1" directory. I'm not quite sure where it would be under windoze but I bet if you could find the "plt" folder, it would then be under "pltcollectssrfi1



(lib "list.ss" "srfi" "1") Contains:



Constructors

cons list

xcons cons* make-list list-tabulate

list-copy circular-list iota



Predicates

pair? null?

proper-list? circular-list? dotted-list?

not-pair? null-list?

list=



Selectors

car cdr ... cddadr cddddr list-ref

first second third fourth fifth sixth seventh eighth ninth tenth

car+cdr

take       drop

take-right drop-right

take!      drop-right!

split-at   split-at!

last last-pair



Miscellaneous: length, append, concatenate, reverse, zip & count

length length+

append  concatenate  reverse

append! concatenate! reverse!

append-reverse append-reverse!

zip unzip1 unzip2 unzip3 unzip4 unzip5

count



Fold, unfold & map

map for-each

fold       unfold       pair-fold       reduce

fold-right unfold-right pair-fold-right reduce-right

append-map append-map!

map! pair-for-each filter-map map-in-order



Filtering & partitioning

filter  partition  remove

filter! partition! remove!



Searching

member memq memv

find find-tail

any every

list-index

take-while drop-while take-while!

span break span! break!



Deleting

delete  delete-duplicates

delete! delete-duplicates!



Association lists

assoc assq assv

alist-cons alist-copy

alist-delete alist-delete!



Set operations on lists

lset<= lset= lset-adjoin

lset-union         lset-union!

lset-intersection      lset-intersection!

lset-difference              lset-difference!

lset-xor         lset-xor!

lset-diff+intersection           lset-diff+intersection!



Primitive side-effects

set-car! set-cdr!

[netytan]

Thanks eddie I looked in the wrong folder, I was looking in mzlib. I wouldn't know where this would be located on windows either not being a windows user ;). At a guess I'd say in the same dir structure under whatever location you installed it?



The second argument must be the subdir to load the file from but whats the trailing "1" for?



Thanks again eddie,



Enjoy all!



Mark.

[eddier]

The "srfi" are standard libraries for scheme. For instance "1" is for extra list functionality.  For example,



(require (lib "string.ss" "srfi" "13"))



will load a bunch of string functionality. Below are libraries included with mzscheme (drscheme).



SRFI-1             list.ss                      1

 SRFI-2             and-let.ss                     2

 SRFI-4(*1)         4.ss

 SRFI-5             let.ss                         5

 SRFI-6(+)          6.ss

 SRFI-7             program.ss                     7

 SRFI-8             receive.ss                     8

 SRFI-9             record.ss                      9

 SRFI-11(+)         11.ss

 SRFI-13            string.ss                     13

 SRFI-14            char-set.ss                   14

 SRFI-16(+)         16.ss

 SRFI-17            set.ss                        17

 SRFI-18(++)        18.ss

 SRFI-19(*2)        time.ss                       19

 SRFI-23(+)         23.ss

 SRFI-25            array.ss                      25

 SRFI-26            cut.ss                        26

 SRFI-27            random-bits.ss                27

 SRFI-28(+)         28.ss

 SRFI-29            localization.ss               29

 SRFI-30(+)         30.ss

 SRFI-31            rec.ss                        31

 SRFI-34            exception.ss                  34

 SRFI-38(+)         38.ss

 SRFI-39(+)         39.ss

 SRFI-40            stream.ss                     40

 SRFI-42       comprehensions.ss             42

 SRFI-43            vector-lib.ss                 43

 SRFI-45(*3)        lazy.ss                       45

 SRFI-48            format.ss                     48

 SRFI-57            records.ss                    57

 SRFI-59            vicinity.ss                   59

 SRFI-60            60.ss                         60

 SRFI-67            compare.ss                    67

 SRFI-69             hash.ss                       69



Notes:

,--------------------

| +  Supported by the core of PLT Scheme

`--------------------

 

,--------------------

| ++ Partially supported by the core of PLT Scheme

`--------------------

 

,--------------------

| *1 The functionality is all part of mzscheme available via

| (lib "foreign.ss"), the only missing part is the i/o syntax.

`--------------------

 

,--------------------

| *2 The time module does not export its time structure (you have to

| use the time-* procedures.)  It renames all the date-* accessors to

| tm:date-* so that you won't get errors when including this code in

| other modules.  Care most be taken NOT to confuse the internal date

| structure with the PLT Scheme one, they are not the same, and all

| procedures from this library expect the former.

`--------------------

 

,--------------------

| *3 This port also provide |promise?| / |srfi-45-promise?|.

`--------------------





Eddie