CS 345 slide 97 Spring 200510 February 2005Numerical methodsA widely used algorithm for computing N isNewton’s method, which computes a sequence ofever-improving approximations:ai+1=ai+Nai2 ; as i , ai2 NIn Haskell, the sequence of approximations can berepresented by an infinite list.A Haskell function which computes a betterapproximation of N from a given approximation:> next :: Float -> Float -> Float> next n a = (a + n/a) / 2.0Call the initial approximation a0; then the sequence ofapproximations is the list> iterate (next n) a0Now we need a function that traverses the list:> within :: Float -> [Float] -> Float> within eps (a:b:bs)> | abs(a-b) <= eps = b> | otherwise = within eps (b:bs)The parameter eps determines the closeness of theapproximation.Then> sqrt eps n = within eps (iterate (next n) 1.0)The traversal of the list causes elements to be computed,but only as far as needed.CS 345 slide 98 Spring 200510 February 2005Problem: A fixed value of eps will allow a relativelylarge error when N is very small, and may result innon-termination when N is very large.If we expect N to cover a wide range, we prefer analternative to within:> relative :: Float -> [Float] -> Float> relative eps (a:b:bs)> | abs(a/b-1.0) <= eps = b> | otherwise = relative eps (b:bs)and then> rsqrt eps n> = relative eps (iterate (next n) 1.0)Because of the floating-point division (/), relative isslower than within.Note that only the list-traversal function is changed;the list of approximations(iterate (next n) 1.0)is reused without alteration.Moreover, within and relative could be applied,without alteration, to other converging approxima-tion sequences (cube roots, differentials, integrals,etc.).Conclusion: Infinite lists play a role like that ofloops, and functions applied to them serve as term-ination conditions. By enabling loops and theirtermination conditions to be defined separately,infinite lists provide a new way to modularizefunctional programs.CS 345 slide 99 Spring 200510 February 2005MemoizationInfinite lists can be used to speed up functions by“caching” their results for reuse, avoiding the cost ofrecomputing them.Given: a function f :: Int -> Int defined for allarguments x  N (the natural numbers).Define> f Mem :: Int -> Int> f Mem x = f List !! x> f List = [ f n | n <- [0..] ]The list fList is an infinite list of applications:f 0 : f 1 : f 2 : f 3 : ...Thanks to laziness,• each list element f n will be evaluated only when—and if— its value is needed• when an element is evaluated, its value replacesthe function applicationA famous example of redundant computation is the“naïve” definition of the Fibonacci function:> fib :: Int -> Integer> fib 0 = 0> fib 1 = 1> fib n | n >1 = fib (n-1) + fib (n-2)The double recursion makes this algorithmexponentially expensive.CS 345 slide 100 Spring 200510 February 2005To avoid the recomputations, we use a list to“memoize” the function:> ffib :: Int -> Integer> ffib 0 = 0> ffib 1 = 1> ffib n | n >1 = fibList!!(n-1) + fibList!!(n-2)> fibList = [ fib n | n <- [0..] ]But computing each list element is still exponentiallyexpensive. That can be remedied by a small change:> fibList = [ ffib n | n <- [0..] ]Each list element is computed from its twopredecessors.Laziness  The list grows only as long as needed.Because the cost of xs!!k is in (k), we’ve reduced thecost from exponential ((\n->k^n) to quadratic((\n->n^2)).A further improvement, to linear cost ((\n->n)),results from eliminating most of the list indexing:> vFib :: Int -> Integer> vFib n = fibs!!n> fibs = 0 : 1 : [ a+ b | (a,b) <- zip fibs (tail fibs) ]… a nice example of recursive stream processing.CS 345 slide 101 Spring 200510 February 2005How can I/O be Referentially Transparent?How can one define a Haskell program that readsfrom the standard input stream?The Standard-ML approach:inputChar :: CharEach evaluation of inputChar reads the next keystrokefrom the input stream; the value received determinesinputChar’s value.Now consider the expressioninputChar == inputCharand suppose that the next two values in the inputstream are different. This would be a violation of referentialtransparency, which requires that everyoccurrence of an expression in a given scopehave the same value.Another problem arises when we considery == y where y = inputCharHow many characters are read from the inputstream?If two characters are read, then we have the same violation of referentialtransparency as noted above.If only one character is read, then we have another violation of referentialtransparency: y and inputChar are defined to beequal, but replacing y by inputChar changes thevalue of (y == y).CS 345 slide 102 Spring 200510 February 2005Haskell I/ORather than abandon referential transparency,Haskell rejects the idea of obtaining input values byexpression evaluation.Instead, Haskell provides a polymorphic abstractdata type (ADT)IO awhose values represent I/O actions.The operations applicable to this ADT’s values arecarefully designed so that no side-effects of perform-ing I/O actions can be detected within a Haskellprogram.The simplest kind of I/O action merely displays asingle character on the worksheet, or obtains a singlecharacter from the keyboard. I/O actions can becombined in sequence to make more complex I/Oactions.IO itself is, like [], a type constructor.[a] lists containing elements of type aIO a I/O actions delivering values of type aA value of the type IO a is an action which —if it evertakes place—• performs some I/O• delivers a value of type a.The prelude provides• some elementary I/O actions• several ways of combining actions into sequencesof actionsCS 345 slide 103 Spring 200510 February 2005Two elementary IO actions which read from thekeyboard:getChar :: IO ChargetLine :: IO StringThese deliver a character and a string, respectively.Output actions (i.e., I/O actions that write in theworksheet) don’t deliver anything, but the typeconstructor IO requires a type as an argument.For this purpose, Haskell provides the unit type (),whose only element is the unit value (). Thus( ) :: ( )Output actions then have the typeIO ( )Two I/O actions which write in the worksheet arereturned by these functions:putChar :: Char -> IO ()putStr :: String -> IO ()A function which returns an action which writes agiven line in the worksheet:> putStrLn