2378 lines
201 KiB
HTML
2378 lines
201 KiB
HTML
<?xml version="1.0" encoding="iso-8859-1" ?>
|
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
<!--http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd-->
|
|
<html xmlns="http://www.w3.org/1999/xhtml"
|
|
>
|
|
<head><title>9 Standard Prelude</title>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
|
|
<meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" />
|
|
<meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" />
|
|
<!-- 2,html,xhtml -->
|
|
<meta name="src" content="haskell.tex" />
|
|
<meta name="date" content="2010-07-20 13:11:00" />
|
|
<link rel="stylesheet" type="text/css" href="haskell.css" />
|
|
</head><body
|
|
>
|
|
<!--l. 7--><div class="crosslinks"><p class="noindent">[<a
|
|
href="haskellch10.html" >next</a>] [<a
|
|
href="haskellch8.html" >prev</a>] [<a
|
|
href="haskellch8.html#tailhaskellch8.html" >prev-tail</a>] [<a
|
|
href="#tailhaskellch9.html">tail</a>] [<a
|
|
href="haskellpa1.html#haskellch9.html" >up</a>] </p></div>
|
|
<h2 class="chapterHead"><span class="titlemark">Chapter 9</span><br /><a
|
|
id="x16-1710009"></a>Standard Prelude</h2>
|
|
<p class="noindent"> In this chapter the entire Haskell Prelude is given. It constitutes a <span
|
|
class="ptmri7t-">specification </span>for the Prelude. Many of the
|
|
definitions are written with clarity rather than efficiency in mind, and it is not required that the specification be
|
|
implemented as shown here.
|
|
<p class="noindent"> The default method definitions, given with <span
|
|
class="pcrr7t-">class</span> declarations, constitute a specification <span
|
|
class="ptmri7t-">only </span>of the default
|
|
method. They do not constitute a specification of the meaning of the method in all instances. To take one
|
|
particular example, the default method for <span
|
|
class="pcrr7t-">enumFrom</span> in class <span
|
|
class="pcrr7t-">Enum</span> will not work properly for types
|
|
whose range exceeds that of <span
|
|
class="pcrr7t-">Int</span> (because <span
|
|
class="pcrr7t-">fromEnum</span> cannot map all values in the type to distinct <span
|
|
class="pcrr7t-">Int</span>
|
|
values).
|
|
<p class="noindent"> The Prelude shown here is organized into a root module, <span
|
|
class="pcrr7t-">Prelude</span>, and three sub-modules, <span
|
|
class="pcrr7t-">PreludeList</span>,
|
|
<span
|
|
class="pcrr7t-">PreludeText</span>, and <span
|
|
class="pcrr7t-">PreludeIO</span>. This structure is purely presentational. An implementation is not required to use
|
|
this organisation for the Prelude, nor are these three modules available for import separately. Only the exports of
|
|
module <span
|
|
class="pcrr7t-">Prelude</span> are significant.
|
|
<p class="noindent"> Some of these modules import Library modules, such as <span
|
|
class="pcrr7t-">Data.Char</span>, <span
|
|
class="pcrr7t-">Control.Monad</span>, <span
|
|
class="pcrr7t-">System.IO</span>, and
|
|
<span
|
|
class="pcrr7t-">Numeric</span>. These modules are described fully in Part <a
|
|
href="haskellpa2.html#x20-192000II">II<!--tex4ht:ref: libraries --></a>. These imports are not, of course, part of the specification of
|
|
the <span
|
|
class="pcrr7t-">Prelude</span>. That is, an implementation is free to import more, or less, of the Library modules, as it
|
|
pleases.
|
|
<p class="noindent"> Primitives that are not definable in Haskell, indicated by names starting with “<span
|
|
class="pcrr7t-">prim</span>”, are defined in a system
|
|
dependent manner in module <span
|
|
class="pcrr7t-">PreludeBuiltin</span> and are not shown here. Instance declarations that simply bind
|
|
primitives to class methods are omitted. Some of the more verbose instances with obvious functionality have been left
|
|
out for the sake of brevity.
|
|
<p class="noindent"> Declarations for special types such as <span
|
|
class="pcrr7t-">Integer</span>, or <span
|
|
class="pcrr7t-">()</span> are included in the Prelude for completeness even though
|
|
the declaration may be incomplete or syntactically invalid. An ellipsis “<span
|
|
class="pcrr7t-">...</span>” is often used in places where the
|
|
remainder of a definition cannot be given in Haskell.
|
|
<p class="noindent"> To reduce the occurrence of unexpected ambiguity errors, and to improve efficiency, a number of
|
|
commonly-used functions over lists use the <span
|
|
class="pcrr7t-">Int</span> type rather than using a more general numeric type, such as
|
|
<span
|
|
class="pcrr7t-">Integral</span><span
|
|
class="pcrr7t-"> a</span> or <span
|
|
class="pcrr7t-">Num</span><span
|
|
class="pcrr7t-"> a</span>. These functions are: <span
|
|
class="pcrr7t-">take</span>, <span
|
|
class="pcrr7t-">drop</span>, <span
|
|
class="pcrr7t-">!!</span>, <span
|
|
class="pcrr7t-">length</span>, <span
|
|
class="pcrr7t-">splitAt</span>, and <span
|
|
class="pcrr7t-">replicate</span>. The
|
|
more general versions are given in the <span
|
|
class="pcrr7t-">Data.List</span> library, with the prefix “<span
|
|
class="pcrr7t-">generic</span>”; for example
|
|
<span
|
|
class="pcrr7t-">genericLength</span>.
|
|
|
|
|
|
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-161">
|
|
module Prelude (
|
|
 <br />    module PreludeList, module PreludeText, module PreludeIO,
|
|
 <br />    Bool(False, True),
|
|
 <br />    Maybe(Nothing, Just),
|
|
 <br />    Either(Left, Right),
|
|
 <br />    Ordering(LT, EQ, GT),
|
|
 <br />    Char, String, Int, Integer, Float, Double, Rational, IO,
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171001"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-162">
|
|
--      These built-in types are defined in the Prelude, but
|
|
 <br />--      are denoted by built-in syntax, and cannot legally
|
|
 <br />--      appear in an export list.
|
|
 <br />--  List type: []((:), [])
|
|
 <br />--  Tuple types: (,)((,)), (,,)((,,)), etc.
|
|
 <br />--  Trivial type: ()(())
|
|
 <br />--  Functions: (->)
|
|
 <br />
|
|
 <br />    Eq((==), (/=)),
|
|
 <br />    Ord(compare, (<), (<=), (>=), (>), max, min),
|
|
 <br />    Enum(succ, pred, toEnum, fromEnum, enumFrom, enumFromThen,
|
|
 <br />         enumFromTo, enumFromThenTo),
|
|
 <br />    Bounded(minBound, maxBound),
|
|
 <br />    Num((+), (-), (⋆), negate, abs, signum, fromInteger),
|
|
 <br />    Real(toRational),
|
|
 <br />    Integral(quot, rem, div, mod, quotRem, divMod, toInteger),
|
|
 <br />    Fractional((/), recip, fromRational),
|
|
 <br />    Floating(pi, exp, log, sqrt, (⋆⋆), logBase, sin, cos, tan,
|
|
 <br />             asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh),
|
|
 <br />    RealFrac(properFraction, truncate, round, ceiling, floor),
|
|
 <br />    RealFloat(floatRadix, floatDigits, floatRange, decodeFloat,
|
|
 <br />              encodeFloat, exponent, significand, scaleFloat, isNaN,
|
|
 <br />              isInfinite, isDenormalized, isIEEE, isNegativeZero, atan2),
|
|
 <br />    Monad((>>=), (>>), return, fail),
|
|
 <br />    Functor(fmap),
|
|
 <br />    mapM, mapM_, sequence, sequence_, (=<<),
|
|
 <br />    maybe, either,
|
|
 <br />    (&&), (||), not, otherwise,
|
|
 <br />    subtract, even, odd, gcd, lcm, (^), (^^),
|
|
 <br />    fromIntegral, realToFrac,
|
|
 <br />    fst, snd, curry, uncurry, id, const, (.), flip, ($), until,
|
|
 <br />    asTypeOf, error, undefined,
|
|
 <br />    seq, ($!)
|
|
 <br />  ) where
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-163">
|
|
import PreludeBuiltin                      -- Contains all ‘prim' values
|
|
 <br />import UnicodePrims( primUnicodeMaxChar )  -- Unicode primitives
|
|
 <br />import PreludeList
|
|
 <br />import PreludeText
|
|
 <br />import PreludeIO
|
|
 <br />import Data.Ratio( Rational )
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171002"></a><a
|
|
id="dx16-171003"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-164">
|
|
infixr 9  .
|
|
 <br />infixr 8  ^, ^^, ⋆⋆
|
|
 <br />infixl 7  ⋆, /, ‘quot‘, ‘rem‘, ‘div‘, ‘mod‘
|
|
 <br />infixl 6  +, -
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171004"></a><a
|
|
id="dx16-171005"></a><a
|
|
id="dx16-171006"></a><a
|
|
id="dx16-171007"></a><a
|
|
id="dx16-171008"></a><a
|
|
id="dx16-171009"></a><a
|
|
id="dx16-171010"></a><a
|
|
id="dx16-171011"></a><a
|
|
id="dx16-171012"></a><a
|
|
id="dx16-171013"></a><a
|
|
id="dx16-171014"></a><a
|
|
id="dx16-171015"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-165">
|
|
-- The (:) operator is built-in syntax, and cannot legally be given
|
|
 <br />-- a fixity declaration; but its fixity is given by:
|
|
 <br />--   infixr 5  :
|
|
 <br />
|
|
 <br />infix  4  ==, /=, <, <=, >=, >
|
|
 <br />infixr 3  &&
|
|
 <br />infixr 2  ||
|
|
 <br />infixl 1  >>, >>=
|
|
 <br />infixr 1  =<<
|
|
 <br />infixr 0  $, $!, ‘seq‘
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171016"></a><a
|
|
id="dx16-171017"></a><a
|
|
id="dx16-171018"></a><a
|
|
id="dx16-171019"></a><a
|
|
id="dx16-171020"></a><a
|
|
id="dx16-171021"></a><a
|
|
id="dx16-171022"></a><a
|
|
id="dx16-171023"></a><a
|
|
id="dx16-171024"></a><a
|
|
id="dx16-171025"></a><a
|
|
id="dx16-171026"></a><a
|
|
id="dx16-171027"></a><a
|
|
id="dx16-171028"></a><a
|
|
id="dx16-171029"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-166">
|
|
-- Standard types, classes, instances and related functions
|
|
 <br />
|
|
 <br />-- Equality and Ordered classes
|
|
 <br />
|
|
 <br />class  Eq a  where
|
|
 <br />    (==), (/=) :: a -> a -> Bool
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      (==) or (/=)
|
|
 <br />    x /= y     =  not (x == y)
|
|
 <br />    x == y     =  not (x /= y)
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-167">
|
|
class  (Eq a) => Ord a  where
|
|
 <br />    compare              :: a -> a -> Ordering
|
|
 <br />    (<), (<=), (>=), (>) :: a -> a -> Bool
|
|
 <br />    max, min             :: a -> a -> a
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      (<=) or compare
|
|
 <br />        -- Using compare can be more efficient for complex types.
|
|
 <br />    compare x y
|
|
 <br />         | x == y    =  EQ
|
|
 <br />         | x <= y    =  LT
|
|
 <br />         | otherwise =  GT
|
|
 <br />
|
|
 <br />    x <= y           =  compare x y /= GT
|
|
 <br />    x <  y           =  compare x y == LT
|
|
 <br />    x >= y           =  compare x y /= LT
|
|
 <br />    x >  y           =  compare x y == GT
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-168">
|
|
-- note that (min x y, max x y) = (x,y) or (y,x)
|
|
 <br />    max x y
|
|
 <br />         | x <= y    =  y
|
|
 <br />         | otherwise =  x
|
|
 <br />    min x y
|
|
 <br />         | x <= y    =  x
|
|
 <br />         | otherwise =  y
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-169">
|
|
-- Enumeration and Bounded classes
|
|
 <br />
|
|
 <br />class  Enum a  where
|
|
 <br />    succ, pred       :: a -> a
|
|
 <br />    toEnum           :: Int -> a
|
|
 <br />    fromEnum         :: a -> Int
|
|
 <br />    enumFrom         :: a -> [a]             -- [n..]
|
|
 <br />    enumFromThen     :: a -> a -> [a]        -- [n,n'..]
|
|
 <br />    enumFromTo       :: a -> a -> [a]        -- [n..m]
|
|
 <br />    enumFromThenTo   :: a -> a -> a -> [a]   -- [n,n'..m]
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      toEnum, fromEnum
|
|
 <br />        --
|
|
 <br />        -- NOTE: these default methods only make sense for types
|
|
 <br />        --       that map injectively into Int using fromEnum
|
|
 <br />        --       and toEnum.
|
|
 <br />    succ             =  toEnum . (+1) . fromEnum
|
|
 <br />    pred             =  toEnum . (subtract 1) . fromEnum
|
|
 <br />    enumFrom x       =  map toEnum [fromEnum x ..]
|
|
 <br />    enumFromTo x y   =  map toEnum [fromEnum x .. fromEnum y]
|
|
 <br />    enumFromThen x y =  map toEnum [fromEnum x, fromEnum y ..]
|
|
 <br />    enumFromThenTo x y z =
|
|
 <br />                        map toEnum [fromEnum x, fromEnum y .. fromEnum z]
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-170">
|
|
class  Bounded a  where
|
|
 <br />    minBound         :: a
|
|
 <br />    maxBound         :: a
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-171">
|
|
-- Numeric classes
|
|
 <br />
|
|
 <br />class  (Eq a, Show a) => Num a  where
|
|
 <br />    (+), (-), (⋆)    :: a -> a -> a
|
|
 <br />    negate           :: a -> a
|
|
 <br />    abs, signum      :: a -> a
|
|
 <br />    fromInteger      :: Integer -> a
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      All, except negate or (-)
|
|
 <br />    x - y            =  x + negate y
|
|
 <br />    negate x         =  0 - x
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-172">
|
|
class  (Num a, Ord a) => Real a  where
|
|
 <br />    toRational       ::  a -> Rational
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-173">
|
|
class  (Real a, Enum a) => Integral a  where
|
|
 <br />    quot, rem        :: a -> a -> a
|
|
 <br />    div, mod         :: a -> a -> a
|
|
 <br />    quotRem, divMod  :: a -> a -> (a,a)
|
|
 <br />    toInteger        :: a -> Integer
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      quotRem, toInteger
|
|
 <br />    n ‘quot‘ d       =  q  where (q,r) = quotRem n d
|
|
 <br />    n ‘rem‘ d        =  r  where (q,r) = quotRem n d
|
|
 <br />    n ‘div‘ d        =  q  where (q,r) = divMod n d
|
|
 <br />    n ‘mod‘ d        =  r  where (q,r) = divMod n d
|
|
 <br />    divMod n d       =  if signum r == - signum d then (q-1, r+d) else qr
|
|
 <br />                        where qr@(q,r) = quotRem n d
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-174">
|
|
class  (Num a) => Fractional a  where
|
|
 <br />    (/)              :: a -> a -> a
|
|
 <br />    recip            :: a -> a
|
|
 <br />    fromRational     :: Rational -> a
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      fromRational and (recip or (/))
|
|
 <br />    recip x          =  1 / x
|
|
 <br />    x / y            =  x ⋆ recip y
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-175">
|
|
class  (Fractional a) => Floating a  where
|
|
 <br />    pi                  :: a
|
|
 <br />    exp, log, sqrt      :: a -> a
|
|
 <br />    (⋆⋆), logBase       :: a -> a -> a
|
|
 <br />    sin, cos, tan       :: a -> a
|
|
 <br />    asin, acos, atan    :: a -> a
|
|
 <br />    sinh, cosh, tanh    :: a -> a
|
|
 <br />    asinh, acosh, atanh :: a -> a
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      pi, exp, log, sin, cos, sinh, cosh
|
|
 <br />        --      asin, acos, atan
|
|
 <br />        --      asinh, acosh, atanh
|
|
 <br />    x ⋆⋆ y           =  exp (log x ⋆ y)
|
|
 <br />    logBase x y      =  log y / log x
|
|
 <br />    sqrt x           =  x ⋆⋆ 0.5
|
|
 <br />    tan  x           =  sin  x / cos  x
|
|
 <br />    tanh x           =  sinh x / cosh x
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-176">
|
|
class  (Real a, Fractional a) => RealFrac a  where
|
|
 <br />    properFraction   :: (Integral b) => a -> (b,a)
|
|
 <br />    truncate, round  :: (Integral b) => a -> b
|
|
 <br />    ceiling, floor   :: (Integral b) => a -> b
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      properFraction
|
|
 <br />    truncate x       =  m  where (m,_) = properFraction x
|
|
 <br />
|
|
 <br />    round x          =  let (n,r) = properFraction x
|
|
 <br />                            m     = if r < 0 then n - 1 else n + 1
|
|
 <br />                          in case signum (abs r - 0.5) of
|
|
 <br />                                -1 -> n
|
|
 <br />                                0  -> if even n then n else m
|
|
 <br />                                1  -> m
|
|
 <br />
|
|
 <br />    ceiling x        =  if r > 0 then n + 1 else n
|
|
 <br />                        where (n,r) = properFraction x
|
|
 <br />
|
|
 <br />    floor x          =  if r < 0 then n - 1 else n
|
|
 <br />                        where (n,r) = properFraction x
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-177">
|
|
class  (RealFrac a, Floating a) => RealFloat a  where
|
|
 <br />    floatRadix       :: a -> Integer
|
|
 <br />    floatDigits      :: a -> Int
|
|
 <br />    floatRange       :: a -> (Int,Int)
|
|
 <br />    decodeFloat      :: a -> (Integer,Int)
|
|
 <br />    encodeFloat      :: Integer -> Int -> a
|
|
 <br />    exponent         :: a -> Int
|
|
 <br />    significand      :: a -> a
|
|
 <br />    scaleFloat       :: Int -> a -> a
|
|
 <br />    isNaN, isInfinite, isDenormalized, isNegativeZero, isIEEE
|
|
 <br />                     :: a -> Bool
|
|
 <br />    atan2            :: a -> a -> a
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      All except exponent, significand,
|
|
 <br />        --                 scaleFloat, atan2
|
|
 <br />    exponent x       =  if m == 0 then 0 else n + floatDigits x
|
|
 <br />                        where (m,n) = decodeFloat x
|
|
 <br />
|
|
 <br />    significand x    =  encodeFloat m (- floatDigits x)
|
|
 <br />                        where (m,_) = decodeFloat x
|
|
 <br />
|
|
 <br />    scaleFloat k x   =  encodeFloat m (n+k)
|
|
 <br />                        where (m,n) = decodeFloat x
|
|
 <br />
|
|
 <br />    atan2 y x
|
|
 <br />      | x>0           =  atan (y/x)
|
|
 <br />      | x==0 && y>0   =  pi/2
|
|
 <br />      | x<0  && y>0   =  pi + atan (y/x)
|
|
 <br />      |(x<=0 && y<0)  ||
|
|
 <br />       (x<0 && isNegativeZero y) ||
|
|
 <br />       (isNegativeZero x && isNegativeZero y)
|
|
 <br />                      = -atan2 (-y) x
|
|
 <br />      | y==0 && (x<0 || isNegativeZero x)
|
|
 <br />                      =  pi    -- must be after the previous test on zero y
|
|
 <br />      | x==0 && y==0  =  y     -- must be after the other double zero tests
|
|
 <br />      | otherwise     =  x + y -- x or y is a NaN, return a NaN (via +)
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-178">
|
|
-- Numeric functions
|
|
 <br />
|
|
 <br />subtract         :: (Num a) => a -> a -> a
|
|
 <br />subtract         =  flip (-)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171030"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-179">
|
|
even, odd        :: (Integral a) => a -> Bool
|
|
 <br />even n           =  n ‘rem‘ 2 == 0
|
|
 <br />odd              =  not . even
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171031"></a><a
|
|
id="dx16-171032"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-180">
|
|
gcd              :: (Integral a) => a -> a -> a
|
|
 <br />gcd 0 0          =  error "Prelude.gcd: gcd 0 0 is undefined"
|
|
 <br />gcd x y          =  gcd' (abs x) (abs y)
|
|
 <br />                    where gcd' x 0  =  x
|
|
 <br />                          gcd' x y  =  gcd' y (x ‘rem‘ y)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171033"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-181">
|
|
lcm              :: (Integral a) => a -> a -> a
|
|
 <br />lcm _ 0          =  0
|
|
 <br />lcm 0 _          =  0
|
|
 <br />lcm x y          =  abs ((x ‘quot‘ (gcd x y)) ⋆ y)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171034"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-182">
|
|
(^)              :: (Num a, Integral b) => a -> b -> a
|
|
 <br />x ^ 0            =  1
|
|
 <br />x ^ n | n > 0    =  f x (n-1) x
|
|
 <br />                    where f _ 0 y = y
|
|
 <br />                          f x n y = g x n  where
|
|
 <br />                                    g x n | even n  = g (x⋆x) (n ‘quot‘ 2)
|
|
 <br />                                          | otherwise = f x (n-1) (x⋆y)
|
|
 <br />_ ^ _            = error "Prelude.^: negative exponent"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171035"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-183">
|
|
(^^)             :: (Fractional a, Integral b) => a -> b -> a
|
|
 <br />x ^^ n           =  if n >= 0 then x^n else recip (x^(-n))
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171036"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-184">
|
|
fromIntegral     :: (Integral a, Num b) => a -> b
|
|
 <br />fromIntegral     =  fromInteger . toInteger
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171037"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-185">
|
|
realToFrac     :: (Real a, Fractional b) => a -> b
|
|
 <br />realToFrac      =  fromRational . toRational
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171038"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-186">
|
|
-- Monadic classes
|
|
 <br />
|
|
 <br />class  Functor f  where
|
|
 <br />    fmap              :: (a -> b) -> f a -> f b
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-187">
|
|
class  Monad m  where
|
|
 <br />    (>>=)  :: m a -> (a -> m b) -> m b
|
|
 <br />    (>>)   :: m a -> m b -> m b
|
|
 <br />    return :: a -> m a
|
|
 <br />    fail   :: String -> m a
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      (>>=), return
|
|
 <br />    m >> k  =  m >>= \_ -> k
|
|
 <br />    fail s  = error s
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-188">
|
|
sequence       :: Monad m => [m a] -> m [a]
|
|
 <br />sequence       =  foldr mcons (return [])
|
|
 <br />                    where mcons p q = p >>= \x -> q >>= \y -> return (x:y)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171039"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-189">
|
|
sequence_      :: Monad m => [m a] -> m ()
|
|
 <br />sequence_      =  foldr (>>) (return ())
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171040"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-190">
|
|
-- The xxxM functions take list arguments, but lift the function or
|
|
 <br />-- list element to a monad type
|
|
 <br />mapM             :: Monad m => (a -> m b) -> [a] -> m [b]
|
|
 <br />mapM f as        =  sequence (map f as)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171041"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-191">
|
|
mapM_            :: Monad m => (a -> m b) -> [a] -> m ()
|
|
 <br />mapM_ f as       =  sequence_ (map f as)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171042"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-192">
|
|
(=<<)            :: Monad m => (a -> m b) -> m a -> m b
|
|
 <br />f =<< x          =  x >>= f
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171043"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-193">
|
|
-- Trivial type
|
|
 <br />
|
|
 <br />data  ()  =  ()  deriving (Eq, Ord, Enum, Bounded)
|
|
 <br />        -- Not legal Haskell; for illustration only
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-194">
|
|
-- Function type
|
|
 <br />
|
|
 <br />-- identity function
|
|
 <br />id               :: a -> a
|
|
 <br />id x             =  x
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171044"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-195">
|
|
-- constant function
|
|
 <br />const            :: a -> b -> a
|
|
 <br />const x _        =  x
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171045"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-196">
|
|
-- function composition
|
|
 <br />(.)              :: (b -> c) -> (a -> b) -> a -> c
|
|
 <br />f . g            =  \ x -> f (g x)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171046"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-197">
|
|
-- flip f  takes its (first) two arguments in the reverse order of f.
|
|
 <br />flip             :: (a -> b -> c) -> b -> a -> c
|
|
 <br />flip f x y       =  f y x
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171047"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-198">
|
|
seq :: a -> b -> b
|
|
 <br />seq = ...       -- Primitive
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171048"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-199">
|
|
-- right-associating infix application operators
|
|
 <br />-- (useful in continuation-passing style)
|
|
 <br />($), ($!) :: (a -> b) -> a -> b
|
|
 <br />f $  x    =  f x
|
|
 <br />f $! x    =  x ‘seq‘ f x
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171049"></a><a
|
|
id="dx16-171050"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-200">
|
|
-- Boolean type
|
|
 <br />
|
|
 <br />data  Bool  =  False | True     deriving (Eq, Ord, Enum, Read, Show, Bounded)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171051"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-201">
|
|
-- Boolean functions
|
|
 <br />
|
|
 <br />(&&), (||)       :: Bool -> Bool -> Bool
|
|
 <br />True  && x       =  x
|
|
 <br />False && _       =  False
|
|
 <br />True  || _       =  True
|
|
 <br />False || x       =  x
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171052"></a><a
|
|
id="dx16-171053"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-202">
|
|
not              :: Bool -> Bool
|
|
 <br />not True         =  False
|
|
 <br />not False        =  True
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171054"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-203">
|
|
otherwise        :: Bool
|
|
 <br />otherwise        =  True
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171055"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-204">
|
|
-- Character type
|
|
 <br />
|
|
 <br />data Char = ... 'a' | 'b' ... -- Unicode values
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171056"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-205">
|
|
instance  Eq Char  where
|
|
 <br />    c == c'          =  fromEnum c == fromEnum c'
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-206">
|
|
instance  Ord Char  where
|
|
 <br />    c <= c'          =  fromEnum c <= fromEnum c'
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-207">
|
|
instance  Enum Char  where
|
|
 <br />    toEnum            = primIntToChar
|
|
 <br />    fromEnum          = primCharToInt
|
|
 <br />    enumFrom c        = map toEnum [fromEnum c .. fromEnum (maxBound::Char)]
|
|
 <br />    enumFromThen c c' = map toEnum [fromEnum c, fromEnum c' .. fromEnum lastChar]
|
|
 <br />                      where lastChar :: Char
|
|
 <br />                            lastChar | c' < c    = minBound
|
|
 <br />                                     | otherwise = maxBound
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-208">
|
|
instance  Bounded Char  where
|
|
 <br />    minBound  =  '\0'
|
|
 <br />    maxBound  =  primUnicodeMaxChar
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-209">
|
|
type  String = [Char]
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171057"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-210">
|
|
-- Maybe type
|
|
 <br />
|
|
 <br />data  Maybe a  =  Nothing | Just a      deriving (Eq, Ord, Read, Show)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171058"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-211">
|
|
maybe              :: b -> (a -> b) -> Maybe a -> b
|
|
 <br />maybe n f Nothing  =  n
|
|
 <br />maybe n f (Just x) =  f x
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171059"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-212">
|
|
instance  Functor Maybe  where
|
|
 <br />    fmap f Nothing    =  Nothing
|
|
 <br />    fmap f (Just x)   =  Just (f x)
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-213">
|
|
instance  Monad Maybe  where
|
|
 <br />    (Just x) >>= k   =  k x
|
|
 <br />    Nothing  >>= k   =  Nothing
|
|
 <br />    return           =  Just
|
|
 <br />    fail s           =  Nothing
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-214">
|
|
-- Either type
|
|
 <br />
|
|
 <br />data  Either a b  =  Left a | Right b   deriving (Eq, Ord, Read, Show)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171060"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-215">
|
|
either               :: (a -> c) -> (b -> c) -> Either a b -> c
|
|
 <br />either f g (Left x)  =  f x
|
|
 <br />either f g (Right y) =  g y
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171061"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-216">
|
|
-- IO type
|
|
 <br />
|
|
 <br />data IO a = ...         -- abstract
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171062"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-217">
|
|
instance  Functor IO where
|
|
 <br />   fmap f x           =  x >>= (return . f)
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-218">
|
|
instance Monad IO where
|
|
 <br />   (>>=)  = ...
|
|
 <br />   return = ...
|
|
 <br />   fail s = ioError (userError s)
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-219">
|
|
-- Ordering type
|
|
 <br />
|
|
 <br />data  Ordering  =  LT | EQ | GT
|
|
 <br />          deriving (Eq, Ord, Enum, Read, Show, Bounded)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171063"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-220">
|
|
-- Standard numeric types.  The data declarations for these types cannot
|
|
 <br />-- be expressed directly in Haskell since the constructor lists would be
|
|
 <br />-- far too large.
|
|
 <br />
|
|
 <br />data  Int  =  minBound ... -1 | 0 | 1 ... maxBound
|
|
 <br />instance  Eq       Int  where ...
|
|
 <br />instance  Ord      Int  where ...
|
|
 <br />instance  Num      Int  where ...
|
|
 <br />instance  Real     Int  where ...
|
|
 <br />instance  Integral Int  where ...
|
|
 <br />instance  Enum     Int  where ...
|
|
 <br />instance  Bounded  Int  where ...
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171064"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-221">
|
|
data  Integer  =  ... -1 | 0 | 1 ...
|
|
 <br />instance  Eq       Integer  where ...
|
|
 <br />instance  Ord      Integer  where ...
|
|
 <br />instance  Num      Integer  where ...
|
|
 <br />instance  Real     Integer  where ...
|
|
 <br />instance  Integral Integer  where ...
|
|
 <br />instance  Enum     Integer  where ...
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171065"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-222">
|
|
data  Float
|
|
 <br />instance  Eq         Float  where ...
|
|
 <br />instance  Ord        Float  where ...
|
|
 <br />instance  Num        Float  where ...
|
|
 <br />instance  Real       Float  where ...
|
|
 <br />instance  Fractional Float  where ...
|
|
 <br />instance  Floating   Float  where ...
|
|
 <br />instance  RealFrac   Float  where ...
|
|
 <br />instance  RealFloat  Float  where ...
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171066"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-223">
|
|
data  Double
|
|
 <br />instance  Eq         Double  where ...
|
|
 <br />instance  Ord        Double  where ...
|
|
 <br />instance  Num        Double  where ...
|
|
 <br />instance  Real       Double  where ...
|
|
 <br />instance  Fractional Double  where ...
|
|
 <br />instance  Floating   Double  where ...
|
|
 <br />instance  RealFrac   Double  where ...
|
|
 <br />instance  RealFloat  Double  where ...
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171067"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-224">
|
|
-- The Enum instances for Floats and Doubles are slightly unusual.
|
|
 <br />-- The ‘toEnum' function truncates numbers to Int.  The definitions
|
|
 <br />-- of enumFrom and enumFromThen allow floats to be used in arithmetic
|
|
 <br />-- series: [0,0.1 .. 0.95].  However, roundoff errors make these somewhat
|
|
 <br />-- dubious.  This example may have either 10 or 11 elements, depending on
|
|
 <br />-- how 0.1 is represented.
|
|
 <br />
|
|
 <br />instance  Enum Float  where
|
|
 <br />    succ x           =  x+1
|
|
 <br />    pred x           =  x-1
|
|
 <br />    toEnum           =  fromIntegral
|
|
 <br />    fromEnum         =  fromInteger . truncate   -- may overflow
|
|
 <br />    enumFrom         =  numericEnumFrom
|
|
 <br />    enumFromThen     =  numericEnumFromThen
|
|
 <br />    enumFromTo       =  numericEnumFromTo
|
|
 <br />    enumFromThenTo   =  numericEnumFromThenTo
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-225">
|
|
instance  Enum Double  where
|
|
 <br />    succ x           =  x+1
|
|
 <br />    pred x           =  x-1
|
|
 <br />    toEnum           =  fromIntegral
|
|
 <br />    fromEnum         =  fromInteger . truncate   -- may overflow
|
|
 <br />    enumFrom         =  numericEnumFrom
|
|
 <br />    enumFromThen     =  numericEnumFromThen
|
|
 <br />    enumFromTo       =  numericEnumFromTo
|
|
 <br />    enumFromThenTo   =  numericEnumFromThenTo
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-226">
|
|
numericEnumFrom         :: (Fractional a) => a -> [a]
|
|
 <br />numericEnumFromThen     :: (Fractional a) => a -> a -> [a]
|
|
 <br />numericEnumFromTo       :: (Fractional a, Ord a) => a -> a -> [a]
|
|
 <br />numericEnumFromThenTo   :: (Fractional a, Ord a) => a -> a -> a -> [a]
|
|
 <br />numericEnumFrom         =  iterate (+1)
|
|
 <br />numericEnumFromThen n m =  iterate (+(m-n)) n
|
|
 <br />numericEnumFromTo n m   =  takeWhile (<= m+1/2) (numericEnumFrom n)
|
|
 <br />numericEnumFromThenTo n n' m = takeWhile p (numericEnumFromThen n n')
|
|
 <br />                             where
|
|
 <br />                               p | n' >= n   = (<= m + (n'-n)/2)
|
|
 <br />                                 | otherwise = (>= m + (n'-n)/2)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171068"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-227">
|
|
-- Lists
|
|
 <br />
|
|
 <br />data  [a]  =  [] | a : [a]  deriving (Eq, Ord)
|
|
 <br />        -- Not legal Haskell; for illustration only
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-228">
|
|
instance Functor [] where
|
|
 <br />    fmap = map
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-229">
|
|
instance  Monad []  where
|
|
 <br />    m >>= k          = concat (map k m)
|
|
 <br />    return x         = [x]
|
|
 <br />    fail s           = []
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-230">
|
|
-- Tuples
|
|
 <br />
|
|
 <br />data  (a,b)   =  (a,b)    deriving (Eq, Ord, Bounded)
|
|
 <br />data  (a,b,c) =  (a,b,c)  deriving (Eq, Ord, Bounded)
|
|
 <br />        -- Not legal Haskell; for illustration only
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-231">
|
|
-- component projections for pairs:
|
|
 <br />-- (NB: not provided for triples, quadruples, etc.)
|
|
 <br />fst              :: (a,b) -> a
|
|
 <br />fst (x,y)        =  x
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171069"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-232">
|
|
snd              :: (a,b) -> b
|
|
 <br />snd (x,y)        =  y
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171070"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-233">
|
|
-- curry converts an uncurried function to a curried function;
|
|
 <br />-- uncurry converts a curried function to a function on pairs.
|
|
 <br />curry            :: ((a, b) -> c) -> a -> b -> c
|
|
 <br />curry f x y      =  f (x, y)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171071"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-234">
|
|
uncurry          :: (a -> b -> c) -> ((a, b) -> c)
|
|
 <br />uncurry f p      =  f (fst p) (snd p)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171072"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-235">
|
|
-- Misc functions
|
|
 <br />
|
|
 <br />-- until p f  yields the result of applying f until p holds.
|
|
 <br />until            :: (a -> Bool) -> (a -> a) -> a -> a
|
|
 <br />until p f x
|
|
 <br />     | p x       =  x
|
|
 <br />     | otherwise =  until p f (f x)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171073"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-236">
|
|
-- asTypeOf is a type-restricted version of const.  It is usually used
|
|
 <br />-- as an infix operator, and its typing forces its first argument
|
|
 <br />-- (which is usually overloaded) to have the same type as the second.
|
|
 <br />asTypeOf         :: a -> a -> a
|
|
 <br />asTypeOf         =  const
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171074"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-237">
|
|
-- error stops execution and displays an error message
|
|
 <br />
|
|
 <br />error            :: String -> a
|
|
 <br />error            =  primError
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171075"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-238">
|
|
-- It is expected that compilers will recognize this and insert error
|
|
 <br />-- messages that are more appropriate to the context in which undefined
|
|
 <br />-- appears.
|
|
 <br />
|
|
 <br />undefined        :: a
|
|
 <br />undefined        =  error "Prelude.undefined"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-171076"></a>
|
|
|
|
|
|
|
|
<h3 class="sectionHead"><span class="titlemark">9.1 </span> <a
|
|
id="x16-1720009.1"></a>Prelude <span
|
|
class="pcrr7t-">PreludeList</span></h3>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-239">
|
|
-- Standard list functions
|
|
 <br />
|
|
 <br />module PreludeList (
|
|
 <br />    map, (++), filter, concat, concatMap,
|
|
 <br />    head, last, tail, init, null, length, (!!),
|
|
 <br />    foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
|
|
 <br />    iterate, repeat, replicate, cycle,
|
|
 <br />    take, drop, splitAt, takeWhile, dropWhile, span, break,
|
|
 <br />    lines, words, unlines, unwords, reverse, and, or,
|
|
 <br />    any, all, elem, notElem, lookup,
|
|
 <br />    sum, product, maximum, minimum,
|
|
 <br />    zip, zip3, zipWith, zipWith3, unzip, unzip3)
|
|
 <br />  where
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172001"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-240">
|
|
import qualified Data.Char(isSpace)
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-241">
|
|
infixl 9  !!
|
|
 <br />infixr 5  ++
|
|
 <br />infix  4  ‘elem‘, ‘notElem‘
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172002"></a><a
|
|
id="dx16-172003"></a><a
|
|
id="dx16-172004"></a><a
|
|
id="dx16-172005"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-242">
|
|
-- Map and append
|
|
 <br />map :: (a -> b) -> [a] -> [b]
|
|
 <br />map f []     = []
|
|
 <br />map f (x:xs) = f x : map f xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172006"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-243">
|
|
(++) :: [a] -> [a] -> [a]
|
|
 <br />[]     ++ ys = ys
|
|
 <br />(x:xs) ++ ys = x : (xs ++ ys)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172007"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-244">
|
|
filter :: (a -> Bool) -> [a] -> [a]
|
|
 <br />filter p []                 = []
|
|
 <br />filter p (x:xs) | p x       = x : filter p xs
|
|
 <br />                | otherwise = filter p xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172008"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-245">
|
|
concat :: [[a]] -> [a]
|
|
 <br />concat xss = foldr (++) [] xss
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172009"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-246">
|
|
concatMap :: (a -> [b]) -> [a] -> [b]
|
|
 <br />concatMap f = concat . map f
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172010"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-247">
|
|
-- head and tail extract the first element and remaining elements,
|
|
 <br />-- respectively, of a list, which must be non-empty.  last and init
|
|
 <br />-- are the dual functions working from the end of a finite list,
|
|
 <br />-- rather than the beginning.
|
|
 <br />
|
|
 <br />head             :: [a] -> a
|
|
 <br />head (x:_)       =  x
|
|
 <br />head []          =  error "Prelude.head: empty list"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172011"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-248">
|
|
tail             :: [a] -> [a]
|
|
 <br />tail (_:xs)      =  xs
|
|
 <br />tail []          =  error "Prelude.tail: empty list"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172012"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-249">
|
|
last             :: [a] -> a
|
|
 <br />last [x]         =  x
|
|
 <br />last (_:xs)      =  last xs
|
|
 <br />last []          =  error "Prelude.last: empty list"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172013"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-250">
|
|
init             :: [a] -> [a]
|
|
 <br />init [x]         =  []
|
|
 <br />init (x:xs)      =  x : init xs
|
|
 <br />init []          =  error "Prelude.init: empty list"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172014"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-251">
|
|
null             :: [a] -> Bool
|
|
 <br />null []          =  True
|
|
 <br />null (_:_)       =  False
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172015"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-252">
|
|
-- length returns the length of a finite list as an Int.
|
|
 <br />length           :: [a] -> Int
|
|
 <br />length []        =  0
|
|
 <br />length (_:l)     =  1 + length l
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172016"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-253">
|
|
-- List index (subscript) operator, 0-origin
|
|
 <br />(!!)                :: [a] -> Int -> a
|
|
 <br />xs     !! n | n < 0 =  error "Prelude.!!: negative index"
|
|
 <br />[]     !! _         =  error "Prelude.!!: index too large"
|
|
 <br />(x:_)  !! 0         =  x
|
|
 <br />(_:xs) !! n         =  xs !! (n-1)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172017"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-254">
|
|
-- foldl, applied to a binary operator, a starting value (typically the
|
|
 <br />-- left-identity of the operator), and a list, reduces the list using
|
|
 <br />-- the binary operator, from left to right:
|
|
 <br />--  foldl f z [x1, x2, ..., xn] == (...((z ‘f‘ x1) ‘f‘ x2) ‘f‘...) ‘f‘ xn
|
|
 <br />-- foldl1 is a variant that has no starting value argument, and  thus must
|
|
 <br />-- be applied to non-empty lists.  scanl is similar to foldl, but returns
|
|
 <br />-- a list of successive reduced values from the left:
|
|
 <br />--      scanl f z [x1, x2, ...] == [z, z ‘f‘ x1, (z ‘f‘ x1) ‘f‘ x2, ...]
|
|
 <br />-- Note that  last (scanl f z xs) == foldl f z xs.
|
|
 <br />-- scanl1 is similar, again without the starting element:
|
|
 <br />--      scanl1 f [x1, x2, ...] == [x1, x1 ‘f‘ x2, ...]
|
|
 <br />
|
|
 <br />foldl            :: (a -> b -> a) -> a -> [b] -> a
|
|
 <br />foldl f z []     =  z
|
|
 <br />foldl f z (x:xs) =  foldl f (f z x) xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172018"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-255">
|
|
foldl1           :: (a -> a -> a) -> [a] -> a
|
|
 <br />foldl1 f (x:xs)  =  foldl f x xs
|
|
 <br />foldl1 _ []      =  error "Prelude.foldl1: empty list"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172019"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-256">
|
|
scanl            :: (a -> b -> a) -> a -> [b] -> [a]
|
|
 <br />scanl f q xs     =  q : (case xs of
|
|
 <br />                            []   -> []
|
|
 <br />                            x:xs -> scanl f (f q x) xs)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172020"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-257">
|
|
scanl1           :: (a -> a -> a) -> [a] -> [a]
|
|
 <br />scanl1 f (x:xs)  =  scanl f x xs
|
|
 <br />scanl1 _ []      =  []
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172021"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-258">
|
|
-- foldr, foldr1, scanr, and scanr1 are the right-to-left duals of the
|
|
 <br />-- above functions.
|
|
 <br />
|
|
 <br />foldr            :: (a -> b -> b) -> b -> [a] -> b
|
|
 <br />foldr f z []     =  z
|
|
 <br />foldr f z (x:xs) =  f x (foldr f z xs)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172022"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-259">
|
|
foldr1           :: (a -> a -> a) -> [a] -> a
|
|
 <br />foldr1 f [x]     =  x
|
|
 <br />foldr1 f (x:xs)  =  f x (foldr1 f xs)
|
|
 <br />foldr1 _ []      =  error "Prelude.foldr1: empty list"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172023"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-260">
|
|
scanr             :: (a -> b -> b) -> b -> [a] -> [b]
|
|
 <br />scanr f q0 []     =  [q0]
|
|
 <br />scanr f q0 (x:xs) =  f x q : qs
|
|
 <br />                     where qs@(q:_) = scanr f q0 xs 
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172024"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-261">
|
|
scanr1          :: (a -> a -> a) -> [a] -> [a]
|
|
 <br />scanr1 f []     =  []
|
|
 <br />scanr1 f [x]    =  [x]
|
|
 <br />scanr1 f (x:xs) =  f x q : qs
|
|
 <br />                   where qs@(q:_) = scanr1 f xs 
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172025"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-262">
|
|
-- iterate f x returns an infinite list of repeated applications of f to x:
|
|
 <br />-- iterate f x == [x, f x, f (f x), ...]
|
|
 <br />iterate          :: (a -> a) -> a -> [a]
|
|
 <br />iterate f x      =  x : iterate f (f x)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172026"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-263">
|
|
-- repeat x is an infinite list, with x the value of every element.
|
|
 <br />repeat           :: a -> [a]
|
|
 <br />repeat x         =  xs where xs = x:xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172027"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-264">
|
|
-- replicate n x is a list of length n with x the value of every element
|
|
 <br />replicate        :: Int -> a -> [a]
|
|
 <br />replicate n x    =  take n (repeat x)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172028"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-265">
|
|
-- cycle ties a finite list into a circular one, or equivalently,
|
|
 <br />-- the infinite repetition of the original list.  It is the identity
|
|
 <br />-- on infinite lists.
|
|
 <br />
|
|
 <br />cycle            :: [a] -> [a]
|
|
 <br />cycle []         =  error "Prelude.cycle: empty list"
|
|
 <br />cycle xs         =  xs' where xs' = xs ++ xs'
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172029"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-266">
|
|
-- take n, applied to a list xs, returns the prefix of xs of length n,
|
|
 <br />-- or xs itself if n > length xs.  drop n xs returns the suffix of xs
|
|
 <br />-- after the first n elements, or [] if n > length xs.  splitAt n xs
|
|
 <br />-- is equivalent to (take n xs, drop n xs).
|
|
 <br />
|
|
 <br />take                   :: Int -> [a] -> [a]
|
|
 <br />take n _      | n <= 0 =  []
|
|
 <br />take _ []              =  []
|
|
 <br />take n (x:xs)          =  x : take (n-1) xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172030"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-267">
|
|
drop                   :: Int -> [a] -> [a]
|
|
 <br />drop n xs     | n <= 0 =  xs
|
|
 <br />drop _ []              =  []
|
|
 <br />drop n (_:xs)          =  drop (n-1) xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172031"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-268">
|
|
splitAt                  :: Int -> [a] -> ([a],[a])
|
|
 <br />splitAt n xs             =  (take n xs, drop n xs)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172032"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-269">
|
|
-- takeWhile, applied to a predicate p and a list xs, returns the longest
|
|
 <br />-- prefix (possibly empty) of xs of elements that satisfy p.  dropWhile p xs
|
|
 <br />-- returns the remaining suffix.  span p xs is equivalent to
|
|
 <br />-- (takeWhile p xs, dropWhile p xs), while break p uses the negation of p.
|
|
 <br />
|
|
 <br />takeWhile               :: (a -> Bool) -> [a] -> [a]
|
|
 <br />takeWhile p []          =  []
|
|
 <br />takeWhile p (x:xs)
|
|
 <br />            | p x       =  x : takeWhile p xs
|
|
 <br />            | otherwise =  []
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172033"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-270">
|
|
dropWhile               :: (a -> Bool) -> [a] -> [a]
|
|
 <br />dropWhile p []          =  []
|
|
 <br />dropWhile p xs@(x:xs')
|
|
 <br />            | p x       =  dropWhile p xs'
|
|
 <br />            | otherwise =  xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172034"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-271">
|
|
span, break             :: (a -> Bool) -> [a] -> ([a],[a])
|
|
 <br />span p []            = ([],[])
|
|
 <br />span p xs@(x:xs')
|
|
 <br />            | p x       =  (x:ys,zs)
|
|
 <br />            | otherwise =  ([],xs)
|
|
 <br />                           where (ys,zs) = span p xs'
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172035"></a><a
|
|
id="dx16-172036"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-272">
|
|
break p                 =  span (not . p)
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-273">
|
|
-- lines breaks a string up into a list of strings at newline characters.
|
|
 <br />-- The resulting strings do not contain newlines.  Similary, words
|
|
 <br />-- breaks a string up into a list of words, which were delimited by
|
|
 <br />-- white space.  unlines and unwords are the inverse operations.
|
|
 <br />-- unlines joins lines with terminating newlines, and unwords joins
|
|
 <br />-- words with separating spaces.
|
|
 <br />
|
|
 <br />lines            :: String -> [String]
|
|
 <br />lines ""         =  []
|
|
 <br />lines s          =  let (l, s') = break (== '\n') s
|
|
 <br />                      in  l : case s' of
|
|
 <br />                                []      -> []
|
|
 <br />                                (_:s'') -> lines s''
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172037"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-274">
|
|
words            :: String -> [String]
|
|
 <br />words s          =  case dropWhile Char.isSpace s of
|
|
 <br />                      "" -> []
|
|
 <br />                      s' -> w : words s''
|
|
 <br />                            where (w, s'') = break Char.isSpace s'
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172038"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-275">
|
|
unlines          :: [String] -> String
|
|
 <br />unlines          =  concatMap (++ "\n")
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172039"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-276">
|
|
unwords          :: [String] -> String
|
|
 <br />unwords []       =  ""
|
|
 <br />unwords ws       =  foldr1 (\w s -> w ++ ' ':s) ws
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172040"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-277">
|
|
-- reverse xs returns the elements of xs in reverse order.  xs must be finite.
|
|
 <br />reverse          :: [a] -> [a]
|
|
 <br />reverse          =  foldl (flip (:)) []
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172041"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-278">
|
|
-- and returns the conjunction of a Boolean list.  For the result to be
|
|
 <br />-- True, the list must be finite; False, however, results from a False
|
|
 <br />-- value at a finite index of a finite or infinite list.  or is the
|
|
 <br />-- disjunctive dual of and.
|
|
 <br />and, or          :: [Bool] -> Bool
|
|
 <br />and              =  foldr (&&) True
|
|
 <br />or               =  foldr (||) False
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172042"></a><a
|
|
id="dx16-172043"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-279">
|
|
-- Applied to a predicate and a list, any determines if any element
|
|
 <br />-- of the list satisfies the predicate.  Similarly, for all.
|
|
 <br />any, all         :: (a -> Bool) -> [a] -> Bool
|
|
 <br />any p            =  or . map p
|
|
 <br />all p            =  and . map p
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172044"></a><a
|
|
id="dx16-172045"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-280">
|
|
-- elem is the list membership predicate, usually written in infix form,
|
|
 <br />-- e.g., x ‘elem‘ xs.  notElem is the negation.
|
|
 <br />elem, notElem    :: (Eq a) => a -> [a] -> Bool
|
|
 <br />elem x           =  any (== x)
|
|
 <br />notElem x        =  all (/= x)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172046"></a><a
|
|
id="dx16-172047"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-281">
|
|
-- lookup key assocs looks up a key in an association list.
|
|
 <br />lookup           :: (Eq a) => a -> [(a,b)] -> Maybe b
|
|
 <br />lookup key []    =  Nothing
|
|
 <br />lookup key ((x,y):xys)
|
|
 <br />    | key == x   =  Just y
|
|
 <br />    | otherwise  =  lookup key xys
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172048"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-282">
|
|
-- sum and product compute the sum or product of a finite list of numbers.
|
|
 <br />sum, product     :: (Num a) => [a] -> a
|
|
 <br />sum              =  foldl (+) 0
|
|
 <br />product          =  foldl (⋆) 1
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172049"></a><a
|
|
id="dx16-172050"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-283">
|
|
-- maximum and minimum return the maximum or minimum value from a list,
|
|
 <br />-- which must be non-empty, finite, and of an ordered type.
|
|
 <br />maximum, minimum :: (Ord a) => [a] -> a
|
|
 <br />maximum []       =  error "Prelude.maximum: empty list"
|
|
 <br />maximum xs       =  foldl1 max xs
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172051"></a><a
|
|
id="dx16-172052"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-284">
|
|
minimum []       =  error "Prelude.minimum: empty list"
|
|
 <br />minimum xs       =  foldl1 min xs
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-285">
|
|
-- zip takes two lists and returns a list of corresponding pairs.  If one
|
|
 <br />-- input list is short, excess elements of the longer list are discarded.
|
|
 <br />-- zip3 takes three lists and returns a list of triples.  Zips for larger
|
|
 <br />-- tuples are in the List library
|
|
 <br />
|
|
 <br />zip              :: [a] -> [b] -> [(a,b)]
|
|
 <br />zip              =  zipWith (,)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172053"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-286">
|
|
zip3             :: [a] -> [b] -> [c] -> [(a,b,c)]
|
|
 <br />zip3             =  zipWith3 (,,)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172054"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-287">
|
|
-- The zipWith family generalises the zip family by zipping with the
|
|
 <br />-- function given as the first argument, instead of a tupling function.
|
|
 <br />-- For example, zipWith (+) is applied to two lists to produce the list
|
|
 <br />-- of corresponding sums.
|
|
 <br />
|
|
 <br />zipWith          :: (a->b->c) -> [a]->[b]->[c]
|
|
 <br />zipWith z (a:as) (b:bs)
|
|
 <br />                 =  z a b : zipWith z as bs
|
|
 <br />zipWith _ _ _    =  []
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172055"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-288">
|
|
zipWith3         :: (a->b->c->d) -> [a]->[b]->[c]->[d]
|
|
 <br />zipWith3 z (a:as) (b:bs) (c:cs)
|
|
 <br />                 =  z a b c : zipWith3 z as bs cs
|
|
 <br />zipWith3 _ _ _ _ =  []
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172056"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-289">
|
|
-- unzip transforms a list of pairs into a pair of lists.
|
|
 <br />
|
|
 <br />unzip            :: [(a,b)] -> ([a],[b])
|
|
 <br />unzip            =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172057"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-290">
|
|
unzip3           :: [(a,b,c)] -> ([a],[b],[c])
|
|
 <br />unzip3           =  foldr (\(a,b,c) ~(as,bs,cs) -> (a:as,b:bs,c:cs))
|
|
 <br />                          ([],[],[])
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-172058"></a>
|
|
|
|
|
|
|
|
<h3 class="sectionHead"><span class="titlemark">9.2 </span> <a
|
|
id="x16-1730009.2"></a>Prelude <span
|
|
class="pcrr7t-">PreludeText</span></h3>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-291">
|
|
module PreludeText (
|
|
 <br />    ReadS, ShowS,
|
|
 <br />    Read(readsPrec, readList),
|
|
 <br />    Show(showsPrec, show, showList),
|
|
 <br />    reads, shows, read, lex,
|
|
 <br />    showChar, showString, readParen, showParen ) where
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173001"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-292">
|
|
-- The instances of Read and Show for
|
|
 <br />--      Bool, Maybe, Either, Ordering
|
|
 <br />-- are done via "deriving" clauses in Prelude.hs
|
|
 <br />
|
|
 <br />import Data.Char(isSpace, isAlpha, isDigit, isAlphaNum,
|
|
 <br />                 showLitChar, readLitChar, lexLitChar)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173002"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-293">
|
|
import Numeric(showSigned, showInt, readSigned, readDec, showFloat,
|
|
 <br />               readFloat, lexDigits)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173003"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-294">
|
|
type  ReadS a  = String -> [(a,String)]
|
|
 <br />type  ShowS    = String -> String
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173004"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-295">
|
|
class  Read a  where
|
|
 <br />    readsPrec        :: Int -> ReadS a
|
|
 <br />    readList         :: ReadS [a]
|
|
 <br />
|
|
 <br />        -- Minimal complete definition:
|
|
 <br />        --      readsPrec
|
|
 <br />    readList         = readParen False (\r -> [pr | ("[",s)  <- lex r,
|
|
 <br />                                                    pr       <- readl s])
|
|
 <br />                       where readl  s = [([],t)   | ("]",t)  <- lex s] ++
|
|
 <br />                                        [(x:xs,u) | (x,t)    <- reads s,
|
|
 <br />                                                    (xs,u)   <- readl' t]
|
|
 <br />                             readl' s = [([],t)   | ("]",t)  <- lex s] ++
|
|
 <br />                                        [(x:xs,v) | (",",t)  <- lex s,
|
|
 <br />                                                    (x,u)    <- reads t,
|
|
 <br />                                                    (xs,v)   <- readl' u]
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-296">
|
|
class  Show a  where
|
|
 <br />    showsPrec        :: Int -> a -> ShowS
|
|
 <br />    show             :: a -> String
|
|
 <br />    showList         :: [a] -> ShowS
|
|
 <br />
|
|
 <br />        -- Mimimal complete definition:
|
|
 <br />        --      show or showsPrec
|
|
 <br />    showsPrec _ x s   = show x ++ s
|
|
 <br />
|
|
 <br />    show x            = showsPrec 0 x ""
|
|
 <br />
|
|
 <br />    showList []       = showString "[]"
|
|
 <br />    showList (x:xs)   = showChar '[' . shows x . showl xs
|
|
 <br />                        where showl []     = showChar ']'
|
|
 <br />                              showl (x:xs) = showChar ',' . shows x .
|
|
 <br />                                             showl xs
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-297">
|
|
reads            :: (Read a) => ReadS a
|
|
 <br />reads            =  readsPrec 0
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173005"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-298">
|
|
shows            :: (Show a) => a -> ShowS
|
|
 <br />shows            =  showsPrec 0
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173006"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-299">
|
|
read             :: (Read a) => String -> a
|
|
 <br />read s           =  case [x | (x,t) <- reads s, ("","") <- lex t] of
|
|
 <br />                         [x] -> x
|
|
 <br />                         []  -> error "Prelude.read: no parse"
|
|
 <br />                         _   -> error "Prelude.read: ambiguous parse"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173007"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-300">
|
|
showChar         :: Char -> ShowS
|
|
 <br />showChar         =  (:)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173008"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-301">
|
|
showString       :: String -> ShowS
|
|
 <br />showString       =  (++)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173009"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-302">
|
|
showParen        :: Bool -> ShowS -> ShowS
|
|
 <br />showParen b p    =  if b then showChar '(' . p . showChar ')' else p
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173010"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-303">
|
|
readParen        :: Bool -> ReadS a -> ReadS a
|
|
 <br />readParen b g    =  if b then mandatory else optional
|
|
 <br />                    where optional r  = g r ++ mandatory r
|
|
 <br />                          mandatory r = [(x,u) | ("(",s) <- lex r,
|
|
 <br />                                                 (x,t)   <- optional s,
|
|
 <br />                                                 (")",u) <- lex t    ]
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173011"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-304">
|
|
-- This lexer is not completely faithful to the Haskell lexical syntax.
|
|
 <br />-- Current limitations:
|
|
 <br />--    Qualified names are not handled properly
|
|
 <br />--    Octal and hexidecimal numerics are not recognized as a single token
|
|
 <br />--    Comments are not treated properly
|
|
 <br />
|
|
 <br />lex              :: ReadS String
|
|
 <br />lex ""           =  [("","")]
|
|
 <br />lex (c:s)
|
|
 <br />   | isSpace c   =  lex (dropWhile isSpace s)
|
|
 <br />lex ('\'':s)     =  [('\'':ch++"'", t) | (ch,'\'':t)  <- lexLitChar s,
|
|
 <br />                                         ch /= "'" ]
|
|
 <br />lex ('"':s)      =  [('"':str, t)      | (str,t) <- lexString s]
|
|
 <br />                    where
|
|
 <br />                    lexString ('"':s) = [("\"",s)]
|
|
 <br />                    lexString s = [(ch++str, u)
|
|
 <br />                                         | (ch,t)  <- lexStrItem s,
|
|
 <br />                                           (str,u) <- lexString t  ]
|
|
 <br />
|
|
 <br />                    lexStrItem ('\\':'&':s) =  [("\\&",s)]
|
|
 <br />                    lexStrItem ('\\':c:s) | isSpace c
|
|
 <br />                                           =  [("\\&",t) |
|
|
 <br />                                               '\\':t <-
|
|
 <br />                                                   [dropWhile isSpace s]]
|
|
 <br />                    lexStrItem s           =  lexLitChar s
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-173012"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-305">
|
|
lex (c:s) | isSingle c = [([c],s)]
|
|
 <br />          | isSym c    = [(c:sym,t)       | (sym,t) <- [span isSym s]]
|
|
 <br />          | isAlpha c  = [(c:nam,t)       | (nam,t) <- [span isIdChar s]]
|
|
 <br />          | isDigit c  = [(c:ds++fe,t)    | (ds,s)  <- [span isDigit s],
|
|
 <br />                                            (fe,t)  <- lexFracExp s     ]
|
|
 <br />          | otherwise  = []    -- bad character
|
|
 <br />             where
|
|
 <br />              isSingle c =  c ‘elem‘ ",;()[]{}_‘"
|
|
 <br />              isSym c    =  c ‘elem‘ "!@#$%&⋆+./<=>?\\^|:-~"
|
|
 <br />              isIdChar c =  isAlphaNum c || c ‘elem‘ "_'"
|
|
 <br />
|
|
 <br />              lexFracExp ('.':c:cs) | isDigit c
|
|
 <br />                            = [('.':ds++e,u) | (ds,t) <- lexDigits (c:cs),
|
|
 <br />                                               (e,u)  <- lexExp t]
|
|
 <br />              lexFracExp s  = lexExp s
|
|
 <br />
|
|
 <br />              lexExp (e:s) | e ‘elem‘ "eE"
|
|
 <br />                       = [(e:c:ds,u) | (c:t)  <- [s], c ‘elem‘ "+-",
|
|
 <br />                                                 (ds,u) <- lexDigits t] ++
|
|
 <br />                         [(e:ds,t)   | (ds,t) <- lexDigits s]
|
|
 <br />              lexExp s = [("",s)]
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-306">
|
|
instance  Show Int  where
|
|
 <br />    showsPrec n = showsPrec n . toInteger
|
|
 <br />        -- Converting to Integer avoids
|
|
 <br />        -- possible difficulty with minInt
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-307">
|
|
instance  Read Int  where
|
|
 <br />  readsPrec p r = [(fromInteger i, t) | (i,t) <- readsPrec p r]
|
|
 <br />        -- Reading at the Integer type avoids
|
|
 <br />        -- possible difficulty with minInt
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-308">
|
|
instance  Show Integer  where
|
|
 <br />    showsPrec           = showSigned showInt
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-309">
|
|
instance  Read Integer  where
|
|
 <br />    readsPrec p         = readSigned readDec
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-310">
|
|
instance  Show Float  where
|
|
 <br />    showsPrec p         = showFloat
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-311">
|
|
instance  Read Float  where
|
|
 <br />    readsPrec p         = readSigned readFloat
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-312">
|
|
instance  Show Double  where
|
|
 <br />    showsPrec p         = showFloat
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-313">
|
|
instance  Read Double  where
|
|
 <br />    readsPrec p         = readSigned readFloat
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-314">
|
|
instance  Show ()  where
|
|
 <br />    showsPrec p () = showString "()"
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-315">
|
|
instance Read () where
|
|
 <br />    readsPrec p    = readParen False
|
|
 <br />                            (\r -> [((),t) | ("(",s) <- lex r,
|
|
 <br />                                             (")",t) <- lex s ] )
|
|
 <br />instance  Show Char  where
|
|
 <br />    showsPrec p '\'' = showString "'\\''"
|
|
 <br />    showsPrec p c    = showChar '\'' . showLitChar c . showChar '\''
|
|
 <br />
|
|
 <br />    showList cs = showChar '"' . showl cs
|
|
 <br />                 where showl ""       = showChar '"'
|
|
 <br />                       showl ('"':cs) = showString "\\\"" . showl cs
|
|
 <br />                       showl (c:cs)   = showLitChar c . showl cs
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-316">
|
|
instance  Read Char  where
|
|
 <br />    readsPrec p      = readParen False
|
|
 <br />                            (\r -> [(c,t) | ('\'':s,t)<- lex r,
|
|
 <br />                                            (c,"\'")  <- readLitChar s])
|
|
 <br />
|
|
 <br />    readList = readParen False (\r -> [(l,t) | ('"':s, t) <- lex r,
|
|
 <br />                                               (l,_)      <- readl s ])
|
|
 <br />        where readl ('"':s)      = [("",s)]
|
|
 <br />              readl ('\\':'&':s) = readl s
|
|
 <br />              readl s            = [(c:cs,u) | (c ,t) <- readLitChar s,
|
|
 <br />                                               (cs,u) <- readl t       ]
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-317">
|
|
instance  (Show a) => Show [a]  where
|
|
 <br />    showsPrec p      = showList
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-318">
|
|
instance  (Read a) => Read [a]  where
|
|
 <br />    readsPrec p      = readList
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-319">
|
|
-- Tuples
|
|
 <br />
|
|
 <br />instance  (Show a, Show b) => Show (a,b)  where
|
|
 <br />    showsPrec p (x,y) = showChar '(' . shows x . showChar ',' .
|
|
 <br />                                       shows y . showChar ')'
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-320">
|
|
instance  (Read a, Read b) => Read (a,b)  where
|
|
 <br />    readsPrec p       = readParen False
|
|
 <br />                            (\r -> [((x,y), w) | ("(",s) <- lex r,
|
|
 <br />                                                 (x,t)   <- reads s,
|
|
 <br />                                                 (",",u) <- lex t,
|
|
 <br />                                                 (y,v)   <- reads u,
|
|
 <br />                                                 (")",w) <- lex v ] )
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-321">
|
|
-- Other tuples have similar Read and Show instances
|
|
 <br />
|
|
 <br />
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<h3 class="sectionHead"><span class="titlemark">9.3 </span> <a
|
|
id="x16-1740009.3"></a>Prelude <span
|
|
class="pcrr7t-">PreludeIO</span></h3>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-322">
|
|
module PreludeIO (
|
|
 <br />    FilePath, IOError, ioError, userError, catch,
|
|
 <br />    putChar, putStr, putStrLn, print,
|
|
 <br />    getChar, getLine, getContents, interact,
|
|
 <br />    readFile, writeFile, appendFile, readIO, readLn
|
|
 <br />  ) where
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174001"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-323">
|
|
import PreludeBuiltin
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174002"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-324">
|
|
type  FilePath = String
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174003"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-325">
|
|
data IOError    -- The internals of this type are system dependent
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174004"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-326">
|
|
instance  Show IOError  where ...
|
|
 <br />instance  Eq IOError  where ...
|
|
</div>
|
|
<p class="noindent">
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-327">
|
|
ioError    ::  IOError -> IO a
|
|
 <br />ioError    =   primIOError
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174005"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-328">
|
|
userError  ::  String -> IOError
|
|
 <br />userError  =   primUserError
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174006"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-329">
|
|
catch      ::  IO a -> (IOError -> IO a) -> IO a
|
|
 <br />catch      =   primCatch
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174007"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-330">
|
|
putChar    :: Char -> IO ()
|
|
 <br />putChar    =  primPutChar
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174008"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-331">
|
|
putStr     :: String -> IO ()
|
|
 <br />putStr s   =  mapM_ putChar s
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174009"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-332">
|
|
putStrLn   :: String -> IO ()
|
|
 <br />putStrLn s =  do putStr s
|
|
 <br />                 putStr "\n"
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174010"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-333">
|
|
print      :: Show a => a -> IO ()
|
|
 <br />print x    =  putStrLn (show x)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174011"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-334">
|
|
getChar    :: IO Char
|
|
 <br />getChar    =  primGetChar
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174012"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-335">
|
|
getLine    :: IO String
|
|
 <br />getLine    =  do c <- getChar
|
|
 <br />                 if c == '\n' then return "" else
|
|
 <br />                    do s <- getLine
|
|
 <br />                       return (c:s)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174013"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-336">
|
|
getContents :: IO String
|
|
 <br />getContents =  primGetContents
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174014"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-337">
|
|
interact    ::  (String -> String) -> IO ()
|
|
 <br />-- The hSetBuffering ensures the expected interactive behaviour
|
|
 <br />interact f  =  do hSetBuffering stdin  NoBuffering
|
|
 <br />                  hSetBuffering stdout NoBuffering
|
|
 <br />                  s <- getContents
|
|
 <br />                  putStr (f s)
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174015"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-338">
|
|
readFile   :: FilePath -> IO String
|
|
 <br />readFile   =  primReadFile
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174016"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-339">
|
|
writeFile  :: FilePath -> String -> IO ()
|
|
 <br />writeFile  =  primWriteFile
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174017"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-340">
|
|
appendFile :: FilePath -> String -> IO ()
|
|
 <br />appendFile =  primAppendFile
|
|
 <br />
|
|
 <br />  -- raises an exception instead of an error
|
|
 <br />readIO   :: Read a => String -> IO a
|
|
 <br />readIO s =  case [x | (x,t) <- reads s, ("","") <- lex t] of
|
|
 <br />              [x] -> return x
|
|
 <br />              []  -> ioError (userError "Prelude.readIO: no parse")
|
|
 <br />              _   -> ioError (userError "Prelude.readIO: ambiguous parse")
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174018"></a>
|
|
|
|
|
|
|
|
<div class="verbatim" id="verbatim-341">
|
|
readLn :: Read a => IO a
|
|
 <br />readLn =  do l <- getLine
|
|
 <br />             r <- readIO l
|
|
 <br />             return r
|
|
</div>
|
|
<p class="noindent"> <a
|
|
id="dx16-174019"></a>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<!--l. 6--><div class="crosslinks"><p class="noindent">[<a
|
|
href="haskellch10.html" >next</a>] [<a
|
|
href="haskellch8.html" >prev</a>] [<a
|
|
href="haskellch8.html#tailhaskellch8.html" >prev-tail</a>] [<a
|
|
href="haskellch9.html" >front</a>] [<a
|
|
href="haskellpa1.html#haskellch9.html" >up</a>] </p></div>
|
|
<p class="noindent"> <a
|
|
id="tailhaskellch9.html"></a>
|
|
</body></html>
|