palatable/lambda

Functional patterns for Java

lambda's Issues

ConstT

HList.cons() static factory method doesn't infer tail type

HList.cons should be parametrized to take advantage of Generalized Target Type Inference, making the following expression infer the resulting HList type from right-hand argument:

SingletonHList<Integer> cons = HList.cons(1, HList.nil());
Tuple2<String, Integer> cons = HList.cons("foo", HList.cons(1, HList.nil()));
// ... and so on for other tuple specializations

Unfortunately, after adding this behavior, compile time was observed to have exponentially increased to over 15 seconds thanks to JDK-8055984, so this behavior shouldn't be added back until it's fixed (targeted for Java 1.9).

Lambda Iterators should automatically deforest when nested

Currently, nested Iterators have to explicitly deforest intermediate iterators in their own independent implementations. Not only does this offer sparse coverage of this capability, it also means that nested iterators of different types that could theoretically flatten together don't know they can do that.

The largest performance gains from Iterators to date have been from deforesting. Clearly this is a desirable trait to support across the board.

99 Lisp Problems sub-site for lambda

It would probably be pretty compelling to see the 99 lisp problems (https://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html) solved with lambda solutions.

TypeAligned

It may make sense to have a TypeAligned type, ala Twan's FunList a.k.a. Oleg's FTCQueue, as a general implementation of stack-safe kleisli composition for lazy monads.

This has at least two caveats. The first is that, in lieu of existentials, the append node type is going to need an eliminator, which is going to be somewhat painful to deal with in the trampoline. The second is that the only lazy monads other than Lazy and IO, which are already internally trampolined, are basically arrows, which means that it's not enough to be able to just heap-allocate composition: the inputs must also be preserved at unwrapping time in a stack-safe manner. Getting the ergonomics right for this may require some finagling.

Target JDK11

JDK10 is GA; hopefully it's less of a disaster than JDK9.

Pattern Matching

A reasonable encoding of value-level pattern matching may be achievable/desirable.

• partial and total matches type check
• destructuring logic should be supplementary to value types, not part of the class definition. This also means there can be multiple ways to destructure the same value type, decidable at match time
• reasonable default match combinators with seamless integration with current Predicate type hierarchy

Getting

Cut ties to java.util.*

Stop using java.util.Function/Bifunction/etc, all of them are horrific. Enough is absolutely enough.

Add support for first-class Monoids

Add support for Monoids, Semigroups with an identity. Consider implications on fold/reduce left/right.

Dependent on #3.

IdentityT

What do we do about Streams?

WIth Java8 came Stream, an interface supporting many of the functional operations that lambda supports, but specialized for the Stream type, instead of Iterable. Due to Stream becoming the canonical medium for mapping, filtering, etc. over Iterable-like types, they are increasingly prevalent in client codebases, and maneuvering between Iterable and Stream is unfortunately not terribly natural. This is not too bad for Stream -> Iterable, but Iterable -> Stream requires an outside wrapping of StreamSupport.stream(it.spliterator(), boolean).

The question is, what do we do about Streams? Some observations:

• Stream is nowhere in the type hierarchy for most Iterable types, so using Stream as an input argument to the builtins buys us almost nothing. Collection does support stream(), so you're at least only one jump away.
• Streams can only be iterated once, which is a generally problematic property for potentially deferred, reordered, cached, or repetitive iteration operations
• Stream has buggy lazy operations, as in the following non-terminating example:

Stream.iterate(1, x -> x + 1).flatMap(x -> Stream.iterate(x, y -> y + 1)).findFirst();

None of these points make Stream a terribly compelling candidate for lambda support, but it's becoming rather ubiquitous, so I suspect it can't be avoided. Here are some options:

1. Provide lenses for viewing Iterables as Streams and vice versa, so the translation can happen either up front or at the end, whichever is most convenient for working with the builitins
2. Support a custom LambdaStream subtype specialization of Stream, where the builtins can be invoked as methods, rather than external functions
3. Offer a separate fork of the builtins, replacing Iterable with Stream, possibly as a separate maven artifact

1 is certainly the easiest, but admittedly this is because it does little to solve the convenience problem. After all, a method reference can convert a Stream to an Iterable, and it's only a single method invocation to do the inverse. A lens would likely not improve on this, although it should do sensible things like not requiring a parallel parameter (a default of false).

2 is probably the most bang for the buck. Working with Streams already relegates one to method chaining and potential train wrecks, so this proposal can be seen as just an extension of the builtin Stream type, with Lambda specific operations. The downsides are unfortunate: Stream is further specialized for primitive ops as IntStream, LongStream, and DoubleStream, etc., with orthogonal interfaces in many cases (IntFunction vs Function, etc), and those would likely need to be independently subtyped as well.

3 preserves the lambda idioms more than the previous two proposals, but seems by far to be the most work. Furthermore, it would likely incur another library dependency, as I would not like to see Lambda's core grow merely to support Streams. Perhaps this is an unreasonable position, but extending the builtins currently is probably off the table, as the additional Stream overloads will likely conflict with the current Iterable versions, resulting in ambiguous call site dispatch, requiring additional typing overhead. Java has enough typing overhead as it is, and I'd rather not exacerbate this. The upside, if there is one, is that the clients need not incur additional cognitive overhead beyond what Lambda core already imposes, as the forked functions would certainly retain the semantics of their Iterable counterparts.

Whatever the path forward, this is not a decision to be taken lightly.

AST Transforms

Would it be useful to have some clang-format style AST transforms that rewrite code in a functional style?

Which AST rewriter is the most robust for Java? Jetbrains Community libraries, one of the Apache projects, ANTLR?

Maintain singletons of all stateless builtins

All the builtins (fn1/fn2/fn3, soon to come monoids, semigroups, etc.) that are stateless should be converted to singleton instances to avoid memory allocation costs.

Add disclaimers in the documentation for unlawful lenses

just dropping some comment, might not even be relevant for this lib:

I just found this and i really like the idea to make stuff visible in the types and having some bits of experience in Java and Haskell, i might even use this in the future

but while looking through the readme in the chapter about lenses, something struck me:

lenses have to fullfill 3 laws, and if you do so you can vary the 4 type parameters of a lens freely. they are (https://hackage.haskell.org/package/lens-4.15.1/docs/Control-Lens-Lens.html)

1. You get back what you put in:

view l (set l v s)  ≡ v

2. Putting back what you got doesn't change anything:

set l (view l s) s  ≡ s

3. Setting twice is the same as setting once:

set l v' (set l v s) ≡ set l v' s

coming back to the first example:

Lens<List<String>, List<String>, Optional<String>, String>

would be something like: (where [] is List)

Lens [String] [String] (Maybe String) String

this is obviously not a lawfull lens. getting and then setting won't work, bc of the types involved.

some other examples are violating the laws, too.

If this was done for convenience reasons, I'd suggest making the lenses lawful and adding prisms (doing it right) or explicitly say that the lenses are broken. This is common in Haskell, some lenses can be unlawful under certain circumstances, but it is documented.

Just some random thoughts from me:
i think only providing java with lenses won't go a long way, because accessors already compose (foo.bar.baz -> no need for view(bar.compose(baz),foo) ). Keeping it immutable is a bonus from lenses. And polymorphic updates are too. But having Prisms and Traversals pushes this even further, eleminating the need for Iterators and explicit Optional handling.

I haven't considered the verboseness of this in Java which might hinder the overall goal.

And especially more contrived use cases where you want indexed optics can be difficult to get right in java, but might be worth it

EDIT: Grammar

Offer some TailRec isomorphism for anamorphism

There is a valid curried, type-safe encoding of tail recursion that's possible with an algebraic data type that constrains base case and recursion case inputs and outputs. Furthermore, this is generalizable to or from anamorphism (unfoldr), so it should be able to seamlessly transition between the two.

It may require a type-level bidirectional inference binding between Tuple* and Fn* to ensure that a tail recursive implementation of an Fn3 requires a Tuple3 input in the recursive case. We'll see. If this is possible, certainly Into3-8 should be nixed in favor of the same encoding.

Eliminate illegal reflection warning from Mockito on Jdk9+

Post java9, reflective operations like those that at least used to be common in Mockito need an explicit JVM flag set, or else are considered illegal and print as much to stderr. Probably mockito just needs to be upgraded to eliminate this, although I'm probably pretty behind on it.

Prism

StateT

Update README

The README hasn't been updated in a while. Add a brief treatment for:

• Choice
• Semigroup
• Monoid
• Functor
• Applicative
• Traversable

Consider adding Divisible / Decidable

Create an idiom to represent a monad transformer

OOP variance rules + FP

Here, http://jnape.com/the-perils-of-implementing-functor-in-java/, you assert that the OOP inheritance (variance) in Java is at odds with the FP functor. I am rather fresh in my understanding of the Java and Haskell systems, but I would appreciate if you could elaborate on this issue.

I intend to contemplate this further... perhaps you could give me a head start. Is there another variance rule that would permit the encoding of the functor abstraction to your satisfaction? What does OCaml do?

LazyT

IterateT

Something like an IO interleaved with a Stream would generalize an effectful iterator and make it much easier to express traversable-once data types. Bonus points if IO can just be a monadic context the elements of the stream are lifted into (I don't see why it couldn't be).

First-class Semigroups

Add support for first-class Semigroups, probably implemented as Fn2<A,A,A>.

Try should defer evaluation until forced

Support for Iterable core operations

Given that the majority of the builtin functions produce Iterables, a Lens (or possibly even just core more builtin functions) supporting at least common operations like cons, head, tail, empty, etc. is a necessity.

Make View compatible with Getting

IO Sequence Proposal

Using sequence on an Iterable<IO<A>> should result in an IO<Iterable<A>> that:

1. immediately returns, i.e. avoids eagerly constructing the full call graph
2. is stack safe, i.e. trampolines both forms of composition (zip and flatMap), as well as arbitrarily deeply staggered nestings of the two
3. immediately executes available work, i.e. produces more frames of the call graph as needed, rather than fully upon initial execution
4. is parallelizable, i.e. continues to use zip and preserves the semantics of unsafePerformAsyncIO
5. is repeatable, i.e. one execution does not implicitly interfere with a second execution of the same IO

Currently only 4 and 5 are supported, but I am convinced this is possible until somebody proves to me otherwise, although a straightforward implementation has admittedly eluded me thus far. I suspect the solution involves Lazy in the synchronous (unsafePerformIO) case, and a combination of CompletableFuture and a BlockingQueue in the asynchronous case.

Additionally, there should be a sequence (likely sequence_) variant that supports execution without accumulating the intermediate result, such that an infinite Iterable could be sequenced, the resulting IO run in parallel with an Executor, and a constant amount memory used.

Finally, a monadic variant of both functions should exist that chooses flatMap over zip for composition (leading to linearized execution for IOs, but otherwise semantically identical).

As far as I'm concerned, this is the most important thing that is worth working on right now, and until this is done, or somehow proven to be impossible with the current IO interface, nothing else gets any attention.

EitherT

Zippers

Tracked on the zippers branch.

MonadError

Add MonadError, a principled way to monadically throw errors. This will allow better patterns regarding transformers that need to transform monads that can throw.

MaybeT

Should all Lenses implicitly use defensive copies?

Originally I felt that implicitly creating defensive copies in lenses would violate the principle of least surprise, not just because the data structures themselves are mutable, but also because this would result in possibly unexpected memory increases.

Over time, it's become increasingly clear to me that nearly every use of lenses over mutable core JDK types call asCopy to avoid mutating the original data structure. This is particularly annoying in cases like MapLens.keys() since there are two structures that need to be copied to avoid any mutation, the Map and the resulting Set of keys. I'm all but convinced that the community would prefer (or would at the very least tolerate) a change to all built-in lenses over mutable data structures to leave all original instances unmodified and use defensive copies all the way down.

My current leaning is to make the change to use defensive copies, but I'll leave this question open for a while to give any interested community members the option to voice their preferences and veto this decision if they have a compelling argument against it.

Optics v2

Related to #10: It's long past time for prisms/folds/traversals to arrive.

Tracking this work on optics

Eliminate LensLike

After adding Optic

Lazy<A>

For stack-safety in the face of large compositional chains, IO (and Fn1 for that matter) should have some idiom for composing on the heap rather than the stack. Extra points if this can be done automatically, or with minimal feedback from the user.

IO

Abandon all hope, ye who enter here.

Consider adding the Alternative typeclass

Should this even exist? How much value will it add? Maybe and LambdaIterable benefit out of the gate, but that's about it. Also, should it extend Applicative, or should it just be a specialized Monoid?

Generic Product Types

Adding generic Product2-8 interfaces (a la CoProduct2-8) with default into methods would allow client code to opt-in to all the goodies that tuples currently benefit from without violating HList's closed universe of inhabitants.

Optic

Generalize (p a (f b)) -> (p s (f t)), then update:

• Lens
• Iso
• View
• Set
• Over
• Under

Add support for a partition function

Proposed signature might look like:

public static <X, L, R> Tuple2<Iterable<L>, Iterable<R>> partition(Function<? super X, ? extends Either<L, R>> fn,
                                                                       Iterable<X> xs) {
        //...
    }

Update README

The readme has fallen into disarray, is woefully out of date, and needs an overhaul.

Improve SortBy

SortBy can be dreadfully slow when the provided Comparable function is expensive, since Comparators#comparing doesn't internally memoize. It might be a good time to offer Memoized from way back, or else an alternate interface that takes a Comparator directly. Or, simply "memoize" via a tagged element, as in Iterable<A> -> Iterable<Tuple2<Comparable, A>> -> sortBy(Tuple2::_1) -> map(Tuple2::_2) -> toCollection(ArrayList::new), which would add an extra full list traversal as well as an extra list copy. I don't know, do something.

Make Bifunctor/Profunctor extend Functor

I've found a way to do this with another unification parameter for Bifunctor and Profunctor. Now might also be a good time to add Invariant, BoundedFunctor, and BoundedProfunctor

Attempt to encode Jacobi identity into Semigroup and Monoid

Then write a paper on it, I guess.

Lambda doesn't compile under the latest JDK9

Compilation using the latest JDK is a disaster. Type inference and narrowing problems everywhere. These are likely all missed regressions in Java9, but I'll leave this issue open until I can get in touch with the OpenJDK guys and submit the likely myriad of bug reports necessary to bring it back to compilation parity with Java8.

Applicatives

Add applicative functors, supporting type-safe distributive functions.

MVar

An MVar is a volatile reference with fair scheduling (FIFO) for both take and put and blocking semantics with strong guarantees of a consumer-notify happens-before on put and a supplier-notify happens-before on take.