Computational Expressions: Implementing Combine
In the previous post we looked at the methods Zero And Yield. In this post, we'll look at returning multiple values from a computational expression using the method Combine.
Note that “builder” in the context of computational expressions is not the same as the object-oriented “builder” pattern, which is used to construct and validate objects.
How things look at the moment…
At the moment our expression builder class looks like this:
type TraceBuilder() =
member this.Bind(m, f) =
match m with
| None ->
printfn "Bind с None. Выход."
| Some a ->
printfn "Bind с Some(%A). Продолжение." a
Option.bind f m
member this.Return(x) =
printfn "Return с незавёрнутым %A" x
Some x
member this.ReturnFrom(m) =
printfn "Return с завёрнутым (%A)" m
m
member this.Zero() =
printfn "Zero"
None
member this.Yield(x) =
printfn "Yield с незавёрутым %A" x
Some x
member this.YieldFrom(m) =
printfn "Yield с завёрнутым (%A)" m
m
// создаём экземпляр процесса
let trace = new TraceBuilder()
And at the moment this class works great. But we're about to run into a problem…
Problem with two 'yields'
Previously we saw how yield used to return values - just like return.
Usually yield is used not once, but several times to return values, for example, when enumerating. Let's try:
trace {
yield 1
yield 2
} |> printfn "Результат yield и следующего за ним yield: %A"
But the trouble is, we get an error message:
Конструкция данного элемента управления может использоваться только в том случае, если построитель вычислительного выражения определяет метод "Combine"
If you write return instead of yieldwe will get the same error.
trace {
return 1
return 2
} |> printfn "Результат return и следующего за ним return: %A"
This problem arises in other contexts as well. For example, if we want to do something and then return the result, like in this code:
trace {
if true then printfn "привет"
return 1
} |> printfn "Результат if и следующего за ним return: %A"
We will get the same error about the missing 'Combine' method.
Understanding the problem
So what's going on here?
To understand, let's look again at how computational expressions work under the hood. We know that return And yield is the last step in a series of continuations, such as here:
Bind(1,fun x ->
Bind(2,fun y ->
Bind(x + y,fun z ->
Return(z) // или Yield
You may be thinking about return And yield, as about the indentation “reset” operators. So when we do return/yield and then again return/yieldwe generate the following code:
Bind(1,fun x ->
Bind(2,fun y ->
Bind(x + y,fun z ->
Yield(z)
// начинаем новое выражение
Bind(3,fun w ->
Bind(4,fun u ->
Bind(w + u,fun v ->
Yield(v)
But in reality it can be simplified to:
let value1 = какое-то выражение
let value2 = какое-то другое выражение
In other words, now in our computational expression there is two meanings. Now the obvious question is: how do we combine these two values to get the overall result for the entire computational expression?
This is a very important point. Return and yield Not perform an early exit from a computational expression. The entire computational expression, up to the closing curly brace, Always is evaluated and returns a single result. I repeat again: all parts of the expression will be calculated anyway and there is no way to avoid it.
If we really want to interrupt the calculation, we will have to write some code and we will discuss how to do this later.
But let's return to the pressing issue. We have two expression results: how to combine them into one?
Introduction to “Combine”
Answer: use method Combinewhich takes two *wrapped” values and combines them into a new wrapped value. And we are the ones who decide what that means combination.
In our case, we are dealing with int options, so one of the simplest implementations that comes to mind is to add numbers. Each parameter is, of course, option (wrapped type), so we have to unwrap them and handle four possible options:
type TraceBuilder() =
// другие члены, как раньше
member this.Combine (a,b) =
match a,b with
| Some a', Some b' ->
printfn "Combine %A с %A" a' b'
Some (a' + b')
| Some a', None ->
printfn "Combine %A с None" a'
Some a'
| None, Some b' ->
printfn "Combine None с %A" b'
Some b'
| None, None ->
printfn "Combine None с None"
None
// создаём новый экземпляр
let trace = new TraceBuilder()
Let's run the test code again:
trace {
yield 1
yield 2
} |> printfn "Результат yield и следующего за ним yield: %A"
Now we get another error message:
Конструкция данного элемента управления может использоваться только в том случае, если построитель вычислительного выражения определяет метод "Delay"
Delay is a special method that allows you to defer the evaluation of an expression until it is needed. We'll discuss it in detail soon; but for now let's just create a default implementation:
type TraceBuilder() =
// другие члены как раньше
member this.Delay(f) =
printfn "Delay"
f()
// создаём новый экземпляр
let trace = new TraceBuilder()
Let's run the test code again:
trace {
yield 1
yield 2
} |> printfn "Результат yield и следующего за ним yield: %A"
And in the end we get working code.
Delay
Yield с незавёрнутым 1
Delay
Yield с незавёрнутым 2
Combine 1 с 2
Результат yield и следующего за ним yield: Some 3
The result of the entire process is the sum of all yield constructs, that is Some 3.
If the first step of our process results in “failure” (i.e. None), second operator yield`` не сработает и весь результат окажется равным Some 1`.
trace {
yield 1
let! x = None
yield 2
} |> printfn "Результат yield и следующего за ним None: %A"
We may have three operators yield instead of two:
trace {
yield 1
yield 2
yield 3
} |> printfn "Результат тройного yield: %A"
The result, as you might guess, is Some 6.
We might even try to mix yield And return in one code. Despite the difference in syntax, the effect of the operators is the same.
trace {
yield 1
return 2
} |> printfn "Результ yield и следующего за ним return: %A"
trace {
return 1
return 2
} |> printfn "Результат return и следующего за ним return: %A"
Using Combine to Generate Sequences
Adding numbers is not the real goal yieldalthough you might like the idea of using an operator to concatenate strings, as in StringBuilder.
But usually yield used to generate sequences, and now that we know how it works Combinewe can extend the “ListBuilder” process (from the previous article) with the necessary methods.
Here is the entire class:
type ListBuilder() =
member this.Bind(m, f) =
m |> List.collect f
member this.Zero() =
printfn "Zero"
[]
member this.Yield(x) =
printfn "Yield незавёрнутого %A в виде списка" x
[x]
member this.YieldFrom(m) =
printfn "Yield завёрнутого (%A) непосредственно" m
m
member this.For(m,f) =
printfn "For %A" m
this.Bind(m,f)
member this.Combine (a,b) =
printfn "Combine %A и %A" a b
List.concat [a;b]
member this.Delay(f) =
printfn "Delay"
f()
// создаём экземпляр процесса
let listbuilder = new ListBuilder()
And here is its use:
listbuilder {
yield 1
yield 2
} |> printfn "Результат yield и следующего за ним yield: %A"
listbuilder {
yield 1
yield! [2;3]
} |> printfn "Результат yield и следующего за ним yield! : %A"
A more complex example with a loop for and several yield.
listbuilder {
for i in ["красная";"синяя"] do
yield i
for j in ["шапка";"повязка"] do
yield! [i + " " + j;"-"]
} |> printfn "Результат for..in..do : %A"
And the result:
["красная"; "красная шапка"; "-"; "красная повязка"; "-"; "синяя"; "синяя шапка"; "-"; "синяя повязка"; "-"]
As you can see, combining for..in..do With yieldwe are not too far from the built-in expression syntax seq. Of course, except that seq lazy.
I strongly encourage you to experiment with these methods to get a feel for how they work under the hood. As can be seen from the example above, to use yield You can get creative and use it to generate all sorts of irregular lists, not just the simplest ones.
Note: If you are wondering how it works While. We will discuss this method after we understand Delay in the next post.
Processing order for multiple “Combine” methods
The method Combine only two parameters. What happens when you want to combine more than two values? Here are, for example, four values to combine:
listbuilder {
yield 1
yield 2
yield 3
yield 4
} |> printfn "Результат четырёх yield: %A"
Looking at the program output, you will see that the values are combined in pairs, which is generally natural.
Cobmine [3] и [4]
Cobmine [2] и [3; 4]
Cobmine [1] и [2; 3; 4]
Результат четырёх yield: [1; 2; 3; 4]
A subtle but important point is that they are combined “in reverse order”, from last value to first. First “3” is combined with “4”, then the result is combined with “2”, and so on.
Combining is not for sequences
In the second of our problem examples, we had no consistency; we had two separate expressions in a row.
trace {
if true then printfn "привет" // выражение 1
return 1 // выражение 2
} |> printfn "Результат комбинирования: %A"
How should these expressions be combined?
The answer depends on what concepts underlie our computational process.
We implement “Combine” for processes with “success” and “failure”
If the process is based on the concept of “successful” and “unsuccessful” calculations, then the standard approach is:
If the first expression is “successful” (whatever that means), use its value.
Otherwise, use the value of the second expression.
In this case the method Zero also usually returns “failure”.
This approach is useful for combining multiple expressions into an “or else” chain, where the final result is the result of the first successful expression.
если (первое выражение)
или иначе (второе выражение)
или иначе (третье выражение)
For example, for the process maybe A common practice is to return the first expression if it has a result, and the second otherwise, as here:
type TraceBuilder() =
// другие члены как раньше
member this.Zero() =
printfn "Zero"
None // неудача
member this.Combine (a,b) =
printfn "Combine %A и %A" a b
match a with
| Some _ -> a // успех — берём значение a
| None -> b // неудача — вместо этого берём значение b
// создаём новый экземпляр
let trace = new TraceBuilder()
Example: Parsing
Let's see how our string parsing example works:
type IntOrBool = I of int | B of bool
let parseInt s =
match System.Int32.TryParse(s) with
| true,i -> Some (I i)
| false,_ -> None
let parseBool s =
match System.Boolean.TryParse(s) with
| true,i -> Some (B i)
| false,_ -> None
trace {
return! parseBool "42" // неудача
return! parseInt "42"
} |> printfn "Результат разбора: %A"
We get the result:
Some (I 42)
As you can see, the result of the first return! equals None and he is ignored. The final result is the result of the second expression Some (I 42).
Example: Dictionary Lookup
Here we will try to look up the same key in multiple dictionaries, and return the first value found:
let map1 = [ ("1","Один"); ("2","Два") ] |> Map.ofList
let map2 = [ ("A","Аня"); ("B","Вова") ] |> Map.ofList
trace {
return! map1.TryFind "A"
return! map2.TryFind "A"
} |> printfn "Результат поиска в словаре: %A"
Result:
Результат поиска в словаре: "Аня"
As you can see, the first search returns None and is ignored. The result of the whole process is the result of the second search.
Obviously, this technique works well if you need to evaluate a sequence of expressions with a possible “unsuccessful” result.
Implementing “Combine” for processes with sequential steps
If the process is based on the concept of sequential execution, then the result of the entire calculation will be the value of the last expression, and all previous steps will be executed only because of their side effects.
In regular F# we could write:
выполнить какое-то выражение
выполнить какое-то другое выражение
финальное выражение
Or, using semicolon syntax:
выполнить какое-то выражение, выполнить какое-то другое выражение, финальное выражение
In regular F#, every expression (except the last) evaluates to a value of type unit.
An equivalent approach in computational expressions would be to treat each expression (except the last) as wrapped values unit with passing it to the next expression until you reach the last expression.
This is exactly what binding does, so the simplest implementation is to simply reuse the method Bind. Also, for this approach to work, the method Zero should return the wrapped value unit.
type TraceBuilder() =
// другие члены как раньше
member this.Zero() =
printfn "Zero"
this.Return () // unit — это не None
member this.Combine (a,b) =
printfn "Combine %A и %A" a b
this.Bind( a, fun ()-> b )
// создаём новый экземпляр
let trace = new TraceBuilder()
The difference from regular binding is that the continuation function has a parameter of type unit and calculates b. It follows that a has a wrapper type with a parameter unitthat is, in our case unit option.
Here is an example of sequential processing, where Combine works the same as Bind:
trace {
if true then printfn "привет......."
if false then printfn ".......мир"
return 1
} |> printfn "Результат последовательного комбинирования: %A"
Here is the trace of our program. Please note that the result of the entire expression is the same as the result of the last expression in the sequence. Just like in regular F# code.
привет.......
Zero
Return с незавёрнутым <null>
Zero
Return с незавёрнутым <null>
Return с незавёрнутым 1
Combine Some null и Some 1
Combine Some null и Some 1
Результат последовательного комбинирования: Some 1
We implement “Combine” for processes that build data structures
Finally, another common pattern for processes is the construction of data structures.
Here's the method Combine should merge two data structures, and the method Zero should return an empty data structure if at all possible.
In the “list builder” example, we used exactly this concept.
Recommendations for mixing “Combine” and “Zero”
We saw two different implementations Combine for optional types.
The first used national values to indicate “success/failure”, where the first success “wins”. In this case
Zeromust returnNone.In the second case, we were talking about sequential execution. In this case
Zerowas defined asSome ().
Both options work great, but was it a coincidence? Are there any guidelines for proper implementation? Combine And Zero?
Firstly, please note that Combine Not must give the same result if the parameters are swapped. That is Combine(a,b) does not necessarily have the same meaning as Combine(b,a). The list builder is a good example of such an implementation.
On the other hand, there is a useful rule that relates Zero And Combine.
Rule: Combine(a,Zero) should be equal Combine(Zero,a)which in turn should be equal to simply a.
Using an analogy from arithmetic, you can think of Combineas about addition (which is not a bad analogy – since the method really folds two meanings).
AND Zero in this case, of course, the number is zero! So the rule can be reformulated:
Rule: a + 0 should be equal 0 + awhich, in turn, must be equal to aWhere + means CombineA 0 means Zero.
Looking at the first implementation (“success/failure”) Combine for optional types, you will see that it does follow this rule, just like the second implementation (“binding” with Some()).
But if we combine the second implementation Combinewith the first implementation Zerothe addition rule will no longer hold, which means we are doing something wrong.
“Combine” without “Bind”
As in other cases, you are not required to implement methods you don't need. So, for a process that simply performs operations one by one, you can create a builder class with methods Combine, Zero And Yield; and without methods Bind And Return.
Here is an example of a minimal working implementation:
type TraceBuilder() =
member this.ReturnFrom(x) = x
member this.Zero() = Some ()
member this.Combine (a,b) =
a |> Option.bind (fun ()-> b )
member this.Delay(f) = f()
// создаём экземпляр процесса
let trace = new TraceBuilder()
Here's how it's used:
trace {
if true then printfn "привет......."
if false then printfn ".......мир"
return! Some 1
} |> printfn "Результат минимального комбинирования: %A"
Similarly, if you have a data structure oriented process, you can simply implement Combine and a couple of improvised methods. Here, for example, is a minimal implementation of a builder class for lists.
type ListBuilder() =
member this.Yield(x) = [x]
member this.For(m,f) =
m |> List.collect f
member this.Combine (a,b) =
List.concat [a;b]
member this.Delay(f) = f()
// создаём экземпляр процесса
let listbuilder = new ListBuilder()
And even with a minimal implementation, we can write code like this:
listbuilder {
yield 1
yield 2
} |> printfn "Результат: %A"
listbuilder {
for i in [1..5] do yield i + 2
yield 42
} |> printfn "Результат: %A"
Separate function “Combine”
In the previous article, we saw that the binding function (Bind) is sometimes used outside the computational process and is implemented as an operator >>=.
Function Combine is also often used on its own. Unlike Bind, it does not have a standard operator. He is jealous of what exactly is meant by combination.
Symmetric operations are often written as ++ or <+>. The “left-handed” combination (which evaluates the second expression only if the first fails) is sometimes written as <++.
Here is an example with a separate left-sided combination of optional values, converted from a dictionary lookup.
module StandaloneCombine =
let combine a b =
match a with
| Some _ -> a // успех — используем a
| None -> b // неудача — вместо a используем b
// создаём инфиксную версию
let ( <++ ) = combine
let map1 = [ ("1","Один"); ("2","Два") ] |> Map.ofList
let map2 = [ ("A","Аня"); ("B","Вова") ] |> Map.ofList
let result =
(map1.TryFind "A")
<++ (map1.TryFind "B")
<++ (map2.TryFind "A")
<++ (map2.TryFind "B")
|> printfn "Результат комбинирования опциональных значений: %A"
Conclusion
What we learned about the method Combine from this article?
You must implement
Combine(AndDelay) if you need to combine or “add” more than one wrapped value in computational expressions.Combinecombines values in pairs, from last to first.No universal implementation
Combinewhich works in all cases – it must be adjusted in accordance with the characteristics of the process.There is a meaningful rule that connects
CombineWithZero.Combinedoes not require the methodBindwas implemented.Combinecan be used as a standalone function.
In the next post, we'll add logic to control expression evaluation time and touch on lazy evaluation.
