[Haskell-cafe] version sorting?

[Javran Cheng]

Hi Cafe,

I'm wondering if there's any existing packages that do "version sorting":
as an example, for a list like:

["foo-10.20", "foo-1.2", "foo-2.100", "foo-1.12"]

I'd like the result to be:

["foo-1.2", "foo-1.12", "foo-2.100", "foo-10.20"]

I could think of an implementation that turns String elements of a list into
[Either Int String] by grouping consecutive chunks using span and isDigit
and then do a sortOn:

versionSort :: [String] -> [String]
versionSort = sortOn brkND
where
tr f g (x,y) = f x : g y
-- ND for non-digits
brkND = tr Right brkD . span (not . isDigit)
brkD = tr (Left . read @Int) brkND . span isDigit

(side question: does the helper function tr I defined above have a commonly
known name?)
just wondering if there are more sophisticated solutions available.

Best,
Javran

[Francesco Ariis]

Hello Jarvan,
https://hackage.haskell.org/package/natural-sort

λ> :m +Algorithms.NaturalSort
λ> :m +Data.List
λ> sortBy (Algorithms.NaturalSort.compare) ["foo-10.20", "foo-1.2", "foo-2.100", "foo-1.12"]
["foo-1.2","foo-1.12","foo-2.100","foo-10.20"]

[Iustin Pop]

Post by Francesco Ariis
Hello Jarvan,
https://hackage.haskell.org/package/natural-sort
λ> :m +Algorithms.NaturalSort
λ> :m +Data.List
λ> sortBy (Algorithms.NaturalSort.compare) ["foo-10.20", "foo-1.2", "foo-2.100", "foo-1.12"]
["foo-1.2","foo-1.12","foo-2.100","foo-10.20"]

Does it really sort 1.2 before 1.12? (or is it just a copy-paste error)

curious,
iustin

[Francesco Ariis]

Post by Iustin Pop
Does it really sort 1.2 before 1.12? (or is it just a copy-paste error)

It does, hence the name of the library!

[Iustin Pop]

Post by Francesco Ariis

Post by Iustin Pop
Does it really sort 1.2 before 1.12? (or is it just a copy-paste error)

It does, hence the name of the library!

Apologies - given the ".12", I implicitly translated ".2" as ".20". Just
a slow day :)

iustin

[Francesco Ariis]

Post by Iustin Pop
Apologies - given the ".12", I implicitly translated ".2" as ".20". Just
a slow day :)

No worries, I have bitten by "0.x/0.x0" more times than I am willing to
admit :P
-F

[Javran Cheng]

Thanks for the suggestion! natural-sort looks like what I want - I've just
taken a quick look and the algorithm is almost the same if I'm not mistaken.

also thanks MarLinn - it's just that as I wrote I realized I've been
implemented "tr" over and over again so there might be a common name for
it. I do recognize there's a (***) out there
and hoogling (a, [a]) -> [a] doesn't yield any function of interest.,
didn't bother to go any further to see the rest of it is just a curried (:).
I'd still prefer "tr" though as for me if you think it as a rewrite rule,
it's more readable than having a chain of function composition.

Cheers!

Post by Francesco Ariis

Post by Iustin Pop
Apologies - given the ".12", I implicitly translated ".2" as ".20". Just
a slow day :)

No worries, I have bitten by "0.x/0.x0" more times than I am willing to
admit :P
-F
_______________________________________________
Haskell-Cafe mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

[MarLinn]

Post by Javran Cheng
versionSort :: [String] -> [String]
versionSort = sortOn brkND
  where
    tr f g (x,y) = f x : g y
    -- ND for non-digits
    brkND = tr Right brkD . span (not . isDigit)
(side question: does the helper function tr I defined above have a
commonly known name?)

I don't think so, but that's just because you made the cut at a weird
point. It's very close to (***)
<https://hoogle.haskell.org/?hoogle=%28***%29&scope=set%3Astackage> from
Control.Arrow, Data.Tuple.Extra, Data.Profunctor, and other libraries,
also known as bimap
<https://hoogle.haskell.org/?hoogle=bimap&scope=set%3Astackage> in
Data.Bifunctor and in the lens package.

Rewriting your functions to tease it out even more (not tested):

versionSort :: [String] -> [String]
versionSort = sortOn gatherNonDigits
 where

 gatherAll predicate gather continue = uncurry (:) . (gather *** continue) . span predicate

 -- 'NonDigits' for non-digits
      gatherNonDigits = gatherAll (not . isDigit) wrapNonDigits gatherDigits
    gatherDigits  = gatherAll isDigit wrapDigits gatherNonDigits

 wrapNonDigits = Right
wrapDigits = Left . read @Int