úÎl-j$      !"#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 J occurrences 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 E of occurrences 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  occurrences 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, with  replaced by . The + function is the non-overloaded version of . The 0 function provides decorate-sort-undecorate for . This variant of 1 recomputes the sorting key 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 ' plus zero computes the sum of a list ' using a balanced tree of operations. ' necessarily diverges 6 on infinite lists, hence it is a stricter variant of (.  '" is used in the implementation of  and . ( The function ( plus zero" computes the sum of a list using D a sequence of balanced trees of operations. Given an appropriate plus J operator, this function can be productive on an infinite list, hence it  is lazier than '. (" is used in the implementation of    and ". The  4 function merges a (potentially) infinite number of G ordered lists, under the assumption that the heads of the inner lists F are sorted. An element is duplicated in the result as many times as 5 the total number of occurrences in all inner lists. The   function is closely related to )  []. C The former does not assume that the outer list is finite, whereas D the latter makes no assumption about the heads of the inner lists. A When both sets of assumptions are met, these two functions are  equivalent. This implementation of  % uses a tree of comparisons, and is K based on input from Dave Bayer, Heinrich Apfelmus, Omar Antolin Camarena,  and Will Ness. !The !/ function is the non-overloaded variant of the   function. "The "7 computes the union of a (potentially) infinite number C of lists, under the assumption that the heads of the inner lists D are sorted. The result will duplicate an element as many times as I the maximum number of occurrences in any single list. Thus, the result 4 is a set if and only if every inner list is a set.  Analogous to  , " is closely related to  )  []1; The outer does not assume that the outer list G is finite, whereas the right fold does not assume anything about the G heads of the inner lists. When both sets of assumptions are met, the  functions are equivalent. @This implementation is also based on implicit heaps, providing  a tree of comparisons. #The #/ function is the non-overloaded variant of the " function. $  !"#$  !"#"  !"#*      !"#$%&'()*+,-./0-12data-ordlist-0.4.4Data.List.Orderedbase Data.ListsortBysortisSorted isSortedBymembermemberByhashasBy insertBag insertBagBy insertSet insertSetByisectisectByunionunionByminusminusByxunionxunionBymergemergeBysubsetsubsetBysortOnsortOn'nubSort nubSortBy nubSortOn nubSortOn'nubnubBymergeAll mergeAllByunionAll unionAllByghc-prim GHC.TypesTrue GHC.Classes<=GHC.Base. foldTree'foldTreefoldr