úÎiÛg¤$      !"#portable experimentalleon@melding-monads.com%$%&The  predicate returns 'I if the elements of a list occur in non-descending order, equivalent to  ((). The  function returns ' iff the predicate returns true 1 for all adjacent pairs of elements in the list. The  function returns ' if the element appears in the  ordered list. The + function is the non-overloaded version of . The  function returns '% if the element appears in the list;  it is equivalent to 0 except the order of the arguments is reversed, K making it a function from an ordered list to its characteristic function. The + function is the non-overloaded version of . The : function inserts an element into a list. If the element B is already there, then another copy of the element is inserted. The  + function is the non-overloaded version of . The  3 function inserts an element into an ordered list. J If the element is already there, then the element replaces the existing  element. The  + function is the non-overloaded version of  . The  : function computes the intersection of two ordered lists. H An element occurs in the output as many times as the minimum number of I occurences in either input. If either input is a set, then the output  is a set. . isect [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 3,4 ] 1 isect [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1, 2,2 ] The  + function is the non-overloaded version of  . The 3 function computes the union of two ordered lists. E An element occurs in the output as many times as the maximum number D of occurences in either input. If both inputs are sets, then the  output is a set. 8 union [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2, 3,4, 5,6 ] 7 union [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1, 2,2,2 ] The + function is the non-overloaded version of . The 8 function computes the difference of two ordered lists. ? An element occurs in the output as many times as it occurs in G the first input, minus the number of occurrences in the second input. 9 If the first input is a set, then the output is a set. . minus [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2 ] , minus [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 2 ] The + function is the non-overloaded version of . The = function computes the exclusive union of two ordered lists. J An element occurs in the output as many times as the absolute difference B between the number of occurrences in the inputs. If both inputs & are sets, then the output is a set. 4 xunion [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2, 5,6 ] 2 xunion [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1, 2 ] The + function is the non-overloaded version of . The 6 function combines all elements of two ordered lists. A An element occurs in the output as many times as the sum of the  occurences in the lists. > merge [ 1,2, 3,4 ] [ 3,4, 5,6 ] == [ 1,2, 3,3,4,4, 5,6 ] > merge [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1,1,1,1, 2,2,2,2,2 ] The + function is the non-overloaded version of . The 7 function returns true if the first list is a sub-list  of the second. The + function is the non-overloaded version of . The 7 function provides the decorate-sort-undecorate idiom,  also known as the "Schwartzian transform". This variant of . recomputes the sorting key every comparison. = This can be better for functions that are cheap to compute. M This is definitely better for projections, as the decorate-sort-undecorate D saves nothing and adds two traversals of the list and extra memory  allocation. The  function is equivalent to  )  , except G somewhat more efficient as duplicates are removed as it sorts. It is > essentially Data.List.sort, a mergesort by Ian Lynagh, with   replaced by . The + function is the non-overloaded version of . The 0 function provides decorate-sort-undecorate for . This variant of & recomputes the for each comparison. On ordered lists,  is equivalent to  Data.List.nub, except that K it runs in linear time instead of quadratic. On unordered lists it also ? removes elements that are smaller than any preceding element.  nub [1,1,1,2,2] == [1,2]  nub [2,0,1,3,3] == [2,3]  nub = nubBy (<) The 1 function is the greedy algorithm that returns a ! sublist of its input such that:  ) isSortedBy pred (nubBy pred xs) == True EThis is true for all lists, not just ordered lists, and all binary J predicates, not just total orders. On infinite lists, this statement H is true in a certain mathematical sense, but not a computational one. The   function generalizes "*  []" to a I (possibly infinite) list of (possibly infinite) ordered lists. To make H this possible, it adds the assumption that the heads of the non-empty & lists themselves form a sorted list. +The implementation is based on the article "Implicit Heaps" by A Heinrich Apfelmus, which simplifies an algorithm by Dave Bayer.  8http://apfelmus.nfshost.com/articles/implicit-heaps.html MThe following definition is a simple and reasonably efficient implementation E that is faster for inputs whose smallest elements are highly biased  towards the first few lists:   mergeAll' = foldr merge' []  where merge' [] ys = ys - merge' (x:xs) ys = x : merge xs ys HThis definition uses a linear chain of comparisons whereas the provided L implementation uses a tree of comparisons, which is faster on a wide range  of inputs. !The !/ function is the non-overloaded variant of the   function. "The " function generalizes "*  []" to a @ (possibly infinite) list of (possibly infinite) ordered lists. F To make this possible, it adds the assumption that the heads of the 0 non-empty lists themselves form a sorted list. CThe library implementation is based on some of the same techniques  as used in  .. However, the analogous simple definition ( is not entirely satisfactory, because   unionAll' = foldr union' []  where union' [] ys = ys - union' (x:xs) ys = x : union xs ys  $ unionAll' [[1,2],[1,2]] == [1,1,2] "whereas we really want the result  A unionAll [[1,2],[1,2]] == foldr union [] [[1,2],[1,2]] == [1,2] GThe first equality is only true when both sets of assumptions are met:  " foldr union []"( assumes the outer list is finite, and " 7 assumes that the heads of the inner lists are sorted. #The #/ function is the non-overloaded variant of the " function. $  !"#$  !"#"  !"#+      !"#$%&'()*+,-./01023data-ordlist-0.4Data.List.Orderedbase Data.ListsortsortByisSorted isSortedBymembermemberByhashasBy insertBag insertBagBy insertSet insertSetByisectisectByunionunionByminusminusByxunionxunionBymergemergeBysubsetsubsetBysortOnsortOn'nubSort nubSortBy nubSortOn nubSortOn'nubnubBymergeAll mergeAllByunionAll unionAllByPeopleCrowdVIPghc-primGHC.BoolTrue GHC.Classes<=GHC.Base.foldr