CS 345 slide 225 Spring 200529 March 2005Now we can specify the most general types of functionslike insert and insertSort:> insert :: Ord a => a -> [a] -> [a]> insert x [ ] = [x]> insert x (y:ys)> | x <= y = x:y:ys> | otherwise = y : insert x ys> insertSort :: Ord a => [a] -> [a]> insertSort = foldr insert []Bool is an instance of Ord as well as of Eq:> instance Ord Bool where> False <= _ = True> True <= x = xInt, Integer, Float, and Double belong to Eq and Ord:> instance Eq Int where (==) = primEqInt> instance Ord Int where compare = primCmpInt> instance Ord Integer> where compare = primCmpInteger> instance Eq Float where (==) = primEqFloat> instance Ord Float where compare = primCmpFloatThese prim… functions are Prelude names forfunctions which are provided by the platform(MacOS, Windows, AIX, Solaris, etc.).> primitive primEqInt :: Int -> Int -> Bool> primitive primCmpInt :: Int -> Int -> Orderingetc.CS 345 slide 226 Spring 200529 March 2005Lists belong not only to Eq but also to Ord —providedtheir elements’ type belongs to Ord:> instance Ord a => Ord [a] where> compare [] (_:_) = LT> compare [] [] = EQ> compare (_:_) [ ] = GT> compare (x:xs) (y:ys)> = primCompAux x y (compare xs ys)> where> primCompAux> :: Ord a => a -> a -> Ordering -> Ordering> primCompAux x y o> = case compare x y of> LT -> LT; EQ -> o; GT -> GTNumbers need more than Eq guarantees—> class (Eq a, Show a) => Num a where> (+), (-), (*) :: a -> a -> a> negate :: a -> a> abs, signum :: a -> a> fromInteger :: Integer -> a> fromInt :: Int -> a> x - y = x + negate y> fromInt = fromIntegral> negate x = 0 - x(Types in class Show have functions that convert theirvalues to String.)CS 345 slide 227 Spring 200529 March 2005Num is derived from Eq, but not from Ord, because notall “numeric” types support (<=); for example—complex numbers and matrices.Two of the instance declarations for Num types:> instance Num Int where> (+) = primPlusInt> (-) = primMinusInt> negate = primNegInt> (*) = primMulInt> abs = absReal> signum = signumReal> fromInteger = primIntegerToInt> fromInt x = x> instance Num Float where> (+) = primPlusFloat> (-) = primMinusFloat> negate = primNegFloat> (*) = primMulFloat> abs = absReal> signum = signumReal> fromInteger = primIntegerToFloat> fromInt = primIntToFloatCS 345 slide 228 Spring 200529 March 2005The hierarchy of Haskell classes defined in thePrelude, and the classes’ signatures:RealFrac properFraction truncate, round ceiling, floorShow show showsPrec showListEq (==),(/=)Num (+),(-),(*) negate abs,signum fromInteger fromIntFractional (/) recip fromRational fromDouble Floating pi exp, log, sqrt (**), logBase sin, cos, tan asin, acos, atan sinh, cosh, tanh asinh, acosh, atanhRealFloat floatRadix floatDigits floatRange decodeFloat encodeFloat exponent significand scaleFloat isNaN, isInfinite isDenormalized isNegativeZero, isIEEE atan2Ord compare (<),(<=) (>=),(>) max, minIntegral quot,rem,div,mod quotRem,divMod even,odd toInteger toIntReal toRationalEnum succ, pred toEnum fromEnum enumFrom -- [n..] enumFromThen -- [n,m..] enumFromTo -- [n..m] enumFromThenTo -- [n,n'..m]Read read reads readsPrec readListBounded minBound maxBoundMonad return (>>=) (>>) failCS 345 slide 229 Spring 200529 March 2005The hierarchy of Haskell classes defined in thePrelude, and the Prelude types that are instances ofthese classes:CS 345 slide 230 Spring 200529 March 2005Type classes and Algebraic typesFor some classes, the Haskell compiler can derivealgebraic-type instance declarations automatically:For example,> data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat> deriving (Eq, Ord, Enum, Show, Read, Bounded)(Enum instances valid only for enumerated types).Main> Tue == TueTrueMain> Mon < WedTrueMain> Mon > WedFalseMain> max Tue ThuThuMain> sort [Thu,Tue,Sun,Wed][Sun,Tue,Wed,Thu]Main> [Mon .. Fri][Mon,Tue,Wed,Thu,Fri]Main> read "Sat" :: DaySatMain> reads "Sat.." :: [(Day,String)][(Sat,"..")]Main> maxBound :: DaySatMain> minBound :: DaySunCS 345 slide 231 Spring 200529 March 2005Derived instances aren’t always useful.> data Temp = Celsius Float | Fahrenheit Float> deriving (Eq, Ord, Show, Read)Main> read "Celsius 12" :: TempCelsius 12.0Main> show (Fahrenheit 451)"Fahrenheit 451.0"Main> Celsius 35 < Celsius 40TrueMain> Celsius 35 < Fahrenheit 0True -- oopsMain> Celsius 0 == Fahrenheit 32False -- oopsBetter:> data Temp = Celsius Float | Fahrenheit Float> deriving (Show, Read)> instance Eq Temp where> t1 == t2 = degreesC t1 == degreesC t2> instance Ord Temp where> t1 <= t2 = degreesC t1 <= degreesC t2> degreesC :: Temp -> Float> degreesC (Celsius d) = d> degreesC (Fahrenheit d) = 5/9 * (d - 32)CS 345 slide 232 Spring 200529 March 2005Procedures and Functions in ImperativeLanguages: Definition & InvocationTerminology:functions return values —their invocations can be used as expressions(can also cause state changes)procedures cause state changes only —their invocations cannot be used as expressionsC nomenclature uses “function” for both.Modula–2 nomenclature uses “PROCEDURE” for both(function procedures have return types)Sethi’s nomenclature:function procedure (or “function”)proper procedure (or “procedure”)A procedure (either kind) is an abstraction (i.e., ageneralization)body: a program text that is defined once,used many times with differentbindings for its free namesparameters: names that are free in the proced-ure’s body, bound to caller’s argu-ments (variables or expressions) ateach