The Lazy applicative functor by Mark Seemann
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 overload 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.
