Sanctuary: Add S.sort and S.sortBy

Created on 23 Feb 2017 · 7Comments · Source: sanctuary-js/sanctuary

Add Sanctuary version of R.sort and R.sortBy.

good first contribution

Source

svozza

Most helpful comment

I think we should borrow heavily from Haskell here.

__sortBy__ :: (a -> a -> Ordering) -> [a] -> [a]

The [sortBy][] function is the non-overloaded version of [sort][].

__sort__ :: Ord a => [a] -> [a]

The [sort][] function implements a stable sorting algorithm. It is a special case of [sortBy][], which allows the programmer to supply their own comparison function.

Let's start with sortBy, which doesn't require a type class. We'll need to define Ordering via sanctuary-def. It will look something like this:

//# Ordering :: Type
var Ordering = $.EnumType(
  'sanctuary/Ordering',
  readmeUrl('Ordering'),
  ['LT', 'EQ', 'GT']
);

davidchambers on 23 Mar 2017

❤1 👍1

All 7 comments

I think we should borrow heavily from Haskell here.

__sortBy__ :: (a -> a -> Ordering) -> [a] -> [a]

The [sortBy][] function is the non-overloaded version of [sort][].

__sort__ :: Ord a => [a] -> [a]

The [sort][] function implements a stable sorting algorithm. It is a special case of [sortBy][], which allows the programmer to supply their own comparison function.

Let's start with sortBy, which doesn't require a type class. We'll need to define Ordering via sanctuary-def. It will look something like this:

//# Ordering :: Type
var Ordering = $.EnumType(
  'sanctuary/Ordering',
  readmeUrl('Ordering'),
  ['LT', 'EQ', 'GT']
);

davidchambers on 23 Mar 2017

❤1 👍1

@davidchambers thank you! I will make progress between today and tomorrow.

sadasant on 23 Mar 2017

👍1

@davidchambers

So, what about def('sortBy', {f: [Z.Applicative, Z.Foldable, Z.Monoid]}, [Fn(a, Fn(a, Ordering)), f(a), f(a)], sortBy); ?

Then we could use something like this: sortBy cmp = foldr (insertBy cmp) [], or should we rather implement the better/harder merge sort that's over here? http://hackage.haskell.org/package/base-4.9.1.0/docs/src/Data.OldList.html#sortBy

Little question: Do we have foldr in sanctuary-js?

sadasant on 24 Mar 2017

sortBy for review: https://github.com/sanctuary-js/sanctuary/pull/365

sadasant on 24 Mar 2017

Let's wait to see what happens with fantasyland/fantasy-land#235, as it will determine the direction we should take with sort and sortBy. Thank you for your work on this, @gabejohnson!

davidchambers on 28 Mar 2017

👍1

Happy to be of service! I'd hate to let an opportunity to generalize pass us by.