F# Short Circuit Pattern Matching

Question

New to F#. The following question may make no sense at all.

// an attempt at Huffman encoder 
let encodeValue x y = function ...

match ((encodeValue left value), (encodeValue right value)) with
    | ((true, encoded), (_, _)) -> (true, encoded + "1")
    | ((_, _), (true, encoded)) -> (true, encoded + "0")
    | ((false, _), (false, _)) -> (false, "")
    | _ -> failwith "Error"

In a real environment, encodeValue may be quite expensive. Is it possible (or reasonable) to ask F# to evaluate encodeValue left value first, attempt matches, and then execute encodeValue right value when necessary?

Answer 1

You can emulate short-circuiting nicely with lazy values and active patterns:

//not sure why function Lazy.force is recognized in VS but not in FSI
//need to use member Force()
let (|Force|) (l:Lazy<_>) =
    l.Force()

let encodeValue x y = function ...

match (encodeValue left value), lazy(encodeValue right value) with
    | (true, encoded), _                    -> (true, encoded + "1")
    | _              , Force(true, encoded) -> (true, encoded + "0")
    | (false, _)     , Force(false, _)      -> (false, "")
    | _                                     -> failwith "Error"

Lazy values are calculated 0 or 1 times: if you never call Force() on them they will never be calculated. The first time you call Force() they are calculated and the result saved for every other time you call Force().

(|Force|) here is a complete active pattern, a really neat feature which allows you to implement custom pattern match structures of sorts.

Notice as @Brian pointed out that you need to use _ in the lazy value position where short-circuiting is possible. If (true, encoded) matches then the lazy, expensive calculation is never forced. Then for each other case multiple matches using the (|Force|) active pattern will only use the result from the first incident.

Update

@Daniel pointed out that F# already has an active pattern that does exactly what (|Force|) does: http://msdn.microsoft.com/en-us/library/ee340223.aspx

Answer 2

The active pattern solution is way cooler but I thought it would at least be worth mentioning that a simple nested match will also look quite passable here:

  match encodeValue left value with
    | true, e -> true, e + "1"
    | false, _ -> 
      match encodeValue right value with
        | true, f -> true, f + "0"
        | _ -> false, ""

Answer 3

Here's another active pattern solution. Pass the partially-applied function to the active pattern:

let (|Encoded|_|) f x = 
  match f x with
  | true, encoded -> Some encoded
  | _ -> None

match value with
  | Encoded (encodeValue left) encoded -> (true, encoded + "1")
  | Encoded (encodeValue right) encoded -> (true, encoded + "0")
  | _ -> (false, "")

I dropped the last pattern because it will never match.

Answer 4

As F# is not lazy functional language (you can make expressions evaluation lazy explicitly though). What you can do is break down the pattern matching as shown below.

let a() = match encodeValue left value with
          | (true,encoded) -> (true,encoded + "1")
          | _ -> (false,"")
let b() = match encodeValue right value with
          | (true,encoded) -> (true,encoded + "0")
          | _ -> (false,"")
match a() with
| (false,_) -> b()
| r -> r