List of sub-optimal definitions in `Data.List.Base`

[JacquesCarette]

While looking at PR #2355 from @mildsunrise I noticed a ridiculous number of uses of with. These turn out to not be localized to Data.List.Properties but come from uses of with in Data.List.Base. The vast majority of them can be simplified, with a really nice knock-on effect to simplify quite a few proofs.

But I'm guessing this is yet another case of breaking change, so has to wait until 3.0? I think we should outlaw uses of with in function definitions, if favour of defining explicit 'helper' functions.

---

• mapMaybe Improve Data.List.Base.mapMaybe (#2359; deprecate use of with #2123) #2361
• unalignWith
• unfold Improve Data.List.Base.unfold (#2359; deprecate use of with #2123) #2364
• scanr -- but already in another PR? Refactor Data.List.Base.scan* and their properties #2395
• initLast -- ditto?
• unsnoc
• takeWhile Improve Data.List.Base (fix #2359; deprecate use of with #2123) #2365
• dropWhile Improve Data.List.Base (fix #2359; deprecate use of with #2123) #2365
• filter
• partition Improve Data.List.Base (fix #2359; deprecate use of with #2123) #2365
• span Improve Data.List.Base (fix #2359; deprecate use of with #2123) #2365
• linesBy Improve Data.List.Base (fix #2359; deprecate use of with #2123) #2366
• wordsBy Improve Data.List.Base (fix #2359; deprecate use of with #2123) #2366
• derun Improve Data.List.Base (fix #2359; deprecate use of with #2123) #2365

[jamesmckinna]

This is, I think, the standing criticism from @omelkonian and others (related to the various issue he has posted on the main issue tracker about inspect and our attempts to deprecate it...), but only indirectly alluded to in #1937 / #2123 ... although PRs associated with those have tackled some of the worst offenders (esp. wrt turning with into let, esp. in recursive calls).

In response to @MatthewDaggitt 's cautious nudge, @mildsunrise suggests in #2355 that the refactoring of catMaybe/mapMaybe that I suggested based on Orestis' prelude may in fact have the same behaviour as the existing definitions, so we should investigate that for all the examples you have identified... and if the computational behaviour is the same, then I think that shouldn't count as breaking...

[jamesmckinna]

@JacquesCarette Could you make a task list here on the issue of the 'worst'/most egregious examples? Then the analysis could be parallelised across us all... and we could document our arguments for the behaviour being preserved...?
UPDATED: on a PR-by-function basis

[MatthewDaggitt]

Yes if the computational behaviour is the same then it's backwards compatible.

[JacquesCarette]

As long as "forcing evaluation by with" and "forcing evaluation through pattern-matching" are 'the same computational behaviour', then yes. They sure have very different usability behaviour!!

[JacquesCarette]

Updated with an actual list.

[jamesmckinna]

Looking at the list, definitely a case of too much with on a Bool instead of if_then_else_ as in the first bullet of #1937 ... notwithstanding that proofs of properties of such functions may themselves require with to fix the types up properly in each case branch... (and I suppose at some point it might be relevant to document the list of "650--700" uses of with in stdlib I refer to there...)

See also @gallais 's comment there about if_then_else_ potentially being too eager to unfold...

[jamesmckinna]

initLast is an early example of using views to write functions... for which the use of with is often (but not always) a corollary side-effect... so I'd be tempted to go after the lower-hanging fruit first ;-)

[jamesmckinna]

Re: lower hanging fruit: clearly some uses of with (eg in merge) have already been 'deprecated' in favour of if_then_else_, so I suspect the others might also be 'harmless'.

[mildsunrise]

i would love to see this happen. how would we name the new helper functions? do we have existing modules where we're using helper functions that serve as precedent? also, aren't there compatibility concerns from adding many new exports to a Base module?

[jamesmckinna]

Well, the way to replace with by an explicit helper function is already described in the paper which introduces the notation... but as to polluting the namespace, such things may always (?) be encapsulated as part of a local where block, so I think the knock-on effect on the API can be minimised?

[JacquesCarette]

The problem with local-only functions is that it's hard to prove things about them. Some of those helpers are independently useful, so those are 'easy', in a sense.

For many of the ones in Data.List.Base, the 'helpers' actually already exist - most of them are just maybe from Data.Maybe.Base !!

[JacquesCarette]

initLast is an early example of using views to write functions... for which the use of with is often (but not always) a corollary side-effect... so I'd be tempted to go after the lower-hanging fruit first ;-)

I'm starting to see that there are different kinds of views. At the very least:

1. structurally obvious sub-computations (where you want to match on the results)
2. computationally necessary sub-computations (on which you want to match)
3. change of coordinates, then match

For 1, I'd argue that using views for defining a function (as opposed doing a proof) is an anti-pattern. For 2, like initLast, I am undecided. For 3, I think with makes quite a bit of sense.

[jamesmckinna]

Interesting analysis! (and some of the first since VfL to subject this monster to more 'scientific'/empirical scrutiny ;-))

'Anti-patterns in DTFP': a catchy, if niche, book title!?

[JacquesCarette]

Don't know if we could fill a book (yet), but certainly a non-trivial paper.

[jamesmckinna]

@JacquesCarette for how many of your shopping list do you have PRs ready-to-go? (I don't want to duplicate work... ;-))