Functional Programming - Iowa State University
Functional ProgrammingOverview!!!!!!Functional vs. imperative programmingFundamental conceptsEvaluation strategiesPattern matchingHigher order functionsLazy listsReferences!!!Richard Bird, “Introduction to Functional Programming using Haskell”, PrenticeHall, 1998Antony J. T. Davie, “An Introduction to Functional Programming Systems UsingHaskell”, Cambridge University Press, 1992Simon Peyton Jones et al., “Haskell 98 – Report on the ProgrammingLanguage”, http://www.haskell.orgCom S 541
A Bit of History!!!!!!Lambda calculus (Church, 1932-33):! Formal model of computationLisp (McCarthy, 1960):! Symbolic computations with listsAPL (Iverson, 1962):! Algebraic programming with arraysISWIM (Landin, 1966):! Let and where clauses! Equational reasoning; birth or “pure” functional programmingMiranda (Turner, 1985)! Lazy evaluationHaskell (Hudak, Wadler, et al., 1988):! “Grand unification”of functional languagesCom S 541
Programming Without StateImperative style:n : x;a : 1;while n 0 dobegina : a * n;n : n – 1;end;Declarative (functional) style:fac n if 0then 1else n * fac( n – 1)!Programs in pure functional languages have no explicit state.!Programs are constructed entirely by composing expressions (functions).!The main concept in functional programming is the application of afunction f to an argument e, written fe.Com S 541
Side Effects!!!!Consider the expression f g and suppose we wish to calculate the twosub-expressions f and g and then add them.An optimizing compiler might decide to calculate f first and then g or theother way round or might, if possible, try to calculate both expressions inparallel.If the calculation of one of them has the effect of changing the value of theother (via a side effect), then we would be in trouble, because the result off g would depend on the order of the evaluation of the sub-expressions fand g.Such a language is not “referentially transparent”. In general, everyprogramming language that provides imperative programming abstractionsbelongs to this class of languages.Com S 541
Referential Transparency!A function has the property of “referential transparency” if its value dependsonly on the values of its parameters.!Does f(x) f(x) equal 2 * f(x)? In C? In Haskell?!Referential transparency means that “equals can be replaced by equals”.!!Referential transparency means that a well-formed sub-expression can bereplaced by another with the same value without effecting the value of thewhole expression.Pure functional languages, like Haskell, have this property and therefore, inthese languages functions yield the same result no matter how often they arecalled.Com S 541
Pure Functional Programming!What is a program?!A program (computation) is a transformation from input data to output data.!Imperative programming: program algorithm data!Functional programming: program function · function!Key features of pure functional languages:!!!!!All programs and procedures are functions.There are no variables or assignments – only input parameters.There are no loops – only recursive functions.The value of a function depends only on the values of its parameters.Functions are first-class values.Com S 541
HaskellHaskell is a general purpose, purely functional programming languageincorporating many recent innovations in programming language design.Haskell provides higher-order functions, non-strict semantics, staticpolymorphic typing, user-defined algebraic datatypes, pattern-matching, listcomprehensions, a module system, a monadic I/O system, and a rich set ofprimitive datatypes, including lists, arrays, arbitrary and fixed precisionintegers, and floating-point numbers. Haskell is both the culmination andsolidification of many years of research on lazy functional languages.- The Haskell 98 report.Com S 541
Haskell Program Structure!!!!At the topmost level a Haskell program is a set of modules (scripts) thatprovide a way to control namespaces and to re-use software in largeprograms.The top level of a module consists of a collection of declarations (e.g.values, datatypes, type classes).At the next lower level are expressions, which are the heart of Haskellprograms. An expression denotes a value and has a static type.The bottom level is the lexical structure of Haskell. The lexical structurecaptures the concrete representation of Haskell programs in text files.Com S 541
Sessions and Scripts!The computer is a calculator:?6*742!A more intellectually and challenging aspect of functional programmingconsists of building definitions. A list (sequence) of definitions is called“script”.squaresquare x:: smaller::smaller (x,y) x y otherwiseInt - Intx*x(Int, Int) - Int x yCom S 541
Application of Definitions? square 23456550183936? square( smaller( 5, 3 4 ) )25? smaller( square( 25 ), square( 35 ) )625!The purpose of a definition is to introduce a binding associating a givenname with a given definition. A set of bindings is called an environment orcontext. Expressions are always evaluated in some context. This contextmust contain definitions for all occurrences of free (used) names used inthe actual expression to be evaluated.Com S 541
A First Modulemodule FirstModule(square, smaller, greater) wheresquare :: Int - Intsquare x x * xsmaller :: (Int,Int) - Intsmaller (x,y) x y x otherwise ygreater :: (Int,Int) - Intgreater (x,y) if x y then x else yCom S 541
Haskell Scripts!!!!!Haskell scripts are collections of definitions.Definitions are expressed as equations between expressions and describe amathematical function.Every definition has to be accompanied by a type signature.During a session, scripts can be loaded in order to introduce newdefinitions, which extent the current working environment.Definitions can contain references to other functions defined in preludes,libraries, or user-defined scripts.Com S 541
Evaluation!!The computer evaluates an expression by reducing it to the simplestequivalent form. The term evaluation, simplification, and reduction areused interchangeably to describe this process.Consider the expression square (12 – 1), which has the following reductiontree:square(12 – 1)(12 – 1) * (12 – 1)square 1111 * (12 – 1)11 * 11121Com S 541(12 – 1) * 11
Strict Evaluation!Strict evaluation strategy reduces the leftmost-innermost expression(redex) first. Using this strategy, functions arguments are evaluated priorthe function evaluation. This evaluation strategy is therefore also calledcall-by-value, application order reduction, or eager evaluation. square( 12 – 1 ){definition of –}square 11{definition of square}11 * 11{definition of *}121Com S 541
Non-strict Evaluation!Non-strict evaluation strategy reduces the leftmost-outermost expression(redex) first. Using this strategy, functions arguments are only evaluated ifneeded, i.e., they are not evaluated prior function evaluation. Thisevaluation strategy is therefore also called call-by-name, normal orderreduction, or lazy evaluation. square( 12 – 1 ){definition of square}(12 – 1) * (12 – 1){definition of -}(12 – 1) * 11{definition of -}11 * 11{definition of *}121Com S 541
Normal Form!!!!An expression is said to be canonical, or in normal form, if it cannot befurther reduced.In the previous example (square (12 – 1)) we have seen that independentof the chosen evaluation strategy the final result was always the same –121.It is a characteristic feature of functional programming that if two differentreduction sequences both terminate, then they lead to the same result. Inother words, the meaning of an expression is its value and the task of thecomputer is simply to obtain it.However, not every expression has a normal form: apply x x xapply apply " apply apply " apply apply " " apply applyCom S 541
The Church-Rosser Property!If an expression can be evaluated at all, it can be evaluated by consistentlyusing normal-order evaluation. If an expression can be evaluated in severaldifferent orders (mixing normal-order and applicative-order evaluation),then all these evaluation orders yield the same result.square (12-1):!!!Applicative-order evaluation:square (12-1) " square 11 " 11 * 11 " 121Normal-order evaluation:square (12-1) " (12-1) * (12-1) " 11 * (12-1) " 11 * 11 " 121Note, by means of lazy evaluation, we can both avoid having to calculatevalues before we need them, and also avoid having to calculate them morethan once.Com S 541
Infinity!For some expressions the process of reduction never stops and never produces anyresult.three :: Int - Intthree x 3infinityinfinity:: Int infinity 1strict evaluation:three infinity {definition of infinity}three (infinity 1) {definition of infinity}three ((infinity 1) 1) non-strict evaluation:three infinity {definition of three}3Com S 541
Bottom Valueinfinity :: Intinfinity infinity 1!!!!Such an expression do not denote well-defined values in the normal mathematicalsense.Another example is the operator /, which denotes numerical division, returning afloating-point number. However, the expression 1/0 does not denote a well-definedfloating-point number.Such expressions may cause the evaluator to respond with an error message (e.g.‘divide by zero’), or go into an infinitely long sequence of calculations withoutproducing any result.In order to say that, without exception, every syntactically well-formed expressiondenotes a value, it is convenient to introduce a special symbol , pronounced“bottom”, to stand for the undefined value of a particular type.Com S 541
Properties of Bottom!!!The computer is not expected to produce the undefined value. Instead, theevaluator will produce an error message or run forever and may remainperpetually silent. The former situation is detectable while the latter is not(the evaluation simply takes more time depending on complexity class ofthe algorithm or the of function called – e.g. Ackermann function, whileTuring computable, grows faster than any primitive recursive function).Therefore, is a special kind of value. In fact, every data type (e.g. Int,Float, tuple, function, etc.) has an additional element, namely .If / / , then f is said to be a strict function; otherwise it is non-strict.Thus, square is a strict function, while three is non-strict. Lazy evaluationallows non-strict functions to be defined, some other strategies do not.Com S 541
Pattern Matching!Languages like Haskell support a number of styles for specifying whichexpressions should be evaluated for different cases of arguments:fac :: Int - IntPatterns:fac 0 1fac n n * fac (n-1)orfac 0 1fac (n 1) (n 1) * fac nGuards:fac n n 0 1 n 1 n * fac (n-1)Note that patterns are tested is their given order. If there is no matchingpattern, the evaluation of the functions terminates with a run-time error.Com S 541
Lists!Lists are pairs of elements and lists of elements:!!!!![]x:xs[1,2,3][1.n]stands for the empty liststands for the list with x as the head and xs as the rest of the listis syntactic sugar for 1:2:3:[]stands for [1,2,3, ,n]Lists can be constructed using patterns:head (x: ) xlen []len (x:xs) 0 1 len xsprod []prod (x:xs) 1 x * prod xsfac n prod [1.n]Com S 541
Polymorphic Types!!!In languages like C and Pascal, the use of user-defined functions is veryrestricted. The types of the actual parameters have to match exactly thetypes of the formal parameter. Exceptions are only possible, if we switch offtype checking, i.e. if we use type-casts.Haskell is a strongly typed language, i.e. we can assign all values a (unique)type. However, it is possible to define functions, where the parameters of afunction can be instantiated to different types in different circumstances.Such functions are called polymorph.In order to use a polymorphic abstractions, Haskell provides type variables,and hence a type that is built using type variables is called a polymorphictype. We use a, b, c to denoted type variables:(.) :: (b - c) - (a - b) - (a - c)map :: (a - b) - [a] - [b]Com S 541
What Is a Function?!!!!Functions are the most important kind of value in functional programming.It is important to note that we cannot display as function values. We canapply functions to arguments and display the results, when the result canbe displayed (i.e. the result is not again a function).A function is a rule of correspondence that associates each element of agiven type A with a unique element of a second type B. The type A iscalled the source type, and B the target type of the function.We express this information by writing f::A " B, which asserts that thetype of fis A " B, i.e. fis a function from A to B, like:!!!three :: Int - Intsquare :: Int - Intsmaller :: (Int,Int) - IntCom S 541
Extensional and Intentional Views!Extensional view:A (total) function f: A " B is a subset of A B (i.e. a relation) such that:1. for each a A, there exists some (a,b) f (i.e. f(a) is defined), and2. if (a,b1) f and (a,b2) f, then b1 b2 (i.e. f(a) is unique)!Intentional view:A function f: A " B is an abstraction λ x.e, where x is a variable name,and e is an expression, such that when a value a A is substituted forx in e, then the expression (i.e. f(a)) evaluates to some (unique) valueb B.Com S 541
Extensionality!Two functions are equal, if they yield the same result for equal arguments, i.e.f g, if and only if fx g x for all x. This principle is called extensionality, andstates the correspondence between arguments and result.double :: Int - Intdouble x x x!!double’ :: Int - Intdouble’ x 2 * xThe two definitions describe different functions for obtaining thecorrespondence, one involving addition and the other involving multiplication,but double and double’define the same function value, and therefore it holdsdouble double’. But one function may be more or less efficient that the other,but efficiency is an intentional property of a function.Extensionality means that we can prove f g by proving fx g x for all x.Depending on the definitions of fand g we may be able to prove f g directly.Com S 541
Tail Recursion – Modeling State!!Recursive functions can be less efficient than loops because of the high costs offunction calls on most hardware. But a tail-recursive function calls itself only as itslast operation, so the recursive call can be optimized away by a modern compiler.A recursive function can be converted to a tail-recursive one by representing partialcomputations (i.e. state) as explicit function parameters:sfac :: Int - Int - Intsfac s n if n 0then selse sfac (s*n) (n-1)!sfac 1 4- - - - - - - - - sfac (1*4) (4-1)sfac 4 3sfac (4*3) (3-1)sfac 12 2sfac (12*2) (2-1)sfac 24 1sfac (24*1) (1-1)sfac 24 024Tail-recursive functions are typically more efficient since no information about theprevious call needs to be kept.Com S 541
Multiple Recursion – Remembering State!Naive recursion may result in unnecessary recalculations:fibfibfibfib!:: Int - Int1 12 1(n 2) fib n fib (n 1)Efficiency can be regained by explicity passing calculated values:fib’ 1fib’ n 1 awhere (a, ) fibPair nfibPair :: Int - (Int,Int)fibPair 1 (1,0)fibPair (n 2) (a b,a)where (a,b) fibPair (n 1)Com S 541
Higher-order Functions!Higher-order functions treat other functions as first-class values that canbe composed to produce new functions.map :: (a - b) - [a] - [b]map f [] []map f (x:xs) f x : map f xs? map fac [1.5][1,2,6,24,120]!-- fac implements the factorial functionAnonymous functions can be written as “lambda abstractions”:? map (\x - x * x) [1.10][1,4,9,16,25,36,49,64,81,100]Note: m ap fac and m ap (\x- x* x)are new functions that can be applied tolists.Com S 541
Curried Functions!A Curried function takes its arguments one at a time, allowing it to be treated as ahigher-order function.plus x y x y? plus 1 23-- curried additioninc plus 1? Inc 23-- bind first argument of plus to 1fac sfac 1-- factorial binds first argument ofwhere sfac s n-- a curried factorial function n 0 s n 1 sfac (s*n) (n-1)Curried functions are named after the logician H.B. Curry, who popularized them.Com S 541
Currying!The following higher-order function takes a binary function as an argument andturn it into a curried function:curry :: ((a, b) - c) - (a - b - c)curry f a b f (a,b)-- take a binary function and curry itplus :: (Int,Int) - Intplus (x,y) x y-- not a curried functionplusc :: Int - Int - Intplusc curry plus-- make plusc the curried version of plusinc :: Int - Intinc plusc 1-- bind first argument of plusIt is left as an exercise to define a function uncurry that goes the other way andconverts a curried function into a non-curried one.Com S 541
Functional Composition!The composition of two functions fand g is denoted by f.g and is definedby the equation(.) :: (b - c) - (a - b) - (a - c)(f . g) x f (g x)In words, f.g applied to x is defined to be the outcome of the firstapplying g to x, and then applying fto the result.!!Not every pair of functions can be composed since the types have to bematched up: we require that g has type a " b for some types a and b, andthat fhas type b " c for some type c.Functional composition is an associate operation: (f . g) . h f . (g .h)Com S 541
Lazy Evaluation!“Lazy”, or “normal-order” evaluation only evaluates expressions when they areactually needed. Clever implementation techniques allow replicated expressions tobe shared, and thus avoid needless recalculations. So:square x x * xsquare (12-1) " (12-1) * (12-1) " 11 * 11 " 121!Lazy evaluation allows some functions to be evaluated even if they are passedincorrect or non-terminating arguments:ifTrue :: Bool - a - a - aifTrue True x y xifTrue False x y y?ifTrue True 1 (5/0)1Com S 541
The Power of Lazy Evaluation!Recall that a complete functional program is just a function from its input to its output. If fand gare such programs, then (f.g)is a program which, when applied to its input, computesf (g input)The program g computes its output, which is used as the input to program f.!!!This scheme might be implemented conventionally by storing the output from g in a temporary file(e.g. gzip, pipes-and-filters architecture). The problem with this is that the temporary file mightoccupy so much memory that it is impractical to glue the programs together in this way.Functional languages provide a solution to this problem. The two programs fand g run in strictsynchronization. G is only started once ftries to read some input, and only runs for long enoughto deliver the output fis trying to read. Then g is suspended and frun until it tries to read anotherinput.This method is called “lazy evaluation” and provides a practical means to modularize a program.Moreover, in functional languages lazy evaluation is uniformly used for every function call.Com S 541
Lazy Lists!Lazy lists are infinite data structures whose values are generated by need:from :: Int - [Int]from n n : from (n 1)taketaketaketake:: a - [a] - 0[](n 1) (x:xs)?take 5 (from 10)[10,11,12,13,14]Note: The lazy list (from n) has a special syntax: [n.]? take 5 [20.] " [20,21,22,23,24]fibs :: [Int]fibs 1 : 1 : fibgen 1 1where fibgen a b (a b) : fibgen b (a b)? take 10 fibs[1,1,2,3,5,8,13,21,34,55]Com S 541[a] [] [] x : take n xs
List Comprehensions!Haskell provides an alternative notation, called a list comprehension, for describingcomputations involving map and filter:? [x * x x - [1.5], odd x][1,9,25]This reads: the list of squares of odd numbers in the range 1 to 5.!!Formally, a list comprehension takes the form [e Q ]where e is an expression andQ is a qualifier. A qualifier is a possible empty sequence of generators and guards.A generator takes the form x -xs, where x is a variable or tuple of variables, andxs is a list-valued expression. A guard is a boolean-valued expression.pairs [(i,j) I - [1.2], j - [1.3]]? [I j (i,j)
Functional Programming Overview! Functional vs. imperative programming! Fundamental concepts! Evaluation strategies! Pattern matching! Higher order functions! Lazy lists References! Richard Bird, “Introduction to Functional Programming using Haskell”, Prentice Hall, 1998! Antony J. T. Davie, “An In
Iowa Chapter, American Academy of Pediatrics Iowa Dental Association Iowa Department of Public Health Iowa Health Care Association Iowa Hospital Association Iowa Medical Society Iowa Nurses Association Iowa Pharmacy Association Iowa Veterinary Medical Association Iowa‘s Statewide Epidemiology Education and Consultation Program State Hygienic .
Numeric Functional Programming Functional Data Structures Outline 1 Stuff We Covered Last Time Data Types Multi-precision Verification Array Operations Automatic Differentiation Functional Metaprogramming with Templates 2 Numeric Functional Programming Advanced Functional Programming with Templates Functional Data Structures Sparse Data Structures
Functional programming paradigm History Features and concepts Examples: Lisp ML 3 UMBC Functional Programming The Functional Programming Paradigm is one of the major programming paradigms. FP is a type of declarative programming paradigm Also known as applicative programming and value-oriented
Agricultural Biotechnology Stewardship Technical Committee (ABSTC), Iowa Corn Growers Association (ICGA), the Iowa Chapter of the American Society of Farm Managers and Rural Appraisers (ASFMRA), Iowa Farm Bureau Federation (IFBF), Iowa Independent Crop Consultants Association, Iowa Institute for Cooperatives (IIC), Iowa Soybean Association (ISA),
functional programming style. Adding functional programming facilities to Prolog results in a more powerful language, as they allow higher-order functional expres-sions to be evaluated conveniently within the logic programming environment. And, as will be shown in this thesis, the efficiency of functional programming in logic is
Development, Iowa State University, Ames, Iowa 50011- 1070. For questions or comments about the contents of this paper, please contact Wendong Zhang , wdzhang@iastate.edu . Iowa State University does not discriminate on the basis of race, color, age, ethnicity, religion, national origin, pregnancy ,
Iowa Department of Public Health Text4baby Iowa State Contact 515-778-2212 Kelly.Schulte@idph.iowa.gov Let’s work together to promote this terrific resource to pregnant women and new mothers in Iowa! Approximately 1.8% of estimated pregnant women and new moms in Iowa have enrolled in Text4baby since its launch.
The Adventure Tourism Development Index (ATDI) is a joint initiative of The George Washington University and The Adventure Travel Trade Association (ATTA). The ATDI offers a ranking of countries around the world based on principles of sustainable adventure tourism
