CODEWITHSUNDEEP
clojure
Exorsky
Exorsky

Reputation: 15

Clojure filter method without standard clojure functions

I need to make filter method, but i can't return method name as argument, not as result.

In my case, i need to input odd? method as argument and call recursion.

I can use only this construction:

(defn my-filter [p xn])

My code:

(defn my-filter [p xs]
  (if (p (first xs))
      (cons (first xs) (recur p (next xs))) 
      (recur p (next xs) )))


(my-filter odd? '(1 2 3 4 5))

Error: IllegalArgumentException Argument must be an integer: clojure.core/even? (core.clj:1372)

As i can see, where recursion is called, arguments are calculating result, instead of call recursion with odd? and (next xs) arguments

Upvotes: 1

Views: 226

Answers (3)

RRR
RRR

Reputation: 103

I really like this solution, therefore I share with you. Very simple. (I know, that is not exactly what was the question but different approach.)

(def data (vec (range 10)))

Map implementation

(defn -map [f coll]
  (reduce
    (fn [acc v]
      (conj acc (f v)))
    []
    coll))

Filter implementation

(defn -filter [f coll]
  (reduce
    (fn [acc v]
      (if (f v)
        (conj acc v))
    []
    coll))

Example usage

(->> data
     (-map inc)
     (-filter odd?))

Upvotes: 0

Thumbnail
Thumbnail

Reputation: 13473

Your code does not compile:

Syntax error (UnsupportedOperationException) compiling recur at ... .
Can only recur from tail position

You have to replace the recurs with explicit recursive calls to my-filter:

(defn my-filter [p xs]
  (if (p (first xs))
    (cons (first xs) (my-filter p (next xs)))
    (my-filter p (next xs))))

Now it compiles, but ...

(my-filter odd? [])
Execution error (IllegalArgumentException) at ...
Argument must be an integer:

You need to check that the sequence argument xs is not empty before doing anything else with it:

(defn my-filter [p xs]
  (when (seq xs)
    (if (p (first xs))
      (cons (first xs) (my-filter p (rest xs)))
      (my-filter p (rest xs)))))

The when evaluates to nil if the condition fails. The nil, called on to be a sequence, behaves as an empty one. So ...

(my-filter odd? [])
=> nil
(my-filter odd? (range 10))
=> (1 3 5 7 9)

It works. However, it evaluates (first xs) twice, and mentions (my-filter p (rest xs)) twice. Factoring these out, we get

(defn my-filter [p xs]
  (when (seq xs)
    (let [head (first xs)
          tail (my-filter p (rest xs))]
      (if (p head) (cons head tail) tail))))

This uses direct recursion. So it runs out of stack on a long sequence:

(count (my-filter odd? (range 10000)))
Execution error (StackOverflowError) at ...

Wrapping the recursion in lazy-seq flattens the evaluation, devolving it to whatever explores the sequence:

(defn my-filter [p xs]
  (lazy-seq
    (when (seq xs)
      (let [head (first xs)
            tail (my-filter p (rest xs))]
        (if (p head) (cons head tail) tail)))))

Now ...

(count (my-filter odd? (range 10000)))
=> 5000

If you want an eager version, you had better build the returned sequence as a vector:

(defn eager-filter [p coll]
  (loop [answer [], coll (seq coll)]
    (if-let [[x & xs] coll]
      (recur
        (if (p x) (conj answer x) answer)
        xs)
      (sequence answer))))

This won't run out of stack:

(count (eager-filter odd? (range 10000)))
=> 5000

But it can't handle an endless sequence:

(first (eager-filter odd? (range)))

Process finished with exit code 137 (interrupted by signal 9: SIGKILL)

I had to kill the process.

Upvotes: 0

Biped Phill
Biped Phill

Reputation: 1281

Two issues need attention. Or maybe only one issue, if you don't need to handle very long lists. 1) The function does not notice when the inputs are exhausted. Open a REPL and try (odd? nil) and you will see what happens! 2) If you try the function on a really long list, you might get a StackOverflow. The clojure.org guide for recursion has an example of how to avoid that problem - actually it illustrates solutions to both problems: https://clojure.org/guides/learn/flow#_recursion

Upvotes: 3

Related Questions