HOOG2"!';;AACC:<>\_a !!))+.259;GGIJLMVcknppzzb IN^_ddhhnnpp||c -.25DFWX\\``nnqqss}~d   (+/055:=UUggjje (+.014488:FHKNSUUX_ahjjllnprx||f&8:;INg  9<RRjjww}~h''++00347;?CEFRRXZ]]__aaccfflnuvi &+0028<NUUXZ\]_cefklv|jk''004488??BCFFOQTUXXZ]__aaccffll{{l !"$$&'+028??RUiinnppwwy~m!%)*28:;GGIJLMVfhh|~n (.55<HRRUU\\``eiklssww}~o /8:;??DFINTU\\``ghjlppuw{{}p #%9;??GGIMTakmy~qrsr %'1<>FIKYZddhhjlnpuv|s  ""-.18:;>FHNPQSS[]ooqt !!#'+.08>HKKNNQRXZ\]_accffhhjmpptwyu  ++??INTUWXijss{{vSSbcefoow''++003478?CEFXXZZ]]__aceflluvx()==UUbcy#%''004488??BCFFJJMMOQXXZ_aaccffll}~zxx|N҅w+)E$U Y s().$->#All#Any# BlockReason#Bool#CCharF#CClock#CDev"CDouble"CFloat0"CIno!CInt!CIntMaxX!CIntPtr!CLDouble CLLongo CLong' CModeCOffCPidOCPtrdiffCSCharCShortw CSigAtomic/CSizeCSsizeCTimemCUChar%CUIntCUIntMaxCUIntPtrMCULLongCULongCUShortuCWchar-Chan"CharComplex ConsoleEventConstr ConstrRepDataRepDataTypeDigityDocsDoubleLDynamic3E12$E6Either ElemErrno ExceptionFd FingerTreefFixity]Float6GeneralCategoryHandleHashDataIOIOUArrayfIdQInsertsMIntInt16Int32Int64Int8IntMapfIntPtrIntSetIntegerLexemeMapMaybe|NestedAtomicallyc NoMethodErrorJNode,NonTerminationOrderingPPatternMatchFailQSemQSemNReadPReadPrec RecConErrorz RecSelErrora RecUpdErrorHSTM/SeqSet StableNameTVarThreadId ThreadStatusTimeoutTreeOTyConITypeRepCUnique;Version ViewLViewRWordWord16Word32[Word644Word8 WordPtrZipList[::][]` TraversableFoldable Applicative AlternativeMonadFix MonadPlusFunctorMonadFunctor Applicative ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEqIArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorable Typeable1FunctorFoldable Traversable Typeable1FunctorFoldable TraversableEqOrdShowReadTypeableOrdEqDataData Typeable1Functor ApplicativeMonad TraversableFoldableTypeableShow ExceptionEqShowOrdEqShowEqOrdTypeableData Typeable1 Typeable1Foldable Typeable1FunctorFoldable TraversableMonad MonadPlus Typeable1 Typeable1FunctorMonadTypeableShow ExceptionTypeableShow ExceptionTypeableShow ExceptionFunctorMonad MonadPlusFunctorMonad MonadPlusTypeableTypeableTypeableShow ExceptionMonad MonadPlusMonoidDataIxTypeableShow ExceptionFoldableFunctor TraversableTypeableShow ExceptionTypeableShow Exception TraversableFoldable Applicative AlternativeMonadFix MonadPlusFunctorMonad Typeable2ShowEq PrintfArgDataBitsIxMonoidDataEqOrdShowReadTypeable ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEqFoldableFunctor Typeable1IArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorableIArrayMArray PrintfArgDataStorableBitsIxEqFunctor Applicative Typeable2MArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArrayMArray ApplicativeMonadFixShowEqDataIxBoundedShowReadEnumOrdEqIArrayMArray PrintfArgDataStorableShowEqFoldableFunctor Traversable ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEqTypeable ExceptionShowEqEqFunctorFoldable Traversable Typeable2 HasResolution HasResolution ExceptionTypeableShowIArrayMArray PrintfArgDataStorableShowFoldableFunctor TraversableShowTypeableDataShowEqShowEqShowEqReadShowEnumOrdEqTypeable Typeable1IArrayMArray PrintfArgIsCharDataStorableIx Typeable1 ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeable RealFloatRealFracFloating FractionalRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEq ReadShowTypeable RealFloatRealFracFloating FractionalRealStorableEnumNumOrdEq ReadShowTypeable RealFloatRealFracFloating FractionalRealStorableEnumNumOrdEq ReadShowTypeableRealStorableEnumNumOrdEq ReadShowTypeableRealStorableEnumNumOrdEq ReadShowTypeableBitsIntegralBoundedRealStorableEnumNumOrdEqIArrayMArrayDataStorableIxShowOrdEqMonoidBoundedShowReadOrdEqMonoidBoundedShowReadOrdEqArrow ArrowChoice ArrowApply ArrowLoopCategoryMonoidDataEqOrdIxI$+Bounds) ByteCount)CString) CStringLen(CWString( CWStringLen( ClockTick(ConIndex(DeviceID( DiffArray( DiffUArrayn(Edge\( EpochTimeT(FileIDM(FileModeE( FileOffset>(FilePath1(FinalizerEnvPtr' FinalizerPtr'Forest'Generic'GenericB'GenericM'GenericQ'GenericR'GenericT'Graphj'IOError\'IPrJ'KeyD'Limit<'Micro.'Pico'Prec'ProcessGroupID' ProcessID 'Rational&ReadS& SampleVar&ShowS&String&Tablem&Vertexg&IntaArrayInta[]Char[]Char[]CharaMVar(,)IntMVaraa[]Char[](,)a[]CharRatioIntegerCPidCPidIntFixedE12FixedE6CLongInt(,)IntInt IOExceptionArrayInt[]Intaammararmamaacacaa[]TreeaaFunPtrPtraIO()envaFunPtrPtrenvPtraIO()[]CharCOffCModeCInoCTime(,)IntInt IOToDiffArrayIOUArray IOToDiffArrayIOArrayCDevIntCClock(,)PtrCWcharIntPtrCWchar(,)PtrCCharIntPtrCCharCSize(,)IntInt(v[vapblcbd^e[fVgUhCSiMjMkPMlJmVGnlDoiAp=q~=r{9sr3t.u,vV,w**z)i)g)p)l)i)s)t)ZipListz)a)g*m *o*d*e *Mode#L,e0,ot+r@*a*iL*tS*eZ*ma*oh*do*ev*IOModep*aF+m+p*e*d*a*m*o*n*a*d* WrappedMonadr*r*o*w+ WrappedArrowo+n&+a-+d4+ WrappedMonadrM+rT+o[+wb+ WrappedArrowr{+d+Word#!,1 ,3+6+8+p+t+r+WordPtrWord84+Word642+Word326,Word16Word#a7,k>,WeakWorde,ib,ei,wp,l,r|,ViewRViewLr,s,t,e,x,Vertexi,o,n,Versiona.n-ph-s-e-r-i-n#-t*-e1-r8-r?-uF-pM-tT-AsyncExceptionpo-ev-r}-c-a-s-e-l-e-t-t-e-r-GeneralCategoryd .i-q-u-e-Uniquee.fL.r.f#.l*.o1.w8.ArithExceptioniS.nZ.ea.dh.eo.lv.e}.m.e.n.t.ArrayExceptionr.r.a.y.UArrayaN3e2h61i0rX0v(0y.c 0p /e/a5STRepSTRefrc5aj5bq5lx5e5Storablea5r5r5a5y5 StorableArraySTMb6c06r 6t5e5#5State#r6a6y6STArrayk76o>6vE6eL6rS6fZ6la6oh6wo6AsyncExceptionl6e6n6p6t6r6 StablePtra6m6e6 StableNamea6c6e7i7n7g7c7o7m$7b+7i27n97i@7nG7gN7mU7a\7rc7kj7GeneralCategoryGeneralCategorym7e7e7x7c7e7p7t7i7o7n7 SomeExceptionz7e8d 8Sizedo]8u(8t/8d68o=8wD8nK8 ConsoleEventwd8Showsw8ShowSe8q8t8SetSeqk8f8m8o8d8e8SeekModer8o8m9e9n9d9SeekModec*9SCCm>9pE9lL9eS9vZ9aa9rh9 SampleVara+=e9i9g9h9t9Eithera;c:l:q:t9u9r9n9i9n9o9r9d:e:r:ArgOrderan:u(:i/:r6:e=:oD:rK:dR:eY:r`:ArgOrderru:g|:ArgDescra:t:i:v:e:s:e:e:k:SeekModect;s.;u:p:d:e:r;r ;o;r; RecUpdErrore5;l<;eC;rJ;rQ;oX;r_; RecSelErroro{;n;e;r;r;o;r; RecConErrorda<l;Realf <w;o;r;l;d; RealWorldl9<r<a <c'<RealFraco@<aG<tN< RealFloatReadm =p<s<w<r<i<t<e<m<o<d<e<IOModeReadSReadPr<e<c<ReadPreco=d=e=IOModet2=LexemeiC=oJ=Ration^=ae=ll=Rationals=e=m=QSemn=QSemNa8@e@i?o?r,>s >t=u=n=c=Lexemer>Ptrt>r> TextDetailse?i>o=>co>dI>uP>cW>t^>Productev>s}>s>g>i>d> ProcessIDr>o>u>p>i>d>ProcessGroupIDn7?v>a>t?e ?u?s?e"?GeneralCategoryt>?fE?az?tQ?yX?p_?ef? PrintfTyper?g? PrintfArgc?f?i?x?FixityPreco?l?Poolc?o?Picor@m@u@t#@e*@ArgOrdergOIORefoTOd[OebOIOModerOx~OcOeOpOtOiOoOnO IOExceptionrOoOrOIOErrortOyOpOeP IOErrorTyper Pr'Pa.Py5PIOArrayd^RfDRiQt\PInt #Q1Q3Q6Q8Qc`QeQmPpPrPsPePtPIntSetePpPDataReptPrPIntPtraPpQIntMapgQeHQr(Qa/Ql6QIntegralrOQIntegerogQnnQsuQt|QrQ ConstrRepInt84QInt642QInt326QInt16Int#tQiQaRl RqRuRo!Rt(Re/RGeneralCategoryiKRxRRFixityeeRxlRosRuzRtRoRfRbRoRuRnRdRsRArrayExceptionnRoRrReRHandlereRnSt SLexemerSr%Sa,Sy3SIArrayaTeSpTSr[SibSniStpSfwSt~SySpSeS HPrintfTypeaSpSoSvSeSrSfSlSoSwSAsyncExceptionnTsThpTrTe!Ts(To/Tl6Tu=TtDTiKToRTnYT HasResolutiontwTa~TbTlTeT HashTabledTlTeTHandlepTrTHandleroTsTnT HandlePosne{UmlUq]Ur9Ut*U GenericT'a@UpGUhNUGraph GenericQ' GenericM'nUeUrUaViUcUGeneric'tVbbVm8VqVrUtUGenericT'U GenericT'GenericRGenericQ'%V GenericQ'GenericM'OV GenericM'GenericBGeneric'lVcVaVtVeVgVoVrVyVGeneralCategoryd[i YlkXoWrUWuVnWc/WpWtWrWFunPtrt6Wo=WrDWFunctora\WccWtjWiqWoxWnWaWlW Fractionall6XrWeWmWaWtWGeneralCategoryiWsWtWForestgXn XpXtXr"X ForeignPtrd=XaDXbKXlRXeYXFoldableorXayXtXFloatcXiXrXeXpXDataRepnXgXFloatingoXnXsXtXrX ConstrReplJZn~YraYx!YeKYi-Yt4Yy;YFixitydRYFixedshYtoYFirstaYlYiYqYuYoYtYeYGeneralCategoryzYeYrYeZpYtYrY FinalizerPtrnZvZp#Zt*Zr1ZFinalizerEnvPtreQZiZmZoZpgZanZtuZh|ZFilePathfZfZsZeZtZ FileOffsetoZdZeZFileModedZFileIDFd 1}^6q^dU^i)^m]n\]oI]p]q\r\xH[cO\iT[t[[c(\e[f[sq[ux[c[c[e[s[s[ExitCodea[i[l[u[r[e[ExitCodex[c[e[p[t\i \o\n\ Exceptiono/\d6\e=\ExitCodeeV\p]\td\ik\or\ny\ Exception Exceptionr\n\o\r\c\a\l\l\ ErrorCallo\ErrnoEqo ]c]h]t!]i(]m/]e6] EpochTimefP]Lexemec]d]um]mt]Enumo]Endol]o]s]i]n]g]m]a]r]k]GeneralCategoryp]t^y^l^r^ViewRViewLt0^h7^e>^rE^Eitherg\^ec^EdgeE62^E12aae}`i_oM_u1_y^n^a _e^x^c^e^p^t^i^o^n^ Exceptionm_i_c _Dynamica8_l?_Dualc_us_w^_ne_Downbz_l_e_DoubleDocf`v_i_d_e_b_y_z_e_r_o_ArithExceptionf `aN`u`a`r%`r,`a3`y:` DiffUArrayrU`r\`ac`yj` DiffArrayaac-afan`v`i`c`e`i`d`DeviceIDo`r`m`a`l`ArithExceptiona aualat aHandleri4am;aaBalIanPauWam^abeaelarsaGeneralCategorydalaoacakaDeadlocks.btaaaDatarbtayapaeaDataTypeebpbDataReph5bpkhjijjNjl imhofpfs[et7eucw#cybcblbibccs cccccSCCccs/ct6cr=ciDcnKcgRcCWStringlicepcnwc CWStringLenhcacrcCWcharceidl[drcschcocrctcCUShortrdedndcdyds#dy*dm1db8do?dlFdGeneralCategoryldogdnndgudCULongodndgdCULLongndtdCUIntmdpdtdrdCUIntPtradxeCUIntMaxhea er'eCUChari>emEeeLeCTimectfhOfiesetver}eienegeCStringleeene CStringLeniezeeeCSsizegfzeefCSizeaftfo&fm-fi4fc;f CSigAtomicoVfr]ftdfCShorth{fafrfCSChariftfrfdfifffffCPtrdiffdfCPidfhmhngiyhngsWgtgrgo$gl+gGeneralCategorycEg ConsoleEventogtcgConstrwgConstrrgegpg ConstrReplgegegvgegngtg ConsoleEventegcht hohrhphu%hn,hc3ht:huAhaHhtOhiVho]hndhGeneralCategorynhdhehxhConIndexphlhehxhComplexfhCOffohdhehCModedjlioicinis/ie6i ConsoleEventpMiuTin[icbitiiupiawit~iiioiniGeneralCategorygiCLongkitiiiciki ClockTickoinjg jCLLongo ju'jb.jl5jenipoJnnQnbodoe?ofnmnonsvnt}nmn BlockReasontnhnenrn BlockReasonvnanrn BlockReasononrneniog onocoa ol'ol.o BlockReasonxFocMoeTop[otboiiooponwo BlockReasoneoaodomovoaoroBlockedOnDeadMVarloaocokohooolpe p BlockReasonn$pd+pe2pf9pi@pnGpiNptUpe\plcpyjpBlockedIndefinitelyupfpfpeprpipnpgp BufferModetpspBitsbmvc,vdvlDun0uptrqsqsqy!qn(qc/qe6qx=qcDqeKqpRqtYqi`qogqnnqAsyncExceptioneqrqtqiqoqnqfqaqiqlqeqdqAssertionFailedg9tisrraTsorwrArrowa$scrlrmrplrzDreKrrRroYr ArrowZerolsruzrsr ArrowPlusornrardr ArrowMonadororpr ArrowLoophroriscses ArrowChoicep+sp2sl9sy@s ArrowApplyy[sArray#setsx{scsespstsisosnsArrayExceptionArray#tshsesxscsesptt titotn!tArithExceptiondstoEtrLtdSteZtratArgOrdereztstctrtArgDescrptetltitctatttitvtet Applicativenudumuoudue$uIOModey7uAnygulutUue\urcunjuaqutxuiuvueu AlternativeAllcurueupuDataRepounusuturu ConstrRepdvrv#vAddr#y3vc:vlAviHvcOvsVvc]vcdvSCCstvo{vlvuvtvevsvevevkvSeekMode:v]v[]:v]v[::])v() wh; R+K&b}||zzxBool{xogDC@7/.%IntyE80IntSet |zplZYaKF91 bIntSetBoolIntSet(,,)nIntIntArray IntSetInt(,)tIntSetIntSet(,)mak(,)h"akMap!iUONM&$#ak2MapbkMapckMapckMapa(,)Int[]IntArrayaIntMapa(,)aSeta(,)<cIntMapa(,)Char[] vba`XGA+IntMaybeInt[]w aIntMaprqeTLaMaybefaSeq ~}sk[:43aSet ^]\W?>aTreeaViewL5aViewR;6a[]VJB,bIntMapbSetkSet)k[]-vertexSCC_vertex[]2akMapak(,)(,)!akMapakMap(,)ckMapbkMap(,) akMapaMaybeakMap(,,)IntInt(,)[] IntSetInt(,)MaybeuaInt(,)[]ak(,)[]*akMapa(,)Maybe(IntMaybekeykey[]keynode(,,)IntInt[]IntArray(,,)Q key[]keynode(,,)IntInt[]IntArray(,)PaIntMapa(,)MaybeaSeta(,)Maybe=aSetBoolaSet(,,)akMapaMaybe(,)aIntMapaMaybeaIntMap(,,)daIntMapaIntMap(,)caIntMapaMaybe(,)aSeqaSeq(,)jaSetaSet(,)cIntMapbIntMap(,)VertexTree[] aTree[]HaTreema[][]InodeSCC[]Skey[]keynode(,,)SCC[]RakMapak(,)(,)Maybe'aIntMapaInt(,)(,)MaybeVertex[]Tree[] aTree[]mօ}qI݋ڊAŇaaaIntaaakabaIntbbaIntbbakcbakca(,)bIntaca(,)bkaaMaybebaIntaMaybebak BoolaIntBoolakBoolbaaaIntaaa aakababaIntbakbbIntbbacbaca(,)bacbEitheraIntcbEitherakChar[]akaMaybeaIntaMaybeakaMaybebabMaybeaIntbMaybeakBoolIntBoolaIntIntaabak2k1cbEitherab[]a(,)baMaybeabMaybeab[]a(,)mbaMaybeaMaybeBoolbbaa``Int"srqponmlkjihgfedc9IntSet||{{zyxwvutponmba~}srq;:bk1vertexIntInt(,)akMap@ih10/.-,+*)('&%%$$#"!ak1MapbkMap&Int[]IntArray   Int[]YIntSet[]ZaIntMap:rgfedc` aSeq~skj;:98765443aSetaFEDCBA@@??>=<aTreeKJIHa[]^]\[bIntMapb[]vertexSCC2vertex[]_key[]keynode(,,)[]SRQPIntInt(,)[]aInt(,)[]Lak(,)[]ONMakMap[]UChar[]TreeGStringTree[]XaIntMap[]TaSCC[]VaSet[]WaTree[]~sh]@/ƪs[L=2 ҩzo`QB3"Ѩƨ}raVE:/$קȧx_LA0%ܦѦnN;( ץĥw^E3$٤ΤäufWL=. ܣͣyhS>, ٢Ȣuj_NC8-ӡqbSD5*ߠԠàziZK<1 Пş~sh]F;0%ڞϞĞmVE6+ ՝ĝp[P?4#Ordk2Ordkj?OrdkOrdkOrdkOrdksEqk/OrdkOrdkVOrdkOrdkStringOrdk?Ordk5Ordk39=Ordk !MonadmMonadmForestForestOrdkhgeOrdk=Ordk<OrdaOrdbOrdk2OrdkKey+Ordk*~OrdkqEqkp}Key-Ordk,OrdkKey6:KeyTOrdaOrdaSOrdkOrdkQOrdk1Ordk0Key7;OrdkfiKeyKey>KeyKeyKeyKeyrKey.KeyKey8<KeyUKeyKeyKey>Key4KeyKeyROrdkOrdkWOrdkOrdkOrdkOrdk#Ordk OrdkOrdkaOrdk`KeyForestOrda$Orda OrdaOrda  9#/3Y]GString'+2KeyKey" B%EKeyKey!KeyKeyKeyStringShowaStringShowaString |OrdaoEqaw{'muy@ForestString)Ordad(Ordk& Ordkey OrdkeyOrdkeyGraphVertexOrdkeyGraphVertexzOrdknEqkvltxKeybForestAString[_AOrdaIShowaStringOrda;%Orda15)- HGE c Ordk@OrdkHShowaShowkString:OrdkEqaOrdk$Ordk04Z^(,X\KeyFKeyShowaStringKeyKey8Eqa".2&*GraphVertexGraphVertex7ForestGraphVertexCGraphVertex6ForestGraphForestGraphDEdgeGraphGraphTableGraphBoundsEdgeGraphKPONMLJzjZ>t\<Z0X8޿ƿ~fN*hN. ƽR^DֻfB κn8йlH ҸhFͷ{a5Ŷ}W+wS5 ۴ǴqVD(lJ0 lVBڱ~X, °|X6үzJ(ή_>.|>5|>HviewrHViewRFviewrGviewliViewLDviewlEverticesverticesCvertexVertexBvalidvalid@A updatewithkey updateWithKey>?updateminwithkey updateMinWithKey<= updatemin6 updateMin:;updatemaxwithkey_updateMaxWithKey89 updatemax updateMax67updatelookupwithkeyupdateLookupWithKey45updateat߯updateAt3updateupdate012 unionwithkey unionWithKey./ unionwithD unionWith,- unionswithg unionsWith*+unionsunions&'()unionunion"#$%unfoldtreem_bfհunfoldTreeM_BF! unfoldtreem unfoldTreeM  unfoldtree unfoldTreeunfoldforestm_bfAunfoldForestM_BF unfoldforestmj unfoldForestM unfoldforest unfoldForesttreeTree transposegɱ transposeGtopsorttopSorttolisttoList toasclist& toAscListtakeKtaketable`Table subforestz subForeststronglyconncomprstronglyConnCompR stronglyconncompͲstronglyConnComp  splitmember splitMember   splitlookup splitLookup splitat<splitAtsplitTsplitsizeusize singleton singleton showtreewith˳ showTreeWithshowtreeshowTreesetSetsequence5SequenceseqLSeqscc^SCCscc rootlabel rootLabelreversereverse reachable reachablepathдpathpartitionwithkeypartitionWithKey partition partition outdegreeC outdegreenull\null notmember notMembernodeNodeminviewwithkeyȵminViewWithKeyminviewminViewmembermembermaxviewwithkey>maxViewWithKeymaxviewcmaxView mapwithkey mapWithKey mapmonotonic mapMonotonicmapmaybewithkeyٶmapMaybeWithKeymapmaybemapMaybe mapkeyswith# mapKeysWithmapkeysmonotonicJmapKeysMonotonicmapkeysmmapKeysmapeitherwithkeymapEitherWithKey mapeither mapEithermapaccumwithkeymapAccumWithKeymapaccummapAccummap#Mapmap lookupindexV lookupIndexlookupslookuplevelslevelslengthlengthkeyssetkeysSetkeys۸keyskeyKey issubsetof  isSubsetOf issubmapofby1 isSubmapOfBy issubmapofW isSubmapOfispropersubsetofisProperSubsetOfispropersubmapofbyisProperSubmapOfByispropersubmapofisProperSubmapOfintset IntSetintmap'IntMapintersectionwithkeyPintersectionWithKeyintersectionwithintersectionWith intersection intersectioninsertwithkey'insertWithKey' insertwithkey insertWithKey insertwith'0 insertWith' insertwithQ insertWithinsertlookupwithkey~insertLookupWithKeyinsertinsertindexʻindexindegreeindegreegraphfromedges'graphFromEdges'graphfromedges/graphFromEdgesgraphNGraphfromlistwithkeyrfromListWithKey fromlistwith fromListWith}~fromlistfromListxyz{|fromdistinctasclistfromDistinctAscListtuvwfromasclistwithkey5fromAscListWithKeyrsfromasclistwithffromAscListWithpq fromasclist fromAscListlmnoforestForestk foldwithkeyֽ foldWithKeyijfoldfoldefgh flattensccs flattenSCCsd flattenscc= flattenSCCcflattenZflattenbfindwithdefault|findWithDefault`afindminfindMin\]^_findmaxȾfindMaxXYZ[ findindex findIndexW filterwithkey filterWithKeyUVfilter5filterQRSTemptyrYEmptyRPemptylqEmptyLOemptyemptyJKLMNelemselemsFGHIelematѿelemAtEedgesedgesDedgeEdgeCdropdropBdrawtree)drawTreeA drawforestG drawForest@differencewithkeyndifferenceWithKey>?differencewithdifferenceWith<= difference difference89:;dfsdfs7dffdff6 deletemin deleteMin2345 deletemax> deleteMax./01 deletefindminl deleteFindMin*+,- deletefindmax deleteFindMax&'()deleteatdeleteAt%deletedelete!"#$ cyclicscc  CyclicSCC containers+ containers componentsK componentsbuildggbuildGboundsBoundsbccbccassocsassocsalteralter adjustwithkey adjustWithKeyadjust adjust acyclicscc- AcyclicSCC\\E\\>< <|q<| :>:> :<:< !! H,Ėԉȅd"Ղ7K~}M}|zgxLwurpmlrkj%jihg*fRecb`_^M]]\[ZXXvWVUUTSR'R?QPN"NKL0KgIFC? ?x>=<4<:987q76~655+5442820/.--*H*)p('d'&%%?#h! =  mm.I V Z9,p!a2$Zp q_g>t޶ҴCwzH`}mlQh=ޞʝWEٗϑt uՇ׀~|C{yx?vtsrqon8mkmjihgfe=d8c{a_R_1^]E\[ZAZiYXrXWDUgTQ^PtMJIIH)HGGGFFEECCUA?;8787H65N5%4321.,)( '$ ktL`#%u6   ! h<qDjveq7AJqNd4N|> (|>) :: Seq a -> a -> Seq a<"SeqaaSeqa|O(1). Add an element to the right end of a sequence. Mnemonic: a triangle with the single element at the pointy end. viewrviewr :: Seq a -> ViewR aSeqaViewRa2O(1). Analyse the right end of a sequence. ViewRdata ViewR az%View of the right end of a sequence. viewlviewl :: Seq a -> ViewL aSeqaViewLa1O(1). Analyse the left end of a sequence. ViewLdata ViewL a`$View of the left end of a sequence. verticesvertices :: Graph -> [Vertex]Graph[]VertexAll vertices of a graph. Vertextype Vertex = Int;%Abstract representation of vertices. validvalid ::  Ord a => Set a -> BoolOrdaSetaBool:O(n). Test if the internal set structure is valid. validvalid ::  Ord k => Map k a -> BoolsSOrdkMapkaBoolO(n). Test if the internal map structure is valid. 
valid (fromAscList [(3,"b"), (5,"a")]) == True
valid (fromAscList [(5,"a"), (3,"b")]) == False
 updateWithKey  updateWithKey ::  Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k aOrdkkaMaybeakMapkaMapkadO(log n). The expression (updateWithKey f k map) updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 
let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
 updateWithKey  updateWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> IntMap a KeyaMaybeaKeyIntMapaIntMapa`O(min(n,W)). The expression (update f k map) updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 
let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateMinWithKeyupdateMinWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k akaMaybeaMapkaMapka*O(log n). Update the value at the minimal key. 
updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateMinWithKeyupdateMinWithKey :: (Key -> a -> a) -> IntMap a -> IntMap aKeyaaIntMapaIntMapa*O(log n). Update the value at the minimal key. 
updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
 updateMin updateMin :: (a -> Maybe a) -> Map k a -> Map k aaMaybeaMapkaMapkaO(log n). Update the value at the minimal key. 
updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
 updateMin updateMin :: (a -> a) -> IntMap a -> IntMap a<aaIntMapaIntMapaO(log n). Update the value at the minimal key. 
updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
updateMin (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateMaxWithKeyupdateMaxWithKey :: (k -> a -> Maybe a) -> Map k a -> Map k akaMaybeaMapkaMapka*O(log n). Update the value at the maximal key. 
updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
updateMaxWithKeyupdateMaxWithKey :: (Key -> a -> a) -> IntMap a -> IntMap aKeyaaIntMapaIntMapa*O(log n). Update the value at the maximal key. 
updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
updateMaxWithKey (\ _ _ -> Nothing)                     (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
 updateMax updateMax :: (a -> Maybe a) -> Map k a -> Map k aQaMaybeaMapkaMapkaO(log n). Update the value at the maximal key. 
updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
 updateMax updateMax :: (a -> a) -> IntMap a -> IntMap a aaIntMapaIntMapaO(log n). Update the value at the maximal key. 
updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
updateMax (\ _ -> Nothing)         (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
updateLookupWithKey updateLookupWithKey ::  Ord k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)OrdkkaMaybeakMapka(,)MaybeaMapka0O(log n). Lookup and update. See also updateWithKey. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted. 
let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "5:new a", fromList [(3, "b"), (5, "5:new a")])
updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
updateLookupWithKey updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> IntMap a -> (Maybe a, IntMap a) KeyaMaybeaKeyIntMapa(,)MaybeaIntMapaMO(min(n,W)). Lookup and update. The function returns original value, if it is updated. This is different behavior than Data.Map.updateLookupWithKey. Returns the original key value if the map entry is deleted. 
let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
updateAt updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a kaMaybeaIntMapkaMapkaiO(log n). Update the element at index. Calls error when an invalid index is used. 
updateAt (\ _ _ -> Just "x") 0    (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")]
updateAt (\ _ _ -> Just "x") 1    (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")]
updateAt (\ _ _ -> Just "x") 2    (fromList [(5,"a"), (3,"b")])    Error: index out of range
updateAt (\ _ _ -> Just "x") (-1) (fromList [(5,"a"), (3,"b")])    Error: index out of range
updateAt (\_ _  -> Nothing)  0    (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
updateAt (\_ _  -> Nothing)  1    (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
updateAt (\_ _  -> Nothing)  2    (fromList [(5,"a"), (3,"b")])    Error: index out of range
updateAt (\_ _  -> Nothing)  (-1) (fromList [(5,"a"), (3,"b")])    Error: index out of range
update update :: Int -> a -> Seq a -> Seq a IntaSeqaSeqaO(log(min(i,n-i))). Replace the element at the specified position. If the position is out of range, the original sequence is returned. update update ::  Ord k => (a -> Maybe a) -> k -> Map k a -> Map k aOOrdkaMaybeakMapkaMapka3O(log n). The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 
let f x = if x == "a" then Just "new a" else Nothing
update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
update update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a+aMaybeaKeyIntMapaIntMapa6O(min(n,W)). The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 
let f x = if x == "a" then Just "new a" else Nothing
update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
 unionWithKey  unionWithKey ::  Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a4OrdkkaaaMapkaMapkaMapkaO(n+m). Union with a combining function. The implementation uses the efficient hedge-union algorithm. Hedge-union is more efficient on (bigset `union` smallset). 
let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
 unionWithKey  unionWithKey :: (Key -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a]KeyaaaIntMapaIntMapaIntMapaO(n+m). The union with a combining function. 
let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
 unionWith  unionWith ::  Ord k =>  (a -> a -> a) -> Map k a -> Map k a -> Map k au6OrdkaaaMapkaMapkaMapkaO(n+m). Union with a combining function. The implementation uses the efficient hedge-union algorithm. 
unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
 unionWith  unionWith ::  (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a'aaaIntMapaIntMapaIntMapaO(n+m). The union with a combining function. 
unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
 unionsWith unionsWith ::  Ord k =>  (a -> a -> a) ->  [Map k a] -> Map k a[Ordkaaa[]MapkaMapkaDThe union of a list of maps, with a combining operation: (unionsWith f == Prelude.foldl (unionWith f) empty). 
unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
    == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
 unionsWith unionsWith ::  (a -> a -> a) ->  [IntMap a] -> IntMap auGaaa[]IntMapaIntMapaThe union of a list of maps, with a combining operation. 
unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
    == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
unionsunions ::  Ord a => [Set a] -> Set aOrda[]SetaSetaaThe union of a list of sets: (unions == foldl union empty). unionsunions ::  Ord k =>  [Map k a] -> Map k aOrdk[]MapkaMapkaThe union of a list of maps: (unions == Prelude.foldl union empty). 
unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
    == fromList [(3, "b"), (5, "a"), (7, "C")]
unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
    == fromList [(3, "B3"), (5, "A3"), (7, "C")]
unionsunions :: [IntSet] -> IntSet[]IntSetIntSetThe union of a list of sets. unionsunions ::  [IntMap a] -> IntMap a`=[]IntMapaIntMapaeThe union of a list of maps. 
unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
    == fromList [(3, "b"), (5, "a"), (7, "C")]
unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
    == fromList [(3, "B3"), (5, "A3"), (7, "C")]
unionunion ::  Ord a => Set a -> Set a -> Set aO$OrdaSetaSetaSetaO(n+m). The union of two sets, preferring the first set when equal elements are encountered. The implementation uses the efficient hedge-union algorithm. Hedge-union is more efficient on (bigset union smallset). unionunion ::  Ord k => Map k a -> Map k a -> Map k aOrdkMapkaMapkaMapkaO(n+m). The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered, i.e. (union == unionWith const). The implementation uses the efficient hedge-union algorithm. Hedge-union is more efficient on (bigset `union` smallset). 
union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
unionunion :: IntSet -> IntSet -> IntSet>#IntSetIntSetIntSet&O(n+m). The union of two sets. unionunion :: IntMap a -> IntMap a -> IntMap aIntMapaIntMapaIntMapa0O(n+m). The (left-biased) union of two maps. It prefers the first map when duplicate keys are encountered, i.e. (union == unionWith const). 
union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
unfoldTreeM_BFunfoldTreeM_BF ::  Monad m => (b -> m (a, [b])) -> b ->  m (Tree a)  Monadmbm(,)a[]bbmTreeaMonadic tree builder, in breadth-first order, using an algorithm adapted from Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design, by Chris Okasaki, ICFP'00.  unfoldTreeM unfoldTreeM ::  Monad m => (b -> m (a, [b])) -> b ->  m (Tree a)X  Monadmbm(,)a[]bbmTreea+Monadic tree builder, in depth-first order  unfoldTree unfoldTree :: (b -> (a, [b])) -> b -> Tree a  b(,)a[]bbTreeaBuild a tree from a seed value unfoldForestM_BFunfoldForestM_BF ::  Monad m => (b -> m (a, [b])) -> [b] ->  m (Forest a) Monadmbm(,)a[]b[]bmForestaMonadic forest builder, in breadth-first order, using an algorithm adapted from Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design, by Chris Okasaki, ICFP'00.  unfoldForestM unfoldForestM ::  Monad m => (b -> m (a, [b])) -> [b] ->  m (Forest a)HMonadmbm(,)a[]b[]bmForesta-Monadic forest builder, in depth-first order  unfoldForest unfoldForest :: (b -> (a, [b])) -> [b] -> Forest a\+b(,)a[]b[]bForesta*Build a forest from a list of seed values Treedata Tree a2Multi-way trees, also known as rose trees.  transposeG transposeG :: Graph -> GraphF5GraphGraph+The graph obtained by reversing all edges. topSorttopSort :: Graph -> [Vertex]Graph[]VertexA topological sort of the graph. The order is partially specified by the condition that a vertex i precedes j whenever j is reachable from i but not vice versa. toListtoList :: Set a -> [a]Seta[]a4O(n). Convert the set to a list of elements. toListtoList :: Map k a -> [(k, a)]mMapka[](,)kaO(n). Convert to a list of key/value pairs. 
toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
toList empty == []
toListtoList :: IntSet -> [Int]}gIntSet[]Int4O(n). Convert the set to a list of elements. toListtoList :: IntMap a ->  [(Key, a)]%IntMapa[](,)KeyaO(n). Convert the map to a list of key/value pairs. 
toList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
toList empty == []
 toAscList toAscList :: Set a -> [a]Seta[]a?O(n). Convert the set to an ascending list of elements.  toAscList toAscList :: Map k a -> [(k, a)]Mapka[](,)kawO(n). Convert to an ascending list. 
toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
 toAscList toAscList :: IntSet -> [Int]IntSet[]Int?O(n). Convert the set to an ascending list of elements.  toAscList toAscList :: IntMap a ->  [(Key, a)]e@IntMapa[](,)KeyaO(n). Convert the map to a list of key/value pairs where the keys are in ascending order. 
toAscList (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
taketake :: Int -> Seq a -> Seq adIntSeqaSeqaO(log(min(i,n-i))). The first i elements of a sequence. If i is negative, take i s yields the empty sequence. If the sequence contains fewer than i elements, the whole sequence is returned. Tabletype Table a = Array Vertex a/Table indexed by a contiguous set of vertices.  subForest subForest :: Tree a -> Forest aN3TreeaForestazero or more child trees stronglyConnCompRstronglyConnCompR ::  Ord key => [(node, key, [key])] -> [SCC (node, key, [key])]OOrdkey[](,,)nodekey[]key[]SCC(,,)nodekey[]keyTThe strongly connected components of a directed graph, topologically sorted. The function is the same as stronglyConnComp, except that all the information about each node retained. This interface is used when you expect to apply SCC to (some of) the result of SCC, so you don't want to lose the dependency information. stronglyConnCompstronglyConnComp ::  Ord key => [(node, key, [key])] ->  [SCC node]cOrdkey[](,,)nodekey[]key[]SCCnodeMThe strongly connected components of a directed graph, topologically sorted.  splitMember splitMember ::  Ord a => a -> Set a -> (Set a, Bool, Set a)b&OrdaaSeta(,,)SetaBoolSetasO(log n). Performs a split but also returns whether the pivot element was found in the original set.  splitMember splitMember :: Int -> IntSet -> (IntSet, Bool, IntSet)u G IntIntSet(,,)IntSetBoolIntSetvO(min(n,W)). Performs a split but also returns whether the pivot element was found in the original set.  splitLookup splitLookup ::  Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)!j!OrdkkMapka(,,)MapkaMaybeaMapka^O(log n). The expression (splitLookup k map) splits a map just like split but also returns lookup k map. 
splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])
splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a")
splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a")
splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty)
splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)
 splitLookup splitLookup :: Key -> IntMap a -> (IntMap a, Maybe a, IntMap a)$$KeyIntMapa(,,)IntMapaMaybeaIntMapa6O(log n). Performs a split but also returns whether the pivot key was found in the original map. 
splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])
splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a")
splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a")
splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty)
splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)
splitAtsplitAt :: Int -> Seq a -> (Seq a, Seq a)'h'IntSeqa(,)SeqaSeqaO(log(min(i,n-i))). Split a sequence at a given position. splitAt i s = (take i s, drop i s). splitsplit ::  Ord a => a -> Set a -> (Set a, Set a)(|(OrdaaSeta(,)SetaSetaO(log n). The expression (split x set) is a pair (set1,set2) where set1 comprises the elements of set less than x and set2 comprises the elements of set greater than x. splitsplit ::  Ord k => k -> Map k a -> (Map k a, Map k a)X**OrdkkMapka(,)MapkaMapkaO(log n). The expression (split k map) is a pair (map1,map2) where the keys in map1 are smaller than k and the keys in map2 larger than k. Any key equal to k is found in neither map1 nor map2. 
split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)
splitsplit :: Int -> IntSet -> (IntSet, IntSet)y-R-IntIntSet(,)IntSetIntSetNO(min(n,W)). The expression (split x set) is a pair (set1,set2) where set1 comprises the elements of set less than x and set2 comprises the elements of set greater than x. 
split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])
splitsplit :: Key -> IntMap a -> (IntMap a, IntMap a)c/-/KeyIntMapa(,)IntMapaIntMapaO(log n). The expression (split k map) is a pair (map1,map2) where all keys in map1 are lower than k and all keys in map2 larger than k. Any key equal to k is found in neither map1 nor map2. 
split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)
sizesize :: Set a -> IntN2<2SetaInt0O(1). The number of elements in the set. sizesize :: Map k a -> Int22MapkaIntO(1). The number of elements in the map. 
size empty                                   == 0
size (singleton 1 'a')                       == 1
size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
sizesize :: IntSet -> Int33IntSetInt%O(n). Cardinality of the set. sizesize :: IntMap a -> Intz4e4IntMapaIntO(n). Number of elements in the map. 
size empty                                   == 0
size (singleton 1 'a')                       == 1
size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
 singleton singleton :: a -> Set a55aSeta%O(1). Create a singleton set.  singleton singleton :: a -> Seq a!66aSeqa#O(1). A singleton sequence.  singleton singleton :: k -> a -> Map k a66kaMapkaO(1). A map with a single element. 
singleton 1 'a'        == fromList [(1, 'a')]
size (singleton 1 'a') == 1
 singleton singleton :: Int -> IntSet77IntIntSet#O(1). A set of one element.  singleton singleton :: Key -> a -> IntMap a&88KeyaIntMapa{O(1). A map of one element. 
singleton 1 'a'        == fromList [(1, 'a')]
size (singleton 1 'a') == 1
 showTreeWith  showTreeWith ::  Show a => Bool -> Bool -> Set a -> StringK99ShowaBoolBoolSetaStringgO(n). The expression (showTreeWith hang wide map) shows the tree that implements the set. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown. 
Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
4
+--2
|  +--1
|  +--3
+--5

Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
4
|
+--2
|  |
|  +--1
|  |
|  +--3
|
+--5

Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
+--5
|
4
|
|  +--3
|  |
+--2
   |
   +--1
 showTreeWith  showTreeWith :: (k -> a -> String) -> Bool -> Bool -> Map k a -> Stringz<F<kaStringBoolBoolMapkaString.O(n). The expression (showTreeWith showelem hang wide map) shows the tree that implements the map. Elements are shown using the showElem function. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown. 
Map> let t = fromDistinctAscList [(x,()) | x <- [1..5]]
Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True False t
(4,())
+--(2,())
|  +--(1,())
|  +--(3,())
+--(5,())

Map> putStrLn $ showTreeWith (\k x -> show (k,x)) True True t
(4,())
|
+--(2,())
|  |
|  +--(1,())
|  |
|  +--(3,())
|
+--(5,())

Map> putStrLn $ showTreeWith (\k x -> show (k,x)) False True t
+--(5,())
|
(4,())
|
|  +--(3,())
|  |
+--(2,())
   |
   +--(1,())
 showTreeWith  showTreeWith :: Bool -> Bool -> IntSet -> String<@@BoolBoolIntSetStringO(n). The expression (showTreeWith hang wide map) shows the tree that implements the set. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown.  showTreeWith  showTreeWith ::  Show a => Bool -> Bool -> IntMap a -> StringBAShowaBoolBoolIntMapaStringO(n). The expression (showTreeWith hang wide map) shows the tree that implements the map. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is True, an extra wide version is shown. showTreeshowTree ::  Show a => Set a -> StringClCShowaSetaStringgO(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format. showTreeshowTree :: (Show k, Show a) => Map k a -> StringDUDShowkShowaMapkaStringO(n). Show the tree that implements the map. The tree is shown in a compressed, hanging format. See showTreeWith. showTreeshowTree :: IntSet -> StringcEPEIntSetStringgO(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format. showTreeshowTree ::  Show a => IntMap a -> StringFF#FShowaIntMapaStringgO(n). Show the tree that implements the map. The tree is shown in a compressed, hanging format. Setdata Set aFA set of values a. Seqdata Seq a!G"General-purpose finite sequences. sccscc :: Graph ->  Forest VertexGGGraphForestVertex.The strongly connected components of a graph. SCCdata SCC vertexHStrongly connected component.  rootLabel rootLabel :: Tree a -> aHoHTreeaa label value reversereverse :: Seq a -> Seq aHHSeqaSeqa(O(n). The reverse of a sequence.  reachable reachable :: Graph -> Vertex -> [Vertex]IvIGraphVertex[]Vertex2A list of vertices reachable from a given vertex. path path :: Graph -> Vertex -> Vertex -> BoolNJ.JGraphVertexVertexBool/Is the second vertex reachable from the first? partitionWithKeypartitionWithKey ::  Ord k => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)UK KOrdkkaBoolMapka(,)MapkaMapkaO(n). Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also split. 
partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b")
partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
partitionWithKeypartitionWithKey :: (Key -> a -> Bool) -> IntMap a -> (IntMap a, IntMap a)O(n). Partition the map according to some predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also split. 
partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b")
partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
 partition partition ::  Ord a =>  (a -> Bool) -> Set a -> (Set a, Set a) QPOrdaaBoolSeta(,)SetaSetaO(n). Partition the set into two sets, one with all elements that satisfy the predicate and one with all elements that don't satisfy the predicate. See also split.  partition partition ::  Ord k =>  (a -> Bool) -> Map k a -> (Map k a, Map k a)R;ROrdkaBoolMapka(,)MapkaMapkaO(n). Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also split. 
partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
 partition partition ::  (Int -> Bool) -> IntSet -> (IntSet, IntSet)UTIntBoolIntSet(,)IntSetIntSet<O(n). partition the set according to some predicate.  partition partition ::  (a -> Bool) -> IntMap a -> (IntMap a, IntMap a)UUaBoolIntMapa(,)IntMapaIntMapaO(n). Partition the map according to some predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. See also split. 
partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
 outdegree outdegree :: Graph ->  Table Int@X(XGraphTableInt.A table of the count of edges from each node. nullnull :: Set a -> BoolXXSetaBool$O(1). Is this the empty set? nullnull :: Seq a -> BoolO(1). Is this the empty sequence? nullnull :: Map k a -> BoolYYMapkaBool~O(1). Is the map empty? 
Data.Map.null (empty)           == True
Data.Map.null (singleton 1 'a') == False
nullnull :: IntSet -> BoolZZIntSetBoolO(1). Is the set empty? nullnull :: IntMap a -> Bool [ZIntMapaBoolO(1). Is the map empty? 
Data.IntMap.null (empty)           == True
Data.IntMap.null (singleton 1 'a') == False
 notMember notMember ::  Ord a => a -> Set a -> Bool\[OrdaaSetaBool0O(log n). Is the element not in the set?  notMember notMember ::  Ord k => k -> Map k a -> Bool\\OrdkkMapkaBoolO(log n). Is the key not a member of the map? See also member. 
notMember 5 (fromList [(5,'a'), (3,'b')]) == False
notMember 1 (fromList [(5,'a'), (3,'b')]) == True
 notMember notMember :: Int -> IntSet -> Bool]]IntIntSetBool3O(min(n,W)). Is the element not in the set?  notMember notMember :: Key -> IntMap a -> Bool^^KeyIntMapaBoolO(log n). Is the key not a member of the map? 
notMember 5 (fromList [(5,'a'), (3,'b')]) == False
notMember 1 (fromList [(5,'a'), (3,'b')]) == True
NodeNode :: a -> Forest a -> Tree a__aForestaTreeaminViewWithKeyminViewWithKey :: Map k a -> Maybe ((k, a), Map k a)e`+`MapkaMaybe(,)(,)kaMapkaO(log n). Retrieves the minimal (key,value) pair of the map, and the map stripped of that element, or Nothing if passed an empty map. 
minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
minViewWithKey empty == Nothing
minViewWithKeyminViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)"baIntMapaMaybe(,)(,)KeyaIntMapaO(log n). Retrieves the minimal (key,value) pair of the map, and the map stripped of that element, or Nothing if passed an empty map. 
minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
minViewWithKey empty == Nothing
minViewminView :: Set a -> Maybe (a, Set a)ccSetaMaybe(,)aSetaO(log n). Retrieves the minimal key of the set, and the set stripped of that element, or Nothing if passed an empty set. minViewminView :: Map k a -> Maybe (a, Map k a)ddMapkaMaybe(,)aMapka O(log n). Retrieves the value associated with minimal key of the map, and the map stripped of that element, or Nothing if passed an empty map. 
minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
minView empty == Nothing
minViewminView :: IntSet -> Maybe (Int, IntSet)Jf"fIntSetMaybe(,)IntIntSetO(min(n,W)). Retrieves the minimal key of the set, and the set stripped of that element, or Nothing if passed an empty set. minViewminView :: IntMap a -> Maybe (a, IntMap a)^g.gIntMapaMaybe(,)aIntMapaO(log n). Retrieves the minimal key of the map, and the map stripped of that element, or Nothing if passed an empty map. membermember ::  Ord a => a -> Set a -> BoolahAhOrdaaSetaBool,O(log n). Is the element in the set? membermember ::  Ord k => k -> Map k a -> BoolihOrdkkMapkaBoolO(log n). Is the key a member of the map? See also notMember. 
member 5 (fromList [(5,'a'), (3,'b')]) == True
member 1 (fromList [(5,'a'), (3,'b')]) == False
membermember :: Int -> IntSet -> Bool3jjIntIntSetBool6O(min(n,W)). Is the value a member of the set? membermember :: Key -> IntMap a -> BooljjKeyIntMapaBoolO(min(n,W)). Is the key a member of the map? 
member 5 (fromList [(5,'a'), (3,'b')]) == True
member 1 (fromList [(5,'a'), (3,'b')]) == False
maxViewWithKeymaxViewWithKey :: Map k a -> Maybe ((k, a), Map k a)"lkMapkaMaybe(,)(,)kaMapkaO(log n). Retrieves the maximal (key,value) pair of the map, and the map stripped of that element, or Nothing if passed an empty map. 
maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
maxViewWithKey empty == Nothing
maxViewWithKeymaxViewWithKey :: IntMap a -> Maybe ((Key, a), IntMap a)mmIntMapaMaybe(,)(,)KeyaIntMapaO(log n). Retrieves the maximal (key,value) pair of the map, and the map stripped of that element, or Nothing if passed an empty map. 
maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
maxViewWithKey empty == Nothing
maxViewmaxView :: Set a -> Maybe (a, Set a)ooEoSetaMaybe(,)aSetaO(log n). Retrieves the maximal key of the set, and the set stripped of that element, or Nothing if passed an empty set. maxViewmaxView :: Map k a -> Maybe (a, Map k a)~pNpMapkaMaybe(,)aMapkaO(log n). Retrieves the value associated with maximal key of the map, and the map stripped of that element, or Nothing if passed an 
maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
maxView empty == Nothing
maxViewmaxView :: IntSet -> Maybe (Int, IntSet)qqIntSetMaybe(,)IntIntSetO(min(n,W)). Retrieves the maximal key of the set, and the set stripped of that element, or Nothing if passed an empty set. maxViewmaxView :: IntMap a -> Maybe (a, IntMap a)srIntMapaMaybe(,)aIntMapaO(log n). Retrieves the maximal key of the map, and the map stripped of that element, or Nothing if passed an empty map.  mapWithKey mapWithKey ::  (k -> a -> b) -> Map k a -> Map k b+ttkabMapkaMapkbO(n). Map a function over all values in the map. 
let f key x = (show key) ++ ":" ++ x
mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
 mapWithKey mapWithKey :: (Key -> a -> b) -> IntMap a -> IntMap buVuKeyabIntMapaIntMapbO(n). Map a function over all values in the map. 
let f key x = (show key) ++ ":" ++ x
mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
 mapMonotonic mapMonotonic :: (a -> b) -> Set a -> Set bvvabSetaSetbMO(n). The mapMonotonic f s == map f s, but works only when f is monotonic. The precondition is not checked. Semi-formally, we have: 
and [x < y ==> f x < f y | x <- ls, y <- ls] 
                    ==> mapMonotonic f s == map f s
    where ls = toList s
mapMaybeWithKeymapMaybeWithKey ::  Ord k => (k -> a -> Maybe b) -> Map k a -> Map k bxxOrdkkaMaybebMapkaMapkbO(n). Map keys/values and collect the Just results. 
let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
mapMaybeWithKeymapMaybeWithKey :: (Key -> a -> Maybe b) -> IntMap a -> IntMap b`z-zKeyaMaybebIntMapaIntMapbO(n). Map keys/values and collect the Just results. 
let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
mapMaybemapMaybe ::  Ord k => (a -> Maybe b) -> Map k a -> Map k b{{OrdkaMaybebMapkaMapkbO(n). Map values and collect the Just results. 
let f x = if x == "a" then Just "new a" else Nothing
mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
mapMaybemapMaybe :: (a -> Maybe b) -> IntMap a -> IntMap bB}}aMaybebIntMapaIntMapbO(n). Map values and collect the Just results. 
let f x = if x == "a" then Just "new a" else Nothing
mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
 mapKeysWith  mapKeysWith ::  Ord k2 =>  (a -> a -> a) ->  (k1 -> k2) -> Map k1 a -> Map k2 a~~Ordk2aaak1k2Mapk1aMapk2aO(n*log n). mapKeysWith c f s is the map obtained by applying f to each key of s. The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the associated values will be combined using c. 
mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"
mapKeysMonotonicmapKeysMonotonic ::  (k1 -> k2) -> Map k1 a -> Map k2 asJk1k2Mapk1aMapk2awO(n). mapKeysMonotonic f s == mapKeys f s, but works only when f is strictly monotonic. That is, for any values x and y, if x < y then f x < f y. The precondition is not checked. Semi-formally, we have: 
and [x < y ==> f x < f y | x <- ls, y <- ls] 
                    ==> mapKeysMonotonic f s == mapKeys f s
    where ls = keys s
This means that f maps distinct original keys to distinct resulting keys. This function has better performance than mapKeys. 
mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True
valid (mapKeysMonotonic (\ _ -> 1)     (fromList [(5,"a"), (3,"b")])) == False
mapKeysmapKeys ::  Ord k2 =>  (k1 -> k2) -> Map k1 a -> Map k2 aYOrdk2k1k2Mapk1aMapk2aDO(n*log n). mapKeys f s is the map obtained by applying f to each key of s. The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the value at the smallest of these keys is retained. 
mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])                        == fromList [(4, "b"), (6, "a")]
mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c"
mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
mapEitherWithKeymapEitherWithKey ::  Ord k => (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)fOrdkkaEitherbcMapka(,)MapkbMapkcO(n). Map keys/values and separate the Left and Right results. 
let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])

mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
mapEitherWithKeymapEitherWithKey :: (Key -> a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)MKeyaEitherbcIntMapa(,)IntMapbIntMapcO(n). Map keys/values and separate the Left and Right results. 
let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])

mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
 mapEither mapEither ::  Ord k => (a -> Either b c) -> Map k a -> (Map k b, Map k c)׍OrdkaEitherbcMapka(,)MapkbMapkcO(n). Map values and separate the Left and Right results. 
let f a = if a < "c" then Left a else Right a
mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])

mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
 mapEither mapEither :: (a -> Either b c) -> IntMap a -> (IntMap b, IntMap c)2aEitherbcIntMapa(,)IntMapbIntMapcO(n). Map values and separate the Left and Right results. 
let f a = if a < "c" then Left a else Right a
mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])

mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
    == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
mapAccumWithKey mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> Map k b ->  (a, Map k c)]akb(,)acaMapkb(,)aMapkcAO(n). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys. 
let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
mapAccumWithKey mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> IntMap b ->  (a, IntMap c)vaKeyb(,)acaIntMapb(,)aIntMapcJO(n). The function mapAccumWithKey threads an accumulating argument through the map in ascending order of keys. 
let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
mapAccum mapAccum :: (a -> b -> (a, c)) -> a -> Map k b ->  (a, Map k c)–ab(,)acaMapkb(,)aMapkcO(n). The function mapAccum threads an accumulating argument through the map in ascending order of keys. 
let f a b = (a ++ b, b ++ "X")
mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
mapAccum mapAccum :: (a -> b -> (a, c)) -> a -> IntMap b ->  (a, IntMap c)Vab(,)acaIntMapb(,)aIntMapcO(n). The function mapAccum threads an accumulating argument through the map in ascending order of keys. 
let f a b = (a ++ b, b ++ "X")
mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
mapmap :: (Ord a, Ord b) => (a -> b) -> Set a -> Set bKOrdaOrdbabSetaSetbO(n*log n). map f s is the set obtained by applying f to each element of s. It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y mapmap :: (a -> b) -> Map k a -> Map k babMapkaMapkbO(n). Map a function over all values in the map. 
map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
mapmap ::  (Int -> Int) -> IntSet -> IntSet͜IntIntIntSetIntSetO(n*min(n,W)). map f s is the set obtained by applying f to each element of s. It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y mapmap :: (a -> b) -> IntMap a -> IntMap bF!abIntMapaIntMapbO(n). Map a function over all values in the map. 
map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
Mapdata Map k a1A Map from keys k to values a.  lookupIndex lookupIndex ::  Ord k => k -> Map k a ->  Maybe IntџOrdkkMapkaMaybeIntO(log n). Lookup the index of a key. The index is a number from 0 up to, but not including, the size of the map. 
isJust (lookupIndex 2 (fromList [(5,"a"), (3,"b")]))   == False
fromJust (lookupIndex 3 (fromList [(5,"a"), (3,"b")])) == 0
fromJust (lookupIndex 5 (fromList [(5,"a"), (3,"b")])) == 1
isJust (lookupIndex 6 (fromList [(5,"a"), (3,"b")]))   == False
lookuplookup ::  Ord k => k -> Map k a -> Maybe ašOrdkkMapkaMaybeaO(log n). Lookup the value at a key in the map. The function will return the corresponding value as (Just value), or Nothing if the key isn't in the map. An example of using lookup: 
import Prelude hiding (lookup)
import Data.Map

employeeDept = fromList([("John","Sales"), ("Bob","IT")])
deptCountry = fromList([("IT","USA"), ("Sales","France")])
countryCurrency = fromList([("USA", "Dollar"), ("France", "Euro")])

employeeCurrency :: String -> Maybe String
employeeCurrency name = do
    dept <- lookup name employeeDept
    country <- lookup dept deptCountry
    lookup country countryCurrency

main = do
    putStrLn $ "John's currency: " ++ (show (employeeCurrency "John"))
    putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))
The output of this program: 
John's currency: Just "Euro"
Pete's currency: Nothing
lookuplookup :: Key -> IntMap a -> Maybe aإKeyIntMapaMaybeaTO(min(n,W)). Lookup the value at a key in the map. See also Data.Map.lookup. levelslevels :: Tree a -> [[a]]Treea[][]a*Lists of nodes at each level of the tree. lengthlength :: Seq a -> Int3!SeqaInt5O(1). The number of elements in the sequence. keysSetkeysSet :: Map k a -> Set kͧMapkaSetkO(n). The set of all keys of the map. 
keysSet (fromList [(5,"a"), (3,"b")]) == Data.Set.fromList [3,5]
keysSet empty == Data.Set.empty
keysSetkeysSet :: IntMap a -> IntSetΨIntMapaIntSetO(n*min(n,W)). The set of all keys of the map. 
keysSet (fromList [(5,"a"), (3,"b")]) == Data.IntSet.fromList [3,5]
keysSet empty == Data.IntSet.empty
keyskeys :: Map k a -> [k]թMapka[]kO(n). Return all keys of the map in ascending order. 
keys (fromList [(5,"a"), (3,"b")]) == [3,5]
keys empty == []
keyskeys :: IntMap a -> [Key]IntMapa[]KeyO(n). Return all keys of the map in ascending order. 
keys (fromList [(5,"a"), (3,"b")]) == [3,5]
keys empty == []
Keytype Key = Intv isSubsetOf isSubsetOf ::  Ord a => Set a -> Set a -> BoolޫOrdaSetaSetaBoolzO(n+m). Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.  isSubsetOf isSubsetOf :: IntSet -> IntSet -> BoolIntSetIntSetBoolzO(n+m). Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.  isSubmapOfBy  isSubmapOfBy ::  Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool:OrdkabBoolMapkaMapkbBoolO(n+m). The expression (isSubmapOfBy f t1 t2) returns True if all keys in t1 are in tree t2, and when f returns True when applied to their respective values. For example, the following expressions are all True: 
isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
But the following are all False: 
isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (<)  (fromList [('a',1)]) (fromList [('a',1),('b',2)])
isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
 isSubmapOfBy  isSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> BoolıabBoolIntMapaIntMapbBoolO(n+m). The expression (isSubmapOfBy f m1 m2) returns True if all keys in m1 are in m2, and when f returns True when applied to their respective values. For example, the following expressions are all True: 
isSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
But the following are all False: 
isSubmapOfBy (==) (fromList [(1,2)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (<) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
 isSubmapOf isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> BoolxBOrdkEqaMapkaMapkaBooldO(n+m). This function is defined as (isSubmapOf = isSubmapOfBy (==)).  isSubmapOf isSubmapOf :: Eq a => IntMap a -> IntMap a -> BooluIEqaIntMapaIntMapaBooleO(n+m). Is this a submap? Defined as (isSubmapOf = isSubmapOfBy (==)). isProperSubsetOfisProperSubsetOf ::  Ord a => Set a -> Set a -> BooluNOrdaSetaSetaBoolFO(n+m). Is this a proper subset? (ie. a subset but not equal). isProperSubsetOfisProperSubsetOf :: IntSet -> IntSet -> BoolA(IntSetIntSetBoolFO(n+m). Is this a proper subset? (ie. a subset but not equal). isProperSubmapOfBy isProperSubmapOfBy ::  Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> BoolZOrdkabBoolMapkaMapkbBool*O(n+m). Is this a proper submap? (ie. a submap but not equal). The expression (isProperSubmapOfBy f m1 m2) returns True when m1 and m2 are not equal, all keys in m1 are in m2, and when f returns True when applied to their respective values. For example, the following expressions are all True: 
isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
But the following are all False: 
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
isProperSubmapOfBy (<)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])
isProperSubmapOfBy isProperSubmapOfBy :: (a -> b -> Bool) -> IntMap a -> IntMap b -> BoolFabBoolIntMapaIntMapbBool*O(n+m). Is this a proper submap? (ie. a submap but not equal). The expression (isProperSubmapOfBy f m1 m2) returns True when m1 and m2 are not equal, all keys in m1 are in m2, and when f returns True when applied to their respective values. For example, the following expressions are all True: 
isProperSubmapOfBy (==) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (<=) (fromList [(1,1)]) (fromList [(1,1),(2,2)])
But the following are all False: 
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1),(2,2)])
isProperSubmapOfBy (==) (fromList [(1,1),(2,2)]) (fromList [(1,1)])
isProperSubmapOfBy (<)  (fromList [(1,1)])       (fromList [(1,1),(2,2)])
isProperSubmapOfisProperSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool&OrdkEqaMapkaMapkaBoolO(n+m). Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy (==)). isProperSubmapOfisProperSubmapOf :: Eq a => IntMap a -> IntMap a -> Boola5EqaIntMapaIntMapaBoolO(n+m). Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy (==)). IntSetdata IntSet'A set of integers. IntMapdata IntMap al(A map of integers to values a. intersectionWithKey intersectionWithKey ::  Ord k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k cu3OrdkkabcMapkaMapkbMapkc0O(n+m). Intersection with a combining function. Intersection is more efficient on (bigset `intersection` smallset). 
let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
intersectionWithKey intersectionWithKey :: (Key -> a -> b -> a) -> IntMap a -> IntMap b -> IntMap az@KeyabaIntMapaIntMapbIntMapaO(n+m). The intersection with a combining function. 
let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
intersectionWith intersectionWith ::  Ord k =>  (a -> b -> c) -> Map k a -> Map k b -> Map k c6OrdkabcMapkaMapkbMapkcO(n+m). Intersection with a combining function. 
intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
intersectionWith intersectionWith ::  (a -> b -> a) -> IntMap a -> IntMap b -> IntMap asabaIntMapaIntMapbIntMapaO(n+m). The intersection with a combining function. 
intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
 intersection intersection ::  Ord a => Set a -> Set a -> Set aOrdaSetaSetaSetaO(n+m). The intersection of two sets. Elements of the result come from the first set, so for example 
import qualified Data.Set as S
data AB = A | B deriving Show
instance Ord AB where compare _ _ = EQ
instance Eq AB where _ == _ = True
main = print (S.singleton A `S.intersection` S.singleton B,
              S.singleton B `S.intersection` S.singleton A)
prints (fromList [A],fromList [B]).  intersection intersection ::  Ord k => Map k a -> Map k b -> Map k aA OrdkMapkaMapkbMapka,O(n+m). Intersection of two maps. Return data in the first map for the keys existing in both maps. (intersection m1 m2 == intersectionWith const m1 m2). 
intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
 intersection intersection :: IntSet -> IntSet -> IntSetIntSetIntSetIntSet-O(n+m). The intersection of two sets.  intersection intersection :: IntMap a -> IntMap b -> IntMap aIntMapaIntMapbIntMapaO(n+m). The (left-biased) intersection of two maps (based on keys). 
intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
insertWithKey' insertWithKey' ::  Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k aCOrdkkaaakaMapkaMapkaNSame as insertWithKey, but the combining function is applied strictly.  insertWithKey  insertWithKey ::  Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k af+OrdkkaaakaMapkaMapkaO(log n). Insert with a function, combining key, new value and old value. insertWithKey f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert the pair (key,f key new_value old_value). Note that the key passed to f is the same key passed to insertWithKey. 
let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
 insertWithKey  insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a"KeyaaaKeyaIntMapaIntMapaxO(min(n,W)). Insert with a combining function. insertWithKey f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert f key new_value old_value. 
let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
 insertWith'  insertWith' ::  Ord k =>  (a -> a -> a) -> k -> a -> Map k a -> Map k ac+OrdkaaakaMapkaMapkaKSame as insertWith, but the combining function is applied strictly.  insertWith  insertWith ::  Ord k =>  (a -> a -> a) -> k -> a -> Map k a -> Map k au=OrdkaaakaMapkaMapkaAO(log n). Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert the pair (key, f new_value old_value). 
insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
 insertWith  insertWith ::  (a -> a -> a) -> Key -> a -> IntMap a -> IntMap ap@aaaKeyaIntMapaIntMapaO(min(n,W)). Insert with a combining function. insertWith f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert f new_value old_value. 
insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
insertLookupWithKey insertLookupWithKey ::  Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)<OrdkkaaakaMapka(,)MaybeaMapka)O(log n). Combines insert operation with old value retrieval. The expression (insertLookupWithKey f k x map) is a pair where the first element is equal to (lookup k map) and the second element equal to (insertWithKey f k x map). 
let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")
This is how to define insertLookup using insertLookupWithKey: 
let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])
insertLookupWithKey insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a, IntMap a)aKeyaaaKeyaIntMapa(,)MaybeaIntMapaO(min(n,W)). The expression (insertLookupWithKey f k x map) is a pair where the first element is equal to (lookup k map) and the second element equal to (insertWithKey f k x map). 
let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")
This is how to define insertLookup using insertLookupWithKey: 
let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])
insertinsert ::  Ord a => a -> Set a -> Set a"OrdaaSetaSetaO(log n). Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value. insert insert ::  Ord k => k -> a -> Map k a -> Map k aN!OrdkkaMapkaMapkaO(log n). Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. insert is equivalent to insertWith const. 
insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
insert 5 'x' empty                         == singleton 5 'x'
insertinsert :: Int -> IntSet -> IntSetxIntIntSetIntSetO(min(n,W)). Add a value to the set. When the value is already an element of the set, it is replaced by the new one, ie. insert is left-biased. insert insert :: Key -> a -> IntMap a -> IntMap aKeyaIntMapaIntMapaO(min(n,W)). Insert a new key/value pair in the map. If the key is already present in the map, the associated value is replaced with the supplied value, i.e. insert is equivalent to insertWith const. 
insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
insert 5 'x' empty                         == singleton 5 'x'
indexindex :: Seq a -> Int -> aSeqaIntaO(log(min(i,n-i))). The element at the specified position, which should be a positive integer less than the size of the sequence. If the position is out of range, index fails with an error. indegreeindegree :: Graph ->  Table Int/GraphTableInt.A table of the count of edges into each node. graphFromEdges'graphFromEdges' ::  Ord key => [(node, key, [key])] -> %(Graph, Vertex -> (node, key, [key]))YOrdkey[](,,)nodekey[]key(,)GraphVertex(,,)nodekey[]keyIdentical to graphFromEdges, except that the return value does not include the function which maps keys to vertices. This version of graphFromEdges is for backwards compatibility. graphFromEdgesgraphFromEdges ::  Ord key => [(node, key, [key])] -> :(Graph, Vertex -> (node, key, [key]), key -> Maybe Vertex)COrdkey[](,,)nodekey[]key(,,)GraphVertex(,,)nodekey[]keykeyMaybeVertexBuild a graph from a list of nodes uniquely identified by keys, with a list of keys of nodes this node should have edges to. The out-list may contain keys that don't correspond to nodes of the graph; they are ignored. Graphtype Graph = Table [Vertex]^YAdjacency list representation of a graph, mapping each vertex to its list of successors. fromListWithKeyfromListWithKey ::  Ord k => (k -> a -> a -> a) -> [(k, a)] -> Map k aw<Ordkkaaa[](,)kaMapka5O(n*log n). Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey. 
let f k a1 a2 = (show k) ++ a1 ++ a2
fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
fromListWithKey f [] == empty
fromListWithKeyfromListWithKey :: (Key -> a -> a -> a) ->  [(Key, a)] -> IntMap ab-Keyaaa[](,)KeyaIntMapa O(n*min(n,W)). Build a map from a list of key/value pairs with a combining function. See also fromAscListWithKey'. 
fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty
 fromListWith fromListWith ::  Ord k =>  (a -> a -> a) -> [(k, a)] -> Map k aOrdkaaa[](,)kaMapka O(n*log n). Build a map from a list of key/value pairs with a combining function. See also fromAscListWith. 
fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty
 fromListWith fromListWith ::  (a -> a -> a) ->  [(Key, a)] -> IntMap aaaa[](,)KeyaIntMapaO(n*min(n,W)). Create a map from a list of key/value pairs with a combining function. See also fromAscListWith. 
fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
fromListWith (++) [] == empty
fromListfromList ::  Ord a => [a] -> Set aL,Orda[]aSeta9O(n*log n). Create a set from a list of elements. fromListfromList :: [a] -> Seq a[]aSeqaO(n). Create a sequence from a finite list of elements. There is a function toList in the opposite direction for all instances of the Foldable class, including Seq. fromListfromList ::  Ord k => [(k, a)] -> Map k a+Ordk[](,)kaMapkalO(n*log n). Build a map from a list of key/value pairs. See also fromAscList. If the list contains more than one value for the same key, the last value for the key is retained. 
fromList [] == empty
fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
fromListfromList :: [Int] -> IntSet[]IntIntSet<O(n*min(n,W)). Create a set from a list of integers. fromListfromList ::  [(Key, a)] -> IntMap a[](,)KeyaIntMapaO(n*min(n,W)). Create a map from a list of key/value pairs. 
fromList [] == empty
fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
fromDistinctAscListfromDistinctAscList :: [a] -> Set a[]aSetaO(n). Build a set from an ascending list of distinct elements in linear time. The precondition (input list is strictly ascending) is not checked. fromDistinctAscListfromDistinctAscList :: [(k, a)] -> Map k a;[](,)kaMapkaTO(n). Build a map from an ascending list of distinct elements in linear time. The precondition is not checked. 
fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
valid (fromDistinctAscList [(3,"b"), (5,"a")])          == True
valid (fromDistinctAscList [(3,"b"), (5,"a"), (5,"b")]) == False
fromDistinctAscListfromDistinctAscList :: [Int] -> IntSet[]IntIntSetOO(n*min(n,W)). Build a set from an ascending list of distinct elements. fromDistinctAscListfromDistinctAscList ::  [(Key, a)] -> IntMap a[](,)KeyaIntMapaO(n*min(n,W)). Build a map from a list of key/value pairs where the keys are in ascending order and all distinct. 
fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
fromAscListWithKeyfromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k aw = Eqkkaaa[](,)kaMapkaO(n). Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked. 
let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
valid (fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")]) == True
valid (fromAscListWithKey f [(5,"a"), (3,"b"), (5,"b"), (5,"b")]) == False
fromAscListWithKeyfromAscListWithKey :: (Key -> a -> a -> a) ->  [(Key, a)] -> IntMap a  Keyaaa[](,)KeyaIntMapaO(n*min(n,W)). Build a map from a list of key/value pairs where the keys are in ascending order, with a combining function on equal keys. 
fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
fromAscListWithfromAscListWith :: Eq k =>  (a -> a -> a) -> [(k, a)] -> Map k a  Eqkaaa[](,)kaMapkaO(n). Build a map from an ascending list in linear time with a combining function for equal keys. The precondition (input list is ascending) is not checked. 
fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
valid (fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")]) == True
valid (fromAscListWith (++) [(5,"a"), (3,"b"), (5,"b")]) == False
fromAscListWithfromAscListWith ::  (a -> a -> a) ->  [(Key, a)] -> IntMap aaaa[](,)KeyaIntMapaO(n*min(n,W)). Build a map from a list of key/value pairs where the keys are in ascending order, with a combining function on equal keys. 
fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
 fromAscList fromAscList :: Eq a => [a] -> Set aW8Eqa[]aSetaO(n). Build a set from an ascending list in linear time. The precondition (input list is ascending) is not checked.  fromAscList fromAscList :: Eq k => [(k, a)] -> Map k ac7Eqk[](,)kaMapkaO(n). Build a map from an ascending list in linear time. The precondition (input list is ascending) is not checked. 
fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]
fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
valid (fromAscList [(3,"b"), (5,"a"), (5,"b")]) == True
valid (fromAscList [(5,"a"), (3,"b"), (5,"b")]) == False
 fromAscList fromAscList :: [Int] -> IntSet^H[]IntIntSetFO(n*min(n,W)). Build a set from an ascending list of elements.  fromAscList fromAscList ::  [(Key, a)] -> IntMap a"[](,)KeyaIntMapaO(n*min(n,W)). Build a map from a list of key/value pairs where the keys are in ascending order. 
fromAscList [(3,"b"), (5,"a")]          == fromList [(3, "b"), (5, "a")]
fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
Foresttype Forest a = [Tree a]i foldWithKey  foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> bkabbbMapkab{O(n). Fold the keys and values in the map, such that foldWithKey f z == Prelude.foldr (uncurry f) z . toAscList. For example, 
keys map = foldWithKey (\k x ks -> k:ks) [] map

let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
 foldWithKey  foldWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b%KeyabbbIntMapab{O(n). Fold the keys and values in the map, such that foldWithKey f z == Prelude.foldr (uncurry f) z . toAscList. For example, 
keys map = foldWithKey (\k x ks -> k:ks) [] map

let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
fold fold ::  (a -> b -> b) -> b -> Set a -> b#abbbSetabFO(n). Fold over the elements of a set in an unspecified order. fold fold ::  (a -> b -> b) -> b -> Map k a -> babbbMapkabO(n). Fold the values in the map, such that fold f z == Prelude.foldr f z . elems. For example, 
elems map = fold (:) [] map

let f a len = len + (length a)
fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
fold fold :: (Int -> b -> b) -> b -> IntSet -> bz\IntbbbIntSetbO(n). Fold over the elements of a set in an unspecified order. 
sum set   == fold (+) 0 set
elems set == fold (:) [] set
fold fold ::  (a -> b -> b) -> b -> IntMap a -> boabbbIntMapabO(n). Fold the values in the map, such that fold f z == Prelude.foldr f z . elems. For example, 
elems map = fold (:) [] map

let f a len = len + (length a)
fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
 flattenSCCs flattenSCCs :: [SCC a] -> [a] []SCCa[]a9The vertices of a list of strongly connected components.  flattenSCC flattenSCC ::  SCC vertex -> [vertex]  SCCvertex[]vertex0The vertices of a strongly connected component. flattenflatten :: Tree a -> [a]?!(!Treea[]a%The elements of a tree in pre-order. findWithDefault findWithDefault ::  Ord k => a -> k -> Map k a -> a"!OrdkakMapkaa:O(log n). The expression (findWithDefault def k map) returns the value at key k or returns default value def when the key is not in the map. 
findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
findWithDefault findWithDefault :: a -> Key -> IntMap a -> a##aKeyIntMapaa:O(min(n,W)). The expression (findWithDefault def k map) returns the value at key k or returns def when the key is not an element of the map. 
findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
findMinfindMin :: Set a -> aY%I%Setaa/O(log n). The minimal element of a set. findMinfindMin :: Map k a -> (k, a)%%Mapka(,)kaO(log n). The minimal key of the map. Calls error is the map is empty. 
findMin (fromList [(5,"a"), (3,"b")]) == (3,"b")
findMin empty                            Error: empty map has no minimal element
findMinfindMin :: IntSet -> Int.''IntSetInt2O(min(n,W)). The minimal element of a set. findMinfindMin :: IntMap a -> a''IntMapaa-O(log n). The minimal key of the map. findMaxfindMax :: Set a -> a=(-(Setaa/O(log n). The maximal element of a set. findMaxfindMax :: Map k a -> (k, a)((Mapka(,)kaO(log n). The maximal key of the map. Calls error is the map is empty. 
findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
findMax empty                            Error: empty map has no maximal element
findMaxfindMax :: IntSet -> Int**IntSetInt2O(min(n,W)). The maximal element of a set. findMaxfindMax :: IntMap a -> a**IntMapaa-O(log n). The maximal key of the map.  findIndex findIndex ::  Ord k => k -> Map k a -> IntQ+/+OrdkkMapkaIntO(log n). Return the index of a key. The index is a number from 0 up to, but not including, the size of the map. Calls error when the key is not a member of the map. 
findIndex 2 (fromList [(5,"a"), (3,"b")])    Error: element is not in the map
findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0
findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1
findIndex 6 (fromList [(5,"a"), (3,"b")])    Error: element is not in the map
 filterWithKey filterWithKey ::  Ord k => (k -> a -> Bool) -> Map k a -> Map k a--OrdkkaBoolMapkaMapkaO(n). Filter all keys/values that satisfy the predicate. 
filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
 filterWithKey filterWithKey :: (Key -> a -> Bool) -> IntMap a -> IntMap a%/.KeyaBoolIntMapaIntMapaO(n). Filter all keys/values that satisfy some predicate. 
filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
filterfilter ::  Ord a =>  (a -> Bool) -> Set a -> Set a\000OrdaaBoolSetaSeta=O(n). Filter all elements that satisfy the predicate. filterfilter ::  Ord k =>  (a -> Bool) -> Map k a -> Map k a611OrdkaBoolMapkaMapkaO(n). Filter all values that satisfy the predicate. 
filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty
filterfilter ::  (Int -> Bool) -> IntSet -> IntSet22IntBoolIntSetIntSet>O(n). Filter all elements that satisfy some predicate. filterfilter ::  (a -> Bool) -> IntMap a -> IntMap a3X3aBoolIntMapaIntMapaO(n). Filter all values that satisfy some predicate. 
filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty
EmptyREmptyR :: ViewR a44ViewRaempty sequence EmptyLEmptyL :: ViewL a5 5ViewLaempty sequence emptyempty :: Set af5[5SetaO(1). The empty set. emptyempty :: Seq a55Seqa!O(1). The empty sequence. emptyempty :: Map k a&66MapkaTO(1). The empty map. 
empty      == fromList []
size empty == 0
emptyempty :: IntSet66IntSetO(1). The empty set. emptyempty :: IntMap a7 7IntMapaTO(1). The empty map. 
empty      == fromList []
size empty == 0
elemselems :: Set a -> [a]77Seta[]a$O(n). The elements of a set. elemselems :: Map k a -> [a]H8/8Mapka[]aO(n). Return all elements of the map in the ascending order of their keys. 
elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
elems empty == []
elemselems :: IntSet -> [Int]G919IntSet[]IntMO(n). The elements of a set. (For sets, this is equivalent to toList) elemselems :: IntMap a -> [a]99IntMapa[]aO(n). Return all elements of the map in the ascending order of their keys. 
elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
elems empty == []
elemAtelemAt :: Int -> Map k a -> (k, a);:IntMapka(,)kaO(log n). Retrieve an element by index. Calls error when an invalid index is used. 
elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b")
elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a")
elemAt 2 (fromList [(5,"a"), (3,"b")])    Error: index out of range
edgesedges :: Graph -> [Edge]<v<Graph[]EdgeAll edges of a graph. Edgetype Edge = (Vertex, Vertex)<-An edge from the first vertex to the second. dropdrop :: Int -> Seq a -> Seq a~=b=IntSeqaSeqaO(log(min(i,n-i))). Elements of a sequence after the first i. If i is negative, take i s yields the whole sequence. If the sequence contains fewer than i elements, the empty sequence is returned. drawTreedrawTree ::  Tree String -> String>>TreeStringString&Neat 2-dimensional drawing of a tree.  drawForest drawForest ::  Forest String -> String|?_?ForestStringString(Neat 2-dimensional drawing of a forest. differenceWithKey differenceWithKey ::  Ord k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a@E@OrdkkabMaybeaMapkaMapkbMapkaO(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y. The implementation uses an efficient hedge algorithm comparable with hedge-union. 
let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
    == singleton 3 "3:b|B"
differenceWithKey differenceWithKey :: (Key -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap aCCKeyabMaybeaIntMapaIntMapbIntMapa%O(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y. 
let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
    == singleton 3 "3:b|B"
differenceWith differenceWith ::  Ord k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k aFFOrdkabMaybeaMapkaMapkbMapkakO(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y. The implementation uses an efficient hedge algorithm comparable with hedge-union. 
let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
    == singleton 3 "b:B"
differenceWith differenceWith :: (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a1JIabMaybeaIntMapaIntMapbIntMapaO(n+m). Difference with a combining function. 
let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
    == singleton 3 "b:B"
 difference difference ::  Ord a => Set a -> Set a -> Set aKKOrdaSetaSetaSetaO(n+m). Difference of two sets. The implementation uses an efficient hedge algorithm comparable with hedge-union.  difference difference ::  Ord k => Map k a -> Map k b -> Map k aLLOrdkMapkaMapkbMapka4O(n+m). Difference of two maps. Return elements of the first map not existing in the second map. The implementation uses an efficient hedge algorithm comparable with hedge-union. 
difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
 difference difference :: IntSet -> IntSet -> IntSetNNIntSetIntSetIntSet,O(n+m). Difference between two sets.  difference difference :: IntMap a -> IntMap b -> IntMap a[O1OIntMapaIntMapbIntMapaO(n+m). Difference between two maps (based on keys). 
difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
dfsdfs :: Graph -> [Vertex] ->  Forest VertexP`PGraph[]VertexForestVertexA spanning forest of the part of the graph reachable from the listed vertices, obtained from a depth-first search of the graph starting at each of the listed vertices in order. dffdff :: Graph ->  Forest VertexQQGraphForestVertexA spanning forest of the graph, obtained from a depth-first search of the graph starting from each vertex in an unspecified order.  deleteMin deleteMin :: Set a -> Set aRpRSetaSeta-O(log n). Delete the minimal element.  deleteMin deleteMin :: Map k a -> Map k a"SSMapkaMapkaO(log n). Delete the minimal key. Returns an empty map if the map is empty. 
deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")]
deleteMin empty == empty
 deleteMin deleteMin :: IntSet -> IntSetNT;TIntSetIntSet0O(min(n,W)). Delete the minimal element.  deleteMin deleteMin :: IntMap a -> IntMap aTTIntMapaIntMapa)O(log n). Delete the minimal key.  deleteMax deleteMax :: Set a -> Set a{UdUSetaSeta-O(log n). Delete the maximal element.  deleteMax deleteMax :: Map k a -> Map k aVUMapkaMapkaO(log n). Delete the maximal key. Returns an empty map if the map is empty. 
deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
deleteMax empty == empty
 deleteMax deleteMax :: IntSet -> IntSetBW/WIntSetIntSet0O(min(n,W)). Delete the maximal element.  deleteMax deleteMax :: IntMap a -> IntMap aWWIntMapaIntMapa)O(log n). Delete the maximal key.  deleteFindMin deleteFindMin :: Set a ->  (a, Set a)XeXSeta(,)aSetauO(log n). Delete and find the minimal element. 
deleteFindMin set = (findMin set, deleteMin set)
 deleteFindMin deleteFindMin :: Map k a -> ((k, a), Map k a)Y^YMapka(,)(,)kaMapkaO(log n). Delete and find the minimal element. 
deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) 
deleteFindMin                                            Error: can not return the minimal element of an empty map
 deleteFindMin deleteFindMin :: IntSet ->  (Int, IntSet)$[[IntSet(,)IntIntSetxO(min(n,W)). Delete and find the minimal element. 
deleteFindMin set = (findMin set, deleteMin set)
 deleteFindMin deleteFindMin :: IntMap a ->  (a, IntMap a)#\[IntMapa(,)aIntMapa6O(log n). Delete and find the minimal element.  deleteFindMax deleteFindMax :: Set a ->  (a, Set a)\\Seta(,)aSetauO(log n). Delete and find the maximal element. 
deleteFindMax set = (findMax set, deleteMax set)
 deleteFindMax deleteFindMax :: Map k a -> ((k, a), Map k a)]]Mapka(,)(,)kaMapkaO(log n). Delete and find the maximal element. 
deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
deleteFindMax empty                                      Error: can not return the maximal element of an empty map
 deleteFindMax deleteFindMax :: IntSet ->  (Int, IntSet)r_S_IntSet(,)IntIntSetxO(min(n,W)). Delete and find the maximal element. 
deleteFindMax set = (findMax set, deleteMax set)
 deleteFindMax deleteFindMax :: IntMap a ->  (a, IntMap a)q`J`IntMapa(,)aIntMapa6O(log n). Delete and find the maximal element. deleteAtdeleteAt :: Int -> Map k a -> Map k a'aaIntMapkaMapkaO(log n). Delete the element at index. Defined as (deleteAt i map = updateAt (k x -> Nothing) i map). 
deleteAt 0  (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
deleteAt 1  (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
deleteAt 2 (fromList [(5,"a"), (3,"b")])     Error: index out of range
deleteAt (-1) (fromList [(5,"a"), (3,"b")])  Error: index out of range
deletedelete ::  Ord a => a -> Set a -> Set aSc/cOrdaaSetaSeta/O(log n). Delete an element from a set. deletedelete ::  Ord k => k -> Map k a -> Map k a dcOrdkkMapkaMapkaAO(log n). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned. 
delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
delete 5 empty                         == empty
deletedelete :: Int -> IntSet -> IntSeteeIntIntSetIntSethO(min(n,W)). Delete a value in the set. Returns the original set when the value was not present. deletedelete :: Key -> IntMap a -> IntMap affKeyIntMapaIntMapaDO(min(n,W)). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned. 
delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
delete 5 empty                         == empty
 CyclicSCC CyclicSCC :: [vertex] ->  SCC vertex]h=h[]vertexSCCvertex.A maximal set of mutually reachable vertices.  components components :: Graph ->  Forest VertexhhGraphForestVertexThe connected components of a graph. Two vertices are connected if there is a path between them, traversing edges in either direction. buildGbuildG :: Bounds -> [Edge] -> GraphiiBounds[]EdgeGraph$Build a graph from a list of edges. Boundstype Bounds = (Vertex, Vertex)fjThe bounds of a Table. bccbcc :: Graph -> Forest [Vertex]jjGraphForest[]Vertex}The biconnected components of a graph. An undirected graph is biconnected if the deletion of any vertex leaves it connected. assocsassocs :: Map k a -> [(k, a)]kkMapka[](,)kaO(n). Return all key/value pairs in the map in ascending key order. 
assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
assocs empty == []
assocsassocs :: IntMap a ->  [(Key, a)]llIntMapa[](,)KeyaO(n). Return all key/value pairs in the map in ascending key order. 
assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
assocs empty == []
alter alter ::  Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k abnnOrdkMaybeaMaybeakMapkaMapkatO(log n). The expression (alter f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a Map. In short : lookup k (alter f k m) = f (lookup k m). 
let f _ = Nothing
alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"

let f _ = Just "c"
alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
alter alter :: (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap aqPqMaybeaMaybeaIntIntMapaIntMapa$O(log n). The expression (alter f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in an IntMap. In short : lookup k (alter f k m) = f (lookup k m).  adjustWithKey  adjustWithKey ::  Ord k =>  (k -> a -> a) -> k -> Map k a -> Map k ams8sOrdkkaakMapkaMapkaO(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned. 
let f key x = (show key) ++ ":new " ++ x
adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjustWithKey f 7 empty                         == empty
 adjustWithKey  adjustWithKey :: (Key -> a -> a) -> Key -> IntMap a -> IntMap auuKeyaaKeyIntMapaIntMapaO(min(n,W)). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned. 
let f key x = (show key) ++ ":new " ++ x
adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjustWithKey f 7 empty                         == empty
adjust adjust :: (a -> a) -> Int -> Seq a -> Seq awwaaIntSeqaSeqaO(log(min(i,n-i))). Update the element at the specified position. If the position is out of range, the original sequence is returned. adjust adjust ::  Ord k => (a -> a) -> k -> Map k a -> Map k a yxOrdkaakMapkaMapkaO(log n). Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned. 
adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjust ("new " ++) 7 empty                         == empty
adjust adjust :: (a -> a) -> Key -> IntMap a -> IntMap a={{aaKeyIntMapaIntMapasO(min(n,W)). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned. 
adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
adjust ("new " ++) 7 empty                         == empty
 AcyclicSCC AcyclicSCC :: vertex ->  SCC vertex}}vertexSCCvertex*A single vertex that is not in any cycle. \\ (\\) ::  Ord a => Set a -> Set a -> Set a}}OrdaSetaSetaSeta&O(n+m). See difference. \\ (\\) ::  Ord k => Map k a -> Map k b -> Map k a~^~OrdkMapkaMapkbMapkaSame as difference. \\ (\\) :: IntSet -> IntSet -> IntSet!IntSetIntSetIntSet&O(n+m). See difference. \\ (\\) :: IntMap a -> IntMap b -> IntMap aIntMapaIntMapbIntMapaSame as difference. >< (><) :: Seq a -> Seq a -> Seq abASeqaSeqaSeqa6O(log(min(n1,n2))). Concatenate two sequences. <| (<|) :: a -> Seq a -> Seq aaSeqaSeqa{O(1). Add an element to the left end of a sequence. Mnemonic: a triangle with the single element at the pointy end. :> (:>) :: Seq a -> a -> ViewR aӁSeqaaViewRaDthe sequence minus the rightmost element, and the rightmost element :< (:<) :: a -> Seq a -> ViewL aaSeqaViewLa.leftmost element and the rest of the sequence ! (!) ::  Ord k => Map k a -> k -> aH(OrdkMapkakaO(log n). Find the value at a key. Calls error when the element can not be found. 
fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
fromList [(5,'a'), (3,'b')] ! 5 == 'a'
! (!) :: IntMap a -> Key -> aoIntMapaKeyaO(min(n,W)). Find the value at a key. Calls error when the element can not be found. 
fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
fromList [(5,'a'), (3,'b')] ! 5 == 'a'
Treemodule Data.Tree5Multi-way trees (aka rose trees) and forests. Setmodule Data.SetAn efficient implementation of sets. Since many function names (but not the type name) clash with Prelude names, this module is usually imported qualified, e.g. 
import Data.Set (Set)
import qualified Data.Set as Set
The implementation of Set is based on size balanced binary trees (or trees of bounded balance) as described by:
  • Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
  • J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.
Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert. Of course, left-biasing can only be observed when equality is an equivalence relation instead of structural equality. Sequencemodule Data.SequenceGeneral purpose finite sequences. Apart from being finite and having strict operations, sequences also differ from lists in supporting a wider variety of operations efficiently. An amortized running time is given for each operation, with n referring to the length of the sequence and i being the integral index used by some operations. These bounds hold even in a persistent (shared) setting. The implementation uses 2-3 finger trees annotated with sizes, as described in section 4.2 of Note: Many of these operations have the same names as similar operations on lists in the Prelude. The ambiguity may be resolved using either qualification or the hiding clause. Mapmodule Data.MapߍAn efficient implementation of maps from keys to values (dictionaries). Since many function names (but not the type name) clash with Prelude names, this module is usually imported qualified, e.g. 
import Data.Map (Map)
import qualified Data.Map as Map
The implementation of Map is based on size balanced binary trees (or trees of bounded balance) as described by:
  • Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
  • J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.
Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert. Operation comments contain the operation time complexity in the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation. IntSetmodule Data.IntSet"An efficient implementation of integer sets. Since many function names (but not the type name) clash with Prelude names, this module is usually imported qualified, e.g. 
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
The implementation is based on big-endian patricia trees. This data structure performs especially well on binary operations like union and intersection. However, my benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced set implementation (see Data.Set).
  • Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps", Workshop on ML, September 1998, pages 77-86, http://citeseer.ist.psu.edu/okasaki98fast.html
  • D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/", Journal of the ACM, 15(4), October 1968, pages 514-534.
Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W -- the number of bits in an Int (32 or 64). IntMapmodule Data.IntMap5An efficient implementation of maps from integer keys to values. Since many function names (but not the type name) clash with Prelude names, this module is usually imported qualified, e.g. 
import Data.IntMap (IntMap)
import qualified Data.IntMap as IntMap
The implementation is based on big-endian patricia trees. This data structure performs especially well on binary operations like union and intersection. However, my benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced map implementation (see Data.Map).
  • Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps", Workshop on ML, September 1998, pages 77-86, http://citeseer.ist.psu.edu/okasaki98fast.html
  • D.R. Morrison, "/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/", Journal of the ACM, 15(4), October 1968, pages 514-534.
Operation comments contain the operation time complexity in the Big-O notation http://en.wikipedia.org/wiki/Big_O_notation. Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W -- the number of bits in an Int (32 or 64). Graphmodule Data.GraphYA version of the graph algorithms described in: Lazy Depth-First Search and Linear Graph Algorithms in Haskell, by David King and John Launchbury. containerspackage  containers'Assorted concrete container types This package contains efficient general-purpose implementations of various basic immutable container types. The declared cost of each operation is either worst-case or amortized, but remains valid even if structures are shared. xk^RDataGraphDataIntMapDataIntSetDataMapDataTreeDataSequenceDataSet containers0.2.0.1Hhttp://hackage.haskell.org/packages/archive/containers/0.2.0.1/doc/html/Ehttp://hackage.haskell.org/cgi-bin/hackage-scripts/package/containers