DOC PREVIEW
UT CS 345 - Making lazy functions strict

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UT CS 345 - Making lazy functions strict

Download Making lazy functions strict
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Making lazy functions strict and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Making lazy functions strict 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?