Filter, Guarding You From Fold

"You and your ways; whose wraths to guard you from,"

-- Shakespeare, The Tempest

Act III, Scene III, Line 80

Filter

Filter is a lot like a higher order functional bouncer, it prevents undesirable elements from getting into the resulting collection.  

A simple example would be a filtering with a function which says if a value is odd or not.

In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", he gives the following definition of Filter in terms of Fold:

filter :: (α → Bool) → ([α] → [α])

filter p = fold (λx xs → if p x then x : xs else xs) [ ]

From the definition above, we see that Filter is just Map but with a predicate clause stating if the element should be placed in the resulting collection or not.

Let us look at an example using my name Mike and a function which will check if a character is lower case.

(similar to Map last time)

First Memoize has nothing and X has M.

Next Memoize still has nothing (since M is upper case) and X has i.

Now Memoize has i and X has k.

Then Memoize has i and k while X has e.

Now the Filter will return the result of "ike".

Now what we all came to see, some code examples.

Clojure

In Clojure we can use the reduce function to move through the collection checking the predicate condition with the if macro guard against undesirable elements.

C#

With the C# code we'll need to create some type of collection with the seed value which will allow us to add elements to it, we'll use the collection class of List.  We'll simply iterate through the collection using Aggregate and add elements to the memoize List if they pass the predicate clause.

ECMAScript 2015

In the code above that we'll use the build in JavaScript array method of push to add an element which gets past the guarding predicate function to the array at the end.  We are simply move through the collection we are filtering, pushing elements into the memoize array.

Fin

There you have it we are able to keep the riffraff elements out using Fold. 

Reducing Filter to Reduce OR All You Need is Fold

"All springs reduce their currents to mine eyes"
-- Shakespeare, Richard III
Act II, Scene II, Line 68

Intro

Last time we look at using the ideas presented in Graham Hutton's paper "A tutorial on the universality and expressiveness of fold" around mapping map to a fold.  This post will look at filtering filter down to a fold.

Filter

Filter goes by many different names, to those who speak Clojure, Haskell, and Underscore.js it is called Filter, to others that speak C# it is know as Where, while those that speak C++ know it as Remove, ... we could go on like this for a bit.

The point is that this is the same idea called by different names.  With a Filter what you are doing is taking a collection and applying a predict which state which members of the collection to let into the resulting collection and which members to not allow.  Think of it as a bouncer at a club, some of the people looking to get in will be admitted to the club others will be turned away, the bouncer is the predict, the people are the collection, and those few that get into the club are the resulting collection.

An easy example is to filter out all members of a collection of integers which are not odd.  In Clojure and C# we could use the following code to do this.



We see in both languages that we can use a higher order function to filter our collection down to the resulting collection with the property of oddness that we are looking for.  Clojure has a built in predicate function to check for oddness of a number while in C# we have to roll our own with a lambda function.

Fold

We talk about Fold last time, but we'll review it really quick.

When we are talking about Fold we are talking about taking a collection and applying a function against each member of the collection resulting in a result of a single "value".

Hmm, this sounds kind of similar to what we are doing with Filter...

Folding Filter into a Fold

When we looked at Filter we saw some similarities to Fold.

1. apply a function to each member of a collection
2. building a result

In fact we could look at Filter in the following way:

If we take a Fold (aka Reduce), a predicate function, and a collection to hold the resulting collection, we end up with a Filter.  We can looking at the following examples in Clojure and C# using our friend isOdd with a Fold to produce a Filter



In the Clojure code we see that we have a predicate function testing if a value is odd and if it is we conj it to a memorized resulting collection else we just pass along the memorized result collection.  We seed the Reduce (aka Fold) with an empty vector was is used to hold the memorized result collection.  Note, the memorized result collection is %1 in the lambda function while the current member we are looking at is %2, this pattern is typical in Folds across different languages (I cannot think of one which does not have this as the order, but maybe one exist).

In the C# code we new up a List to hold our resulting collection and in our lambda we test the current member we are looking at, if it passes we add it to the memorized result collection, then we always pass the memorized result collection along to the next call of Aggregate (aka Fold).  Since we had an array of integers as our input, we need to reshape the result collection with a call to ToArray.

By looking at this simple example we see that all we really need is Fold.  :)

Maps, Filters, and Folding ... Oh My! OR Yet Another Blog on Higher Order Functions

"Ay me! I see the ruin of my house.
The tiger now hath seized the gentle hind;
Insulting tyranny begins to jut

Upon the innocent and aweless throne.

Welcome destruction, blood, and massacre!
I see, as in a map, the end of all."
-- Shakespeare, Richard III
Act II, Scene IV, Lines 49-54

This is taken from my presentation called, "Maps, Filters, and Folding.  Oh my!" given at the Chicago Code Camp on April 27th, 2013.

f ◦ g

By higher order functions, we are talking about functions that take functions.  In other words we are talking about f ◦ g.

Mapping

Our first higher order function is f : A → B, called the mapping function.

In a mapping function everything in A has a value that it maps to through the function f to B.  Thus we can write f : A → B.

Mapping example - Identity

The identity function takes a value and maps it to the value given.  In other words it does nothing.

C#

var x = new List{1, 2, 3};

var numbers = from number in x
              select number;

F#

let x = [1; 2; 3]

let numbers = List.map (fun n -> n) x

OR

let x = [1; 2; 3]

let numbers = x |> List.map id

Haskell

map (\x -> x) [1, 2, 3]

OR

[x | x <- 2="" 3="" font="">

OR

 map id [1, 2, 3]

C

int* mapIdentity(int* list, int length) {

  int result[length];

  int i;

  for (i = 0; i < length; i++) {

    result[i] = list[i];

  }

  return result;

}

Mapping example - Turtles All the Way Down

Stephen Hawkings in a Brief History of Time gives us the following story:

A well-known scientist once gave a public lecture on astronomy. He described how the earth orbits around the sun and how the sun, in turn, orbits around the center of a vast collection of stars called our galaxy. At the end of the lecture, a little old lady at the back of the room got up and said: "What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise." The scientist gave a superior smile before replying, "What is the tortoise standing on?" "You're very clever, young man, very clever," said the old lady. "But it's turtles all the way down!"

If you want to create a function, which would describe a world in which everything is a Turtle you could use the following.

C#

var x = new List{1, 2, 3};

var numbers = 
  x.Select(t => "turtle");

F#

[1; 2; 3] |> List.map (fun _ -> "turtle")

Haskell

map (\_ -> "turtle") [1, 2, 3]

Mapping example - Shift Letters

Suetonius in The Twelve Caesars gives use the following about Julius Caesar:

If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.

If we wanted to create a simple shifting function we could use the following.

C#

var caesar = 

  String.Concat(

    "DOG".Select(

      c => (char)(c + 13)));

F#

"DOG" 

  |> List.ofSeq

  |> List.map (fun c -> char(int c + 13))

  |> List.toArray

  |> (fun s -> System.String s)

Haskell

map (\c -> chr (ord c + 13)) "DOG"

Filtering

Our second higher order function is f : A → if (f(A)) then B, called filtering.

In filtering, not everything in A which goes through the function f has a value in B.  Thus we say that f filters A into B or f : A → if (f(A)) then B.

Filtering example - Odds only

Say we want a function which will only let Odd values into a club.  We could use the following as a bouncer.

C#

var x = new List{1, 2, 3};

var odd = x.Where(

            (a) => a % 2 == 1);

F#

[1; 2; 3] |> List.filter (fun x -> x % 2 = 1)

Haskell

filter (\x -> mod x 2 == 1) [1, 2, 3]

OR

filter odd [1, 2, 3]

Filtering example - Strings longer than 7

Say you want a function which will only let strings that are greater than 7 in length.

C#

var x = new List{

  "Scarecrow",

  "Tin Man",

  "Cowardly Lion"};

var moreThanSeven = 

  x.Where((a) => a.Length > 7);

F#

["Scarecrow"; "Tin Man"; "Cowardly Lion"]

  |> List.filter (fun x -> String.length x > 7)

Haskell

filter (\x -> length x > 7) 

  ["Scarecrow", "Tin Man", "Cowardly Lion"]

Filtering example - Divisors of 6

In number theory it is common to want to know if some is a divisor of a number.

C#

var x = 

  new List{1, 2, 3, 4, 5};

var divisor = 

  x.Where((a) => 6 % a == 0);

F#

[1..5] |> List.filter (fun x -> 6 % x = 0)

Haskell

filter (\x -> mod 6 x == 0) [1..5]

Folding

Our third and finial higher order function is folding.  Folding is when you have a set of values and you run them through a function f and get one value out of the function, f : A → a.  Max, sum, average, ... are all examples of folding.

Folding example - Sum

A common problem with a set of number is finding the total, this is also called summing.

Since addition is associative, it does not matter if we fold from the left or from the right.  If we were doing subtracts, it would matter.  5 - 2 = 3, but 2 - 5 = -3.

C#

var x = new List{1, 2, 3};

var s = x.Sum();

F#

[1; 2; 3] |> List.fold (fun acc x -> acc + x) 0

OR

[1; 2; 3] |> List.sum

Haskell

foldl (\acc x -> acc + x) 0 [1, 2, 3]

OR

sum [1, 2, 3]

Folding example - Counting

It is funny once you get into really high mathematics you find that a lot the same problems that you study earlier, come up again with fancier names and more abstract ideas.  Combinatorics is a branch of mathematics which is concerned with grouping and counting items.  We can use folding to create a counting function.

C#

var x = new List{1, 2, 3};

var c = x.Count();

F#

[1; 2; 3] |> List.fold (fun acc _ -> acc + 1) 0

OR

[1; 2; 3] |> List.length

Haskell

foldl (\acc _ -> acc + 1) 0 [1, 2, 3]

OR

length [1, 2, 3]

Folding example - Min

It is quite a common problem to want to find the minimum value of a given set.  Again, we can use a folding function to solve this problem.

C#

var x = new List{1, 2, 3};

var m = x.Min();

F#

[1; 2; 3] |> List.fold (

        fun m x -> if m > x then x else m)

      System.Int32.MaxValue

OR

[1; 2; 3] |> List.min

Haskell

foldr1 (\m x -> if m > x then x else m) [1, 2, 3]

OR

minimum [1, 2, 3]

The rest of the presentation has been covered in the following previous blog post:

• Finding Perfect Numbers
• Counting Letter Occurrence
• Finding Islands of Data

Finding Perfect Numbers

"Behoves me keep at utterance. I am perfect"
-- Shakespeare Cymbeline
Act III, Scene I, Line 73

Perfection is rare, one can even say perfection is anti-science.  For with perfection there is nothing more to investigate, nothing to ponder, nothing to study.

Perfect Numbers

In mathematics we have a class of numbers which are called perfect.  These numbers have the property that the some of their proper divisors is equal to them.

We can break this algorithm down into three steps.

Step 1: Find divisors

Given the example of n = 6

In Haskell

filter (\x -> mod 6 x == 0) [1..5]

In F#

[1..5] |> List.filter (fun x -> 6 % x = 0)

Step 2: Sum divisors

Still working with n = 6, we have [1, 2, 3] to sum.

In Haskell

sum [1, 2, 3]

In F#

[1; 2; 3] |> List.sum

Step 3: Compare

In Haskell

6 == 6

In F#

6 = 6

Putting it together

In Haskell (on codepad)

isPerfect :: Int -> Bool
isPerfect n =
  sum (
    filter (\x -> mod n x == 0) [1..(n-1)]) == n

main = print $ isPerfect 496

> true

In F# (on tryfsharp)

let isPerfect n =
  let d = [1..(n-1)] 
            |> List.filter (fun x -> n % x = 0)
            |> List.sum
  d = n
;;

isPerfect 496;;

> true

Higher Order Functions

"Do not confine your children to your own learning for they were born in another time."
--Hebrew Proverb

A higher order function is a function which does at least one of the following two things:

1. it takes a function as an input
2. it returns a function as an output

A normal working programmer more likely than not will use a higher order function in his normal day to day work.

Case 1: Mapping

Simple case in point, if you have use simple SELECT statement in SQL, you have used a higher order function.  A SELECT applies a function you give it against the input it is given from the FROM clause.  Let's use the following statement to illustration this point:


SELECT
    x AS 'value'
   ,(x + x) AS 'add to self'
   ,(x + 1) AS 'increment by 1'
   ,(x * 5) AS 'multiply by 5'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
;

The input given to the SELECT is 1, 2, 3, 4, and 5 from the FROM statement (using the VALUES statement and the AS to create a "table" with the values and a column called x, this will only work in SQL Server, because of the VALUES if you want to use it on a different platform use the UNION ALL for the different values).  We have 4 functions being applied by SELECT to the input given to it.

1. identity function (do nothing)
2. add the value to it self
3. add 1 to the value
4. multiply the value by 5

As one would expect the output is the following (from SQL fiddle):

VALUE	ADD TO SELF	INCREMENT BY 1	MULTIPLY BY 5
1	2	2	5
2	4	3	10
3	6	4	15
4	8	5	20
5	10	6	25

This is type of higher order function is called a mapping.

We can do the same thing in F# using the following code:

let values = [1; 2; 3; 4; 5];;

values |> List.map id;;
values |> List.map (fun x -> x + x);;
values |> List.map (fun x -> x + 1);;
values |> List.map (fun x -> x * 5);;


Using List.map we are able to apply a function against each member of the list, this is exactly what we did in the SQL above!  This F# code gives use the exact same output:


>val values : int list = [1; 2; 3; 4; 5]

> val it : int list = [1; 2; 3; 4; 5]
> val it : int list = [2; 4; 6; 8; 10]
> val it : int list = [2; 3; 4; 5; 6]
> val it : int list = [5; 10; 15; 20; 25]

Case 2: Filtering

Another simple case of everyday use of higher order functions would be the simple WHERE clause again from SQL.  The WHERE clause applies Boolean functions you give it against the input it gets from the FROM clause.  If the output of the Boolean function with the given input is true then the value is passed on, if it is false then it is filtered out.  Let's use the following statement to show this:


SELECT
    x AS 'is even'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
  WHERE (x % 2) = 0
;

This statement filters out the odd numbers using the modulo operation and compares the result against the value 0, thus if the number is divisible by 2 (and hence even) then it is include in the output given to the SELECT statement (which is doing a simple mapping using the identity function).  The output is again as one would expect (from SQL fiddle):

IS EVEN
2
4

This is called filtering in higher order functional terms.

We can do the same thing in F# using the following code:


let values = [1; 2; 3; 4; 5];
 
values |> List.filter (fun x -> x % 2 = 0);;

Again we are simply taking a list of values and by using List.filter we are filtering out the output using a function which compares the input against the modulo operation with 2 to see if the number is even.  This would give the following output:


>val values : int list = [1; 2; 3; 4; 5]

>val it : int list = [2; 4]

Case 3: Folding

Last simple case for today, when you need to apply an operation against a set of values and this operation should give you a single result say a SUM or AVG windowing function.  This is folding in higher order functional land.

Let's use the following SQL to explore this:


SELECT DISTINCT
    SUM(x) OVER () AS 'sum'
   ,AVG(x) OVER () AS 'average'
  FROM (
    VALUES (1),(2),(3),(4),(5)
  ) AS value(x)
;


We are folding the sum of 1, 2, 3, 4, and 5 into one value, 15, and the average value is 3.

As we can see in the following output  (from SQL fiddle):

SUM	AVERAGE
15	3

We can do the same thing in F# using the following code:


let values = [1; 2; 3; 4; 5];

values |> List.sum;;
(values |> List.fold (fun acc x -> acc + x) 0) / values.Length;;


For the sum we use the built in function List.sum to obtain the value.  For the average we sum using List.fold just to show how List.sum might be implemented.  Then we take the sum and divide it by the number of values we summed giving use the average.  This gives use the following output:


>val values : int list = [1; 2; 3; 4; 5]

> val it : int = 15
> val it : int = 3


There you have it higher order functions with examples in F# and SQL!

Sample code is on SQL Fiddle here and Try F# here.  Enjoy.

Sieve of Eratosthenes in F#

"God may have not play dice with the universe, but something strange is going on with the prime numbers."
Paul Erdős

"Mathematicians  have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate."
Leonhard Euler

Before Caesar, before one anno domini, before the internet, there was the library of Alexander and  Eratosthenes.  Eratosthenes of Cyrene was the third librarian of the library of Alexander.  Among other things, he was the first person to calculate the circumference and tilt of the Earth!

If that was not enough, Eratosthenes summoned a simple prime sieve to find prime numbers.  The Sieve of Eratosthenes works in the following way:

1. list integers from 2 to N
2. initially mark 2 as prime (it is prime)
3. cross off all of the integers which are increments of the marked number apart
4. take the next non-crossed off number and mark it as prime
5. repeat step 3 until all numbers are either crossed off or marked as prime

Visually here is what the sieve looks like:

skip to the end

We mark the prime numbers with green and those that have been crossed off with red.

What would the Sieve of Eratosthenes look like in F#?  Well we would want to have a list created from 2 to N, then a function which would take the head of the list and filter out the numbers from the list that are divisible by the head (I know this is not exactly the same as what is above) and loop back around to the top of the function with the new filtered list.


> let sieve n =
-   let rec aux list =      
-     match list with
-     | [] -> []
-     | hd :: tl -> hd :: aux (list |> List.filter (fun x -> x % hd <> 0) )
-   aux [2 .. n]
- ;;

val sieve : int -> int list

Let's test it (I'll blog about using FsUnit at a latter date, so we'll just use poking around testing for now).


> sieve 3;;
val it : int list = [2; 3]
> sieve 11;;
val it : int list = [2; 3; 5; 7; 11]
> sieve 100;;
val it : int list =
  [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
   73; 79; 83; 89; 97]

> sieve 2;;  

val it : int list = [2]

> sieve 1;;

val it : int list = []

Looks like it works.

How to Find Perfect Numbers with F#

"But no perfection is so absolute, That some impurity doth not pollute."
-- The Rape of Lucrece Ver. 124 by William Shakespeare

"It is reasonable to have perfection in our eye ; that we may always advance towards it"
-- Samuel Johnson in letters to The Adventurer

Few things in life can be said to be perfect, but in mathematics there do exist numbers which are said to be perfect.  A perfect number is a number who's sum of its divisors (other than its self) is equal to its self.  

For exemplification, the number 6 is a perfect number.  Why is 6 perfect?

• 6 is divisible by 1
• 6 is divisible by 2
• 6 is divisible by 3

The sum of 1, 2, and 3 is 6 (e.g. 1 + 2 + 3 = 6).  Thus by the definition of a perfect number given above, 6 is a perfect number.  In fact 6 is the first perfect number (1 is never include in the realm of special numbers).

In order to say that a number is perfect we would need to do the following.

1. Find all of the divisors of the given number
2. Sum up the divisors found in step 1
3. Compare the sum found in step 2 to the input

Above is an example of what the flow would look like with the number 6.  We would take the numbers 1 - 5 as a list of possible divisors.  Filter down to 1, 2, and 3.  Sum 1, 2, and 3 giving us 6.  Last comparing the sum we got from the summing step to the input.  Since 6 equals 6, we would return true.

Hmmm, step 1 sounds a lot like a filter and step 2 sounds like folding.  I bet we can write a simple F# function that can find perfect numbers using a filter and a fold (using fsi.exe and Mono).

> let isPerfect x =

-   match x with

-   | x when x <= 1 -> false

-   | _ -> [1 .. x-1] |> List.filter (fun n -> x % n = 0) |> List.sum = x

- ;;

val isPerfect : int -> bool

In the function above we pattern match anything less than and including 1 as false, since by definition those numbers are not perfect numbers (if we wanted we could go up to and including 5 since 6 is the first perfect number).  Succeeding we just need to create a list of numbers up to the number x that we are checking for perfection.  We take this list and filter out the numbers that are not divisors leaving just the divisors.  Then we use the built in folding of summing with the List.sum function.  Finally we compare the sum of the divisors against the input number x.

Now lets test out the function with the perfect numbers 6, 28, and 496.  We'll also test with the less than perfect numbers of 5 and 99.

> isPerfect 6;;

val it : bool = true

> isPerfect 28;;

val it : bool = true

> isPerfect 496;;

val it : bool = true

> isPerfect 5;;  

val it : bool = false

> isPerfect 99;;

val it : bool = false

In fact if we wanted to we could use this function with List.filter against all of the numbers from 1 to 9999!

> [1 .. 9999] |> List.filter isPerfect

- ;;

val it : int list = [6; 28; 496; 8128]

That is in fact the first 4 perfect numbers which were known to the Greeks.

Note, this code is made to be readable not to be fast a few changes should be made to make it fast.

Evens with a Filter

One of the most common "tools" in the functional programming tool belt is the filter.  A filter is typically a function which applied to remove elements a list.

Given the image above, the light green filter called Evens which filters out the member of the list which are not even, in this case out of the list [3; 4; 5; 6] only the members [4; 6] survive the filter.

Note in a language like F# which is immutable the list the filter returns is a new list.

If we want to filter out all of the odd numbers from 1 to 100 we could do the following in F# (using fsi.exe running against Mono).


> let x = [ 1 .. 100 ];;

val x : int list =
  [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
   22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40;
   41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59;
   60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78;
   79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97;
   98; 99; 100]

> let evens x =
-   match x with
-   | x when x % 2 = 0 -> true
-   | _ -> false;;

val evens : int -> bool

> x |> List.filter evens
- ;;
val it : int list =
  [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; 38; 40;
   42; 44; 46; 48; 50; 52; 54; 56; 58; 60; 62; 64; 66; 68; 70; 72; 74; 76; 78;
   80; 82; 84; 86; 88; 90; 92; 94; 96; 98; 100]

In our code above we have a list x which has the values 1 through 100 in it.  We likewise have a function called evens which returns true or false based on if the value passed in is divisible by 2.  We conclude with List.filter utilizing our function evens against every member of list x, if evens returns true that element of x is passed to the output list.  Hence with any function which returns a bool, we can encumber that function to a list using List.filter and filter out any undesirable elements.