## 2 Functional Languages under Consideration
### Brief Introduction to Haskell  
The core notion of functional programming is the mathematical function, that is, a program is a function. Complex functional programs are created by starting with simple basic functions and using functional composition. Haskell is the _de facto_ standard of the lazy-evaluation functional programming community. It is a strongly typed language including polymorphism, higher-order programming facilities, and lazy order of evaluation of expressions. _Lazy evaluation_ is an evaluation strategy which delays the evaluation of each expression until the exact moment when it is actually required. As it can be expected, the language provides large libraries of predefined functions, and also predefined data types for the most common cases, including lists. Let us remark that Haskell provides _polymorphism_. Thus, data types can depend on other types. For instance, the programmer can define a generic type to deal with binary trees of any concrete type a:  
dataTreea=Empty|Nodea(Treea)(Treea)  
New functions can be defined by analyzing cases on the structure of the data types. For instance, the following function computes the total number of elements of any tree (of any concrete type) by using _pattern matching_:  
length::Treea->Int lengthEmpty=0 length(Nodext1t2)=1+lengtht1+lengtht2  
The first line of the definition is optional, and it represents the type declaration of the function: Given a tree of any concrete type a, it returns an integer. The rest of the definition represents the definition of the behavior of the function: If it receives an empty tree, then it returns 0; otherwise, it adds 1 to the sum of the lengths of both subtrees. Structures like binary trees are potentially infinite. Usually, a computation over such infinite structure would imply the evaluation of the whole structure, that is, it would mean the non-termination of the program. How can we manage with them? Haskell provides a very powerful tool to treat this type of structures: _laziness_. When an expression is not needed, thanks to laziness it is not evaluated. In particular, the evaluation is driven by demand. For instance, let us consider the following definition of an infinite binary tree:  
infTree::TreeInt infTree=Node1 infTree infTree and the following function to know whether a binary tree is empty or not:  
emptyTree::Treea->Bool emptyTreeEmpty=True emptyTree(Nodeabc)=FalseKnowing whether the binary tree  
(Node l) infTree infTree  
is empty or not is possible because, thanks to laziness, both subexpressions infTree of  
emptyTree ((Node l)infTree infTree)  
remain unevaluated. Other powerful characteristic of Haskell is _higher-order_. It means that functions can be arguments of functions. For instance, the following predefined function map receives as input a function f and a list, and then it applies function f to every element of the list:  
map :: (a -> b) -> [a] -> [b]  map f [] = []  map f (x:xs) = (f x):(map f xs)  
Notice that the type declaration of function map indicates that its first parameter has type a->b, denoting that the first parameter is a function that receives values of type a and returns values of type b. The second parameter is a list of elements of type a, and the result is again a list, but in this case of elements of type b. It is also possible to define functions dealing with lists by using _comprehension lists_. For instance, the previous map definition is equivalent to the following one:  
map :: (a -> b) -> [a] -> [b]  map f xs = [f x | x <- xs]  
Notice that, in higher-order languages like Haskell, it is also possible to deal with partially applied functions. For instance, map can take as its functional argument a partial application of function (+) :  
mapPlusOne :: [Int] -> [Int]  mapPlusOne xs = map (l+) xs  
Thus, it adds one to each element of the list. Let us remark that functions like map can be used to deal with lists of any type. However, sometimes it is also useful to have functions that can deal with many types but not all of them.