some/many on Alternative

[johnynek]

Haskell's Alternative has some/many defined as:

some v = (:) <$> v <*> many v
many v = some v <|> pure []

We couldn't add those because without laziness the simple thing doesn't terminate. However, now that we have Defer[F] we can actually write these methods:

  def listOf[A](fa: F[A])(implicit F: Defer[F]): F[List[A]] =
    combineK(map(nonEmptyListOf(fa)(_.toList)), pure(Nil))

  def nonEmptyListOf[A](fa: F[A])(implicit F: Defer[F]): F[NonEmptyList[A]] =
    map2(fa, F.defer(listOf(fa)))(NonEmptyList(_, _))

[johnynek]

That said, I can basically only see these as useful for parsers, so I am not sure we should bother adding it. On the other (other) hand, having this method here means you can code a lot of parser code against just Alternative and Defer and then you could share parsers more easily.

[LukaJCB]

Possibly related to #3446

[djspiewak]

I wrote a very long diatribe on these functions here: https://github.com/scalaz/scalaz/issues/1097#issue-132780274

[johnynek]

Daniel, I don't think I agree. you claim there are only two implementations (really they are both familes of the same:

val count: Int = ??? // any value will do here
def many(fa: F[A]): F[List[A]] = fa map { a => List.fill(count)(a) }

That is not what many actually does since you are ignoring the role of combineK. So clearly there are more implementations that the one you claim.

My implementations above rule out the concerns you had about non-termination because they always terminate due to using Defer. There is no Defer[F] for the kinds of strict data structures that cause a problem (there is no Defer[Option] or Defer[List] or other strict data structures we think of that have an Alternative[F] implementation).

I can't see an F that has both Defer[F] and Alternative[F] that is problematic at the moment. Can you? Certainly the main use of these functions are for parsers (I think they were introduced as such, but I can be mistaken).

My initial motivation was to write code that could generate both the Parser[A] and a Gen[A] with the same generic code, but you can't use many/some for Gen, there is a different approach there (repeatA with some Gen[Int]).

The List[A] vs some lazy structure, I think is beside the point, the laziness is in the F[_] not in the List[_] part.

I think the bottom line is that is just isn't very common at all to have both Defer and Alternative, so I think that is the key reason. I don't think I see any relevant reasons (once Defer has entered the picture) in your linked comment above.

That said, I do think Defer[F] still has a lot of unexplored space. In Haskell, everything is Defer[F] because the whole language is lazy, so it obscures where this concept is being used. I think by exploring it more we can probably find a few more use cases in scala where we can write more general code that has so far been pushed up to things like IO, or into one-offs using Eval.