Sequential comparison in F#
Aug. 29th, 2012 06:00 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
This kind of questions becomes more and more popular:
if(x == y && y == z)
.I wish I could write
if(x == y and z)
but there is no syntax for that. What can I do?Look at this solution. Also, is seems to be a good example of using monads, also known as Computation Expressions. Surprisingly to myself, it is fairly fast.
// Generic
let inline mOp1<'a> op sample x = op sample x, sample
let inline mOp2<'a> op1 op2 (b, sample) x = op1 b (op2 sample x), sample
// Implementation for (=) and (&&)
let (==) = mOp1 (=)
let (&=) = mOp2 (&&) (=)
// Use
let ret1 = a == b &= c &= d &= e |> fst
How it works
The approach is a very simplified State monad. The monadic type is a tuple of (bool, 'T)
. The first component is the boolean value of ongoing calculation, and the second is the sample value to compare with.
(==)
would initialize the monad, similar to Delay
operator.(&=)
is used for all subsequent comparisons. It is similar to Bind
operator.
We don't need Return
because fst
would serve pretty fine.mOp1
and mOp2
are abstractions over the logical operations. These allow defining your own operators. Here are examples of or-equal
and and-greater-than
:
let (|=) = mOp2 (||) (=)
let (.>) = mOp1 (>)
let (&>) = mOp2 (&&) (>)
// Use
let ret2 = a == b |= c |= d |= e |> fst // if any of b,c,d,e equals to a
let ret3 = 5 .> 3 &> 4 |> fst // true: 5>3 && 5>4
let ret4 = 5 .> 3 &> 8 &> 4 |> fst // false
Performance
I have looked at solutions like List.forall (fun n -> n = a)
, but constructing [a; b; c;]
List
is quite slow, so my primary goal was performance.
Running a chain of 8 comparisons, 10 million times:
- 04972ms
a=b && a=с && ...
- 23138ms
List
-based - 12367ms monadic
P.S. If you like it, you may upvote it on StackOverflow. :)