## Monday, September 27, 2010

### F# Computation Expressions, Yield/For Mechanics

Today’s episode of the ongoing computation expression saga features Yield/YieldFrom and For. One encounters fewer examples of these than of Bind/Return, though in most respects their operation is every bit as fundamental.

The code accompanying this post shows the use of these computation expression members in creating a rudimentary list comprehension builder. Of course, in real life you’ll want to use F#’s far superior built-in list comprehensions. But playing “how would I implement built-in construct X” is an old tradition in functional languages, so here it is. (As always, the code and information here are presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

First, although the desired output is a list, the ongoing concatenation is maintained internally as a sequence. The Run operator does the work of converting the final sequence into a list. This makes the computation expression class more general, because the internal sequence could easily be converted to an array, .NET generic collection, etc., with a single change or override.

`  member this.Run a = `
`    a |> Seq.toList `

Most of the work for the yield operations in the example is done by the Combine operators. The Yield, YieldFrom, Delay, and Zero members are really just defaults (in fact, Yield and YieldFrom are identical in form). Three Combine operators cover most cases:

1) Prepending a yielded item to an ongoing sequence. This is the basic yield operation.

2) Combining a two sequences. This is the yield! operation.

3) Appending a yielded item with an ongoing sequence. This makes it possible to avoid calling the Zero operation using a “().” (Although Zero is supplied in case it is desired.)

`  member this.Combine (a,b) = `
`    Seq.append (Seq.singleton a) b`
` `
`  member this.Combine (a,b) = `
`    Seq.append a b `
` `
`  member this.Combine (a,b) = `
`    Seq.append a (Seq.singleton b) `

The For operator just maps the body of the loop onto each item in the “for” sequence. This is essentially a default behavior for comprehensions. (An iteration across the “for” sequence might be a more appropriate default for some situations.)

`  member this.For (s,f) =`
`    s |> Seq.map f `

At last, here is the full code plus an example. I named the computation expression builder class “SlightComprehension” both in order to reflect its rudimentary nature and to indicate my slight (but improving!) understanding of computation expressions, lol.

`/// Rudimentary list comprehension builder.`
`type SlightComprehension () =`
` `
`  /// Combine an item and a list.`
`  member this.Combine (a,b) = `
`    Seq.append (Seq.singleton a) b`
` `
`  member this.Combine (a,b) = `
`    Seq.append a b `
` `
`  member this.Combine (a,b) = `
`    Seq.append a (Seq.singleton b) `
` `
`  /// Map the function and convert`
`  /// the result to a list.`
`  member this.For (s,f) =`
`    s |> Seq.map f `
` `
`  // The following members are basically defaults.`
` `
`  member this.Delay f = f()`
` `
`  /// The concatenations are maintained`
`  /// internally as a sequence.`
`  /// This call converts them to a list`
`  /// on output.`
`  member this.Run a = `
`    a |> Seq.toList `
` `
`  // The Combine overload makes `
`  // Yield and YieldFrom identical`
`  // in form.`
` `
`  member this.Yield a = a`
` `
`  member this.YieldFrom a = a`
` `
`  member this.Zero() = Seq.empty `
` `
` `
`// Test.`
` `
`let result0 = SlightComprehension () {`
`   yield 1`
`   for i in 2..3 do`
`     yield i `
`   yield 4 `
`   // The following calls Zero.`
`   () }  `
` `
`let result1 = SlightComprehension () {`
`   yield 0`
`   yield! result0`
`   yield seq { for i in 5..7 -> i }`
`   yield 8 }`
` `
`// result1 = [0;1;2;3;4;5;6;7;8]`
`printfn "%A" result1`
` `
`printfn "Your breakpoint here."`
` `
` `
` `