[Haskell-cafe] Why no merge and listDiff?

[Derek Elkins]

On Sun, Jan 17, 2010 at 2:22 PM, Will Ness <will_n48 at yahoo.com> wrote:
> Hello cafe,
>
> I wonder, if we have List.insert and List.union, why no List.merge (:: Ord a =>
> [a] -> [a] -> [a]) and no List.minus ? These seem to be pretty general
> operations.

Presumably by List.minus you mean the (\\) function in Data.List.  You
probably also want to look at the package data-ordlist on hackage
(http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/Data-OrdList.html)
which represents sets and bags as ordered lists and has all of the
operations you mention.

> Brief look into haskell-prime-report/list.html reveals nothing.
>
> Could we please have them?

The trend is to remove things from "standard" libraries and to push
them more to 3rd party libraries hosted on hackage.

> On the wider perspective, is their a way to declare an /ordered/ list on the
> type level (e.g. [1,2,3] would be one, but not [2,3,1])? Non-decreasing lists?
> Cyclical, or of certain length? What are such types called?

There are a few ways to encode such things.  The most direct route is
to use dependent types as Miguel mentioned, but Haskell has no support
for those.  See languages like Agda or Coq.  Another approach is to
use a type that specifically represents what you want and nothing
else.  For example, a list of a set length is just a tuple.  It is
easy to make a type that represents cyclic lists.  Finally, the most
general method is to use an abstract data type to maintain the
invariant.  It is trivial to handle ordered/non-decreasing lists in
this way.  One note about the dependent types route is that the
ability to assert arbitrary properties comes with it the
responsibility to prove them later on.  So you can make a function
which only accepts ordered lists, but then the users need to pass in a
proof that their lists are ordered when they use such functions and
these proofs can be a significant burden.