search

purescript / purescript-lists

Linked Lists
BSD 3-Clause "New" or "Revised" License
57 stars 51 forks source link

Patch API differences #183

Open milesfrain opened 3 years ago

milesfrain commented 3 years ago

See https://github.com/purescript/purescript-lists/issues/183#issuecomment-825460643 for a proposed API

It looks like there are a few missing functions and instances across the different list modules in this library. To tackle this more systematically, I found the contents of each of the cells of a 4-way Venn diagram created by comparing the following modules:

I've only looked over the instances so far. These appear to be the gaps:

Here are some notes on the remaining differences, which appear to be fine:

I still need to look through the functions. Feel free to help me flag or dismiss any of those differences.

Here's a brief explanation of how to read an entry in the listing of cells. For example in this entry:

-----
LazyNonEmpty NonEmpty
-----
Comonad

It means that Comonad appears only in LazyNonEmpty and NonEmpty, but not in any other modules. More specifically, Comonad is the output of:

intersections [LazyNonEmpty, NonEmpty] `difference` unions [Basic, NonEmpty]

This diagram might help with visualizing the "cells":

Here's the full listing (empty cells omitted).

Instances:

-----
Lazy LazyNonEmpty Basic NonEmpty
-----
Alt
Applicative
Apply
Bind
Eq
Extend
Foldable
FoldableWithIndex
Functor
FunctorWithIndex
Monad
Ord
Semigroup
Show
Traversable
TraversableWithIndex
Unfoldable1

-----
Lazy LazyNonEmpty NonEmpty
-----
Newtype

-----
LazyNonEmpty NonEmpty
-----
Comonad

-----
NonEmpty
-----
Foldable1
Traversable1

-----
Lazy Basic
-----
Alternative
Eq1
MonadPlus
MonadZero
Monoid
Ord1
Plus
Unfoldable

-----
Lazy
-----
Lazy

Functions:

-----
Lazy LazyNonEmpty Basic NonEmpty
-----
concatMap
fromFoldable
head
init
last
length
singleton
tail
toUnfoldable
uncons

-----
Lazy Basic NonEmpty
-----
(!!), index
catMaybes
concat
drop
dropWhile
elemIndex
elemLastIndex
filter
filterM
findIndex
findLastIndex
foldM
group
groupBy
insertAt
intersect
intersectBy
mapMaybe
modifyAt
nub
nubBy
partition
reverse
snoc
span
take
takeWhile
union
unionBy
unzip
updateAt
zip
zipWith
zipWithA

-----
Basic NonEmpty
-----
group'
mapWithIndex
sort
sortBy
unsnoc

-----
LazyNonEmpty NonEmpty
-----
appendFoldable
fromList
toList

-----
NonEmpty
-----
cons
cons'
snoc'

-----
Lazy Basic
-----
(..), range
(\\), difference
Pattern(..)
alterAt
delete
deleteAt
deleteBy
insert
insertBy
many
null
slice
some
stripPrefix
transpose

-----
Basic
-----
dropEnd
manyRec
someRec
takeEnd

-----
Lazy LazyNonEmpty
-----
iterate
repeat

-----
Lazy
-----
cycle
foldrLazy
replicate
replicateM
scanrLazy
Eugleo commented 3 years ago

I'll take a look at the functions, bit by bit, starting with the Lazy Basic category, i.e. the things missing from NonEmpty. I'll update this comment later with the other categories as well.

Are you looking to implement these functions specifically for NonEmptyList? Or for NonEmpty a f in general (maybe with some constraints on f)? I noticed these function generally do exist for NonEmptyArray which would suggest the former.

Doesn't make sense with NonEmpty

... or could make sense, taking NonEmpty and returning a basic List, similarly to what filter does.

Does make sense with NonEmpty

Why are the functions implemented for specific types rather than only once per typeclass, by the way? My students are frequently frustrated — in the best case scenario having to sift through tens of different length functions in the autocomplete window, or more commonly having to suffer a "weird type error" as a consequence of importing the incorrect one.

What I (and they) would expect is having only one length in Data.Foldable (and Foldable1), for example. The same with map, filter and fold.

milesfrain commented 3 years ago

Thanks for digging into this.

Are you looking to implement these functions specifically for NonEmptyList? Or for NonEmpty a f in general?

Planning on implementing specifically for NonEmptyList.

Doesn't make sense with NonEmpty ... or could make sense, taking NonEmpty and returning a basic List, similarly to what filter does.

I think range should be able to return NonEmptyList, at least that works for Array.NonEmpty.range.

For the others, I'm leaning towards returning a basic List. Here are some more examples of that behavior from CommonDiffEmptiability in #199 (assume c is NonEmptyList and canEmpty is List):

catMaybes :: forall a. c (Maybe a) -> canEmpty a
drop :: forall a. Int -> c a -> canEmpty a
dropWhile :: forall a. (a -> Boolean) -> c a -> canEmpty a
filter :: forall a. (a -> Boolean) -> c a -> canEmpty a
filterM :: forall m a. Monad m => (a -> m Boolean) -> c a -> m (canEmpty a)
mapMaybe :: forall a b. (a -> Maybe b) -> c a -> canEmpty b
partition :: forall a. (a -> Boolean) -> c a -> { no :: canEmpty a, yes :: canEmpty a }
span :: forall a. (a -> Boolean) -> c a -> { init :: canEmpty a, rest :: canEmpty a }
take :: forall a. Int -> c a -> canEmpty a
takeEnd :: forall a. Int -> c a -> canEmpty a
takeWhile :: forall a. (a -> Boolean) -> c a -> canEmpty a

Does make sense with NonEmpty

Your alterAt proposal looks good and matches Array.NonEmpty.alterAt. Your other proposals look good too.

Why are the functions implemented for specific types rather than only once per typeclass, by the way? My students are frequently frustrated — in the best case scenario having to sift through tens of different length functions in the autocomplete window, or more commonly having to suffer a "weird type error" as a consequence of importing the incorrect one.

What I (and they) would expect is having only one length in Data.Foldable (and Foldable1), for example. The same with map, filter and fold.

I've also wondered why we don't make more use of typeclasses, but have read that this can lead to more issues later on. Some more discussion (and links to other related info) can be found in #184.

For the "weird type error", I'm guessing these are Could not unify type List with List. https://github.com/purescript/purescript/issues/1647 is tracking proposals to improve those error messages.

milesfrain commented 3 years ago

Here's a patched API proposal:

Instances:

-----
Basic NonEmpty Lazy LazyNonEmpty
(all)
-----
Alt
Applicative
Apply
Bind
Eq
Eq1
Extend
Foldable
FoldableWithIndex
Functor
FunctorWithIndex
Monad
Ord
Ord1
Semigroup
Show
Traversable
TraversableWithIndex
Unfoldable1

-----
Basic Lazy
(only canEmpty)
-----
Alternative
MonadPlus
MonadZero
Monoid
Plus
Unfoldable

-----
NonEmpty LazyNonEmpty
(only NonEmpty)
-----
Comonad
Foldable1
Traversable1

-----
Basic NonEmpty
(only strict)
-----
Note that there are no typeclasses exclusive to strict (non-Lazy) lists

-----
Lazy LazyNonEmpty
(only Lazy)
-----
Lazy

-----
NonEmpty Lazy LazyNonEmpty
(non-Basic)
-----
Newtype

Functions:

-----
Basic NonEmpty Lazy LazyNonEmpty
(all)
-----
alterAt
appendFoldable
catMaybes
concat
concatMap
cons
cons'
delete
deleteAt
deleteBy
(\\), difference
drop
dropEnd
dropWhile
elemIndex
elemLastIndex
filter
filterM
findIndex
findLastIndex
foldM
fromFoldable
group
groupAll
groupAllBy
groupBy
head
(!!), index
init
insert
insertAt
insertBy
intersect
intersectBy
last
length
mapMaybe
modifyAt
nub
nubBy
nubByEq
nubEq
partition
Pattern(..)
(..), range
reverse
singleton
slice
snoc
snoc'
some
someRec
sort
sortBy
span
stripPrefix
tail
take
takeEnd
takeWhile
toUnfoldable
transpose
uncons
union
unionBy
unsnoc
unzip
updateAt
zip
zipWith
zipWithA

-----
Basic Lazy
(only canEmpty)
-----
null
many
manyRec

-----
NonEmpty LazyNonEmpty
(only NonEmpty)
-----
fromList
toList

-----
Lazy LazyNonEmpty
(only Lazy)
-----
iterate
repeat
cycle
foldrLazy
scanlLazy
replicate1  (specialized from Unfoldable1's replicate1)
replicate1M (specialized from Unfoldable1's replicate1A)

-----
Lazy
-----
replicate  (specialized from Unfoldable's replicate)
replicateM (specialized from Unfoldable's replicateA)

Summary of changes:

All functions that were previously available to BOTH Lazy and NonEmpty lists are now available to LazyNonEmpty list.

Added to Lazy and LazyNonEmpty
--------------
sort
sortBy
unsnoc
replicate1
replicate1M

Added to Basic and Lazy
--------------
appendFoldable

Added to Basic and LazyNonEmpty
--------------
cons

Added to LazyNonEmpty
--------------
cycle
foldrLazy
scanlLazy

Added to NonEmpty and LazyNonEmpty
--------------
(..), range
(\\), difference
Pattern(..)
alterAt
delete
deleteAt
deleteBy
insert
insertBy
slice
some
stripPrefix
transpose

Added to NonEmpty, Lazy, and LazyNonEmpty
--------------
dropEnd
takeEnd
cons'
snoc'
someRec

Questions:

Should cons' and snoc' be available to all list types? Considering these signatures:

cons' :: forall a. a -> List a -> NonEmptyList a -- existing for NonEmpty
cons' :: forall a. a -> NonEmptyList a -> List a -- new for Basic

Is it correct to assume that the many* functions are incompatible with NonEmpty, and that the *Rec functions are compatible with everything, including Lazy? Would the *Rec functions be useful in the Array library?

Should specialized versions of replicate1/replicate1M be available for both Lazy and LazyNonEmpty? Argument for is that this matches availability of non-specialized versions. Argument against is that I can't think of a reason to use replicate1 instead of replicate for Lazy.

Should List have specialized versions of scanl/scanr, like Array? It looks like List currently relies on Traversable for these functions.

Should there be a toUnfoldable1 function (similar to toUnfoldable) for NonEmpty lists?