[plt-scheme] Generic filter (HOF) with the Visitor Pattern (was Tail Recursion ....)

From: wooks (wookiz at hotmail.com)
Date: Sun Jan 14 03:52:28 EST 2007

Noels post on implementing fold inspired me to genericise my filter.

Of course it's not that simple. My 1st attempt was a straight
translation of  filter

    public static class FilterV implements IList, IListFunction{
        private ILambda pred;
        public FilterV(ILambda pred) {
                this.pred = pred;
        }

//______________________________________________________________
        public Object forEmpty() {
                return AList.Empty.SINGLETON;
        }
        public Object forCons(Object first, AList rest) {
                final AList filterRest = ((AList)rest.accept(this));

                return ((Boolean)pred.execute())?
                        new AList.Cons(first, filterRest):
                        filterRest;
        }
    }


So I have a list of myFile objects that have a name and a filesize and
I want to filter those that are above/below a filesize threshold. The
generic filter knows nothing about myFiles so that is the job of the
lambda that gets passed in.

This is where the plot started to thicken.

Here is the code for that generates the lambda that gets passed in (it
is also a visitor).

    public static class SizeV extends Filter implements IList {
        long sizePassed;
        boolean isMaxFileSize;
        public SizeV(long sizePassed, boolean maxFileSize) {
            this.sizePassed = sizePassed;
            this.isMaxFileSize = isMaxFileSize;
        }

//__________________________________________________________________________
        public Object forCons(final Object first, final AList rest) {

            return new ILambda() {
                public Object execute() {
                    final long size = ((MyFile)first).getSize();
                    return isMaxFileSize?
                        size < sizePassed:
                        size > sizePassed;
                }
            };
        }
    }

Translation -  take a file size threshold passed in from the GUI and a
flag indicating whether the threshold is a minimum or maximum. Then
construct the appropriate lambda expression that is to be passed into
the generic filter HOF.

Now if we look at the code in forCons method in FilterV (the generic
HOF) the first line says

     final AList filterRest = ((AList)rest.accept(this));

but that is going to apply the lambda expression that got constructed
for the first file in  our directory to the rest of the list. It
doesn't move the lambda down the list hence everything gets included or
excluded based on what the predicate of the first invocation returned.

So really what is needed is to something like this

    final AList filterRest = ((AList)rest.accept(new FilterV ......));

but this means we have to create a new lambda for each list member so
the generic HOF needs to be told which visitor to use do that,  which
in turn means we have to amend it's constructor to also pass that
information.

So I ended up with this

    public static class FilterV implements IList, IListFunction{
        private ILambda pred;
        private IList visitor;
        public FilterV(ILambda pred, IList visitor) {
                 this.pred = pred;
                 this.visitor = visitor;
        }

//______________________________________________________________
        public Object forEmpty() {
                 return AList.Empty.SINGLETON;
        }
        public Object forCons(Object first, AList rest) {
                final AList filterRest = ((AList)rest.accept(new
FilterV(((ILambda)rest.accept(visitor)),

    visitor)));
            return ((Boolean)pred.execute())?
                     new AList.Cons(first, filterRest):
                     filterRest;
        }
    }

If you ignore the casts it simply  implements the changes I narrated.



Posted on the users mailing list.