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 all

(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 all

> (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 all

;;  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 all

;;  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 all

(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

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 all

(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 "plt\collects\srfi\1\

(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