cats Redesign `NonEmptyLazyList` to be maximally lazy

Redesign NonEmptyLazyList to be maximally lazy.

[x] docs
[ ] tests
[ ] commit/history cleanup?

Sep 02 '23 06:09 NthPortal

First of all, I have to say that I really appreciate this effort to make NonEmptyLazyList better, thank you @NthPortal for taking on that!

However, let me add my 2 cents worth and outline a few thoughts regarding the APIs being developed. The thoughts may or may not be that good – just my personal perception of the issue:

Any syntax sugar (including infix operators like #:::) should not be the primary point of effort. I.e. if there's an operator #::: defined as LL => NELL => NELL, then there should be a corresponding conventional method with a clear name like prependNell or something. In other words, infix operators should be nothing but shortcuts to some conventional counterparts, e.g.
```
A #:: LL     <=> LL.prepend(A)
NELL #::: LL <=> LL.prependNell(NELL)
```

When it comes to the #::: operator, I would assume it should get some sort of symmetry. I.e. if A #::: B is possible, then B #::: A should be possible as well. Personally, I see three ways how to organize it.

First, it could be defined as a bunch of extension methods on LazyList along with methods defined inside NonEmptyLazyList itself to enable syntax like the following:
```
LL   #::: LL   => LL   (already implemented in LL, but has to be re-defined, see below)
LL   #::: NELL => NELL (can be implemented in NELL)
NELL #::: LL   => NELL (can be implemented as an extension method to LL)
NELL #::: NELL => NELL (can be implemented in NELL, has to be overloaded)
```
(here and below, saying "can be implemented in NELL" I assume NELL.Deferrer of course) If to follow this approach we should also get
```
A #:: LL => NELL
```
However, it does not seem right because there's A #:: LL => LL in the ScalaLib already and re-defining the return value could be quite confusing. As well as the fact that we would have to re-define LL #::: LL => LL inside Cats to keep it working once we get NELL #::: LL => NELL into a scope.

Another approach could be more specific on types. That way there could be the following syntax enabled:

LL    #::: LL    => LL   (already implemented in LL, all good)
W(LL) #::: NELL  => NELL (can be implemented in NELL, takes W as a param)
NELL  #::: W(LL) => NELL (can be implemented in W created from LL)
NELL  #::: NELL  => NELL (can be implemented in NELL, takes NELL as a param)

Here W is some sort of wrapper of LL (like the former Maybe / now Tail in the PR's NELL) Also, W makes it really easy to support the one-item prepend too:

A #:: LL    => LL   (already implemented in LL, all good)
A #:: W(LL) => NELL (can be implemented in W created from LL)

To make lifting of LL to W more convenient it could be enabled as an extension method itself, e.g.

import cats.syntax.lazyList._

val a: LazyList[Int] = ???
val b: NonEmptyLazyList[Int] = ???
val c: NonEmptyLazyList[Int] = a.prepareNell #::: b // requires `a` to be lifted to `W`
val d: NonEmptyLazyList[Int] = b #::: a.prepareNell // requires `a` to be lifted to `W`
val e: NonEmptyLazyList[Int] = c #::: d // no lifting required

where .prepareNell is just the extension method that lifts LL into W.

The last approach in my understanding is the strictest one on types. Here, we could avoid mixing-up LL and NELL in the #::: operator and invite a different name for that (##::: maybe?):

LL   #:::  LL   => LL   (already implemented in LL, all good)
LL   ##::: NELL => NELL (can be implemented in NELL, takes LL as a param)
NELL ##::: LL   => NELL (can be implemented as an extension method to LL)
NELL #:::  NELL => NELL (can be implemented in NELL, takes NELL as a param)
A    #::   LL   => LL   (already implemented in LL, all good)
A    ##::  LL   => NELL (can be implemented as an extension method to LL)

Not sure if it is the best way though, but the simplest and lest ambiguous one for sure.

Worth to mention that ideally it would be nice if at the end of all we could get such an API for LazyList/NonEmptyLasyList that would correspond the API for the regular List/NonEmptyList, i.e. #:: and #::: could be used for LL/NELL in the same cases as :: and ::: are used for L/NEL. We are not there yet because some separate work is necessary to be done for the regular NonEmptyList, but if we could end up with a good non-conflicting design of APIs for NELL, then later we could add all the missing methods to NEL (in a separate PR of course).

Sep 24 '23 06:09 satorg

there should be a corresponding conventional method with a clear name like prependNell

prepend, prependNell, append and appendNell all already exist

Any syntax sugar (including infix operators like #:::) should not be the primary point of effort

it's rather moot given the above, but regardless, I strongly disagree. despite being symbolic methods, #:: and #::: are the default way of constructing LazyLists; as essentially a specialisation of LazyList, NonEmptyLazyList ought to have an equivalent API so that it is predictable to users of LazyList. LazyList has .unfold on its companion with equivalent power/flexibility as #:: and #:::, but it is less used because it is simply less ergonomic

Here, we could avoid mixing-up LL and NELL in the #::: operator and invite a different name for that

this is possible, but seems unnecessarily confusing and annoying to users. the methods do the same thing, so they should be named the same thing

Sep 24 '23 20:09 NthPortal

it could be enabled as an extension method itself, e.g. [...] .prepareNell

I really like this idea, though I think something like asNellTail would be a better name

Sep 24 '23 23:09 NthPortal

I got about halfway through porting the laziness tests over from scala/scala when I burned out on this. I'll try to push up what I've done so far soon, and someone else can push this through if desired. I'll also rebase while I'm at it

Jun 26 '25 17:06 NthPortal