Hi Rob,

First of all, I don't think that your code does exactly what your description indicates, as it will sometimes replace multiple subtrees from the first tree (e.g. when rate is high, you're likely to get both the left and right branches of t1 replaced by t2 in its entirety.

Regardless of how you want to go about doing the actual crossing, I think there are a few techniques that can make manipulating your trees a bit easier.

First, I think it's probably helpful to create an active pattern for matching your trees to simplify handling the different operators, as such:

let (|Binary|Nullary|) = function
| Add(x,y) -> Binary((Add),x,y)
| Sub(x,y) -> Binary((Sub),x,y)
| Multi(x,y) -> Binary((Multi),x,y)
| x -> Nullary(x)

Next, I think it's worthwhile to consider using a zipper datastructure to traverse your trees. You can think of this as a subtree you're looking at, along with the context it came from, which will be a tree with a hole in it. First we need to define a type to represent a tree with a hole in it:

type HoleTree =
| LeftHole of (ExpressionTree * ExpressionTree -> ExpressionTree) * HoleTree * ExpressionTree
| RightHole of (ExpressionTree * ExpressionTree -> ExpressionTree) * ExpressionTree * HoleTree
| Hole

This is based on the Binary/Nullary view on the tree, and represents the cases where the hole is the entire tree, or the hole occurs in the left or right branch of a binary constructor, in which case we track what constructor we're using, along with the full tree on one side, and the tree with a hole on the other side.

Now a zipper is just a pair of a HoleTree and a regular ExpressionTree. We can define a function to plug the tree back into the hole (and therefore convert from the zipper to a normal tree) as such:

let rec plug = function
| LeftHole(con,h,r),t -> con(plug(h,t), r)
| RightHole(con,l,h),t -> con(l, plug(h,t))
| Hole,t -> t

We can also define a function which will descend into a tree, and pull out a single subtree along with the context it came from as follows:

let rec descendTree p = function
| Nullary(x) -> Hole, x
| t when rand.NextDouble() < p -> Hole, t
| Binary(con,l,r) ->
if rand.NextDouble() < 0.5 then
let h,t = descendTree p l
LeftHole(con,h,r),t
else
let h,t = descendTree p r
RightHole(con,l,h),t

Now crossing a single subtree from the first tree with a single subtree from the second is as simple as:

let crossover p t1 t2 =
let h,_ = descendTree p t1
let _,t = descendTree p t2
plug(h,t)

Note that this is slightly different from your example in that the entirety of t1 may be replaced by t2 (i.e. we consider the whole tree to be a possible subtree), but you could restrict the logic to "proper" subtrees with minimal changes.

-Keith