Haskell (programming language)

Haskell is a purely functional programming language, named after the American mathematician Haskell Brooks Curry, whose work in mathematical logic provide a basis for functional programming languages ​​. Haskell is based on the lambda calculus, which is why the Greek letter lambda is used as a logo. The main implementations of the Glasgow Haskell Compiler ( GHC) and Hugs, a Haskell interpreter.

• 3.1 Faculty
• 3.2 Fibonacci
• 3.3 difference equation
• 3.4 Quicksort
• 3.5 Algebra

Development

In the late 1980s, there were already some functional programming languages. In order to provide a unified science research and development base, a standardized and modern language should unify functional programming. First, they wanted to use to Miranda as a starting point; but their developers were not interested. How 1990 Haskell 1.0 was released.

The current version of the programming language is a revised version of the Haskell 98 standard by 1999. Haskell is the functional language on the currently most research is done. Consequently, the voice derivatives are numerous; these include parallel Haskell, Distributed Haskell (formerly Goffin ), Eager Haskell, Eden with a new approach for parallel programming and demand analysis, DNA - Haskell and even object-oriented versions ( Haskell , O'Haskell, Mondrian ). Furthermore, the design of new programming languages ​​Haskell served as a template. Example, it was assumed the lambda notation and list processing syntax in the case of Python.

Properties

Program flow

• Haskell is a purely functional programming language. Functions return only values ​​, but do not change the state of a program (that is, functions have no side effects). Therefore, the result of a function depends only on the input parameters, and not on when or how often the function is called. (see functional programming )
• There is no imperative language constructs. By monads, it is possible to handle input and output operations and state-dependent calculations like random purely functional.
• There are no operations that change the value of a variable. So there is no distinction between variables and constants, and you do not need const attributes or literal macros as in C or in C.
• Between identity and equivalence of objects are not distinguished.
• Since side effects are missing, program proofs are considerably simpler.
• Haskell is non-strict. There are only evaluated expressions that are used for the calculation of the result.

First x y = x          square x = x * x The first function returns when you enter two parameters returns the first as a result. When entering first x (3 7) the evaluation of the sum ( 3 7 ) for the determination result is not necessary, so it should be disregarded. The function square calculated when a parameter whose square. Entering square (3 5 ), which in the course of the evaluation process to (3 5 ) * ( 3 5 ), is a double calculation of the sum (3 5 ) would be inefficient, so it should be avoided. The evaluation strategy, which avoids the two problems just described is called needs analysis (English lazy evaluation ) and comes in Haskell usually used. The needs analysis is possible mainly because of the strict adherence to the functional concept. Conversely, does the requirement analysis, the functional programming pleasant, because it allows better functionality, the pure perform calculations to separate from Ein-/Ausgabefunktionen. The requirement analysis allows working with undefined values ​​and potentially infinitely large amounts of data. So you can look elegant with power series, the time series (such as audio streams ), continued fraction decompositions, decision trees and the like round. But even at finite, but large, or finite and not yet fully known data allows this type of design elegant programs. May be described as a transformation of an XML document as a result of transformation of the entire XML tree. The total transformation is carried out from the beginning but the end of the XML document, even if the end is not yet available. Note, however, that according to Haskell language definition only is non-strict; the need for evaluation is only one possible implementation of non - strictness ( which is, however, used by all current Haskell translators ). Other implementations are possible (eg optimistic evaluation, Ennals & Peyton Jones, ICFP'03 ). Type System

• Haskell is strongly typed. So there is a strict distinction between truth values ​​, characters, integers, floating point numbers and functions to and from various types for example.

• Haskell allows type variables. This functions can be very general terms. If of a general function for certain types of uses, are automatically adjusted the types ( type inference ).

Map :: (a -> b ) -> [ a] -> [ b] If map about with the special function toUpper of type Char - called > Char, gives the type matching          map toUpper :: [ Char ] -> [ Char ] Haskell is statically typed, the basic idea here, although there are also extensions for dynamic types. This means that the identities of participating types at the time of program translation for most calculations. This covers many "obvious" errors before running the program.

• Haskell supports higher-order functions ( functionals). These are functions that have functions as input parameters or functions as a result. An example is the map function that applies a function f to each element of a data type (in this case the list).

Map :: (a -> b ) -> [ a] -> [ b]          map f [ ] = []          map f (x: xs ) = f x: map f xs            map square [1,2,3 ] = [ square 1, square 2 square 3] = [ 1,4,9 ] Functions allow currying. While as arguments are in other languages ​​tuple of functions, that is a function of the types of the form (a, b ) -> c used in Haskell curry form a - > b -> c usual. In order for the partial evaluation of functions is easily possible. The term map toUpper example, a partial evaluation of map, since it describes a function, namely the function that converts all lowercase letters to uppercase a list.

• Haskell permits user-defined data types. This algebraic data types are defined with the help of Datenkonstruktoren.

Data Tree = Leaf Int | Branch Tree Tree Int The example shows the data structure of a binary tree, labeled with integers. Such a tree tree is either a leaf (Leaf Int) or branch (Branch Int t1 t2 ), where t1 and t2 represent the sub-trees, which in turn have the structure tree. For the definition of this data structure of both the digit constructor Leaf and the three-digit Branch constructor was used. Data types with several exclusively parameterless constructors can be used as bullets.          data day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday               Deriving ( Show, Eq, Ord, Ix, Enum) Haskell supports type classes. With type classes can be summarized types that support a certain amount of operations. In function signatures may as gradation between solid types such as Char and free type variables also type variables are used, restricted to certain classes.

• In Haskell input and output functions have a special type constructor called IO.

PutStrLn :: String - > IO ( )          getLine :: IO String putStrLn outputs a text and a newline to the standard output. Since there is no information bearing result, the unit type ( ) is used as the return type. getLine reads a line of text from the standard input. The IO type constructor ensures that you have to disclose the users of the function that the results obtained by Ein-/Ausgabe. This strict enforcement encourages Haskell programmers to the clear separation of input and output, and other parts of a program. The largest part of a Haskell program is to rule out functions without input and output. One can of course also embed IO types into other types and so, for example, define a special IO type, which only permits entries. syntax

Haskell is case- sensitive. Identifiers beginning with a capital letter, are for type and Wertkonstruktoren. Identifiers beginning with a lowercase letter, stand for type variables, functions and parameters.

Dealing with spaces and newlines product is based on the intuitive understanding of mathematical notation, must at line breaks happen only an indentation any depth, so that the connection is not lost. Thus, the expression

Fun a b = a * b entirely equivalent to

Fun a b = a *         b Haskell supports single-line and multi-line comments, the former from the sign -. Till the end of the line and the latter in the inclusion of { - and -}

F x = x ** 2      - F y = y * 5, this line is commented out      { - Everything         does it say here, is also not observed.         F z = z * 2      -} Haskell provides a set of syntactic features. This should not obscure the fact that everything is explained purely functional.

• The do notation makes calculations with monads the appearance of imperative programs. instead of

" input.txt " readFile >> = writeFile " output.txt " or          readFile " input.txt " >> = ( \ content - " output.txt " > write file contents ) It is also          do contents <- " input.txt " readfile             " output.txt " write file contents. Write Both symbolic identifiers (consisting of about , -, *, / ,>, < ) as well as alphanumeric identifier (letters, numbers and apostrophe) can be used for functions and be used as infix operators as well as in prefix notation. It applies, for example,

A b = ( ) A B          a ` div ` b = a div b Haskell allows a notation for list processing (list comprehensions ). Thus, sequences of numbers by two periods ( ..) are indicated:

[0 .5 ] = [ 0,1,2,3,4,5 ]          ['a ' .. ' e' ] = [' a', ' b', ' c ', 'd ', ' e' ] = " abcde "          [0,2 .. 10] = [ 0,2,4,6,8,10 ] If no final value specified, then an infinite list is generated          [ 1. ] = [ 1,2,3, etc.]          [ 10,20 ..] = [ 10,20,30, etc.] Furthermore, a notation allowed, which is modeled on the mathematical notation for quantity definitions. In this example the sequence of the even numbers is extracted from the sequence of positive integers.          [X | x <- [ 1 ], even x. ] as a euphemism for          filter even [ 1. ] or for          do             x <- [ 1. ]             guard even $ x             return x In general, behind the vertical bar any non- empty sequence of generators (pat <- xs ), predicates ( expressions of type Bool) and let bindings can be specified. In particular, it is possible even not to use generators. The term          [x | odd x] increases depending on the value of x, which is provided as already defined, the value of [] and [ x] on. programming

• Haskell allows pattern matching (English pattern matching ). This is the name the use of Konstruktortermen as formal parameters. The parameters are the patterns Terme (English pattern ) of the function arguments.

Fak :: Integer - > Integer          fak 0 = 1          fak fak n = n * ( n-1) The de facto function calculates the factorial of a number. 0 and n are the pattern (Pattern), upon which the determination result. Is a number greater than 0, engages only the pattern n, such that second consists alternative is used. This calculates the result by n * fak (n- 1), where they, as long as ( n -1) is > 0, recursively calls itself until it arrives at 0. There then accesses the pattern 0, so that the former alternative is used, which terminates the recursion clean, returns 1, and the return chain initiates. modules

At Haskell also has a module system. The Haskell 98 standard defines a basic set of modules that must provide a standards compliant Haskell system. For example, a module that provides input and output functions, or a module that functions on lists implemented.

To use modules, you have to import it. This is done using the import command.

Import List     Maybe import Functions and types can have the same name in different modules. This identifier can be distinguished,

• By just one of the identifiers will be imported,

Import Data.List ( delete)          x = delete ' a' " abc" or by the identifier qualified to be clearly made so by connecting to the module name.

Import qualified Data.List          x = Data.List.delete 'a' "abc" or

Import qualified Data.List as List          x = List.delete 'a' "abc" Also possible but not recommended is hiding identifiers when importing with hiding.

Examples

Faculty

An elegant definition of the factorial function using Haskell's notation for lists:

Fac :: Integer - > Integer      fac n = product [ 1. n] Often, but also working recursive:

Facr :: Integer - > Integer      facr 1 = 1      facr n = n * facr ( n-1) Tail recursion is often more efficient, but also to write more complex:

Facrt :: Integer - > Integer      facrt n = n 1 _facrt          where _facrt 1 f = f                _facrt n f = _facrt ( n-1) (F * N ) Fibonacci

A simple implementation of the Fibonacci function:

Fib :: Integer - > Integer      fib 0 = 0      fib 1 = 1      fib n = fib ( n - 2 ) fib ( n - 1 ) A fast implementation of the result:

Fibs :: [Integer ]      fibs = 0: 1: ( zipWith ( ) fibs ( tail fibs ) ) tail removes the first element from a list, zipWith combines two lists element by element using another function (in this case ( )). The definition corresponds to a fixed point equation. The fact that the definition is correct, you checked the fastest, by imagining that fibs is already present calculated finished. Next, one must still consider that the definition can also be evaluated. The first two terms of fibs are immediately clear: 0 and 1 for the calculation of each additional member must, however, be resorted to only on already calculated elements of fibs. The needs analysis means that the sequence is actually fibs calculated element by element.

One could also say that fibs is a fixed point of the function \ xs -> 0: ( zipWith ( ) xs ( tail xs ) ): 1. This in turn can be written directly in Haskell as

Fix ( \ xs -> 0: 1: ( zipWith ( ) xs ( tail xs ))) difference equation

It is very elegant with respect to formulate in this way differential equations or difference equations power series with respect to sequences of numbers and solve simultaneously.

Suppose we would like the equation y '( x) = y is solved with respect to f (x, y (x) ) in the form of a time series, that is, a list of numbers. With this discretization, the differential equation for the difference equation. Instead of an integral, we calculate partial sums. Has the following function as a parameter, the constant of integration and a series of numbers.

Integrate :: Num a = > a -> [ a] -> [ a]      integrate scanl = ( ) scanl accumulates the values ​​of a sequence with the help of another function, where ( ), and returns the list of Akkumulatorzustände back.

So you can already implement the explicit Euler method for the step size 1. x0 and y0 here are the initial values. The apostrophe has no independent meaning, it is part of the name y '.

EulerExplicit :: Num a = > (a -> a -> a) -> a -> a -> [ a]      eulerExplicit f x0 y0 =         let x = iterate ( 1 ) x0             y = y0 integrate y '             y '= f x y zipWith         in y This function definition is therefore mainly due to the finding that y ' is with initial value y0, (or vice versa, y' the integral of y is the derivative of y ) and the actual differential equation y '= zipWith fx y. Because it uses this to register the algorithm rather in the form of the task than in the form of a solution path, we speak here of declarative programming.

Quicksort

The quicksort algorithm, formulated in Haskell:

Qsort :: Ord a = > [ a] -> [ a]      qsort [ ] = []      qsort (x: xs ) = qsort kleinergl [ x] qsort bigger                     where                        kleinergl = [ y | y <- xs, y < = x]                        bigger = [ y | y <- xs, y > x] The first line defines the signature of quicksort. The second line indicates that the function on an empty list applied again to result in an empty list. The third line sorted recursively non-empty lists: the first element of x is used as a central element of the result list. Previously, all non- major are sorted, classified behind all the major elements. List descriptors are used to select from the remaining list all xs those which are greater than x, and all those that are not.

As you would expect of Quicksort, also owns this implementation a mean asymptotic running time of O ( n · log n ) and a worst-case running time of O ( n ²). In contrast to the common implementation in an imperative language this works but qsort not in-place.

Algebra

This example highlights the use of type classes.

Data PhiNum a = { PhiNum numPart :: a, a} Deriving phiPart :: (Eq, Show)   instance Num a = > Num ( PhiNum a) where      from integer n = PhiNum (from integer n ) 0      PhiNum a b c d = PhiNum PhiNum (a c) (b d)      PhiNum from PhiNum cd = PhiNum (a * c b * d) (a * d b * c b * d) *      negate ( PhiNum A B ) = PhiNum ( A ) ( B )      abs = undefined      signum = undefined   fib n = phiPart $ PhiNum 0 1 ^ n fib provides a fast computation of elements of the Fibonacci sequence is dar. Ausgenutzt the predefined ^ that works on Num - implemented types.

Implementations

There are now a number of Haskell implementations, most of which are not fully implementing the language standard.

• The Glasgow Haskell Compiler ( GHC) Haskell support 98 as well as many language extensions. It translates Haskell programs into machine code; for not directly supported platforms it generates C code which is then compiled with a C compiler.
• Hugs is a bytecode compiler, the Haskell 98 implemented almost entirely as well as some extensions. Hugs itself is written in C.
• Nhc (also nhc98 ) is another bytecode compiler, the Haskell 98 supports with certain limitations. The York Haskell Compiler or Yhc is to improve a development of nhc with the goal of portability and performance of the compiled programs.
• The Utrecht Haskell Compiler ( UHC ) is an experimental implementation that is developed at the University of Utrecht. The compiler is based on attribute grammars and translates Haskell into C code. It implements Haskell 98 almost completely as well as some extensions.
• Helium is also being developed at the University of Utrecht. The project focuses on producing easy- to-understand error messages to help beginners learning Haskell. Therefore, a restricted Haskell dialect is implemented, which has, among others, no type classes.

The implementations mentioned here are all open source software. Except for Hugs they are implemented all in Haskell itself.

Influence

Haskell served and serves because of its strong academic origin many programming and scripting languages ​​as a model for new voice functionality. Thus, inter alia, Perl, Python, JavaScript, Java, Scala, and PHP accepted ideas of functional programming language Haskell. These include higher-order functions, such as map, filters, etc., parts of the type generic programming has been implemented, and others.