Sunday, May 16, 2010

Active Pattern Activity

Wow! It's been a while. But I haven't been idle with respect to F#. Far from it; I’m still keeping busy with my proof of concept port and some real-world maintenance/enhancement to the original C#.

It turns out that some of the requested enhancements in the C# version just happened to coincide with my next porting task for my proof-of-concept. So I got to review those parts of the C# version “for free.” What timing!

I have to say the F# proof of concept is still going a lot better than I had ever hoped. Not only is it easy to port the basic algorithms from C# where applicable, but the kind of straightforward design that “functional-thinking” encourages is making for a better program with much less source code.

But for now, here’s a small thing I did to help learn more about active patterns. It uses the some of the ideas I got from Ashley Feniello’s Scheme tokenizer, while working with List types rather than F# lists.

Let me say up front that this is not how I would solve most pattern-matching problems involving List<>. There are better solutions. However, this does show how active patterns could be used to provide analogs of various built-in pattern-matching design patterns. So look at how the idea works with List<> vis-à-vis F# lists below, but imagine it in situations where it might be more useful.

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

open System.Collections.Generic
// Explicit empty.
let inline (|Empty|NonEmpty|) ((l:List<'a>),i) =
  match (l.Count-i)<=0 with
  | true -> Empty
  | _ -> NonEmpty
// Extract the first item, or None on empty.
// (Avoids creating unused tuple on h::_.)
let inline (|Head|_|) ((l:List<'a>),i) =
  match (l.Count-i)<1 with
  | true -> None
  | _ -> Some(l.[i])
// Extract the first item and the tail, 
// or None on empty.
let inline (|HeadTail|_|) ((l:List<'a>),i) =
  match (l.Count-i)<1 with
  | true -> None
  | _ -> Some(l.[i],(l,i+1))
// Extract the first  items and the tail, 
// or None on less than two items.
let inline (|HeadHeadTail|_|) ((l:List<'a>),i) =
  match (l.Count-i)<2 with
  | true -> None
  | _ -> Some(l.[i],l.[i+1],(l,i+2))
type Token =
  | Open
  | Close
  | Symbol of string
let tokenize (listIn:List<char>) =
  let rec symbol s listIn = 
    match listIn with
    | HeadTail(' ',t)
    | HeadTail('(',t) 
    | HeadTail(')',t) -> Symbol(s),listIn
    | HeadTail(c,t) -> symbol (s+(c.ToString())) t
    | _ -> Symbol(s),listIn
  let rec tokenize' (tokens:Token list) = function
    | HeadTail(' ',t) -> tokenize' tokens t
    | HeadTail('(',t) -> tokenize' (Open::tokens) t
    | HeadTail(')',t) -> tokenize' (Close::tokens) t
    | HeadTail(c,t) -> 
      let s,t' = symbol (c.ToString()) t
      tokenize' (s::tokens) t'
    | _ -> tokens
  List.rev (tokenize' [] (listIn,0))
let l0 = List<char>()
for c in ("(this (is a) test)") do
let tokens = tokenize l0
printf "Done."


Bond007 said...

Awesome sample! Good explanation about the active patterns

TechNeilogy said...

Thanks! I like the way active patterns can make difficult sections of code more readable.