ghc/docs/users_guide/libmisc.vsgml

   1 %************************************************************************
   2 %*                                                                      *
   3 <sect1>Miscellaneous libraries
   4 <label id="GHC-library">
   5 <p>
   6 <nidx>libraries, miscellaneous</nidx>
   7 <nidx>misc, syslib</nidx>
   8 %*                                                                      *
   9 %************************************************************************
  10
  11 This section describes a collection of Haskell libraries we've
  12 collected over the years.  Access to any of these modules is provided
  13 by giving the @-syslib misc@<nidx>-syslib misc option</nidx>.
  14
  15 %************************************************************************
  16 %*                                                                      *
  17 <sect2>The @Bag@ type
  18 <label id="Bag">
  19 <p>
  20 <nidx>Bag module (GHC syslib)</nidx>
  21 %*                                                                      *
  22 %************************************************************************
  23
  24 A <em>bag</em> is an unordered collection of elements which may contain
  25 duplicates.  To use, @import Bag@.
  26
  27 <tscreen><verb>
  28 data Bag elt    -- abstract
  29
  30 emptyBag        :: Bag elt
  31 unitBag         :: elt -> Bag elt
  32
  33 consBag         :: elt       -> Bag elt -> Bag elt
  34 snocBag         :: Bag elt   -> elt     -> Bag elt
  35
  36 unionBags       :: Bag elt   -> Bag elt -> Bag elt
  37 unionManyBags   :: [Bag elt] -> Bag elt
  38
  39 isEmptyBag      :: Bag elt   -> Bool
  40 elemBag         :: Eq elt => elt -> Bag elt -> Bool
  41
  42 filterBag       :: (elt -> Bool) -> Bag elt -> Bag elt
  43 partitionBag    :: (elt -> Bool) -> Bag elt-> (Bag elt, Bag elt)
  44         -- returns the elements that do/don't satisfy the predicate
  45
  46 concatBag       :: Bag (Bag a) -> Bag a
  47 foldBag         :: (r -> r -> r) -> (a -> r) -> r -> Bag a -> r
  48 mapBag          :: (a -> b) -> Bag a -> Bag b
  49
  50 listToBag       :: [elt] -> Bag elt
  51 bagToList       :: Bag elt -> [elt]
  52 </verb></tscreen>
  53
  54 %************************************************************************
  55 %*                                                                      *
  56 <sect2>The @FiniteMap@ type
  57 <label id="FiniteMap">
  58 <p>
  59 <nidx>FiniteMap module (GHC syslib)</nidx>
  60 %*                                                                      *
  61 %************************************************************************
  62
  63 What functional programmers call a <em>finite map</em>, everyone else
  64 calls a <em>lookup table</em>.
  65
  66 Out code is derived from that in this paper:
  67 <quote>
  68 S Adams
  69 "Efficient sets: a balancing act"
  70 Journal of functional programming 3(4) Oct 1993, pages 553-562
  71 </quote>
  72 Guess what?  The implementation uses balanced trees.
  73
  74 <tscreen><verb>
  75 data FiniteMap key elt  -- abstract
  76
  77 --      BUILDING
  78 emptyFM         :: FiniteMap key elt
  79 unitFM          :: key -> elt -> FiniteMap key elt
  80 listToFM        :: Ord key => [(key,elt)] -> FiniteMap key elt
  81                         -- In the case of duplicates, the last is taken
  82
  83 --      ADDING AND DELETING
  84                    -- Throws away any previous binding
  85                    -- In the list case, the items are added starting with the
  86                    -- first one in the list
  87 addToFM         :: Ord key => FiniteMap key elt -> key -> elt  -> FiniteMap key elt
  88 addListToFM     :: Ord key => FiniteMap key elt -> [(key,elt)] -> FiniteMap key elt
  89
  90                  -- Combines with previous binding
  91                  -- In the combining function, the first argument is
  92                  -- the "old" element, while the second is the "new" one.
  93 addToFM_C       :: Ord key => (elt -> elt -> elt)
  94                            -> FiniteMap key elt -> key -> elt
  95                            -> FiniteMap key elt
  96 addListToFM_C   :: Ord key => (elt -> elt -> elt)
  97                            -> FiniteMap key elt -> [(key,elt)]
  98                            -> FiniteMap key elt
  99
 100                  -- Deletion doesn't complain if you try to delete something
 101                  -- which isn't there
 102 delFromFM       :: Ord key => FiniteMap key elt -> key   -> FiniteMap key elt
 103 delListFromFM   :: Ord key => FiniteMap key elt -> [key] -> FiniteMap key elt
 104
 105 --      COMBINING
 106                  -- Bindings in right argument shadow those in the left
 107 plusFM          :: Ord key => FiniteMap key elt -> FiniteMap key elt
 108                            -> FiniteMap key elt
 109
 110                    -- Combines bindings for the same thing with the given function
 111 plusFM_C        :: Ord key => (elt -> elt -> elt)
 112                            -> FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
 113
 114 minusFM         :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
 115                    -- (minusFM a1 a2) deletes from a1 any bindings which are bound in a2
 116
 117 intersectFM     :: Ord key => FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
 118 intersectFM_C   :: Ord key => (elt -> elt -> elt)
 119                            -> FiniteMap key elt -> FiniteMap key elt -> FiniteMap key elt
 120
 121 --      MAPPING, FOLDING, FILTERING
 122 foldFM          :: (key -> elt -> a -> a) -> a -> FiniteMap key elt -> a
 123 mapFM           :: (key -> elt1 -> elt2) -> FiniteMap key elt1 -> FiniteMap key elt2
 124 filterFM        :: Ord key => (key -> elt -> Bool)
 125                            -> FiniteMap key elt -> FiniteMap key elt
 126
 127 --      INTERROGATING
 128 sizeFM          :: FiniteMap key elt -> Int
 129 isEmptyFM       :: FiniteMap key elt -> Bool
 130
 131 elemFM          :: Ord key => key -> FiniteMap key elt -> Bool
 132 lookupFM        :: Ord key => FiniteMap key elt -> key -> Maybe elt
 133 lookupWithDefaultFM
 134                 :: Ord key => FiniteMap key elt -> elt -> key -> elt
 135                 -- lookupWithDefaultFM supplies a "default" elt
 136                 -- to return for an unmapped key
 137
 138 --      LISTIFYING
 139 fmToList        :: FiniteMap key elt -> [(key,elt)]
 140 keysFM          :: FiniteMap key elt -> [key]
 141 eltsFM          :: FiniteMap key elt -> [elt]
 142 </verb></tscreen>
 143
 144 %************************************************************************
 145 %*                                                                      *
 146 <sect2>The @ListSetOps@ type
 147 <label id="ListSetOps">
 148 <p>
 149 <nidx>ListSetOps module (GHC syslib)</nidx>
 150 %*                                                                      *
 151 %************************************************************************
 152
 153 Just a few set-sounding operations on lists.  If you want sets, use
 154 the @Set@ module.
 155
 156 <tscreen><verb>
 157 unionLists          :: Eq a => [a] -> [a] -> [a]
 158 intersectLists      :: Eq a => [a] -> [a] -> [a]
 159 minusList           :: Eq a => [a] -> [a] -> [a]
 160 disjointLists       :: Eq a => [a] -> [a] -> Bool
 161 intersectingLists   :: Eq a => [a] -> [a] -> Bool
 162 </verb></tscreen>
 163
 164 %************************************************************************
 165 %*                                                                      *
 166 <sect2>The @Maybes@ type
 167 <label id="Maybes">
 168 <p>
 169 <nidx>Maybes module (GHC syslib)</nidx>
 170 %*                                                                      *
 171 %************************************************************************
 172
 173 The @Maybe@ type is in the Haskell 1.4 prelude. Moreover, the
 174 required @Maybe@ library provides many useful functions on
 175 @Maybe@s. This (pre-1.3) module provides some more:
 176
 177 An @Either@-like type called @MaybeErr@:
 178 <tscreen><verb>
 179 data MaybeErr val err = Succeeded val | Failed err
 180 </verb></tscreen>
 181
 182 Some operations to do with @Maybe@ (some commentary follows):
 183 <tscreen><verb>
 184 maybeToBool :: Maybe a -> Bool      -- Nothing => False; Just => True
 185 allMaybes   :: [Maybe a] -> Maybe [a]
 186 firstJust   :: [Maybe a] -> Maybe a
 187 findJust    :: (a -> Maybe b) -> [a] -> Maybe b
 188
 189 assocMaybe  :: Eq a => [(a,b)] -> a -> Maybe b
 190 mkLookupFun :: (key -> key -> Bool) -- Equality predicate
 191             -> [(key,val)]          -- The assoc list
 192             -> (key -> Maybe val)   -- A lookup fun to use
 193 mkLookupFunDef :: (key -> key -> Bool)  -- Equality predicate
 194                -> [(key,val)]           -- The assoc list
 195                -> val                   -- Value to return on failure
 196                -> key                   -- The key
 197                -> val                   -- The corresponding value
 198
 199     -- a monad thing
 200 thenMaybe   :: Maybe a -> (a -> Maybe b) -> Maybe b
 201 returnMaybe :: a -> Maybe a
 202 failMaybe   :: Maybe a
 203 mapMaybe    :: (a -> Maybe b) -> [a] -> Maybe [b]
 204 </verb></tscreen>
 205
 206 NB: @catMaybes@ which used to be here, is now available via the
 207 standard @Maybe@ interface (@Maybe@ is an instance of @MonadPlus@).
 208
 209 @allMaybes@ collects a list of @Justs@ into a single @Just@, returning
 210 @Nothing@ if there are any @Nothings@.
 211
 212 @firstJust@ takes a list of @Maybes@ and returns the
 213 first @Just@ if there is one, or @Nothing@ otherwise.
 214
 215 @assocMaybe@ looks up in an association list, returning
 216 @Nothing@ if it fails.
 217
 218 Now, some operations to do with @MaybeErr@ (comments follow):
 219 <tscreen><verb>
 220     -- a monad thing (surprise, surprise)
 221 thenMaB   :: MaybeErr a err -> (a -> MaybeErr b err) -> MaybeErr b err
 222 returnMaB :: val -> MaybeErr val err
 223 failMaB   :: err -> MaybeErr val err
 224
 225 listMaybeErrs :: [MaybeErr val err] -> MaybeErr [val] [err]
 226 foldlMaybeErrs :: (acc -> input -> MaybeErr acc err)
 227                -> acc
 228                -> [input]
 229                -> MaybeErr acc [err]
 230 </verb></tscreen>
 231
 232 @listMaybeErrs@ takes a list of @MaybeErrs@ and, if they all succeed,
 233 returns a @Succeeded@ of a list of their values.  If any fail, it
 234 returns a @Failed@ of the list of all the errors in the list.
 235
 236 @foldlMaybeErrs@ works along a list, carrying an accumulator; it
 237 applies the given function to the accumulator and the next list item,
 238 accumulating any errors that occur.
 239
 240 %************************************************************************
 241 %*                                                                      *
 242 <sect2>The @Memo@ library
 243 <label id="memo-library">
 244 <p>
 245 <nidx>Memo (GHC syslib)</nidx>
 246 %*                                                                      *
 247 %************************************************************************
 248
 249 The @Memo@ library provides fast polymorphic memo functions using hash
 250 tables.  The interface is:
 251
 252 <tscreen><verb>
 253 memo :: (a -> b) -> a -> b
 254 </verb></tscreen>
 255
 256 So, for example, @memo f@ is a version of @f@ that caches the results
 257 of previous calls.
 258
 259 The searching is very fast, being based on pointer equality.  One
 260 consequence of this is that the caching will only be effective if
 261 <em/exactly the same argument is passed again to the memoised
 262 function/.  This means not just a copy of a previous argument, but the
 263 same instance.  It's not useful to memoise integer functions using
 264 this interface, because integers are generally copied a lot and two
 265 instances of '27' are unlikely to refer to the same object.
 266
 267 This memoisation library works well when the keys are large (or even
 268 infinite).
 269
 270 The memo table implementation uses weak pointers and stable names (see
 271 the GHC/Hugs library document) to avoid space leaks and allow hashing
 272 for arbitrary Haskell objects.  NOTE: while individual memo table
 273 entries will be garbage collected if the associated key becomes
 274 garbage, the memo table itself will not be collected if the function
 275 becomes garbage.  We plan to fix this in a future version.
 276
 277 There's another version of @memo@ if you want to explicitly give a
 278 size for the hash table (the default size is 1001 buckets):
 279
 280 <tscreen><verb>
 281 memo_sized :: Int -> (a -> b) -> a -> b
 282 </verb></tscreen>
 283
 284 %************************************************************************
 285 %*                                                                      *
 286 <sect2>The @PackedString@ type
 287 <label id="PackedString">
 288 <p>
 289 <nidx>PackedString module (GHC syslib)</nidx>
 290 %*                                                                      *
 291 %************************************************************************
 292
 293 You need to @import PackedString@ and heave in your
 294 @-syslib ghc@ to use @PackedString@s.
 295
 296 The basic type and functions available are:
 297 <tscreen><verb>
 298 data PackedString -- abstract
 299
 300 packString          :: [Char] -> PackedString
 301 packStringST        :: [Char] -> ST s PackedString
 302 packCBytesST        :: Int -> Addr -> ST s PackedString
 303 packBytesForCST     :: [Char] -> ST s (ByteArray Int)
 304 byteArrayToPS       :: ByteArray Int -> PackedString
 305 unsafeByteArrayToPS :: ByteArray a   -> Int -> PackedString
 306 psToByteArray       :: PackedString -> ByteArray Int
 307 psToByteArrayST     :: PackedString -> ST s (ByteArray Int)
 308
 309 unpackPS        :: PackedString -> [Char]
 310 </verb></tscreen>
 311
 312 We also provide a wad of list-manipulation-like functions:
 313 <tscreen><verb>
 314 nilPS       :: PackedString
 315 consPS      :: Char -> PackedString -> PackedString
 316
 317 headPS      :: PackedString -> Char
 318 tailPS      :: PackedString -> PackedString
 319 nullPS      :: PackedString -> Bool
 320 appendPS    :: PackedString -> PackedString -> PackedString
 321 lengthPS    :: PackedString -> Int
 322 indexPS     :: PackedString -> Int -> Char
 323             -- 0-origin indexing into the string
 324 mapPS       :: (Char -> Char) -> PackedString -> PackedString
 325 filterPS    :: (Char -> Bool) -> PackedString -> PackedString
 326 foldlPS     :: (a -> Char -> a) -> a -> PackedString -> a
 327 foldrPS     :: (Char -> a -> a) -> a -> PackedString -> a
 328 takePS      :: Int -> PackedString -> PackedString
 329 dropPS      :: Int -> PackedString -> PackedString
 330 splitAtPS   :: Int -> PackedString -> (PackedString, PackedString)
 331 takeWhilePS :: (Char -> Bool) -> PackedString -> PackedString
 332 dropWhilePS :: (Char -> Bool) -> PackedString -> PackedString
 333 spanPS      :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
 334 breakPS     :: (Char -> Bool) -> PackedString -> (PackedString, PackedString)
 335 linesPS     :: PackedString -> [PackedString]
 336 wordsPS     :: PackedString -> [PackedString]
 337 reversePS   :: PackedString -> PackedString
 338 concatPS    :: [PackedString] -> PackedString
 339 elemPS      :: Char -> PackedString -> Bool
 340   -- Perl-style split&join
 341 splitPS     :: Char -> PackedString -> [PackedString]
 342 splitWithPS :: (Char -> Bool) -> PackedString -> [PackedString]
 343 joinPS      :: PackedString -> [PackedString] -> PackedString
 344
 345 substrPS   :: PackedString -> Int -> Int -> PackedString
 346            -- pluck out a piece of a PackedString
 347            -- start and end chars you want; both 0-origin-specified
 348 </verb></tscreen>
 349
 350 %************************************************************************
 351 %*                                                                      *
 352 <sect2>The @Pretty@ type
 353 <label id="Pretty">
 354 <p>
 355 <nidx>Pretty module (GHC syslib)</nidx>
 356 %*                                                                      *
 357 %************************************************************************
 358
 359 This is the pretty-printer that is currently used in GHC:
 360
 361 <tscreen><verb>
 362 type Pretty
 363
 364 ppShow          :: Int{-width-} -> Pretty -> [Char]
 365
 366 pp'SP           :: Pretty -- "comma space"
 367 ppComma         :: Pretty -- ,
 368 ppEquals        :: Pretty -- =
 369 ppLbrack        :: Pretty -- [
 370 ppLparen        :: Pretty -- (
 371 ppNil           :: Pretty -- nothing
 372 ppRparen        :: Pretty -- )
 373 ppRbrack        :: Pretty -- ]
 374 ppSP            :: Pretty -- space
 375 ppSemi          :: Pretty -- ;
 376
 377 ppChar          :: Char -> Pretty
 378 ppDouble        :: Double -> Pretty
 379 ppFloat         :: Float -> Pretty
 380 ppInt           :: Int -> Pretty
 381 ppInteger       :: Integer -> Pretty
 382 ppRational      :: Rational -> Pretty
 383 ppStr           :: [Char] -> Pretty
 384
 385 ppAbove         :: Pretty -> Pretty -> Pretty
 386 ppAboves        :: [Pretty] -> Pretty
 387 ppBeside        :: Pretty -> Pretty -> Pretty
 388 ppBesides       :: [Pretty] -> Pretty
 389 ppCat           :: [Pretty] -> Pretty
 390 ppHang          :: Pretty -> Int -> Pretty -> Pretty
 391 ppInterleave    :: Pretty -> [Pretty] -> Pretty -- spacing between
 392 ppIntersperse   :: Pretty -> [Pretty] -> Pretty -- no spacing between
 393 ppNest          :: Int -> Pretty -> Pretty
 394 ppSep           :: [Pretty] -> Pretty
 395 </verb></tscreen>
 396
 397 %************************************************************************
 398 %*                                                                      *
 399 <sect2>The @Set@ type
 400 <label id="Set">
 401 <p>
 402 <nidx>Set module (GHC syslib)</nidx>
 403 %*                                                                      *
 404 %************************************************************************
 405
 406 Our implementation of <em>sets</em> (key property: no duplicates) is just
 407 a variant of the @FiniteMap@ module.
 408
 409 <tscreen><verb>
 410 data Set        -- abstract
 411                 -- instance of: Eq
 412
 413 emptySet        :: Set a
 414 mkSet           :: Ord a => [a]  -> Set a
 415 setToList       :: Set a -> [a]
 416 unitSet         :: a -> Set a
 417 singletonSet    :: a -> Set a  -- deprecated, use unitSet.
 418
 419 union           :: Ord a => Set a -> Set a -> Set a
 420 unionManySets   :: Ord a => [Set a] -> Set a
 421 minusSet        :: Ord a => Set a -> Set a -> Set a
 422 mapSet          :: Ord a => (b -> a) -> Set b -> Set a
 423 intersect       :: Ord a => Set a -> Set a -> Set a
 424
 425 elementOf       :: Ord a => a -> Set a -> Bool
 426 isEmptySet      :: Set a -> Bool
 427
 428 cardinality     :: Set a -> Int
 429
 430 </verb></tscreen>
 431
 432 %************************************************************************
 433 %*                                                                      *
 434 <sect2>The @BitSet@ interface
 435 <label id="BitSet">
 436 <p>
 437 <nidx>Bitset interface (GHC syslib)</nidx>
 438 %*                                                                      *
 439 %************************************************************************
 440
 441 Bit sets are a fast implementation of sets of integers ranging from 0
 442 to one less than the number of bits in a machine word (typically 31).
 443 If any element exceeds the maximum value for a particular machine
 444 architecture, the results of these operations are undefined.  You have
 445 been warned.
 446
 447 <tscreen><verb>
 448 data BitSet   -- abstract
 449               -- instance of:
 450
 451 emptyBS       :: BitSet
 452 mkBS          :: [Int] -> BitSet
 453 unitBS        :: Int -> BitSet
 454 unionBS       :: BitSet -> BitSet -> BitSet
 455 minusBS       :: BitSet -> BitSet -> BitSet
 456 isEmptyBS     :: BitSet -> Bool
 457 intersectBS   :: BitSet -> BitSet -> BitSet
 458 elementBS     :: Int -> BitSet -> Bool
 459 listBS        :: BitSet -> [Int]
 460 </verb></tscreen>
 461
 462 %************************************************************************
 463 %*                                                                      *
 464 <sect2>The @Util@ type
 465 <label id="Util">
 466 <p>
 467 <nidx>Util module (GHC syslib)</nidx>
 468 %*                                                                      *
 469 %************************************************************************
 470
 471 Stuff that has been generally useful to use in writing the compiler.
 472 Don't be too surprised if this stuff moves/gets-renamed/etc.
 473
 474 <tscreen><verb>
 475 -- general list processing
 476 forall          :: (a -> Bool) -> [a] -> Bool
 477 exists          :: (a -> Bool) -> [a] -> Bool
 478
 479 nOfThem         :: Int -> a -> [a]
 480 lengthExceeds   :: [a] -> Int -> Bool
 481 isSingleton     :: [a] -> Bool
 482
 483 --paranoid zip'ing (equal length lists)
 484 zipEqual        :: [a] -> [b] -> [(a,b)]
 485 zipWithEqual    :: String -> (a->b->c) -> [a]->[b]->[c]
 486 zipWith3Equal   :: String -> (a->b->c->d) -> [a]->[b]->[c]->[d]
 487 zipWith4Equal   :: String -> (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
 488 -- lazy in second argument
 489 zipLazy :: [a] -> [b] -> [(a,b)]
 490
 491 mapAndUnzip :: (a -> (b, c)) -> [a] -> ([b], [c])
 492 mapAndUnzip3 :: (a -> (b, c, d)) -> [a] -> ([b], [c], [d])
 493
 494 -- prefix and suffix matching on lists of characters.
 495 startsWith :: {-prefix-}String -> String -> Maybe String
 496 endsWith   :: {-suffix-}String -> String -> Maybe String
 497
 498 -- association lists
 499 assoc       :: Eq a => String -> [(a, b)] -> a -> b
 500
 501 -- duplicate handling
 502 hasNoDups    :: Eq a => [a] -> Bool
 503 equivClasses :: (a -> a -> Ordering) -> [a] -> [[a]]
 504 runs         :: (a -> a -> Bool)     -> [a] -> [[a]]
 505 removeDups   :: (a -> a -> Ordering) -> [a] -> ([a], [[a]])
 506
 507 -- sorting (don't complain of no choice...)
 508 quicksort          :: (a -> a -> Bool)     -> [a] -> [a]
 509 sortLt             :: (a -> a -> Bool)     -> [a] -> [a]
 510 stableSortLt       :: (a -> a -> Bool)     -> [a] -> [a]
 511 mergesort          :: (a -> a -> _CMP_TAG) -> [a] -> [a]
 512 mergeSort          :: Ord a => [a] -> [a]
 513 naturalMergeSort   :: Ord a => [a] -> [a]
 514 mergeSortLe        :: Ord a => [a] -> [a]
 515 naturalMergeSortLe :: Ord a => [a] -> [a]
 516
 517 -- transitive closures
 518 transitiveClosure :: (a -> [a])         -- Successor function
 519                   -> (a -> a -> Bool)   -- Equality predicate
 520                   -> [a]
 521                   -> [a]                -- The transitive closure
 522
 523 -- accumulating (Left, Right, Bi-directional)
 524 mapAccumL :: (acc -> x -> (acc, y))
 525                         -- Function of elt of input list and
 526                         -- accumulator, returning new accumulator and
 527                         -- elt of result list
 528           -> acc        -- Initial accumulator
 529           -> [x]        -- Input list
 530           -> (acc, [y]) -- Final accumulator and result list
 531
 532 mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
 533
 534 mapAccumB :: (accl -> accr -> x -> (accl, accr,y))
 535           -> accl -> accr -> [x]
 536           -> (accl, accr, [y])
 537
 538 --list comparison with explicit element comparer.
 539 cmpList :: (a -> a -> Ordering) -> [a] -> [a] -> Ordering
 540
 541 -- pairs
 542 applyToPair :: ((a -> c), (b -> d)) -> (a, b) -> (c, d)
 543 applyToFst  :: (a -> c) -> (a, b) -> (c, b)
 544 applyToSnd  :: (b -> d) -> (a, b) -> (a, d)
 545 foldPair    :: (a->a->a, b->b->b) -> (a, b) -> [(a, b)] -> (a, b)
 546 unzipWith   :: (a -> b -> c) -> [(a, b)] -> [c]
 547 </verb></tscreen>
 548
 549 %************************************************************************
 550 %*                                                                      *
 551 <sect1>Interfaces to C libraries
 552 <label id="C-interfaces">
 553 <p>
 554 <nidx>C library interfaces</nidx>
 555 <nidx>interfaces, C library</nidx>
 556 %*                                                                      *
 557 %************************************************************************
 558
 559 The GHC system library (@-syslib misc@) also provides interfaces to
 560 several useful C libraries, mostly from the GNU project.
 561
 562 %************************************************************************
 563 %*                                                                      *
 564 <sect2>The @Readline@ interface
 565 <label id="Readline">
 566 <p>
 567 <nidx>Readline library (GHC syslib)</nidx>
 568 <nidx>command-line editing library</nidx>
 569 %*                                                                      *
 570 %************************************************************************
 571
 572 (Darren Moffat supplied the @Readline@ interface.)
 573
 574 The @Readline@ module is a straightforward interface to the GNU
 575 Readline library.  As such, you will need to look at the GNU
 576 documentation (and have a @libreadline.a@ file around somewhere...)
 577
 578 You'll need to link any Readlining program with @-lreadline -ltermcap@,
 579 besides the usual @-syslib ghc@ (and @-fhaskell-1.3@).
 580
 581 The main function you'll use is:
 582 <tscreen><verb>
 583 readline :: String{-the prompt-} -> IO String
 584 </verb></tscreen>
 585
 586 If you want to mess around with Full Readline G(l)ory, we also
 587 provide:
 588 <tscreen><verb>
 589 rlInitialize, addHistory,
 590
 591 rlBindKey, rlAddDefun, RlCallbackFunction(..),
 592
 593 rlGetLineBuffer, rlSetLineBuffer, rlGetPoint, rlSetPoint, rlGetEnd,
 594 rlSetEnd, rlGetMark, rlSetMark, rlSetDone, rlPendingInput,
 595
 596 rlPrompt, rlTerminalName, rlSetReadlineName, rlGetReadlineName
 597 </verb></tscreen>
 598 (All those names are just Haskellised versions of what you
 599 will see in the GNU readline documentation.)
 600
 601 %************************************************************************
 602 %*                                                                      *
 603 <sect2>The @Regex@ and @MatchPS@ interfaces
 604 <label id="Regex">
 605 <p>
 606 <nidx>Regex library (GHC syslib)</nidx>
 607 <nidx>MatchPS library (GHC syslib)</nidx>
 608 <nidx>regular-expressions library</nidx>
 609 %*                                                                      *
 610 %************************************************************************
 611
 612 (Sigbjorn Finne supplied the regular-expressions interface.)
 613
 614 The @Regex@ library provides quite direct interface to the GNU
 615 regular-expression library, for doing manipulation on @PackedString@s.
 616 You probably need to see the GNU documentation if you are operating at
 617 this level.  Alternatively, you can use the simpler and higher-level
 618 @RegexString@ interface.
 619
 620 The datatypes and functions that @Regex@ provides are:
 621 <tscreen><verb>
 622 data PatBuffer  # just a bunch of bytes (mutable)
 623
 624 data REmatch
 625  = REmatch (Array Int GroupBounds)  -- for $1, ... $n
 626            GroupBounds              -- for $` (everything before match)
 627            GroupBounds              -- for $& (entire matched string)
 628            GroupBounds              -- for $' (everything after)
 629            GroupBounds              -- for $+ (matched by last bracket)
 630
 631 -- GroupBounds hold the interval where a group
 632 -- matched inside a string, e.g.
 633 --
 634 -- matching "reg(exp)" "a regexp" returns the pair (5,7) for the
 635 -- (exp) group. (PackedString indices start from 0)
 636
 637 type GroupBounds = (Int, Int)
 638
 639 re_compile_pattern
 640         :: PackedString         -- pattern to compile
 641         -> Bool                 -- True <=> assume single-line mode
 642         -> Bool                 -- True <=> case-insensitive
 643         -> PrimIO PatBuffer
 644
 645 re_match :: PatBuffer           -- compiled regexp
 646          -> PackedString        -- string to match
 647          -> Int                 -- start position
 648          -> Bool                -- True <=> record results in registers
 649          -> PrimIO (Maybe REmatch)
 650
 651 -- Matching on 2 strings is useful when you're dealing with multiple
 652 -- buffers, which is something that could prove useful for
 653 -- PackedStrings, as we don't want to stuff the contents of a file
 654 -- into one massive heap chunk, but load (smaller chunks) on demand.
 655
 656 re_match2 :: PatBuffer          -- 2-string version
 657           -> PackedString
 658           -> PackedString
 659           -> Int
 660           -> Int
 661           -> Bool
 662           -> PrimIO (Maybe REmatch)
 663
 664 re_search :: PatBuffer          -- compiled regexp
 665           -> PackedString       -- string to search
 666           -> Int                -- start index
 667           -> Int                -- stop index
 668           -> Bool               -- True <=> record results in registers
 669           -> PrimIO (Maybe REmatch)
 670
 671 re_search2 :: PatBuffer         -- Double buffer search
 672            -> PackedString
 673            -> PackedString
 674            -> Int               -- start index
 675            -> Int               -- range (?)
 676            -> Int               -- stop index
 677            -> Bool              -- True <=> results in registers
 678            -> PrimIO (Maybe REmatch)
 679 </verb></tscreen>
 680
 681 The @MatchPS@ module provides Perl-like ``higher-level'' facilities
 682 to operate on @PackedStrings@.  The regular expressions in
 683 question are in Perl syntax.  The ``flags'' on various functions can
 684 include: @i@ for case-insensitive, @s@ for single-line mode, and
 685 @g@ for global.  (It's probably worth your time to peruse the
 686 source code...)
 687
 688 <tscreen><verb>
 689 matchPS :: PackedString    -- regexp
 690         -> PackedString    -- string to match
 691         -> [Char]          -- flags
 692         -> Maybe REmatch   -- info about what matched and where
 693
 694 searchPS :: PackedString    -- regexp
 695          -> PackedString    -- string to match
 696          -> [Char]          -- flags
 697          -> Maybe REmatch
 698
 699 -- Perl-like match-and-substitute:
 700 substPS :: PackedString     -- regexp
 701         -> PackedString     -- replacement
 702         -> [Char]           -- flags
 703         -> PackedString     -- string
 704         -> PackedString
 705
 706 -- same as substPS, but no prefix and suffix:
 707 replacePS :: PackedString  -- regexp
 708           -> PackedString  -- replacement
 709           -> [Char]        -- flags
 710           -> PackedString  -- string
 711           -> PackedString
 712
 713 match2PS :: PackedString   -- regexp
 714          -> PackedString   -- string1 to match
 715          -> PackedString   -- string2 to match
 716          -> [Char]         -- flags
 717          -> Maybe REmatch
 718
 719 search2PS :: PackedString  -- regexp
 720           -> PackedString  -- string to match
 721           -> PackedString  -- string to match
 722           -> [Char]        -- flags
 723           -> Maybe REmatch
 724
 725 -- functions to pull the matched pieces out of an REmatch:
 726
 727 getMatchesNo    :: REmatch -> Int
 728 getMatchedGroup :: REmatch -> Int -> PackedString -> PackedString
 729 getWholeMatch   :: REmatch -> PackedString -> PackedString
 730 getLastMatch    :: REmatch -> PackedString -> PackedString
 731 getAfterMatch   :: REmatch -> PackedString -> PackedString
 732
 733 -- (reverse) brute-force string matching;
 734 -- Perl equivalent is index/rindex:
 735 findPS, rfindPS :: PackedString -> PackedString -> Maybe Int
 736
 737 -- Equivalent to Perl "chop" (off the last character, if any):
 738 chopPS :: PackedString -> PackedString
 739
 740 -- matchPrefixPS: tries to match as much as possible of strA starting
 741 -- from the beginning of strB (handy when matching fancy literals in
 742 -- parsers):
 743 matchPrefixPS :: PackedString -> PackedString -> Int
 744 </verb></tscreen>
 745
 746 %************************************************************************
 747 %*                                                                      *
 748 <sect2>The @RegexString@ interface
 749 <label id="RegexString">
 750 <p>
 751 <nidx>RegexString library (GHC syslib)</nidx>
 752 <nidx>regular-expressions library</nidx>
 753 %*                                                                      *
 754 %************************************************************************
 755
 756 (Simon Marlow supplied the String Regex wrapper.)
 757
 758 For simple regular expression operations, the @Regex@ library is a
 759 little heavyweight.  @RegexString@ permits regex matching on ordinary
 760 Haskell @String@s.
 761
 762 The datatypes and functions that @RegexString@ provides are:
 763 <tscreen><verb>
 764 data Regex              -- a compiled regular expression
 765
 766 mkRegEx
 767         :: String       -- regexp to compile
 768         -> Regex        -- compiled regexp
 769
 770 matchRegex
 771         :: Regex        -- compiled regexp
 772         -> String       -- string to match
 773         -> Maybe [String] -- text of $1, $2, ... (if matched)
 774 </verb></tscreen>
 775
 776 %************************************************************************
 777 %*                                                                      *
 778 <sect2>Network-interface toolkit---@Socket@ and @SocketPrim@
 779 <label id="Socket">
 780 <p>
 781 <nidx>SocketPrim interface (GHC syslib)</nidx>
 782 <nidx>Socket interface (GHC syslib)</nidx>
 783 <nidx>network-interface library</nidx>
 784 <nidx>sockets library</nidx>
 785 <nidx>BSD sockets library</nidx>
 786 %*                                                                      *
 787 %************************************************************************
 788
 789 (Darren Moffat supplied the network-interface toolkit.)
 790
 791 Your best bet for documentation is to look at the code---really!---
 792 normally in @fptools/ghc/lib/misc/{BSD,Socket,SocketPrim@.lhs}.
 793
 794 The @BSD@ module provides functions to get at system-database info;
 795 pretty straightforward if you're into this sort of thing:
 796 <tscreen><verb>
 797 getHostName         :: IO String
 798
 799 getServiceByName    :: ServiceName -> IO ServiceEntry
 800 getServicePortNumber:: ServiceName -> IO PortNumber
 801 getServiceEntry     :: IO ServiceEntry
 802 setServiceEntry     :: Bool -> IO ()
 803 endServiceEntry     :: IO ()
 804
 805 getProtocolByName   :: ProtocolName -> IO ProtocolEntry
 806 getProtocolByNumber :: ProtocolNumber -> IO ProtcolEntry
 807 getProtocolNumber   :: ProtocolName -> ProtocolNumber
 808 getProtocolEntry    :: IO ProtocolEntry
 809 setProtocolEntry    :: Bool -> IO ()
 810 endProtocolEntry    :: IO ()
 811
 812 getHostByName       :: HostName -> IO HostEntry
 813 getHostByAddr       :: Family -> HostAddress -> IO HostEntry
 814 getHostEntry        :: IO HostEntry
 815 setHostEntry        :: Bool -> IO ()
 816 endHostEntry        :: IO ()
 817 </verb></tscreen>
 818
 819 The @SocketPrim@ interface provides quite direct access to the
 820 socket facilities in a BSD Unix system, including all the
 821 complications.  We hope you don't need to use it!  See the source if
 822 needed...
 823
 824 The @Socket@ interface is a ``higher-level'' interface to sockets,
 825 and it is what we recommend.  Please tell us if the facilities it
 826 offers are inadequate to your task!
 827
 828 The interface is relatively modest:
 829 <tscreen><verb>
 830 connectTo       :: Hostname -> PortID -> IO Handle
 831 listenOn        :: PortID -> IO Socket
 832
 833 accept          :: Socket -> IO (Handle, HostName)
 834 sendTo          :: Hostname -> PortID -> String -> IO ()
 835
 836 recvFrom        :: Hostname -> PortID -> IO String
 837 socketPort      :: Socket -> IO PortID
 838
 839 data PortID     -- PortID is a non-abstract type
 840   = Service String      -- Service Name eg "ftp"
 841   | PortNumber Int      -- User defined Port Number
 842   | UnixSocket String   -- Unix family socket in file system
 843
 844 type Hostname = String
 845 </verb></tscreen>
 846
 847 Various examples of networking Haskell code are provided in
 848 %@ghc/misc/examples/@, notably the @net???/Main.hs@ programs.