(Amateur) Mathematical Interlude

Incidental encounters with the “FizzBuzz” problem and the Project Euler problems got me thinking about divisibility and sieve of Eratosthenes. Listing the numbers, I noticed they followed a pattern. If you list all the numbers up to and including the least common multiple (LCM) of a sequence of numbers, it seems to form a palindromic sequence.

For example, here is the FizzBuzz sequence (starting with zero) with 3 and 5, where “3” means divisible by 3, “5” divisible by 5, “a” divisible by both, and “.“ divisible by neither:

a..3.53..35.3..a

Here is 4 and 6:

a...4.6.4...a...4.6.4...a

And 2,3, and 5 (using a,b,c,d for multiple divisibility):

d.2325a.23b.a.2c2.a.b32.a5232.d

Now, here’s the deal. If you extend this to the entire sequence of primes up to a given index, that should also be a palindromic sequence (proof is left to the reader). And if you take the endpoint (LCM) of that sequence, the form will always be “.x.” In other words, a multiple surrounded by prime twins, relative to the sequence.

My wonder is, and I’m not enough of a mathematician to puzzle this out, is what relationship does this generator of relative prime twins have to the universe of prime twins? What fraction of the numbers it generates are prime twins, and does that fraction approach some limit, or does it continue to fall?

Like I said, I’m no mathematician; questions like these are probably as simple to mathematician as questions like “should I use an int or a float” are to a programmer. It just shows how new interesting questions can stem from the confluence of others.

-Neil

p.s. You can graph these types of palindromic sequences by incrementing each cell in the sieve by a number corresponding to the power of two associated with the index (minus one) of the prime number. E.g. 2=1,3=2,5=4,7=8,etc. This will assign a unique number based on divisibility, which can then be graphed.

For example, here (with gratuitous colorization) is the graph for 2,3,5:

Composable Order Relations

A situation arose where I needed to be certain a list was sorted. I didn’t want to sort the list, because that might mask subtle errors upstream. I just wanted to check the sorting and raise some kind of alert if the list was found to be out of order.

Even before I started experimenting, I realized that checking a list for sorting was just a specific example of checking whether the pairs in a list satisfied a certain binary order relation. So I decided to work directly on a more general solution. I played around with various aggregate list operators, but nothing really “clicked.” In particular, I had trouble finding something which used the built-in predicates in a composable way, and which also produced nice-looking code. The closest solution was that below, which uses List.reduce. However, I didn’t like it because I wanted to handle the errors as a simple case of validation, not as an exception. (As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

/// Example 1.

/// Throws an exception if r a b

/// returns False, b otherwise.

let relTest r a b =

  match r a b with

  | true -> b

  | _ -> failwith "Error."

let ex1_Ok   = [0;1;2] |> List.reduce (relTest (<))

//let ex1_Fail = [1;0;2] |> List.reduce (relTest (<))

So I decided to code it directly. I wrote two versions. The first is a simple test just to get the logic right. It returns true if a predicate holds true for every sequential pair in the list, or short circuits and returns false if the predicate fails. The second version returns Some(index) for the first item in the first pair for which the predicate returns true, or None otherwise. This allows for better user feedback. (Note that the sense of this second version is reversed, it seems to make more sense done that way. The sense of the predicate can be reversed to test for failure.)*

/// Example 2.

/// Returns True if f n (n+1) 

/// returns True for all pairs in l,

/// False otherwise.

/// Returns True for lists of length 0 or 1.

let relForAll r =

  let rec f0 h0 = 

    function 

    | [] -> true

    | h1::t1 ->

      match r h0 h1 with

      | true -> f0 h1 t1

      | _ -> false 

  function

  | [] -> true

  | h::t -> f0 h t

let ex2_True  = [0;1;2] |> relForAll (<)

let ex2_False = [1;0;2] |> relForAll (<)

/// Example 3.

/// Returns Some(i,f n (n+1)) if f n (n+1) 

/// returns true for any pair in l,

/// None otherwise.

/// Returns None for lists of length 0 or 1.

let relTryFind r =

  let rec f0 i h0 = 

    function 

    | [] -> None

    | h1::t1 ->

      match r h0 h1 with

      | false -> f0 (i+1) h1 t1

      | _ -> Some(i) 

  function

  | [] -> None

  | h::t -> f0 0 h t

// Note reversed predicate sense!

let ex3_None = [0;1;2] |> relTryFind (>=)

let ex3_Some = [1;0;2] |> relTryFind (>=)

This last example shows similar functionality, except that the predicate is mapped across the list. It is also doable using List.fold, which is also shown.

/// Example 4.

/// Returns a list, l.Length-1 in length,

/// containing f n (n+1) for each pair.

/// Returns [] for lists of length 0 or 1.

let relMap r =

  let rec f0 acc h0 =

    function 

    | [] -> acc  

    | h1::t1 -> f0 ((r h0 h1)::acc) h1 t1 

  function

  | [] -> []

  | h::t -> f0 [] h t |> List.rev

let ex4_TT = [0;1;2] |> relMap (<)

let ex4_FT = [1;0;2] |> relMap (<)

/// Example 5.

/// Returns a list, l.Length-1 in length,

/// containing f n (n+1) for each pair.

/// Returns [] for lists of length 0 or 1.

let relMap'fold r =

  let rec f0 (acc,h0) h1 =

    (((r h0 h1)::acc),h1) 

  function

  | [] -> []

  | h::t -> 

    let (acc,_) = List.fold f0 ([],h) t

    acc |> List.rev 

let ex5_TT = [0;1;2] |> relMap'fold (<)

let ex5_FT = [1;0;2] |> relMap'fold (<)

There are, of course, lots of variations on this theme. It should be considered more of a composable design pattern than something for which every variation must exist in a library.

-Neil

p.s. Where feasible, I like to solve coding problems using existing language idioms. This is, I think, one of the primary keys to writing maintainable code. Since idiom affects the fundamental way coders structure new code, it’s probably even more important in the grand scheme of things than are naming conventions and comments (though these are important too). In that vein, if anyone has some other solutions which seem more “F#-like,” or which use the library aggregate operators, I’d be happy to see examples as comments. I’m still a relative newcomer to F#, and it’s likely I missed the obvious.

*There are, of course, a number of succinct ways to do this which are not very computationally efficient:

let f l =

  l = (l|>List.sort)

let f0 = f [1;2;3;4]

let f1 = f [1;2;0;4]

Update

The blame for my not updating this blog rests squarely on the shoulders of F#. In fact, it feels like I've been doing nothing by F# programming for the last couple of weeks:

1) My commercial proof-of-concept in F# is going so well, that I'm going to replace some of the components in the current C# version with F# versions developed in my proof-of-concept work. Further, I'm going to recommend that large portions of the project be migrated to F#. (More about what it actually is later, I hope.)

2) I've solved up through problem #10 in Project Euler using F#. Solving the Project Euler problems has been a great help in learning F#, particularly in the use of sequences and sequence operations.

3) I've made good progress in reading (and understanding!) Expert F# 2.0. My copy will soon be as dog-eared as are my copies of Programming F# and Real-World Functional Programming.

4) OK, this last one doesn't have anything to do with F#: I replaced my gradually frying video card so now my computer screen looks a little less like a 1960's psychedelic painting, lol. It was rough going there for a few days, though, waiting for the UPS truck to arrive.

However, it is on my mind that I want to come up with something really cool for a blog post. Watch this space!

-Neil

Flip Operator for F#?

I posted the following message on hubFS:

“Situations often arise where I need to curry the second argument of a function. For example, the divisor in (/). It’s not hard to come up with a function or operator for doing this, as the following code illustrates. But is there a way to do it in F# without defining a new function or operator?”

For instance, one might want to curry the second argument of the divide function (/) in order to produce a curried “divide-by-N” function. This kind of operation is very common in stack-based languages like FORTH, but is not usually needed in imperative languages.

Here is some code that illustrates what I want to do. I decided to use “><” to represent the “flip*” or “swap” operator.

// This code is presented "as-is" and without warranty 

// or implied fitness of any kind; use at your own risk. 

// "Flip" or "swap" operations:

let flip f a b = f b a

let (><) f a b = f b a

// Sundry tests:

let thisIs20 = ((/) >< 5) 100

let also20 = ((><) (/) 5) 100

let d5'0 = flip (/) 5

let d5'1 = (/) >< 5

let m5'0 = flip (%) 5

let m5'1 = (%) >< 5

let t0 = d5'0 99 // 19

let t1 = d5'1 99 // 19

let t2 = m5'0 99 // 4

let t3 = m5'1 99 // 4

let divBy = (><) (/)

let divBy5 = divBy 5

let shouldBe20 = divBy5 100

// etc.

I ask again: is there a good native way to do this in F#? If not, it might well worth standardizing this. (And potentially other FORTH-like operators like “over” and “rot,” perhaps with an extensible syntax.)

-Neil

*Name suggested by “mau” on hubFS.

World's Smartest Rabbit

I couldn't think of what to post, so instead of posting a picture of a rabbit with a pancake on it's head, I thought I'd post proof that Mr. Bun-bun is the world's smartest rabbit. If you listen close enough, you can hear Mr. B exclaim "Potrzebie!" under his breath.

Why I love F#, Part 2

Here’s another small sample of F# readability. When I was an undergraduate, we were taught that the first step in data analysis was the computation of basic descriptive statistics. At first we learned to do this by hand, but later we moved to computer programs like SPSS. However, if asked to imagine a how such a program might look, it would have been a struggle to come up with something in the BASIC that I was learning at the same time.

One the other hand, here is an F# example. I can’t imagine having any trouble explaining the operation of this program to someone with a basic knowledge of statistics but no computer programming experience. It simply looks like what it does in a way that is succinct and comprehensible. (I did deliberately avoid constructs like folding which might make it more difficult to understand.)

Albeit this is a simple example. However, with a little experience, seemingly incomprehensible things like workflows and continuations become just as obvious in F#.

And that’s what I love about F# and why I think it has a future.

// This code is presented "as-is" and without warranty 

// or implied fitness of any kind; use at your own risk. 

// Compute basic statistics.

let basicStats (l:float list) =

  let sum = l |> List.sum 

  let count = (float) l.Length 

  let avg = sum / count

  let std = 

    l 

    |> List.map (fun x->(x-avg)**2.0)

    |> List.sum

    |> (fun x->(x/(count-1.0))**0.5)

  (count,sum,avg,std)

// Test.

let x = 

  [ for i in 0..9 -> (float) i] 

  |> basicStats 

This is why I love F#.

This is why I love F# (and functional programming in general). How could possibly state something so elegantly in any other type of language?

// This code is presented "as-is" and without warranty 

// or implied fitness of any kind; use at your own risk.

// A moving average on a sequence.

let movingAvg n s =

  s |> Seq.windowed n 

    |> Seq.map Array.sum 

    |> Seq.map (fun a->a/n) 

// Currying for the pure joy of it.

let movingAvg3 = movingAvg 3

let r = new System.Random()

// For test purposes, the input sequences are 

// based on lists so they can be easily examined...

let l0 = [ for i in 0..9 do yield i ]

let l1 = [ for i in 0..9 do yield r.Next(100) ]

// ...and the output sequences are converted to lists

// for the same reason.

let x0 = movingAvg3 l0 |> Seq.toList 

let x1 = movingAvg3 l1 |> Seq.toList

Easy, No-Compile DFAs

The methods for compiling a set of finite automata DFAs or NFAs into a composite DFA are found in most introductory compiler texts. But how easy is it to construct a simple engine in F# which recognizes a series of patterns? As it turns out, pretty simple. The code bellow is an experiment I did in this regard. (It’s not intended to be the be-all, end-all of state machine engines – it’s mostly just a bit of practice in F#.)

The code below demonstrates a machine with can recognize strings of objects and generate tags when various strings are recognized. It basically creates lists of “mini-machines” capable of recognizing individual strings. These are then run in parallel using the List functions. The test code shows it working with strings of digits, but it is parameterized to work with any class which supports equality comparison.

For example, one might add machines capable of recognizing 123,345, and 567. In that case the string of digits 123456123 would match 123 two times, 345 once, and 567 not at all.

I went overboard in using various List functions, because one of the purposes of this exercise was to become more used to doing things “the F# way.” If I were doing this for production, I might use tail recursive functions in some places. I also pass around more data than is strictly required, in the interests of playing around with some ideas about composability.

(As an exercise to the reader, it should be noted that it is possible to do away with the Dictionary<> entirely and substitute a List function, albeit with a loss of efficiency.)

As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk. This is something I did really fast, for fun, so there may be any number of bugs and inefficiencies.

open System.Collections.Generic 

// A pattern is a tag and a list of data.

type Pattern<'t,'d> = 't*('d list)

// Maps two functions onto a 2-tuple.

let internal mapTuples f g (a,b) = (f a),(g b)

// Test a datum and update the tag list and the

// list of running machines.

let test (datum:'d) 

         (l0:Pattern<'t,'d> list) = 

  let headMatches (datum:'d) 

                  ((_,data):Pattern<'t,'d>) =

    data.Head=datum

  let emptyDataTail ((_,data):Pattern<'t,'d>) =

    data.Tail.IsEmpty

  let tailPattern ((tag,data):Pattern<'t,'d>) =

    (tag,data.Tail) 

  l0 |> (List.filter (headMatches datum)) 

     |> (List.partition emptyDataTail)

     |> mapTuples (List.map fst) 

                  (List.map tailPattern) 

// Start a machine if required.

// Machines with strings of length 1 are also

// recognized here.

let start (patterns:Dictionary<'d,Pattern<'t,'d> list>) 

          (datum:'d) 

          ((tags,running):'t list*Pattern<'t,'d> list) =

  let dataIsEmpty ((_,data):Pattern<'t,'d>) =

    data.IsEmpty

  let addTag (tags:'t list) ((tag,_):Pattern<'t,'d>) =

    tag::tags

  let addPattern (patterns:Pattern<'t,'d> list) (p:Pattern<'t,'d>) =

    p::patterns

  match patterns.TryGetValue datum with

    | (false,_) -> (tags,running)

    | (_,pl) -> 

      pl |> List.partition dataIsEmpty

         |> mapTuples (List.fold addTag tags) 

                      (List.fold addPattern running) 

// Run one cycle of the machine.

let cycle (patterns:Dictionary<'d,Pattern<'t,'d> list>) 

          ((tags,running):'t list*Pattern<'t,'d> list)

          (datum:'d) =

  running |> test datum 

          |> start patterns datum 

// Helper function to add a machine.

let add (patterns:Dictionary<'d,Pattern<'t,'d> list>) 

        (tag:'t)

        (data:'d list) =

  match data with 

  | [] -> () 

  | h::t ->

    patterns.[h] <-

      (tag,t)::(

        match patterns.TryGetValue h with

        | (false,_) -> []

        | (true,pl) -> pl)

// Test functions.

// Test.

let testDatum (patterns:Dictionary<'d,Pattern<'t,'d> list>) 

              (rtn:'t list*Pattern<'t,'d> list)

              (datum:'d) = 

  let rtn0 = cycle patterns rtn datum

  List.iter (printf "%A ") (fst rtn0)

  printfn "" 

  rtn0

let patterns = new Dictionary<int,Pattern<string,int> list>()

add patterns "0(0)" [0]

add patterns "0(1)" [0]

add patterns "0124" [0;1;2;4]

add patterns "01"   [0;1]

add patterns "013"  [0;1;3]

add patterns "132"  [1;3;2]

let rtn = Seq.fold (testDatum patterns) ([],[]) [0;1;0;1;3;2;4]

printfn "Done."

Surfing the Tuple Pipeline

A situation came up where I needed to pipeline a tuple created by a List.partition to two different functions and then return the result as a tuple. I decided to create a some pipeline operators for tuples. On reading Real-World Functional Programming (RWFP), however, I found a solution involving a map function and the standard forward pipe operator (|>). It turns out that I like the RWFP approach better than mine, but the special tuple pipelines I came up with are not without interest, so I decided to post them here. (As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

First, here are a couple of map functions adapted from the example on page 148 of RWFP. Please excuse my quick-and-dirty naming conventions. For clarity in this example only, I named the map functions “map12” for “map one function onto a two-tuple” and “map22” for “map two functions onto a two-tuple.”

let map12 f (a,b) = ((f a),(f b))

let map22 f g (a,b) = ((f a),(g b))

Here are my pipeline operators. The (||>) works like (|> map12), while the second two act like (map22 |>). (||>>) takes tupled functions, while (||>>> takes curried functions.

let (||>) (a,b) f = ((f a),(f b))

let (||>>) (a,b) (f,g) = ((f a),(g b))

let (||>>>) (a,b) f g = ((f a),(g b))

And here is a small test. Each example partitions a list of integers into lists of even and odd integers, creates a list of the halves of the even integers and the doubles of the odd integers, then sums the two lists and returns the sums as a tuple. (This is probably a useless task, but it demonstrates the operation without as much fluff as the real-world example I was working on.)

let isEven n = (n%2)=0

let doubleIt n = n*2

let halveIt n = n/2

let nums = [0..19]

let a = 

  List.partition isEven nums

  |> map22 (List.map halveIt) (List.map doubleIt)

  |> map12 List.sum

let b = 

  List.partition isEven nums

  ||>> (List.map halveIt, List.map doubleIt)

  ||> List.sum

let c = 

  List.partition isEven nums

  ||>>> (List.map halveIt) <| (List.map doubleIt)

  ||> List.sum

All are fairly readable; in general, I prefer the RWFP approach because I feel it better extends the language than does a custom operator. But it would probably be possible to find design situations where any of the three was appropriate.

One more List<>.collect Implementation

I realized that I left out a listCollect method from the previous set of tests. That is, the really, really naïve method which uses indices rather than enumeration. This reduces the cost somewhat, since there is no need to set-up enumeration. This cost is very small for a single call, but it can add up if listCollect is called millions of times.

Here is the code; I called it listCollect7. (As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

let listCollect7<'a,'b> (f:'a->List<'b>)

                        (la:List<'a>) : List<'b> =

  let lb = new List<'b>()

  for ila=0 to (la.Count-1) do

    let fla = f la.[ila]

    for ifla=0 to (fla.Count-1) do

      lb.Add fla.[ifla]

  lb

The numbers from the previous tests showed some variation due to variations in CPU load, GC, the random nature of the test data I was using, etc. So I decided to do a larger test. This test involved 25 million calls of listCollect in each of the seven versions. Below is the tale of the tape. As can be seen, the indexed method was the fastest, beating the enumerated version by about 20%.


At this point, however, I want to sound a cautionary note. I want it to be understood that I am NOT saying that one should ALWAYS pick the fastest method. Rather, one should always pick the BEST method. For performance-critical applications, the fastest method may indeed be the best method. However, in most situations, maintenance will trump speed.

By maintenance, I mean “development usability” in all aspects: the ability to find and avoid bugs, the ability to modify code, composability, etc. And often, the best approach to maintainability is the path of the language-appropriate idiom.

Always think of the user. If the user has to wait a tenth of a second for a screen refresh in a game, she’ll thank you for writing faster code. If she has to wait ten days for a simple change request or bug fix, she’ll thank you for writing more maintainable code.