Haskell (programming language)

Haskell
Basic data
Paradigms :	functional , non-strict , modular , declarative
Publishing year:	1990
Designer:	Lennart Augustsson, Warren Burton, Kevin Hammond, Paul Hudak , John Hughes, Thomas Johnsson, Simon Peyton Jones , John Launchbury, Erik Meijer , Alastair Reid, Philip Wadler
Developer:	Simon Peyton Jones , Paul Hudak , Philip Wadler , et al.
Typing :	static , strong , type inference
Important implementations :	GHC , Hugs , NHC , JHC , Yhc
Dialects:	Helium , Gofer
Influenced by:	APL , LISP , Miranda , ML , C ++
Affected:	Agda , Cayenne , Clean , Curry , Idris , Python , Scala , C # , F # , Swift , JavaScript
Operating system :	Platform independence
	haskell.org

Haskell is a purely functional programming language , named after the US mathematician Haskell Brooks Curry , whose work on mathematical logic forms the basis of functional programming languages. Haskell is based on the lambda calculus , which is why the Greek letter lambda is also used as the logo. The main implementation is the Glasgow Haskell Compiler (GHC) .

development

By the late 1980s there were already some functional programming languages. In order to provide science with a uniform research and development basis, a standardized and modern language should unify the functional programming. At first they wanted to use Miranda as a starting point; but their developers weren't interested. So in 1990 Haskell 1.0 was released.

The Haskell language derivatives are numerous; these include Parallel Haskell , Distributed Haskell (formerly Goffin), Eager Haskell , Eden with a new approach to parallel programming and needs analysis , DNA Haskell and even object-oriented variants ( Haskell ++ , O'Haskell , Mondrian ). Haskell also served as a template for the design of new programming languages. In the case of Python , for example, the Lambda notation and list processing syntax were adopted.

properties

Program flow

Haskell is a purely functional programming language . Functions only return values, they do not change the state of a program (i.e. functions have no side effects ). The result of a function therefore only depends on the input parameters and not on when or how often the function is called.
There are no imperative language constructs . By monads , it is possible to treat input and output operations and state-dependent random calculations as purely functional.
There are no operations that change a variable value. So there is no distinction between variables and constants, and you do not need constattributes or literal macros as in C ++ or C .
No distinction is made between the identity and equivalence of objects.
In the absence of side effects, program proofs are considerably easier.
Haskell is not strict. Only expressions that are needed to calculate the result are evaluated .

        first x y = x
        quadrat x = x * x

firstWhen two parameters are entered, the function returns the first as the result. When entering first x (3+7), the evaluation of the sum is (3+7)not necessary to determine the result, so it should not be taken into account.

quadratWhen a parameter is entered, the function calculates its square. When entering quadrat(3+5)what will become in the course of the evaluation process (3+5)*(3+5), calculating the sum twice would be (3+5)inefficient and should therefore be avoided.

The evaluation strategy that bypasses the two problems just described will need evaluation ( English lazy evaluation called) and comes in Haskell usually used.

The needs evaluation is mainly possible because of the strict adherence to the functional concept. Conversely, the needs evaluation makes functional programming more convenient, because it makes it easier to separate functions that perform pure calculations from input / output functions.

The needs evaluation allows you to work with undefined values and potentially infinitely large amounts of data. So you can elegantly handle power series, time series (e.g. audio signal streams), continued fraction decomposition, decision trees and the like. But even with finite, but large, or finite and not yet fully known data, this type of execution allows elegant programs. For example, a transformation of an XML document can be described as a sequence of transformations of the entire XML tree. The overall transformation is carried out from the beginning to the end of the XML document, even if the end is not yet available.

Note, however, that by language definition, Haskell is merely non-strict ; the needs assessment is only one possible implementation of the non-strictness (which, however, is used by all common Haskell translators). Other implementations are possible (e.g. optimistic evaluation , Ennals & Peyton Jones, ICFP'03).

Type system

Haskell is strongly typed . For example, a strict distinction is made between truth values , characters , whole numbers , floating point numbers and functions from and to different types.

Haskell allows type variables. This allows functions to be formulated very generally. If a general function is used for certain types, the types are automatically compared ( type inference ).

The function mapapplies any function to the elements of a list. Your type is indicated like this:

        map :: (a -> b) -> [a] -> [b]

If, mapfor example, the toUppertype is Char -> Charcalled with the special function, the type comparison results

        map toUpper :: [Char] -> [Char]

The basic idea of Haskell is statically typed, although there are also extensions for dynamic types. This means that the types for most calculations are already determined at the time the program is compiled. This reveals many "obvious" errors even before the program is executed.
Haskell supports higher order functions ( functionals ). These are functions that have functions as input parameters or functions as a result. One example is the mapfunction, which applies a function fto every element of a data type (here list).

        map :: (a -> b) -> [a] -> [b]
        map f [] = []
        map f (x:xs) = f x : map f xs

        map quadrat [1,2,3] = [quadrat 1, quadrat 2, quadrat 3] = [1,4,9]

Functions allow currying . While in other languages tuples are passed as arguments to functions, i.e. function types of the form are used, the Curry form is more common in Haskell . Partial evaluation of functions is thus easily possible. For example, the expression is a partial evaluation of , because it describes a function, namely the function that converts all lowercase letters in a list into uppercase letters.(a, b) -> ca -> b -> cmap toUppermap

Haskell allows user-defined data types. These algebraic data types are defined with the help of data constructors.

        data Tree = Leaf Int | Branch Int Tree Tree

The example shows the data structure of a binary tree labeled with whole numbers . Such a tree consists of either a leaf ( ) or a branch ( ), where and represent the subtrees that in turn have the structure . Both the single-digit constructor and the three-digit constructor were used to define this data structure .TreeLeaf IntBranch Int t1 t2t1t2TreeLeafBranch

Data types with several exclusively parameterless constructors can be used as enumerations .

        data Tag = Montag | Dienstag | Mittwoch | Donnerstag | Freitag | Samstag | Sonntag
             deriving (Show, Eq, Ord, Ix, Enum)

Haskell supports type classes. Type classes can be used to summarize types that support a certain amount of operations. In the signatures of functions, Chartype variables with restriction to certain classes may also be used as a gradation between fixed types such as and free type variables.

All instances of a method of the type class have the same name. So in a way, type classes correspond to overloading functions. The same function name therefore stands for different functions depending on the type. For example, the ==method of the class can be used Eqto compare two numbers as well as two texts . Even so, the equality test works differently depending on the type of argument.

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

        putStrLn :: String -> IO ()
        getLine  :: IO String

putStrLnoutputs a text and a line break on the standard output. Since there is no information-bearing result, the unit () type is used as the return type. getLinereads a line of text from standard input . The IO-Type constructor ensures that you have to reveal to the users of the function that the results were obtained through input / output. This strict approach encourages Haskell programmers to clearly separate input and output and other parts of a program. Most of a Haskell program usually consists of functions with no input or output. You can IOalso embed into other types and define such as a special IO type that only allows input types, of course.

syntax

Haskell is case-sensitive . Identifiers that begin with a capital letter represent type and value constructors. Identifiers that begin with a lowercase letter stand for type variables, functions and parameters.

The handling of spaces and line breaks is based on the intuitive understanding of mathematical notation; line breaks only need to be indented to any depth so that the context is not lost. That's the expression

   fun a b = a*b

completely equivalent to

   fun a  b= a  *
       b

Haskell supports single-line and multi-line comments , the former from characters --to the end of the line and the latter including {-and -}.

    f x = x**2
    -- f y = y*5 diese Zeile ist auskommentiert
    {- Alles, was
       hier drin steht, wird auch nicht beachtet.
       f z = z*2
    -}

Haskell has a number of syntactical features . These should not hide the fact that everything is explained in a purely functional manner.

The donotation gives calculations with monads the appearance of imperative programs.
Instead of

        readFile "eingabe.txt" >>= writeFile "ausgabe.txt"

or

        readFile "eingabe.txt" >>= (\inhalt -> writeFile "ausgabe.txt" inhalt)

you can too

        do inhalt <- readFile "eingabe.txt"
           writeFile "ausgabe.txt" inhalt

write.

Both symbolic identifiers (consisting of +, -, *, /,>, <) as well as alphanumeric identifiers (letters, digits and apostrophes) can be used for function names and can be used as infix operators as well as in prefix notation . For example

        a + b      =  (+) a b
        a `div` b  =  div a b

Haskell allows special notations when processing lists . For example, sequences of numbers can be ..indicated with two dots ( ):

        [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 end value is given, an infinite list is generated

        [1..] = [1,2,3 usw.]
        [10,20..] = [10,20,30 usw.]

Furthermore, a notation is allowed, called "list comprehension", which is based on the mathematical notation for set definitions . In the following example, the sequence of even numbers is extracted from the sequence of positive natural numbers.

        [ x | x <- [1..], even x]

as a paraphrase for

        do
           x <- [1..]
           guard $ even x
           return x

In general, any non-empty sequence of generators ( pat <- xs), predicates (expressions with the type Bool) and letrelations can be specified after the vertical bar . In particular, it is possible not to use any generators at all. The expression

        [x | odd x]

assumes xthe value []or depending on the value of , which is assumed to be already defined [x].

programming

Haskell allows pattern matching . This is what we call the use of constructor terms as formal parameters . The parameters are the Terme pattern (Engl. Pattern ) of the function arguments.

        fak :: Integer -> Integer
        fak 0 = 1
        fak n = n * fak (n-1)

The function fakcalculates the factorial of a number. 0 and nare the patterns on which the determination of the result depends. For numbers greater than 0, only the pattern applies n, so that the second alternative is used. This calculates the result , while it calls itself recursively until it arrives at. The pattern then takes effect there , so that the first alternative is used, which cleanly closes the recursion, returns it and initiates the return chain.n * fak (n-1)(n-1) > 0001

Modules

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

In order to use modules, you have to import them. This is done using the importcommand.

   import List
   import Maybe

Functions and types can have the same names in different modules. These identifiers can be distinguished

by importing only one of the identifiers,

        import Data.List(delete)
        x = delete 'a' "abc"

or by qualifying the identifiers, i.e. making them unique by combining them with 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"

It is also possible, but not recommended, to hide identifiers when importing with hiding.

Examples

Faculty

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

    fac :: Integer -> Integer
    fac n = product [1..n]

Often, however, work is also carried out recursively:

    facr :: Integer -> Integer
    facr 0 = 1
    facr n = n * facr (n-1)

End recursion is often more efficient, but also more complex to write:

    facrt :: Integer -> Integer
    facrt n = _facrt n 1
        where _facrt 0 r = r
              _facrt n r = _facrt (n-1) (r*n)

However, this writing effort can be reduced. In _facrt the parameter r contains the respective (intermediate) result. At the beginning of the iteration, r is set to the start value. With each iteration step, the new intermediate result is calculated with a specific function from the previous intermediate result and n. Finally, r is returned as the final result. This principle can be expressed by a reusable function recur:

    recur :: Num a => (b -> a -> b) -> b -> a -> b
    recur f r 0 = r
    recur f r n = recur f (f r n) (n-1)

Using recur, the factorial function with end recursion can then be written very compactly:

    facrg :: Integer -> Integer
    facrg = recur (*) 1

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 quick implementation of the sequence:

    fibs :: [Integer]
    fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

tailremoves the first element from a list, zipWithcombines two lists element by element with the help of another function (here (+)). The definition corresponds to a fixed point equation . The quickest way to check that the definition is correct is to imagine that the fibscalculation has already been completed. The next thing to consider is that the definition can also be evaluated. The first two terms of fibsare immediately clear: 0 and 1. For the calculation of each additional term, however, only the terms of must be used that have already been calculated fibs. The requirement fibsevaluation means that the sequence is actually calculated element by element.

You could also say that is fibsa fixed point of function . This, in turn, can be noted directly in Haskell as \xs -> 0 : 1 : (zipWith (+) xs (tail xs))

    fix (\xs -> 0 : 1 : (zipWith (+) xs (tail xs)))

Difference equation

In this way one can very elegantly formulate differential equations with regard to power series or difference equations with regard to number sequences and solve them at the same time.

Suppose you want to solve the differential equation y '(x) = f (x, y (x)) with respect to y in the form of a time series, i.e. a list of numbers. This discretization turns the differential equation into a difference equation. Instead of an integral, we calculate partial sums . The following function has the integration constant and a number sequence as parameters.

    integrate :: Num a => a -> [a] -> [a]
    integrate = scanl (+)

scanlaccumulates the values of a sequence using another function, here (+), and returns the list of accumulator states.

With this one can already implement the explicit Euler method for the step size 1. x0and y0are 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  = integrate y0 y'
           y' = zipWith f x y
       in  y

This function definition essentially consists of the statement that ythe integral of is y'with the initial value y0(or vice versa, y'the derivative of y) and of the actual differential equation . Because the algorithm is noted more in the form of the task than in the form of a solution, this is called declarative programming . y' = zipWith f x y

Quicksort

The quick sort - algorithm formulated in Haskell:

    qsort :: Ord a => [a] -> [a]
    qsort []     = []
    qsort (x:xs) = qsort kleinergl ++ [x] ++ qsort groesser
                   where
                      kleinergl = [y | y <- xs, y <= x]
                      groesser  = [y | y <- xs, y > x]

The first line defines the signature of Quicksort . The second line indicates that the function, when applied to an empty list, should result in an empty list again. The third line sorts non-empty lists recursively: the first element xis used as the middle element of the result list. All non-larger elements are sorted in front of this, followed by all larger elements. List descriptions are used to xsselect from the rest of the list all those that are greater than xand all those that are not.

As one expects from Quicksort, this implementation also has 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 qsortdoes not work in-place .

algebra

This example highlights the use of type classes .

data PhiNum a = PhiNum { numPart :: a, phiPart :: a } deriving (Eq, Show)

instance Num a => Num (PhiNum a) where
    fromInteger n = PhiNum (fromInteger n) 0
    PhiNum a b + PhiNum c d = PhiNum (a+c) (b+d)
    PhiNum a b * PhiNum c d = 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

fibrepresents a quick calculation of elements of the Fibonacci sequence. The predefined ^, which works on Num-implementing types, is used.

Implementations

There are now a number of Haskell implementations, but most of them do not fully implement the language standard.

The Glasgow Haskell Compiler (GHC) supports Haskell 98 as well as numerous language extensions. He translates Haskell programs into machine code ; for platforms that are not directly supported, it generates C code , which is then compiled with a C compiler.
Hugs is a bytecode compiler that almost completely implements Haskell 98 and some extensions. Hugs is written in C itself.
nhc (also nhc98 ) is another bytecode compiler that supports Haskell 98 with certain restrictions. The York Haskell Compiler or Yhc is a further development of nhc with the aim of improving the portability and performance of the compiled programs.
The Utrecht Haskell Compiler (UHC) is an experimental implementation that is being developed at Utrecht University . The compiler is based on attribute grammars and translates Haskell into C code. He implements Haskell 98 almost completely and some extensions.
Helium is also being developed at Utrecht University. The focus of the project is on generating easy-to-understand error messages to make it easier for beginners to learn Haskell. Therefore, a restricted Haskell dialect is also implemented, which among other things has no type classes.

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

influence

Because of its strong academic background, Haskell serves as a model for new language functionality in many programming and script languages. So have u. a. Perl , Python , JavaScript , Java , Scala and PHP ideas of functional programming taken from Haskell. This includes higher order functions like map, filter, etc., parts of the way generic programming was implemented, and others.

literature

Richard Bird: Introduction to Functional Programming using Haskell . 2nd Edition. Prentice Hall Europe, 1998, ISBN 0-13-484346-0 .
Marco Block, Adrian Neumann: Haskell Intensive Course: A compact introduction to functional programming . Springer, Heidelberg a. a. 2011, ISBN 978-3-642-04717-6 , doi : 10.1007 / 978-3-642-04718-3 .
Paul Hudak: The Haskell school of expression: Learning functional programming through multimedia . Cambridge University Press, Cambridge u. a. 2000, ISBN 0-521-64338-4 (English, new edition: The Haskell school of music (PDF; 2.4 MB), version 2.2, 2012).
Ernst-Erich Doberkat: Haskell - An introduction for the object-oriented . Oldenbourg Wissenschaftsverlag, Munich 2012, ISBN 978-3-486-71417-3 .
John Hughes: Why functional programming matters . In: The Computer Journal . tape 32 , no. 2 , 1989, pp. 98–107 (English, chalmers.se [accessed on April 18, 2017] Advantages of functional programming. Shows forms of modularization that are essentially based on higher-order functions and needs evaluation.).
Miran Lipovača: Learn you a Haskell for great good! A beginner's guide . No Starch Press, San Francisco 2011, ISBN 1-59327-283-9 (English, HTML version [accessed April 18, 2017]).
Bryan O'Sullivan, Don Stewart, John Goerzen: Real world Haskell . O'Reilly, Sebastopol 2008, ISBN 0-596-51498-0 (English, HTML version [accessed April 18, 2017]).
Simon Peyton Jones (Ed.): Haskell 98 Language and Libraries: The Revised Report . Cambridge University Press, 2003, ISBN 0-521-82614-4 ( HTML version ).
Simon Thompson: Haskell: The craft of functional programming . 3. Edition. Addison-Wesley, Harlow / New York 2011, ISBN 978-0-201-88295-7 (English).

Web links

Commons : Haskell - collection of images, videos and audio files

Wikibooks: Functional programming with Haskell - learning and teaching materials

Wikibooks: Haskell - learning and teaching materials (English)

haskell.org - central point of contact for the Haskell programming language with information on learning Haskell
Online interactive interpreter tutorial (English)

Individual evidence

^ Professor Paul Hudak's website ( June 7, 2011 memento in the Internet Archive ) at Yale University
↑ haskell.org
^ The Glasgow Haskell Compiler . Project website. Retrieved January 9, 2010.
↑ Hugs 98 . Project website. Retrieved January 9, 2010.
↑ nhc98 . Project website. Retrieved January 9, 2010.
↑ Niklas Rojemo: nhc - Nearly a Haskell Compiler. (PDF) Chalmers Tech Report, 1994.
↑ Atze Dijkstra, Jeroen Fokker, S. Doaitse Swierstra: The architecture of the Utrecht Haskell compiler. In: Haskell '09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell. ACM, New York NY 2009, pp. 93-104, doi: 10.1145 / 1596638.1596650 .
↑ Bastiaan Heeren, Daan Leijen, Arjan van IJzendoorn: Helium, for learning Haskell. In: Haskell '03: Proceedings of the 2003 ACM SIGPLAN workshop on Haskell. ACM, New York NY 2003, pp. 62-71, doi: 10.1145 / 871895.871902 .

[1] Professor Paul Hudak's website ( June 7, 2011 memento in the Internet Archive ) at Yale University

[2] skell.org

[3] The Glasgow Haskell Compiler . Project website. Retrieved January 9, 2010.

[4] Hugs 98 . Project website. Retrieved January 9, 2010.

[5] nhc98 . Project website. Retrieved January 9, 2010.

[6] Niklas Rojemo: nhc - Nearly a Haskell Compiler. (PDF) Chalmers Tech Report, 1994.

[7] Atze Dijkstra, Jeroen Fokker, S. Doaitse Swierstra: The architecture of the Utrecht Haskell compiler. In: Haskell '09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell. ACM, New York NY 2009, pp. 93-104, doi: 10.1145 / 1596638.1596650 .

[8] Bastiaan Heeren, Daan Leijen, Arjan van IJzendoorn: Helium, for learning Haskell. In: Haskell '03: Proceedings of the 2003 ACM SIGPLAN workshop on Haskell. ACM, New York NY 2003, pp. 62-71, doi: 10.1145 / 871895.871902 .