By Enrico Buonanno

This article, from Functional Programming in C#, discusses laziness in computing.

Save 37% off Functional Programming in C# with code fccbuonanno at manning.com.

The code Repository, relevant to this article, can be found here: https://github.com/la-yumba/functional-csharp-code

The virtue of laziness

Laziness in computing means deferring a computation until its result is needed. This is beneficial when the computation is expensive, and its result may not be needed in the end. To introduce the idea of laziness, consider the following example of a method that randomly picks one of two given elements. You can try it out in the REPL:

 var rand = new Random();
  
 T Pick<T>(T l, T r) =>
    rand.NextDouble() < 0.5 ? l : r;
  
 Pick(1 + 2, 3 + 4) // => 3, or 7

The interesting thing to point out here is that, when we invoke Pick, both the expressions 11.+ 2 and 3 + 4 are evaluated, even though only one of them is needed in the end. In the example above, the program is performing some unnecessary computation; this is suboptimal and should be avoided if the computation is expensive enough.

To prevent this, we could rewrite Pick to, instead of taking two values, use two lazy computations instead; functions that can produce the required values:

 T Pick<T>(Func<T> l, Func<T> r) =>
    (rand.NextDouble() < 0.5 ? l : r)();
  
 Pick(() => 1 + 2, () => 3 + 4) // => 3, or 7

Pick now firstly picks between the two functions, and then evaluates one of them; as a result, only one computation is performed. In summary, if you’re unsure whether a value is required, and it may be expensive to compute it, pass the value lazily by wrapping it into a function that computes the value. Next, we’ll see how such a lazy API can be beneficial when working with Option.

Lazy APIs for working with Option

The Option API provides a couple of examples that nicely illustrate how laziness can be useful; namely, when we want to use some value only when the Option is in the None state.

PROVIDING A FALLBACK OPTION

OrElse is a convenience function which allows you to combine two Options: it yields the “left” Option, if it’s Some, else falls back to the “right” Option. For example, say you define a repository that looks items up from a cache, failing which it goes to the DB:

 
 interface IRepository<T> { Option<T> Lookup(Guid id); }
  
 class CachingRepository<T> : IRepository<T>
 {
    IRepository<T> cache;
    IRepository<T> db;
  
    public Option<T> Lookup(Guid id)
       => cache.Lookup(id).OrElse(db.Lookup(id));
 }
 

Can you see the problem in the code above? Because OrElse is always called, its argument is always evaluated, meaning that you’re going to the DB even if the item is found in the cache, defeating the purpose of the cache altogether!

This can be solved by using laziness. For such scenarios, I’ve defined an overload of OrElse which doesn’t use a fallback Option, but a function which is evaluated, if necessary, to produce the fallback Option; here are both overloads:

 
 public static Option<T> OrElse<T>
    (this Option<T> left, Option<T> right)
    => left.Match(
       () => right,
       (_) => left);
  
 public static Option<T> OrElse<T>
    (this Option<T> opt, Func<Option<T>> fallback)
    => opt.Match(
       () => fallback(),
       (_) => opt);
 

In the first overload, the fallback option right is always evaluated; in the second one, the fallback function is only evaluated if opt is None. You can accordingly fix the implementation of the caching repository as follows:

 
 public Option<T> Lookup(Guid id)
    => cache.Lookup(id).OrElse(() => db.Lookup(id));
 

Now, if the cache lookup returns Some, OrElse is still called, but db.Lookup isn’t, achieving the desired behavior. As you can see, all you require to make the evaluation of an expression lazy is, instead of an expression, provide a function that evaluates to that expression. Instead of a T, provide a Func<T>.

PROVIDING A DEFAULT VALUE

GetOrElse is a similar function which allows you to get the inner value of an Option, specifying a default value to use in case it’s None. For instance, you may need to look up a value from configuration, and use a default value if no value is specified:

 
 string DefaultApiRoot => "localhost:8000";
  
 string GetApiRoot(IConfigurationRoot config)
    => config.Lookup("ApiRoot").GetOrElse(DefaultApiRoot);
 

Assume that Lookup returns a duly populated Option, whose state depends on whether the value was specified in configuration. Notice that the property DefaultApiRoot is evaluated regardless of the state of the Option.

In this case this is ok, because it returns a constant value. But if DefaultApiRoot involved an expensive computation, then we’d prefer to only perform it if needed, by passing the default value lazily. This is why I’ve also provided two overloads of GetOrElse:

 
 public static T GetOrElse<T>(this Option<T> opt, T defaultValue)
    => opt.Match(
       () => defaultValue,
       (t) => t);
  
 public static T GetOrElse<T>(this Option<T> opt, Func<T> fallback)
    => opt.Match(
       () => fallback(),
       (t) => t);
 

The first overload takes a regular fallback value T, which is evaluated whenever GetOrElse is called. The second overload takes a Func<T>: a function which is evaluated only when necessary.

When should an API take values lazily?

In general, whenever a function may not use some of its arguments, those arguments should be specified as lazy computations. You may choose to provide two overloads, taking a value for the argument, or a lazy computation; then the client code can decide on the most appropriate overload to call:

  • if computing the value is expensive enough, pass the value lazily (more efficient)

  • if the cost of computing the value is negligible, pass the value (more readable)

Composing lazy computations

In the rest of the article, we’ll see how lazy computations can be composed, and why doing this is a powerful technique. We’ll start with the plain-vanilla lazy computation Func<T>, and then move on to lazy computations that include some useful effects such as handling errors or state.

We’ve seen that Func<T> is a lazy computation that can be invoked to obtain a T. It turns out that Func<T> is a functor over T. Remember, a functor is something that has an inner value, over which you can Map a function. How is that possible? The functors we’ve seen are all “containers” of some sort. How can a function possibility be a container, and what’s its inner value?

Well, you can think of a function as containing its “potential” result. If, say, Option<T> “maybe-contains” some value of type T, then you can say that Func<T> “potentially-contains” some value of type T or, perhaps more accurately, contains the potential to produce a value of type T. A function’s inner value is the value it yields when it’s evaluated.

You may know the tale of Aladdin’s magic lamp. When rubbed, it produced a powerful genie. Clearly, such a lamp has the power to contain anything: put a genie into it, and you can rub it to get the genie back out; put your grandma in it, and you can rub it to get grandma back. And you can think of it as a functor: map a “turn blue” function onto the lamp, and whenever you rub the lamp, you’ll get the contents of the lamp, turned blue. Func<T> is such a container, where rubbing is function invocation.

In reality, we know that a functor must expose a Map method with a suitable signature. If we follow the pattern to define Map, we’ll have:

  • an input functor of type () → T; which is a function that can be called to generate a T; let’s call it f

  • a function to be mapped, of type T → R; let’s call it g

  • an expected result of type () → R; which is a function that can be called to generate an R

The implementation is quite simple: invoke f to obtain a T, and then pass it to g to obtain an R, as illustrated below.


Figure 1 Definition of Map for Func<T>


And here’s the corresponding code:

Listing 1 Definition of Map for Func<T>

 
 public static Func<R> Map<T, R>
    (this Func<T> f, Func<T, R> g)
    => () => g(f());
 

Notice that Map doesn’t invoke f: it takes a lazily evaluated T and return a lazily evaluated R. Also notice that the implementation is function composition! To see this in action, open the REPL, import LaYumba.Functional as usual, and type the following:

 
 Func<string> lazyGrandma = () => "grandma";
 Func<string, string> turnBlue = s => $"blue {s}";
 Func<string> lazyGrandmaBlue = lazyGrandma.Map(turnBlue);
  
 lazyGrandmaBlue() // => "blue grandma"
  
 

To better understand the laziness of the whole computation, let’s bake some debug statements in:

 
  
 Func<string> lazyGrandma = () =>
 {
    WriteLine("getting grandma...");
    return "grandma";
 };
  
 Func<string, string> turnBlue = s =>
 {
    WriteLine("turning blue...");
    return $"blue {s}";
 };
  
 var lazyGrandmaBlue = lazyGrandma.Map(turnBlue);  
  
 lazyGrandmaBlue()                                 
 // prints: getting grandma...                     
 //         turning blue...                        
 // => "blue grandma"
 

None of the functions are evaluated yet

All previously composed functions are evaluated now

As you can see, the functions lazyGrandma and turnBlue aren’t invoked until the last line; this shows that we can build up arbitrarily complex logic, without executing anything until we decide to fire things off.

Once you’ve thoroughly understood the examples above, experimented in the REPL, and understood the definition of Map, it’s easy to understand the definition of Bind:

Listing 2. Definition of Bind for Func<T>

 
 public static Func<R> Bind<T, R>
    (this Func<T> f, Func<T, Func<R>> g)
    => () => g(f())();
 

Bind returns a function that, when evaluated, evaluates f to get a T; apply g to it to get a Func<R>, and evaluates it to get the resulting R. This is all interesting, but how useful is it exactly? Well, because functions are already built into the language, being able to treat Func as a monad might not give us a lot. On the other hand, now we know that we can compose functions monadically, and we can bake some effects into how those functions behave.

That’s all for now. For more ways to apply functional programming techniques in your C# programming, see the first chapter of Functional Programming in C# here and this slide deck.