📄 ord-map.mldoc

📁 这是我们参加06年全国开源软件的竞赛作品
💻 MLDOC
字号:
<!-- ord-map.mldoc --><!-- Entities.sgml entry <!ENTITY ORD-MAP SDATA "ord-map-sig.sml"> --><!DOCTYPE ML-DOC SYSTEM><COPYRIGHT OWNER="Bell Labs, Lucent Technologies" YEAR=1998><VERSION VERID="1.0" YEAR=1998 MONTH=6 DAY=10><TITLE>The ORD_MAP signature</TITLE><INTERFACE><HEAD>The <CD/ORD_MAP/ signature</HEAD><SEEALSO>  <SIGREF/ORD_SET/  <SIGREF/ORD_KEY/  <FCTREF/BinaryMapFn/  <FCTREF/SplayMapFn/  <FCTREF/ListMapFn/</SEEALSO><PP>The <SIGREF NOLINK/ORD_MAP/ signature provides an abstractdescription of applicative-style maps on a linearly ordered key type.<SIGNATURE SIGID="ORD_MAP">  <SIGBODY SIGID="ORD_MAP" FILE=ORD-MAP>    <SPEC>      <SUBSTRUCT>Key<ID>ORD_KEY</SUBSTRUCT>    <SPEC>      <TYPE><TYPARAM>'a<ID>map    <SPEC>      <VAL>empty<TY>'a map        <COMMENT>        <PP>        The empty map.    <SPEC>      <VAL>singleton<TY>(Key.ord_key * 'a) -> 'a map	<COMMENT>          <PROTOTY>          singleton (<ARG/k/, <ARG/a/)          <PROTO>	  returns the singleton map that maps the key <ARG/k/ to the	  value <ARG/a/.    <SPEC>      <VAL>insert<TY>('a map * Key.ord_key * 'a) -> 'a map      <VAL>insert'<TY>((Key.ord_key * 'a) * 'a map) -> 'a map        <COMMENT>          <PROTOTY>          insert (<ARG/ma/, <ARG/k/, <ARG/a/)          <PROTO>          insert' ((<ARG/k/, <ARG/a/), <ARG/ma/)          </PROTOTY>          creates a new map by inserting the key-value pair into <ARG/ma/.    <SPEC>      <VAL>inDomain<TY>('a map * Key.ord_key) -> bool        <COMMENT>          <PROTOTY>          inDomain (<ARG/ma/, <ARG/k/)          </PROTOTY>	  returns <CD/true/ if the key <ARG/k/ is in the domain of <ARG/ma/,	  otherwise it returns <CD/false/.    <SPEC>      <VAL>find<TY>('a map * Key.ord_key) -> 'a option        <COMMENT>          <PROTOTY>          find (<ARG/ma/, <ARG/k/)          </PROTOTY>          looks for an item in <ARG/ma/ keyed by <ARG/k/. It returns the          item if it finds it; otherwise, returns	  <CONREF STRID="Option" DOCUMENT=SML-BASIS-DOC/NONE/.    <SPEC>      <VAL>remove<TY>('a map * Key.ord_key) -> ('a map * 'a)      <RAISES><EXNREF STRID="LibBase"/NotFound/        <COMMENT>          <PROTOTY>          remove (<ARG/ma/, <ARG/k/)          </PROTOTY>          removes an item from <ARG/ma/ corresponding to the key <ARG/k/.          If found, the resulting map and item are returned. Raises          <EXNREF STRID="LibBase"/NotFound/ if no such item exists.    <SPEC>      <VAL>first<TY>'a map -> 'a option      <VAL>firsti<TY>'a map -> (Key.ord_key * 'a option)        <COMMENT>	  <PROTY>	    first <ARG/ma/	  </PROTY>	  returns the first element of the map <ARG/ma/ (as defined by	  the ordering on the keys).	  <PROTY>	    firsti <ARG/ma/	  </PROTY>	  returns the first element of the map <ARG/ma/ and its key.	  Both of these functions return	  <CONREF STRID="Option" DOCUMENT=SML-BASIS-DOC/NONE/ when called	  on the empty map.    <SPEC>      <VAL>numItems<TY>'a map -> int        <COMMENT>          <PROTOTY>          numItems <ARG/ma/          </PROTOTY>          returns the number of items in the map.    <SPEC>      <VAL>listItems<TY>'a map -> 'a list      <VAL>listItemsi<TY>'a map -> (Key.ord_key * 'a) list        <COMMENT>          <PROTOTY>          listItems <ARG/ma/          <PROTO>          listItemsi <ARG/ma/          </PROTOTY>          return a list of the items in the map, ordered by increasing          key. The second form also returns the key.    <SPEC>      <VAL>collate<TY>(('a * 'a) -> order) -> ('a map * 'a map) -> order        <COMMENT>          <PROTOTY>          collate <ARG/f/          </PROTOTY>          returns an ordering on maps, given an ordering on the maps'          range.    <SPEC>      <VAL>unionWith<TY>(('a * 'a) -> 'a) -> ('a map * 'a map) -> 'a map      <VAL>unionWithi<TY>((Key.ord_key * 'a * 'a) -> 'a) -> ('a map * 'a map) -> 'a map        <COMMENT>          <PROTOTY>          unionWith <ARG/f/ (<ARG/ma/, <ARG/ma2/)          <PROTO>          unionWithi <ARG/f/ (<ARG/ma/, <ARG/ma2/)          </PROTOTY>          returns a map that is the union of the maps <ARG/ma/ and <ARG/ma2/.          The first argument is used to define the map on elements that          are in the domain of both maps. In the second form, the function          takes the shared key as well as the two range values.    <SPEC>      <VAL>intersectWith<TY>(('a * 'b) -> 'c) -> ('a map * 'b map) -> 'c map      <VAL>intersectWithi<TY>((Key.ord_key * 'a * 'b) -> 'c) -> ('a map * 'b map) -> 'c map        <COMMENT>          <PROTOTY>          intersectWith <ARG/f/ (<ARG/ma/, <ARG/ma2/)          <PROTO>          intersectWithi <ARG/f/ (<ARG/ma/, <ARG/ma2/)          </PROTOTY>          returns a map defined on the intersection of the domains of          the maps <ARG/ma/ and <ARG/ma2/. The function <ARG/f/ is          used to define the range. Specifically, if <CD/(k,u)/ is in          <ARG/ma/ and <CD/(k,v)/ is in <ARG/ma2/, the new map contains          <CD/(k,f(u,v))/ (or <CD/(k,f(k,u,v))/, in the second case).    <SPEC>      <VAL>app<TY>('a -> unit) -> 'a map -> unit      <VAL>appi<TY>((Key.ord_key * 'a) -> unit) -> 'a map -> unit        <COMMENT>          <PROTOTY>          app <ARG/f/ <ARG/ma/          <PROTO>          appi <ARG/f/ <ARG/ma/          </PROTOTY>          applies the function <ARG/f/ to the items in the map in          increasing order of the key.           These are respectively equivalent to:          <CODE>          List.app <ARG/f/ (listItems <ARG/ma/)          List.app <ARG/f/ (listItemsi <ARG/ma/)          </CODE>    <SPEC>      <VAL>map<TY>('a -> 'b) -> 'a map -> 'b map      <VAL>mapi<TY>((Key.ord_key * 'a) -> 'b) -> 'a map -> 'b map        <COMMENT>          <PROTOTY>          map <ARG/f/ <ARG/ma/          <PROTO>          mapi <ARG/f/ <ARG/ma/          </PROTOTY>          creates a new map by applying the function <ARG/f/ to the          elements of the old map <ARG/ma/.          These are respectively equivalent to:          <CODE>          List.foldl (fn((k,v),m) => insert(m,k,f v)) empty (listItemsi ma)          List.foldl (fn((k,v),m) => insert(m,k,f(k,v))) empty (listItemsi ma)          </CODE>    <SPEC>      <VAL>foldl<TY>(('a * 'b) -> 'b) -> 'b -> 'a map -> 'b      <VAL>foldli<TY>((Key.ord_key * 'a * 'b) -> 'b) -> 'b -> 'a map -> 'b        <COMMENT>          <PROTOTY>          foldl <ARG/f/ <ARG/a/ <ARG/ma/          <PROTO>          foldli <ARG/f/ <ARG/a/ <ARG/ma/          </PROTOTY>          applies the folding function <ARG/f/ to the entries of <ARG/ma/          in increasing order. These are respectively equivalent to:          <CODE>          List.foldl f a (listItems ma)          List.foldl (fn((k,v),b) => f(k,v,b)) a (listItemsi ma)          </CODE>    <SPEC>      <VAL>foldr<TY>(('a * 'b) -> 'b) -> 'b -> 'a map -> 'b      <VAL>foldri<TY>((Key.ord_key * 'a * 'b) -> 'b) -> 'b -> 'a map -> 'b        <COMMENT>          <PROTOTY>          foldr <ARG/f/ <ARG/a/ <ARG/ma/          <PROTO>          foldri <ARG/f/ <ARG/a/ <ARG/ma/          </PROTOTY>          applies the folding function <ARG/f/ to the entries of <ARG/ma/          in decreasing order. These are respectively equivalent to:          <CODE>          List.foldr f a (listItems ma)          List.foldr (fn((k,v),b) => f(k,v,b)) a (listItemsi ma)          </CODE>    <SPEC>      <VAL>filter<TY>('a -> bool) -> 'a map -> 'a map      <VAL>filteri<TY>((Key.ord_key * 'a) -> bool) -> 'a map -> 'a map        <COMMENT>          <PROTOTY>          filter <ARG/f/ <ARG/ma/          <PROTO>          filteri <ARG/f/ <ARG/ma/          </PROTOTY>          creates a new map containing only those elements of <ARG/ma/          that satisfy the predicate <ARG/f/.           These are equivalent to:          <CODE>          List.foldl insert' empty (List.filter (fn(k,v) => f v) (listItemsi ma))          List.foldl insert' empty (List.filter f (listItemsi ma))          </CODE>    <SPEC>      <VAL>mapPartial<TY>('a -> 'b option) -> 'a map -> 'b map      <VAL>mapPartiali<TY>((Key.ord_key * 'a) -> 'b option) -> 'a map -> 'b map        <COMMENT>          <PROTOTY>          mapPartial <ARG/f/ <ARG/ma/          <PROTO>          mapPartiali <ARG/f/ <ARG/ma/          </PROTOTY>          creates a new map by applying the partial function <ARG/f/ to the          map <ARG/ma/ in increasing key order.          The function <CD/mapPartiali/ can be implemented as:          <CODE>          fun mapPartiali f ma = let                fun f' (key,value) = case f (key,value)                   of NONE => NONE                    | SOME v => SOME(key,v)                val items = List.mapPartial f' (listItemsi ma)                in                  List.foldl insert' empty items                end          </CODE>          The function <CD/mapPartial/ is equivalent to:          <CODE>          fun mapPartial f ma = mapPartiali (fn (_, item) => f item) ma          </CODE>          <SIGINSTANCE OPAQUE> <ID> IntBinaryMap   <WHERETYPE><ID>Key.ord_key<TY>Int.int   <COMMENT>   <PP>This structure is based on Stephen Adams' integer set code, which usesbinary trees of bounded balance. It can be viewed as an application ofthe functor <FCTREF/BinaryMapFn/ using <CD/ord_key = Int.int/ and<CD/compare = Int.compare/.>/SIGINSTANCE>  <SIGINSTANCE OPAQUE> <ID> IntListMap   <WHERETYPE><ID>Key.ord_key<TY>Int.int   <COMMENT>   <PP>This structure implements integer maps using sorted lists.It can be viewed as an application ofthe functor <FCTREF/ListMapFn/ using <CD/ord_key = Int.int/ and<CD/compare = Int.compare/.>/SIGINSTANCE></SIGNATURE></INTERFACE>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -