CS 345 slide 65 Spring 20053 February 2005Making lazy functions strictArgument evaluation can be forced by using theoperator ($!), whose meaning (but not its implemen-tation) is described by the equation: f $! x = if x ≠ then f x else This has the effect of evaluating x and then applyingf to the result. In other words, lazy evaluation isreplaced by innermost evaluation.Provided x ≠ , f $! x == f x .When using ($!), note that• ($!) is an operator, so it is used in expressions,not in definitions’ left-hand sides• ($!) associates to the rightExample:Prelude> False && (3/0 == 1)FalsePrelude> (False &&) (3/0 == 1)FalsePrelude> (False &&) $! (3/0 == 1)Program error: {primDivDouble 3.0 0.0}A strictified version of facT (Slide 60)> facTS n a> = if n==0 then a else facTS (n –1) $! (n*a)A calculation:facTS 4 1H S facTS 3 4H S facTS 2 12H S facTS 1 24H S facTS 0 24H S 24CS 345 slide 66 Spring 20053 February 2005TypesDespite the absence of type declarations in all of ourexamples so far, Haskell is statically typed: types arechecked at compile time.In most cases, the compiler can infer types withoutdeclarations. Nevertheless, in this class we requirethat Haskell definitions be accompanied by typedeclarations. For example, adding > fac2 :: Int -> Intto the script in which fac2 is defined would declarefac2 to be applicable to Int arguments, returning Intresults.Type declarations have the formExpression :: TypeExpand the (partial) syntax of type expressions isTypeExp ::= (TypeName | TypeVar) [ -> TypeExp ]TypeName ::= Uppercase { Letter }TypeVar ::= Lowercase { Letter }A function’s type always includes not only the typeof its result, but also the types of its argument(s).Each argument’s type is followed by “->”.So\x y -> if x then y+2 else y -3 :: Bool -> Int -> IntCompare with C++:f :: Int -> Int -> Int -- Haskellint f( int, int ); // C, C++, JavaCS 345 slide 67 Spring 20053 February 2005Polymorphic typesWhen the type of an argument or result is uncon-strained by how it is used, it is represented in a typeexpression by a type variable.For example, because (\x -> 7) can be applied toargments of any type whatsoever, with norestrictions, its type is(\x -> 7) :: a -> IntA type whose type expression contains a variable isknown as a polymorphic type.Type variables follow the usual rules for variables inexpressions, so\x -> x :: a -> ameans that• (\x -> x) (the identity function) can be applied toarguments of any type whatsoever• the result’s type is the same as the argument’stype.A type variable’s scope is limited to the typeexpression in which it appears.Restricted polymorphismSome functions are applicable to arguments of morethan one type, but not of all types. For example,\x -> x + 2 :: Num a => a -> abecause the types• for which operator (+) is defined• which can be represented by sequences of digitsare exactly the types belonging to the type class Num,which contains Int, Integer, Float, and Double.Both (+) and 2 are said to be overloaded.CS 345 slide 68 Spring 20053 February 2005Hugs gives expressions’ typesHUGS98 can be asked to show any expression’s type.The show-type command is :type (or just :t).For examplePrelude> :t (+)(+) :: Num a => a -> a -> aPrelude> :t 22 :: Num a => aPrelude> :t \x y -> if x then y+2 else y-3\x y -> if x then y+2 els e y -3 :: Num a => Boo l -> a -> aThe last type is not the same as the one given abovefor the same function:\x y -> if x then y+2 els e y -3 :: Boo l -> In t -> Intbut both are correct.The type given by HUGS98 is the function’s mostgeneral type. The compiler checks any item’s declaredtype for consistency with its most general type.It’s OK to declare an item to have a less general typeprovided it’s consistent with the item’s most generaltype, i.e., it can be obtained from the most generaltype by replacing variables with non-variables. Theeffect is to restrict the function’s type to the declaredone.CS 345 slide 69 Spring 20053 February 2005The difference between Int and Integer is illustratedby the following examples:Main> fac2 (20::Int)-2102132736Main> fac2 (20::Integer)2432902008176640000These examples exhibit several other aspects ofHaskell’s type system:• Int consists of the limited-magnitude integersfurnished by the processor.• Integer is a type of unlimited-magnitude integers.• An overloaded item can be restricted to a specifictype by giving the restricted type explicitly.• As in most programming languages, many built-in functions, e.g. (*), are overloaded.• Unlike most programming languages, Haskellfunctions which apply overloaded functions totheir arguments, e.g. fac2, “inherit” the over-loading.Haskell’s other main “built-in” typesFloat, Double -- the usual floating-point valuesBool -- {False, True}Char -- asciiString -- list of CharCS 345 slide 70 Spring 20053 February 2005Numeric type conversionIn Haskell (unlike C/C++), type conversion is notautomatic.Numeric conversion functions are provided, but theymust be applied explicitly.Each numeric type b provides functionsfromInteger :: Integer -> b fromInt :: Int -> bIn addition, Float and Double providetruncate, round :: a -> bwhere a { Float, Double }b { Int, Integer }Note: The selection of the result type (Int or Integer)depends on the context.Integer literals are overloaded:“An integer numeral (without a decimal point) is …equivalent to an application of fromInteger to thevalue of the numeral as an Integer.”Prelude> 3.0 + 47.0Prelude> 3.0 + (2+4)9.0Prelude> 3.0 + (6 :: Int)ERROR - Illegal Haskell 98 class constraint ininferred type*** Expression : 3.0 + 6*** Type : Fractional Int => IntPrelude>:t 33 :: Num a => aCS 345 slide 71 Spring 20053 February 2005Higher-order functionsA Haskell function can• take functional arguments• return functional resultsFrom such functions —called higher-order func-tions— comes much of functional programming’spower.Example: flip applies a given function to twoarguments in reverse order:> flip :: (a -> b -> c) -> (b -> a -> c)> flip f x y = f y x> subtract :: Int -> Int -> Int> subtract = flip (-)Thensubtract 5 9H S flip (-) 5 9H S (-) 9 5H S 9 - 5More useful is function composition (.):> (.) :: (b -> c) -> (a -> b) -> (a -> c)> (f . g) x = f (g x)Example:> even n = n `rem` 2 == 0> odd = not . evenThenodd yH S (not . even) yH S not (even y)CS 345 slide 72 Spring 20053 February 2005Aggregate typesAggregate
View Full Document