Skip to content

Match nub* functions with Array #178

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
milesfrain opened this issue Dec 16, 2020 · 5 comments · Fixed by #179
Closed

Match nub* functions with Array #178

milesfrain opened this issue Dec 16, 2020 · 5 comments · Fixed by #179
Assignees
Labels
purs-0.14 A reminder to address this issue or merge this PR before we release PureScript v0.14.0

Comments

@milesfrain
Copy link
Contributor

milesfrain commented Dec 16, 2020

The names and signatures of the nub* functions for List and Array are inconsistent.

-- List
nub :: forall a. Eq a => List a -> List a
nubBy :: forall a. (a -> a -> Boolean) -> List a -> List a

-- Array
nub :: forall a. Ord a => Array a -> Array a
nubEq :: forall a. Eq a => Array a -> Array a
nubBy :: forall a. (a -> a -> Ordering) -> Array a -> Array a
nubByEq :: forall a. (a -> a -> Boolean) -> Array a -> Array a

Proposing we make List match Array and use this lineup:

nub :: forall a. Ord a => List a -> List a
nubEq :: forall a. Eq a => List a -> List a
nubBy :: forall a. (a -> a -> Ordering) -> List a -> List a
nubByEq :: forall a. (a -> a -> Boolean) -> List a -> List a

We should also include examples and runtime info.

@hdgarrood
Copy link
Contributor

Thanks for the report. I think 0.14.0 is a good time to do this.

@thomashoneyman thomashoneyman added the purs-0.14 A reminder to address this issue or merge this PR before we release PureScript v0.14.0 label Dec 16, 2020
@milesfrain
Copy link
Contributor Author

I'll work on this (can't self-assign though).

I'm thinking the simplest (and most performant) way to add Ord-based nub/nubBy to List is to just reuse Array's nub/nubBy. I don't expect the O(n) conversion cost to matter much compared to the O(n log n) and O(n^2) runtimes (todo - note these runtimes in the array docs).

We should also double-check and document whether the first, last, or unknown duplicate is kept.

Also going to add these missing functions to Data.List.Lazy and Data.List.NonEmpty.

@milesfrain
Copy link
Contributor Author

Found that our List matches Haskell's nub and nubBy.

nub :: Eq a => [a] -> [a]
nubBy :: (a -> a -> Bool) -> [a] -> [a]

So now I'm wondering if it would be worth maintaining this consistency with Haskell, and editing Array to use this convention:

nub :: forall a. Eq a => Array a -> Array a
nubBy :: forall a. (a -> a -> Boolean) -> Array a -> Array a
nubOrd :: forall a. Ord a => Array a -> Array a
nubByOrd :: forall a. (a -> a -> Ordering) -> Array a -> Array a

@hdgarrood
Copy link
Contributor

This is not a place where I would want to maintain consistency with Haskell, because using Eq for nub is widely considered to have been a mistake. In many cases there is an Ord instance available, and because the performance is so much better when you do use Ord, the default option we provide should be the one that uses Ord. See also discussion in purescript/purescript-arrays#91.

@hdgarrood
Copy link
Contributor

If we don’t already depend on arrays I think it would be better not to add the dependency - sometimes we need to rearrange things in core, and if we have too many things depending on each other unnecessarily that becomes much more difficult to do. However, I think a direct implementation that works on lists should be relatively straightforward, if it follows the general strategy of the Array version. Instead of appending to a mutable array, I think it should be possible to build up a list in reverse order and then reverse it at the end.

As for the behaviour, we should keep the first occurrence of any element, ie we should return a list where the elements are in the same order of the first occurrences of each of them in the input. So eg nub (1:3:2:3:1:Nil) should be (1:3:2:Nil).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
purs-0.14 A reminder to address this issue or merge this PR before we release PureScript v0.14.0
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants