Free Applicative

Independent Computations and Parallel Composition

Purpose

The Free Applicative (FreeAp) is the applicative counterpart to the Free Monad. Whilst the Free Monad captures sequential, dependent computations, Free Applicative captures independent computations that can potentially run in parallel.

The Key Distinction

Consider fetching a user and their posts:

With Free Monad (sequential, dependent):

// Each step depends on the previous result
Free<DbOp, UserProfile> program =
    getUser(userId)
        .flatMap(user ->              // Must wait for user
            getPosts(user.id())       // Uses user.id() from previous step
                .flatMap(posts ->
                    Free.pure(new UserProfile(user, posts))));

With Free Applicative (independent):

// Both fetches are independent - neither needs the other's result
FreeAp<DbOp, UserProfile> program =
    FreeAp.lift(getUser(userId))
        .map2(
            FreeAp.lift(getPosts(userId)),  // Doesn't depend on getUser result
            UserProfile::new
        );

The Free Applicative version makes it explicit that the two fetches are independent. A smart interpreter can execute them in parallel or batch them into a single database query.

Free Monad vs Free Applicative

Core Structure

FreeAp<F, A> is a sealed interface with three constructors:

public sealed interface FreeAp<F, A> permits FreeAp.Pure, FreeAp.Lift, FreeAp.Ap {

    // A completed computation with a value
    record Pure<F, A>(A value) implements FreeAp<F, A> {}

    // A suspended single operation in F
    record Lift<F, A>(Kind<F, A> fa) implements FreeAp<F, A> {}

    // Application: independent function and argument computations
    record Ap<F, X, A>(
        FreeAp<F, Function<X, A>> ff,  // Computation producing a function
        FreeAp<F, X> fa                 // Computation producing a value
    ) implements FreeAp<F, A> {}
}

The crucial insight is in Ap: both ff and fa are independent. Neither depends on the other's result, which is what enables parallelism and static analysis.

Basic Usage

Creating FreeAp Values

// Pure value (no effects)
FreeAp<MyOp, Integer> pure = FreeAp.pure(42);

// Lift a single instruction
FreeAp<MyOp, User> userFetch = FreeAp.lift(new GetUser(userId));

// Map over a FreeAp
FreeAp<MyOp, String> userName = userFetch.map(User::name);

Combining Independent Computations

The map2 method combines two independent computations:

FreeAp<DbOp, User> userFetch = FreeAp.lift(new GetUser(1));
FreeAp<DbOp, List<Post>> postsFetch = FreeAp.lift(new GetPosts(1));

// Combine them - these are INDEPENDENT
FreeAp<DbOp, UserProfile> profile = userFetch.map2(
    postsFetch,
    (user, posts) -> new UserProfile(user, posts)
);

For more values, chain map2 or use the applicative instance:

FreeApApplicative<DbOp> applicative = new FreeApApplicative<>();

// Combine three independent fetches
FreeAp<DbOp, Dashboard> dashboard = applicative.map3(
    FreeAp.lift(new GetUser(1)),
    FreeAp.lift(new GetPosts(1)),
    FreeAp.lift(new GetNotifications(1)),
    Dashboard::new
);

Interpreting with foldMap

To execute a FreeAp program, provide a natural transformation and an Applicative instance:

// Natural transformation: DbOp ~> IO
Natural<DbOpKind.Witness, IOKind.Witness> interpreter = fa -> {
    DbOp<?> op = DB_OP.narrow(fa);
    return switch (op) {
        case GetUser g -> IO.widen(IO.of(() -> database.findUser(g.id())));
        case GetPosts g -> IO.widen(IO.of(() -> database.findPosts(g.userId())));
        case GetNotifications g -> IO.widen(IO.of(() -> database.findNotifications(g.userId())));
    };
};

// Interpret the program
FreeAp<DbOp, Dashboard> program = ...;
Kind<IOKind.Witness, Dashboard> result = program.foldMap(interpreter, ioApplicative);

Parallel Execution

The power of Free Applicative emerges when the target Applicative supports parallelism. Consider using CompletableFuture:

// Interpreter to CompletableFuture (can run in parallel)
Natural<DbOpKind.Witness, CFKind.Witness> parallelInterpreter = fa -> {
    DbOp<?> op = DB_OP.narrow(fa);
    return switch (op) {
        case GetUser g -> CF.widen(
            CompletableFuture.supplyAsync(() -> database.findUser(g.id()))
        );
        case GetPosts g -> CF.widen(
            CompletableFuture.supplyAsync(() -> database.findPosts(g.userId()))
        );
    };
};

// When interpreted, GetUser and GetPosts can run in parallel!
FreeAp<DbOp, UserProfile> program = userFetch.map2(postsFetch, UserProfile::new);
Kind<CFKind.Witness, UserProfile> future = program.foldMap(parallelInterpreter, cfApplicative);

Because the Free Applicative structure makes independence explicit, the CompletableFuture applicative can start both operations immediately rather than waiting for one to complete.

Static Analysis

Unlike Free Monad, Free Applicative programs can be analysed before execution. The analyze method (an alias for foldMap) emphasises this capability:

// Count operations before executing
Natural<DbOpKind.Witness, ConstKind.Witness<Integer>> counter = fa -> {
    return CONST.widen(Const.of(1));  // Each operation counts as 1
};

FreeAp<DbOp, Dashboard> program = ...;
Kind<ConstKind.Witness<Integer>, Dashboard> analysis =
    program.analyze(counter, constApplicative);

int operationCount = CONST.narrow(analysis).value();
System.out.println("Program will execute " + operationCount + " operations");

This is useful for:

• Query optimisation: Batch similar database operations
• Cost estimation: Calculate resource usage before execution
• Validation: Check program structure meets constraints
• Logging: Record what operations will be performed

Validation with Error Accumulation

Free Applicative is excellent for validation that should report all errors, not just the first:

// Define validation operations
sealed interface ValidationOp<A> {
    record ValidateEmail(String email) implements ValidationOp<String> {}
    record ValidateAge(int age) implements ValidationOp<Integer> {}
    record ValidateName(String name) implements ValidationOp<String> {}
}

// Build validation program
FreeAp<ValidationOp, User> validateUser(String name, String email, int age) {
    return FreeAp.lift(new ValidateName(name)).map2(
        FreeAp.lift(new ValidateEmail(email)).map2(
            FreeAp.lift(new ValidateAge(age)),
            (e, a) -> new Pair<>(e, a)
        ),
        (n, pair) -> new User(n, pair.first(), pair.second())
    );
}

// Interpreter to Validated (accumulates all errors)
Natural<ValidationOpKind.Witness, ValidatedKind.Witness<List<String>>> interpreter = fa -> {
    ValidationOp<?> op = VALIDATION_OP.narrow(fa);
    return switch (op) {
        case ValidateName v -> VALIDATED.widen(
            v.name().length() >= 2
                ? Validated.valid(v.name())
                : Validated.invalid(List.of("Name must be at least 2 characters"))
        );
        case ValidateEmail v -> VALIDATED.widen(
            v.email().contains("@")
                ? Validated.valid(v.email())
                : Validated.invalid(List.of("Invalid email format"))
        );
        case ValidateAge v -> VALIDATED.widen(
            v.age() >= 0 && v.age() <= 150
                ? Validated.valid(v.age())
                : Validated.invalid(List.of("Age must be between 0 and 150"))
        );
    };
}

// Execute validation
FreeAp<ValidationOp, User> program = validateUser("X", "invalid", -5);
Kind<ValidatedKind.Witness<List<String>>, User> result =
    program.foldMap(interpreter, validatedApplicative);

// Result: Invalid(["Name must be at least 2 characters", "Invalid email format", "Age must be between 0 and 150"])
// All three errors are reported!

Retracting to the Original Applicative

If your instruction type F is already an Applicative, you can "retract" back to it:

FreeAp<IOKind.Witness, String> program = ...;

// Retract: FreeAp[IO, A] -> IO[A]
Kind<IOKind.Witness, String> io = program.retract(ioApplicative);

// Equivalent to:
Kind<IOKind.Witness, String> io = program.foldMap(Natural.identity(), ioApplicative);

Applicative Laws

FreeAp satisfies the applicative laws by construction:

1. Identity: pure(id).ap(fa) == fa
2. Homomorphism: pure(f).ap(pure(x)) == pure(f(x))
3. Interchange: ff.ap(pure(x)) == pure(f -> f(x)).ap(ff)
4. Composition: pure(.).ap(ff).ap(fg).ap(fa) == ff.ap(fg.ap(fa))

These laws ensure that combining computations behaves predictably.

When to Use Free Applicative

Good Use Cases

1. Parallel data fetching: Multiple independent API calls or database queries
2. Validation: Accumulate all validation errors rather than failing on first
3. Batching: Combine similar operations into bulk requests
4. Static analysis: Inspect program structure before execution
5. Cost estimation: Calculate resource requirements upfront

When Free Monad is Better

1. Conditional logic: "If user is admin, do X, otherwise do Y"
2. Sequential dependencies: "Use the user ID from step 1 in step 2"
3. Early termination: "Stop processing if validation fails"

Combining Both

In practice, you might use both. Free Applicative for independent parts, Free Monad for the sequential orchestration:

// Free Applicative: independent fetches
FreeAp<DbOp, UserData> fetchUserData = userFetch.map2(postsFetch, UserData::new);

// Free Monad: sequential workflow that uses the fetched data
Free<WorkflowOp, Result> workflow =
    liftFreeAp(fetchUserData)               // Run independent fetches
        .flatMap(userData ->                 // Then use the result
            processUser(userData)            // This depends on fetchUserData
                .flatMap(processed ->
                    saveResult(processed))); // This depends on processUser

Summary

Free Applicative provides:

• Independence: Computations don't depend on each other's results
• Parallelism: Smart interpreters can execute operations concurrently
• Static analysis: Full program structure visible before execution
• Error accumulation: Collect all errors rather than failing fast
• Batching potential: Similar operations can be combined

Use Free Applicative when your computations are independent; use Free Monad when they have sequential dependencies. Often the best solution combines both.

Previous: Free Next: Coyoneda