The Lazy applicative functor

Lazy computations form an applicative functor.

This article is an instalment in an article series about applicative functors. A previous article has described how lazy computations form a functor. In this article, you'll see that lazy computations also form an applicative functor.

Apply #

As you have previously seen, C# isn't the best fit for the concept of applicative functors. Nevertheless, you can write an Apply extension method following the applicative 'code template':

public static Lazy<TResult> Apply<TResult, T>(
    this Lazy<Func<T, TResult>> selector,
    Lazy<T> source)
{
    return new Lazy<TResult>(() => selector.Value(source.Value));
}

The Apply method takes both a lazy selector and a lazy value called source. It applies the function to the value and returns the result, still as a lazy value. If you have a lazy function f and a lazy value x, you can use the method like this:

Lazy<Func<int, string>> f = // ...
Lazy<int> x = // ...
Lazy<string> y = f.Apply(x);

The utility of Apply, however, mostly tends to emerge when you need to chain multiple containers together; in this case, multiple lazy values. You can do that by adding as many overloads to Apply as you need:

public static Lazy<Func<T2, TResult>> Apply<T1, T2, TResult>(
    this Lazy<Func<T1, T2, TResult>> selector,
    Lazy<T1> source)
{
    return new Lazy<Func<T2, TResult>>(() => y => selector.Value(source.Value, y));
}

This overload partially applies the input function. When selector is a function that takes two arguments, you can apply a single of those two arguments, and the result is a new function that closes over the value, but still waits for its second input argument. You can use it like this:

Lazy<Func<char, int, string>> f = // ...
Lazy<char> c = // ...
Lazy<int> i = // ...
Lazy<string> s = f.Apply(c).Apply(i);

Notice that you can chain the various overloads of Apply. In the above example, you have a lazy function that takes a char and an int as input, and returns a string. It could, for instance, be a function that invokes the equivalent string constructor overload.

Calling f.Apply(c) uses the overload that takes a Lazy<Func<T1, T2, TResult>> as input. The return value is a Lazy<Func<int, string>>, which the first Apply then picks up, to return a Lazy<string>.

Usually, you may have one, two, or several lazy values, whereas your function itself isn't contained in a Lazy container. While you can use a helper method such as Lazy.FromValue to 'elevate' a 'normal' function to a lazy function value, it's often more convenient if you have another Apply overload like this:

public static Lazy<Func<T2, TResult>> Apply<T1, T2, TResult>(
    this Func<T1, T2, TResult> selector,
    Lazy<T1> source)
{
    return new Lazy<Func<T2, TResult>>(() => y => selector(source.Value, y));
}

The only difference to the equivalent overload is that in this overload, selector isn't a Lazy value, while source still is. This simplifies usage:

Func<char, int, string> f = // ...
Lazy<char> c = // ...
Lazy<int> i = // ...
Lazy<string> s = f.Apply(c).Apply(i);

Notice that in this variation of the example, f is no longer a Lazy<Func<...>>, but just a normal Func.

F# #

F#'s type inference is more powerful than C#'s, so you don't have to resort to various overloads to make things work. You could, for example, create a minimal Lazy module:

module Lazy =
    // ('a -> 'b) -> Lazy<'a> -> Lazy<'b>
    let map f (x : Lazy<'a>) = lazy f x.Value
    // Lazy<('a -> 'b)> -> Lazy<'a> -> Lazy<'b>
    let apply (x : Lazy<_>) (f : Lazy<_>) = lazy f.Value x.Value

In this code listing, I've repeated the map function shown in a previous article. It's not required for the implementation of apply, but you'll see it in use shortly, so I thought it was convenient to include it in the listing.

If you belong to the camp of F# programmers who think that F# should emulate Haskell, you can also introduce an operator:

let (<*>) f x = Lazy.apply x f

Notice that this <*> operator simply flips the arguments of Lazy.apply. If you introduce such an operator, be aware that the admonition from the overview article still applies. In Haskell, the <*> operator applies to any Applicative, which makes it truly general. In F#, once you define an operator like this, it applies specifically to a particular container type, which, in this case, is Lazy<'a>.

You can replicate the first of the above C# examples like this:

let f : Lazy<int -> string> = // ...
let x : Lazy<int> = // ...
let y : Lazy<string> = Lazy.apply x f

Alternatively, if you want to use the <*> operator, you can compute y like this:

let y : Lazy<string> = f <*> x

Chaining multiple lazy computations together also works:

let f : Lazy<char -> int -> string> = // ...
let c : Lazy<char> = // ...
let i : Lazy<int> = // ...
let s = Lazy.apply c f |> Lazy.apply i

Again, you can compute s with the operator, if that's more to your liking:

let s : Lazy<string> = f <*> c <*> i

Finally, if your function isn't contained in a Lazy value, you can start out with Lazy.map:

let f : char -> int -> string = // ...
let c : Lazy<char> = // ...
let i : Lazy<int> = // ...
let s : Lazy<string> = Lazy.map f c |> Lazy.apply i

This works without requiring additional overloads. Since F# natively supports partial function application, the first step in the pipeline, Lazy.map f c has the type Lazy<int -> string> because f is a function of the type char -> int -> string, but in the first step, Lazy.map f c only supplies c, which contains a char value.

Once more, if you prefer the infix operator, you can also compute s as:

let s : Lazy<string> = lazy f <*> c <*> i

While I find operator-based syntax attractive in Haskell code, I'm more hesitant about such syntax in F#.

Haskell #

As outlined in the previous article, Haskell is already lazily evaluated, so it makes little sense to introduce an explicit Lazy data container. While Haskell's built-in Identity isn't quite equivalent to .NET's Lazy<T> object, some similarities remain; most notably, the Identity functor is also applicative:

Prelude Data.Functor.Identity> :t f
f :: a -> Int -> [a]
Prelude Data.Functor.Identity> :t c
c :: Identity Char
Prelude Data.Functor.Identity> :t i
i :: Num a => Identity a
Prelude Data.Functor.Identity> :t f <$> c <*> i
f <$> c <*> i :: Identity String

This little GHCi session simply illustrates that if you have a 'normal' function f and two Identity values c and i, you can compose them using the infix map operator <$>, followed by the infix apply operator <*>. This is equivalent to the F# expression Lazy.map f c |> Lazy.apply i.

Still, this makes little sense, since all Haskell expressions are already lazily evaluated.

Summary #

The Lazy functor is also an applicative functor. This can be used to combine multiple lazily computed values into a single lazily computed value.

Next: Applicative monoids.