Project Euler Problem 1

Today's post is short; my solution to Project Euler problem 1. In brief, the problem is to sum the multiples of 3 or 5 which are less than 1000.

It's possible to use F# aggregate operators and a bit of comprehension meta-programming to get a really succinct solution. The technique is to sum all the multiples of 3, all the multiples of 5, and then subtract out the redundant sum of the multiples of 15. I generalized the solution for any two multiples and any limit (note that my limit is inclusive). (As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

let euler1 d0 d1 n =

  (seq {d0..d0..n}       |> Seq.sum) +

  (seq {d1..d1..n}       |> Seq.sum) -

  (seq {d0*d1..d0*d1..n} |> Seq.sum)

The main thing I like about this solution is something that has become a theme for me in F#: it resembles the problem in such a way that I could explain the solution to someone who wasn't a programmer. This is important for a number of reasons, but particulary because it is allows non-programmer domain experts to participate in the software design and validation process. With the addition of a few domain-specific language extenstions, this becomes even more true. Thus F# can act as an excellent platform for software integration into areas like business, finance, and science.

The code above is not earth-shaking. But it demonstrates how F# permits, and even encourages, something one could call "fluent programming." That is, the encoding of a solution in a way that comprehends and explains a problem, recognizing that a problem and its solution are two sides of the same coin. (In contrast to solutions which do violence to this complementarity by forcing an "unnatural" solution.) And domain experts respond to that kind of representation because that's how they think about problems and solutions. They can look at the code and, even if they're not programmers, they can develop intuitions about its correctness or incorrectness.

And that's what I like about F#.

-Neil

p.s. I don't intend to follow the entire sequence of Project Euler problems here; I'll just pick and choose a few to illustrate some aspects of F#. For an excellent F# series about Project Euler (and other good stuff), please follow the posts and comments at Mark Pearl's blog.

(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.

List<>.collect Implementations with Benchmarks

I had a situation come up in my proof-of-concept where I needed to do a collect on a .NET List<>. So I did some experiments with how it might best be accomplished. A key factor was that this is something that may be done literally millions of times a day if the application makes it to deployment; so I was concerned with performance. I came up with several versions that I benchmarked. All assume an “open System.Collections.Generic.”

As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.

This is the most straightforward; it’s how you would immediately think of doing it in an imperative style:

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

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

  let lb = new List<'b>()

  for a in la do

    for b in (f a) do

      lb.Add b

  lb

These two versions are probably the most straightforward functional style:

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

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

  let lb = new List<'b>()

  Seq.iter (fun a->Seq.iter lb.Add (f a)) la

  lb

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

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

  let lb = new List<'b>()

  Seq.iter lb.Add (Seq.collect f la)

  lb

This version is the same as one of the above functional styles, but with some “hints” to help with optimization:

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

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

  let fAdd (l:List<'b>) (a:'a) = Seq.iter l.Add (f a)

  let lb = new List<'b>()

  let fAddb = fAdd lb

  Seq.iter fAddb la

  lb

This version uses the fold function to manage the returned List<’b>:

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

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

  Seq.fold 

    (fun (l:List<'b>) (b:'b) -> l.Add b; l) 

    (new List<'b>()) 

    (Seq.collect f la) 

These versions mirror 1 and 2, but use sequences until the last step.

let listCollect5<'a,'b> (f:'a->seq<'b>)

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

  let lb = new List<'b>()

  Seq.iter (fun a->Seq.iter lb.Add (f a)) la

  lb

let listCollect6<'a,'b> (f:'a->seq<'b>)

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

  let lb = new List<'b>()

  Seq.iter lb.Add (Seq.collect f la)

  lb

And here are the benchmarks in %. (I left out the test code; it’s not particularly relevant. Suffice to say all were compiled and run in F# 2, release mode, using tests cleverly designed to foil any optimization.)

listCollect0 = 100%

listCollect1 = 210%

listCollect2 = 169%

listCollect3 = 214%

listCollect4 = 205%

listCollect5 = 434%

listCollect6 = 546%

It turns out that the naïve version worked the best by a pretty big margin. The straightforward functional versions (including the one with “hints”) were second. The ones which mixed lists and sequences were the slowest. What does this imply?

First: it says that if performance is an issue, you simply have to run benchmarks. Furthermore, these benchmarks should include at least one version which is designed to be as simple and direct as possible.

Second: although the straightforward functional versions were slower than the naïve version, they were still plenty fast enough for applications where iteration counts may be in the thousands rather than the millions. They might be preferable in the former instances because they provide a familiar idiom for anyone maintaining the code.

Third: attempts to make the code overly general may impair performance. Stick to the level of abstraction you need, neither more nor less. This is where F# has a real advantage, since it is a language that rewards quick experimentation and the local customization of code snippets.

Bottom line: I’ll probably use the naïve version (listCollect0) in my application. If I come across a similar situation which requires lower performance, I’ll probably use something more like listCollect1 or listCollect2.

-Neil

Computation Expressions with .NET Data Types

I’m still working on my proof-of-concept and it’s going well. One thing that’s been on my mind is the desire to use computation expressions in it somewhere. So I’ve been trying to make sure I understood computation expressions well enough to use them to good purpose.

To smooth the integration, the code will have to play nice with existing .NET components written in C#, etc. To this end, I am sometimes using .NET data structures – like List<> – in places where a pure F# implementation might use list, etc. So I decided to practice with some computation expressions that mingle in these other .NET data structures.

Here is a simple example. It splits a string into a tree using various characters and string.Split. It actually does its job using side-effects on the original tree node (Neil dodges rotten tomatoes thrown by the functional programming purists.) For example, splitting the string “a.b:c.d” by colon first and then by dot would result in this tree:



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

open System.Collections.Generic

open System.Text.RegularExpressions

// This is a simple tree node

// which uses List<>.

// Think of it as a proxy for

// some real-world problem.

type Tree = 

  { Text : string

    mutable Children : List<Tree> option }

  // Syntactic sugar.

  static member Make (s) = 

    { Text=s; Children=None }

// Splits the text in the node

// using string.split and

// uses it to create child nodes.

let splitter (c:char) =

  let a = [|c|]

  let f (t:Tree) =

    t.Children <- Some(new List<Tree>())

    Seq.iter 

      (fun s->t.Children.Value.Add(Tree.Make(s))) 

      (t.Text.Split(a,System.StringSplitOptions.None))

    t

  f

// This is almost like a collect,

// except it works through the 

// side-effects in the splitter function.

type TreeCollector () =

  member this.Bind ((lt:Tree),

                    (f:Tree->Tree)) =

    Seq.iter (fun t->(f t)|>ignore) lt.Children.Value

    lt

  member this.Return v = v

// Some tests.

let splitBar   = splitter '|'

let splitColon = splitter ':'

let splitDot   = splitter '.'

let treeCollector = TreeCollector()

// Build a tree by bar, colon, then dot.

let f0 t = treeCollector {

  let! x = splitBar t

  let! x = splitColon x

  let! x = splitDot x

  return x

}

// Build a tree by colon, bar, then dot.

let f1 t = treeCollector {

  let! x = splitColon t

  let! x = splitBar x

  let! x = splitDot x

  return x

}

// Simple test print.

let printo (t:Tree) =

  let rec f s (t:Tree) =

    printfn "%s %s" s t.Text 

    if t.Children.IsSome then

      Seq.iter (f (s+"  ")) t.Children.Value

  f "" t

let t0 = Tree.Make("a0.a1:b0.b1|c0.c1:d0.d1")

let t1 = Tree.Make(t0.Text)

f0 t0 |> ignore

f1 t1 |> ignore

printo t0

printfn ""

printo t1

printfn "Done."

More Active Pattern Activity

Here are some more samples I came up with while practicing with active patterns. Again, I'm not sure I would ever implement any of these in particular; there may be better ways. But still, I could see where a couple of them would be handy, and my main purpose was to become comfortable with using active patterns.

Forgive my unexciting examples, it was late on a Sunday night, lol.

(As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

// Explicit empty; just for fun.

let inline (|Empty|NonEmpty|) (s:string) =

  match System.String.IsNullOrEmpty(s) with

  | true -> Empty

  | _ -> NonEmpty

// Return Some() if s starts with p, else None.

let inline (|StartsWith|_|) (p:string) (s:string) =

  match s with

  | Empty -> None

  | _ ->

    match s.StartsWith(p) with

    | true -> Some()

    | _ -> None

// Return Some(p,s') if s starts with p, else None,

// where s' is the remainder of s.

let inline (|BeginsWith|_|) (p:string) (s:string) =

  match s with

  | Empty -> None

  | _ ->

    match s.StartsWith(p) with

    | true -> Some((p,s.Substring(p.Length)))

    | _ -> None

// Return (p,s') if s starts with p, else ("",s),

// where s' is the remainder of s.

let inline (|SplitStart|) (p:string) (s:string) =

  match s with

  | Empty -> ("",s)

  | _ ->

    match s.StartsWith(p) with

    | true -> (p,s.Substring(p.Length))

    | _ -> ("",s)

// Return index if s contains p, else None,

let inline (|IndexOf|_|) (p:string) (s:string) =

  match s with

  | Empty -> None

  | _ ->

    match s.IndexOf(p) with

    | -1 -> None

    | i -> Some(i)

let test0 (s:string) =

  match s with

  | StartsWith "zero" -> "zero"

  | StartsWith "one" -> "one"

  | _ -> ""

let test1 (s:string) =

  match s with

  | BeginsWith "zero" (h,t) -> t+h

  | BeginsWith "five" (h,t) -> t+h

  | _ -> s

let test2 (s:string) =

  match s with

  | SplitStart "zero" (h,t) -> t+h

let test3 (s:string) =

  match s with

  | IndexOf "zero" (i) -> s.Substring(i)

  | IndexOf "seven" (i) -> s.Substring(i)

  | _ -> ""

let tests = [

  test0;

  test1;

  test2;

  test3 ]

let strings = [

  "zero two";

  "one two seven four";

  "five two";

  "three two" ]

let result =

  List.map 

    (fun t -> List.map t strings)

    tests 

printf "Done."