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]