Predicates

Fork this

https://github.com/iloveponies/predicates

Here are the instructions if you need them. Be sure to fork the repository behind the link above.

Functions as Parameters

So how do you write a funtion that takes a function as a parameter? Well, for starters, let’s define a function called (apply-1 f x) that should return (f x):

(defn apply-1 [f x]
  (f x))

When you take a function as a parameter, you treat it like any other parameter. In clojure functions are just normal values and you can pass them around however you like. Calling a function parameter works like calling any other function.

(apply-1 str 13) ;=> (str 13) ;=> "13"

Exercise 1

Write the function (sum-f f g x) that returns (+ (f x) (g x)).

(sum-f inc dec 4) ;=> 8
(sum-f inc identity 5) ;=> 11
(sum-f identity - 10) ;=> 0

Functions as Return Values

A function that returns a boolean value (false or true) is called a predicate. Usually their name ends in a question mark ?. We’ve already defined a bunch of them and used them with filter.

Let’s write a function that returns a predicate. Suppose that I want to get all numbers greater than some limit from a sequence. I need a predicate for this grater than testing. Here’s a function that returns such predicates.

(defn greater-than [n]
  (fn [k] (> k n)))

We’ve already formed helper functions with fn. Since these functions are just values, we can just return them.

Let’s try it out:

(filter (greater-than 5) [4 6 5 0 9 2 12]) ;=> (6 9 12)

Exercise 2

Write the functions (less-than n) and (equal-to n) that work like greater-than. Use == as comparison in equal-to

(filter (less-than 3) [1 2 3 4 5])   ;=> (1 2)
(filter (less-than 4) [-2 12 3 4 0]) ;=> (-2 3 0)
(filter (equal-to 2) [2 1 3 2.0])    ;=> (2 2.0)
(filter (equal-to 2) [3 4 5 6])      ;=> ()

Keywords and Sets as Predicates

When you have a bunch of maps, you often want to filter those that have a certain :keyword as a key. Most of the time, you can just use the :keyword itself as a predicate.

Here are some graphic novels, some of them belong to a series and some are stand alones.

(def graphic-novels [{:name "Yotsuba 1" :series "Yotsuba"}
                     {:name "Yotsuba 5" :series "Yotsuba"}
                     {:name "Persepolis"}
                     {:name "That Yellow Bastard" :series "Sin City"}
                     {:name "The Hard Goodbye" :series "Sin City"}
                     {:name "Maus"}
                     {:name "Solanin"}
                     {:name "Monster 3" :series "Monster"}])

Now it’s easy to filter those that belong to a series:

(filter :series graphic-novels)
;=> ({:name "Yotsuba 1", :series "Yotsuba"}
;    {:name "Yotsuba 5", :series "Yotsuba"}
;    {:name "That Yellow Bastard", :series "Sin City"}
;    {:name "The Hard Goodbye", :series "Sin City"}
;    {:name "Monster 3", :series "Monster"})

Trouble arises when the value for :keyword can be nil or false. No worries though, we can write a function that turns any key into a predicate.

(defn key->predicate [a-key]
  (fn [a-map] (contains? a-map a-key)))

And these predicates can be used in the same way.

(filter (key->predicate "Name") [{"Name" "Joe"} {"Blargh" 3}])
;=> ({"Name" "Joe"})

A similar thing happens when you want to use a set as a predicate. Set’s act as functions and they work like this. (a-set x) evaluates to - x if x is in a-set - nil otherwise

Now you can use a set as a predicate as long as it doesn’t contain false or nil. You can, for example, use this with filter to get all element’s in a sequence that are also elements of a set:

(filter #{1 2 3} [0 2 4 6]) ;=> (2)

Trouble arises, as mentioned, if the set happens to have falsey values in it.

(filter #{1 2 3 nil} [0 2 4 6 nil]) ;=> (2)

Let’s write a function that turns sets into predicates that works correctly even in this case.

Exercise 3

Write the function (set->predicate a-set) that takes a-set as a parameter and returns a predicate that takes x as a parameter and

  • returns true if x is in a-set
  • otherwise returns false
(filter (set->predicate #{1 2 3})     [0 2 4 6])       ;=> (2)
(filter (set->predicate #{1 2 3 nil}) [2 nil 4 nil 6]) ;=> (2 nil nil)

Functions that both Take Functions as Parameters and Return Functions

Sometimes you have a predicate that almost does what you want. For an example, suppose I want to filter all non-negative values from a sequence. There’s neg? and pos?, but neither allow 0. I could do something like this:

(defn non-negatives [a-seq]
  (let [non-negative? (fn [n] (not (neg? n)))]
    (filter non-negative? a-seq)))

(non-negatives [1 -2 9 4 0 -100 2 0 2]) ;=> (1 0 3 0 7)

Wanting to get the opposite result of a predicate is actually common enough that there’s a function for this. It is called complement. (complement pred) takes a predicate and returns a new predicate that returns true when pred returns a falsey value and false when pred returns a truthy value.

((complement neg?) -5)
;=> (not (neq? -5))
;=> (not true)
;=> false
((complement neg?) 0) ;=> true
((complement neg?) 12) ;=> true

Now we can write non-negatives using complement:

(defn non-negatives [a-seq]
  (filter (complement neg?) a-seq))

Okay, so complement both takes a function as a parameter and returns a new function. Let’s see the definition of complement:

(defn complement [predicate]
  (fn [x] (not (predicate x))))

Sometimes you have multiple predicates and you want to know whethet a value or some values pass all of them. Let’s create a helper function to do just that.

Exercise 4

Write the function (pred-and pred1 pred2) that returns a new predicate that:

  • returns true if both pred1 and pred2 return true
  • otherwise returns false

Suppose I wanted all even positive numbers from a sequence. With pred-and, this should be easy.

(filter (pred-and pos? even?) [1 2 -4 0 6 7 -3]) ;=> [2 6]

Here are some other test cases:

(filter (pred-and pos? odd?) [1 2 -4 0 6 7 -3]) ;=> [1 7]
(filter (pred-and (complement nil?) empty?) [[] '() nil {} #{}])
;=> [[] '() {} #{}]

Exercise 5

Write the function (pred-or pred1 pred2) that takes two predicates and returns a new predicate that:

  • returns true if pred1 or pred2 returns true
  • otherwise returns false
(filter (pred-or pos? odd?) [1 2 -4 0 6 7 -3])  ;=> [1 2 6 7 -3]
(filter (pred-or pos? even?) [1 2 -4 0 6 7 -3]) ;=> [1 2 -4 0 6 7]

Every

Sometimes you want to know if every element in a sequence satisfies a predicate. To do that, there’s (every? predicate a-seq). It returns true if predicate returns a truthy value for every element in a-seq. Otherwise it returns false.

(every? pos? [1 2 3])   ;=> true
(every? pos? [0 1 2 3]) ;=> false -- (pos? 0) ;=> false

It also always returns true with an empty collection.

(every? pos? [])  ;=> true
(every? pos? nil) ;=> true

Exercise 6

Write the function (blank? string) that takes a string as a parameter and returns true if string is empty, nil, or contains only whitespace.

Remember that strings can be used as a sequence of characters with sequence functions like every?. A function whitespace? that tells if a character is whitespace is defined for you in the source file.

(blank? " \t\n\t ") ;=> true
(blank? "  \t a")   ;=> false
(blank? "")         ;=> true

Hint

You have just implemented a function with the same semantics as isWhitespace in Apache Commons. Here is the Java implemention from Apache Commons:

5370        public static boolean isWhitespace(CharSequence cs) {
5371            if (cs == null) {
5372                return false;
5373            }
5374            int sz = cs.length();
5375            for (int i = 0; i < sz; i++) {
5376                if (Character.isWhitespace(cs.charAt(i)) == false) {
5377                    return false;
5378                }
5379            }
5380            return true;
5381        }
This is a good example about how the ability to easily pass around functions as parameters can improve clarity.

Earlier we had some books, let’s add some data to them. Let’s keep track of some awards.

(def china {:name "China Miéville", :birth-year 1972})
(def octavia {:name "Octavia E. Butler"
              :birth-year 1947
              :death-year 2006})
(def kay {:name "Guy Gavriel Kay" :birth-year 1954})
(def dick {:name "Philip K. Dick", :birth-year 1928, :death-year 1982})
(def zelazny {:name "Roger Zelazny", :birth-year 1937, :death-year 1995})

(def authors #{china, octavia, kay, dick, zelazny})

(def cities {:title "The City and the City" :authors #{china}
             :awards #{:locus, :world-fantasy, :hugo}})
(def wild-seed {:title "Wild Seed", :authors #{octavia}})
(def lord-of-light {:title "Lord of Light", :authors #{zelazny}
                    :awards #{:hugo}})
(def deus-irae {:title "Deus Irae", :authors #{dick, zelazny}})
(def ysabel {:title "Ysabel", :authors #{kay}, :awards #{:world-fantasy}})
(def scanner-darkly {:title "A Scanner Darkly" :authors #{dick}})

(def books #{cities, wild-seed, lord-of-light,
             deus-irae, ysabel, scanner-darkly}])

Exercise 7

Write the function (has-award? book award) that returns true if book has won award.

(has-award? ysabel :world-fantasy) ;=> true
(has-award? scanner-darkly :hugo)  ;=> false

Exercise 8

Write the function (HAS-ALL-THE-AWARDS? book awards) that returns true if book has won every award in awards.

(HAS-ALL-THE-AWARDS? cities #{:locus})
;=> true
(HAS-ALL-THE-AWARDS? cities #{:locus :world-fantasy :hugo})
;=> true
(HAS-ALL-THE-AWARDS? cities #{:locus :world-fantasy :hugo :pulitzer})
;=> false
(HAS-ALL-THE-AWARDS? lord-of-light #{:locus :world-fantasy :hugo})
;=> false
(HAS-ALL-THE-AWARDS? lord-of-light #{:hugo})
;=> true
(HAS-ALL-THE-AWARDS? scanner-darkly #{})
;=> true

And Then There Were Some

Finally, when you wan’t to know if at least one element of a sequence passes a predicate, there is (some pred a-seq) which returns a truthy value if pred returns a truthy value for some element in a-seq and otherwise it returns nil.

(some whitespace? "Kekkonen")          ;=> nil
(some whitespace? "Kekkonen Kekkonen") ;=> True
(some even? [1 2 3])                   ;=> true
(some even? [1 3])                     ;=> false

Why some and not some?? Well, some is not actually a predicate. It returns the first truthy value returned by pred, and functions ending in ? should return strictly true or false. This is often useful, but sometimes you need to be careful with it.

(some first [[] [1 2] []]) ;=> 1
(some first [[] [false true] []] ;=> nil
(some nil? [1 nil 2]) ;=> true

Exercise 9

Write you own implementation for some called my-some.

Hint: You might find map, filter and first useful (you won’t necessarily need them all).

(my-some even? [1 3 5 7])       ;=> falsey
(my-some even? [1 3 5 7 8])     ;=> true
(my-some neg? [1 3 5 0 7 8])    ;=> falsey
(my-some neg? [1 3 5 0 7 -1 8]) ;=> true
(my-some neg? [])               ;=> falsey
(my-some first [[false] [1]])   ;=> 1
(my-some first [[false] []])    ;=> falsey
(my-some nil? [1 2])            ;=> falsey
(my-some nil? [1 nil 2])        ;=> true

Exercise 10

Write your own implementation for every? called my-every?.

Hint: the previous hint applies. empty? and complement might come in handy as well.

(my-every? pos? [1 2 3 4])   ;=> true
(my-every? pos? [1 2 3 4 0]) ;=> false
(my-every? even? [2 4 6])    ;=> true
(my-every? even? [])         ;=> true

Exercise 11

Write the function (prime? n) that returns true if n is a prime number and otherwise false.

The function (range k n) returns the sequence

(k (+ k 1) (+ k 2) ... (- n 1))

Here’s a concrete example:

(range 2 10) ;=> (2 3 4 5 6 7 8 9)

A positive integer p is a prime number if the only positive numbers dividing p are p and 1.

Your solution should be of the form

(defn prime? [n]
  (let [pred ...]
    (not (some pred (range 2 n)))))

Here are some tests:

(prime? 4) ;=> false
(prime? 7) ;=> true
(prime? 10) ;=> false
(filter prime? (range 2 50)) ;=> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

Recursion awaits! →