VStream HKT: Type Classes for Lazy Streams

Making VStream a First-Class Citizen of Higher-Kinded-J

Why Does VStream Need HKT?

Without HKT encoding, every function that operates on containers must be rewritten for each type. A function that doubles every number inside a Maybe cannot also double every number inside a VStream without a second, near-identical implementation. HKT encoding solves this by letting VStream present itself as Kind<VStreamKind.Witness, A>, the same shape that Maybe, Either, VTask, and every other Higher-Kinded-J type uses. One generic function handles them all.

// Generic: works with VStream, Maybe, Either, VTask, List, ...
<F extends WitnessArity<TypeArity.Unary>> Kind<F, Integer> doubleAll(
        Functor<F> functor, Kind<F, Integer> fa) {
    return functor.map(n -> n * 2, fa);
}

// Using it with VStream
Kind<VStreamKind.Witness, Integer> doubled =
    doubleAll(VStreamFunctor.INSTANCE, VSTREAM.widen(VStream.of(1, 2, 3)));

List<Integer> result = VSTREAM.narrow(doubled).toList().run();
// [2, 4, 6]

Package: org.higherkindedj.hkt.vstream Module: hkj-core

The HKT Encoding

VStream uses the standard Higher-Kinded-J encoding pattern: a witness type, a Kind interface, and a helper for safe conversions.

                     Kind<F, A>
                         │
                         │ extends
                         ▼
               VStreamKind<A>                 (marker interface)
                    │
                    │ extends
                    ▼
              VStream<A>                      (concrete type)

  VStreamKind.Witness                         (phantom type tag)
  └── implements WitnessArity<TypeArity.Unary>

VStreamKind: The Witness Type

public interface VStreamKind<A> extends Kind<VStreamKind.Witness, A> {
    final class Witness implements WitnessArity<TypeArity.Unary> {
        private Witness() {}
    }
}

VStream<A> extends VStreamKind<A>, so every VStream is already a Kind<VStreamKind.Witness, A>. The Witness class is the phantom type tag that tells the type class machinery "this is VStream".

Widen and Narrow

VStreamKindHelper provides safe conversions between the concrete and HKT representations:

import static org.higherkindedj.hkt.vstream.VStreamKindHelper.VSTREAM;

// Concrete → HKT (simple upcast, since VStream extends VStreamKind)
Kind<VStreamKind.Witness, String> widened = VSTREAM.widen(VStream.of("a", "b"));

// HKT → Concrete (validated downcast)
VStream<String> narrowed = VSTREAM.narrow(widened);

Narrowing performs a type check. If you accidentally pass a Kind with the wrong witness type, you get a clear error rather than a silent ClassCastException.

Type Class Hierarchy

VStream implements the full standard type class tower, from Functor up to Alternative, plus Foldable and Traverse for finite streams.

                   ┌───────────────┐
                   │   Functor     │  map
                   └───────┬───────┘
                           │
                   ┌───────▼───────┐
                   │  Applicative  │  of, ap
                   └───────┬───────┘
                           │
                   ┌───────▼───────┐
                   │    Monad      │  flatMap
                   └───────┬───────┘
                           │
                   ┌───────▼───────┐
                   │  Alternative  │  empty, orElse
                   └───────────────┘

  Also:
                   ┌───────────────┐
                   │   Foldable    │  foldMap  (finite streams only)
                   └───────┬───────┘
                           │
                   ┌───────▼───────┐
                   │   Traverse    │  traverse (finite streams only)
                   └───────────────┘

Each level in the hierarchy extends the one above. VStreamAlternative.INSTANCE provides access to all of Functor, Applicative, Monad, and Alternative in a single object.

Functor: Transforming Elements

VStreamFunctor delegates to VStream.map(), preserving laziness. No elements are produced until a terminal operation runs.

Functor<VStreamKind.Witness> functor = VStreamFunctor.INSTANCE;

Kind<VStreamKind.Witness, String> stream = VSTREAM.widen(VStream.of(1, 2, 3));
Kind<VStreamKind.Witness, String> mapped = functor.map(n -> "#" + n, stream);

List<String> result = VSTREAM.narrow(mapped).toList().run();
// ["#1", "#2", "#3"]

Functor laws satisfied:

• Identity: map(x -> x, stream) produces the same elements as stream
• Composition: map(g.compose(f), stream) equals map(g, map(f, stream))

Applicative: Lifting and Combining

VStreamApplicative uses Cartesian product semantics for ap. When you apply a stream of functions to a stream of values, every function is applied to every value. This is the standard choice for list-like monads, consistent with StreamMonad and NonDetPath.

Applicative<VStreamKind.Witness> applicative = VStreamApplicative.INSTANCE;

// Lift a pure value into a single-element stream
Kind<VStreamKind.Witness, String> single = applicative.of("hello");
// VStream.of("hello")

// Cartesian product: 2 functions x 3 values = 6 results
Kind<VStreamKind.Witness, Function<Integer, String>> fns =
    VSTREAM.widen(VStream.of(n -> "x" + n, n -> "y" + n));

Kind<VStreamKind.Witness, Integer> vals =
    VSTREAM.widen(VStream.of(1, 2, 3));

Kind<VStreamKind.Witness, String> applied = applicative.ap(fns, vals);

List<String> result = VSTREAM.narrow(applied).toList().run();
// ["x1", "x2", "x3", "y1", "y2", "y3"]

Monad: Sequential Composition

VStreamMonad provides flatMap, which substitutes each element with a sub-stream and flattens the results. This is the monadic bind for VStream, and it preserves lazy evaluation throughout.

Monad<VStreamKind.Witness> monad = VStreamMonad.INSTANCE;

Kind<VStreamKind.Witness, Integer> stream = VSTREAM.widen(VStream.of(1, 2, 3));

Kind<VStreamKind.Witness, Integer> expanded = monad.flatMap(
    n -> VSTREAM.widen(VStream.of(n, n * 10)),
    stream
);

List<Integer> result = VSTREAM.narrow(expanded).toList().run();
// [1, 10, 2, 20, 3, 30]

Monad laws satisfied:

• Left identity: flatMap(of(a), f) equals f(a)
• Right identity: flatMap(stream, of) equals stream
• Associativity: flatMap(flatMap(stream, f), g) equals flatMap(stream, x -> flatMap(f(x), g))

Alternative: Empty and Concatenation

VStreamAlternative models choice for streams. The empty() method returns an empty stream (the identity element), and orElse concatenates two streams. This is consistent with list-like Alternative instances: "try all of stream A, then try all of stream B".

Alternative<VStreamKind.Witness> alt = VStreamAlternative.INSTANCE;

Kind<VStreamKind.Witness, Integer> first = VSTREAM.widen(VStream.of(1, 2));
Kind<VStreamKind.Witness, Integer> second = VSTREAM.widen(VStream.of(3, 4));

// Concatenation
Kind<VStreamKind.Witness, Integer> combined = alt.orElse(first, () -> second);
List<Integer> result = VSTREAM.narrow(combined).toList().run();
// [1, 2, 3, 4]

// Empty is the identity
Kind<VStreamKind.Witness, Integer> empty = alt.empty();
Kind<VStreamKind.Witness, Integer> same = alt.orElse(first, () -> empty);
// produces [1, 2]

// Guard: filter based on a boolean condition
Kind<VStreamKind.Witness, Unit> passed = alt.guard(true);   // single Unit
Kind<VStreamKind.Witness, Unit> failed = alt.guard(false);  // empty

Foldable and Traverse: Finite Streams Only

Foldable

foldMap pulls every element, maps each one through a function, and combines the results using a monoid. Because VStream elements are produced via VTask, this is a terminal operation that executes the stream.

VStreamTraverse traverse = VStreamTraverse.INSTANCE;

Kind<VStreamKind.Witness, Integer> stream = VSTREAM.widen(VStream.of(1, 2, 3, 4, 5));

// Sum using the integer addition monoid
int sum = traverse.foldMap(Monoid.intSum(), n -> n, stream);
// 15

// String concatenation
String csv = traverse.foldMap(
    Monoid.string(),
    n -> String.valueOf(n),
    stream
);
// "12345"

Traverse

traverse applies an effectful function to each element and collects the results inside an outer applicative context. For VStream, this materialises the stream to a list first, traverses the list, and reconstructs the result as a VStream.

// Traverse with Maybe: if any element maps to Nothing, the whole result is Nothing
Applicative<MaybeKind.Witness> maybeApp = MaybeMonad.INSTANCE;

Kind<VStreamKind.Witness, Integer> stream = VSTREAM.widen(VStream.of(2, 4, 6));

Kind<MaybeKind.Witness, Kind<VStreamKind.Witness, String>> result =
    traverse.traverse(
        maybeApp,
        n -> n > 0
            ? MaybeKindHelper.MAYBE.widen(Maybe.just("+" + n))
            : MaybeKindHelper.MAYBE.widen(Maybe.nothing()),
        stream
    );

// All positive, so result is Just(VStream.of("+2", "+4", "+6"))

Writing Generic Functions

The real power of HKT encoding is writing functions that work with any monadic type. Here is a function that triples every element in any Functor:

static <F extends WitnessArity<TypeArity.Unary>>
Kind<F, Integer> tripleAll(Functor<F> functor, Kind<F, Integer> fa) {
    return functor.map(n -> n * 3, fa);
}

// Works with VStream
Kind<VStreamKind.Witness, Integer> tripled = tripleAll(
    VStreamMonad.INSTANCE,
    VSTREAM.widen(VStream.of(1, 2, 3))
);
// [3, 6, 9]

// Same function works with Maybe
Kind<MaybeKind.Witness, Integer> tripledMaybe = tripleAll(
    MaybeMonad.INSTANCE,
    MaybeKindHelper.MAYBE.widen(Maybe.just(7))
);
// Just(21)

And a function that uses Monad to compose sequential operations:

static <F extends WitnessArity<TypeArity.Unary>>
Kind<F, String> fetchAndFormat(
        Monad<F> monad,
        Kind<F, Integer> ids) {
    return monad.flatMap(
        id -> monad.map(name -> name + " (id=" + id + ")", monad.of("User" + id)),
        ids
    );
}

// With VStream: processes each id, producing a formatted string per element
Kind<VStreamKind.Witness, String> users = fetchAndFormat(
    VStreamMonad.INSTANCE,
    VSTREAM.widen(VStream.of(1, 2, 3))
);
// ["User1 (id=1)", "User2 (id=2)", "User3 (id=3)"]

How VStream Compares to Other Instances

Previous: VStream Next: Writer