Haskell features

This article describes the features in the programming language Haskell.

This article describes the features in the programming language Haskell. factorial :: Integer -> Integer factorial 0 = 1 factorial n = n * factorial (n-1) Or in one line: factorial n = if n > 1 then n * factorial (n-1) else 1 This describes the factorial as a recursive function, with one terminating base case. It is similar to the descriptions of factorials found in mathematics textbooks. Much of Haskell code is similar to standard mathematical notation in facility and syntax. The first line of the factorial function describes the type of this function; while it is optional, it is considered to be good style to include it. It can be read as the function factorial ( factorial ) has type ( :: ) from integer to integer ( Integer -> Integer ). That is, it takes an integer as an argument, and returns another integer. The type of a definition is inferred automatically if no type annotation is given. The second line relies on pattern matching, an important feature of Haskell. Note that parameters of a function are not in parentheses but separated by spaces. When the function's argument is 0 (zero) it will return the integer 1 (one). For all other cases the third line is tried. This is the recursion, and executes the function again until the base case is reached. Using the product function from the Prelude, a number of small functions analogous to C's standard library, and using the Haskell syntax for arithmetic sequences, the factorial function can be expressed in Haskell as follows: factorial n = product [1..n] Here [1..n] denotes the arithmetic sequence in list form. Using the Prelude function enumFromTo , the expression [1..n] can be written as enumFromTo 1 n , allowing the factorial function to be expressed as factorial n = product (enumFromTo 1 n) which, using the function composition operator (expressed as a dot in Haskell) to compose the product function with the curried enumeration function can be rewritten in point-free style: factorial = product . enumFromTo 1 In the Hugs interpreter, one often needs to define the function and use it on the same line separated by a where or let .. in . For example, to test the above examples and see the output 120 : let { factorial n | n > 0 = n * factorial (n-1); factorial _ = 1 } in factorial 5 or factorial 5 where factorial = product . enumFromTo 1 The GHCi interpreter doesn't have this restriction and function definitions can be entered on one line (with the let syntax without the in part), and referenced later. In the second line calc = ... the equals sign can be read as "can be"; thus multiple lines with calc = ... can be read as multiple possible values for calc , depending on the circumstance detailed in each line. A simple Reverse Polish notation calculator expressed with the higher-order function foldl whose argument f is defined in a where clause using pattern matching and the type class Read: calc :: String -> [Float] calc = foldl f [] . words where f (x:y:zs) "+" = (y + x):zs f (x:y:zs) "-" = (y - x):zs f (x:y:zs) "*" = (y * x):zs f (x:y:zs) "/" = (y / x):zs f (x:y:zs) "FLIP" = y:x:zs f zs w = read w : zs The empty list is the initial state, and f interprets one word at a time, either as a function name, taking two numbers from the head of the list and pushing the result back in, or parsing the word as a floating-point number and prepending it to the list. fibs = 0 : 1 : zipWith (+) fibs (tail fibs) The infinite list is produced by corecursion — the latter values of the list are computed on demand starting from the initial two items 0 and 1. This kind of a definition relies on lazy evaluation, an important feature of Haskell programming. For an example of how the evaluation evolves, the following illustrates the values of fibs and tail fibs after the computation of six items and shows how zipWith (+) has produced four items and proceeds to produce the next item: fibs = 0 : 1 : 1 : 2 : 3 : 5 : ...   + + + + + + tail fibs = 1 : 1 : 2 : 3 : 5 : ...   = = = = = = zipWith ... = 1 : 2 : 3 : 5 : 8 : ... fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 : ... The same function, written using Glasgow Haskell Compiler's parallel list comprehension syntax (GHC extensions must be enabled using a special command-line flag, here -XParallelListComp, or by starting the source file with {-# LANGUAGE ParallelListComp #-} ): fibs = 0 : 1 : [ a+b | a or with regular list comprehensions: fibs = 0 : 1 : [ a+b | (a,b) or directly self-referencing: fibs = 0 : 1 : next fibs where next (a : t@(b:_)) = (a+b) : next t With stateful generating function: fibs = next (0,1) where next (a,b) = a : next (b, a+b) or with unfoldr : fibs = unfoldr (\(a,b) -> Just (a, (b, a+b))) (0, 1) or scanl : fibs = 0 : scanl (+) 1 fibs Using data recursion with Haskell's predefined fixpoint combinator: fibs = fix (\xs -> 0 : 1 : zipWith (+) xs (tail xs)) -- zipWith version factorial n = foldr ((.) . (*)) id [1..n] $ 1 -- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) id )))) 1 -- == (1*) . (2*) . (3*) . (4*) . (5*) . id $ 1 -- == 1* ( 2* ( 3* ( 4* ( 5* ( id 1 ))))) factorial n = foldr ((.) . (*)) (const 1) [1..n] $ () -- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) (const 1) )))) () -- == (1*) . (2*) . (3*) . (4*) . (5*) . const 1 $ () -- == 1* ( 2* ( 3* ( 4* ( 5* ( const 1 () ))))) factorial n = foldr (($) . (*)) 1 [1..n] = foldr ($) 1 $ map (*) [1..n] -- factorial 5 == ((1*) $) ( ((2*) $) ( ((3*) $) ( ((4*) $) ( ((5*) $) 1 )))) -- == (1*) $ (2*) $ (3*) $ (4*) $ (5*) $ 1 -- == 1* ( 2* ( 3* ( 4* ( 5* 1 )))) hamming = 1 : map (2*) hamming `union` map (3*) hamming `union` map (5*) hamming Like the various fibs solutions displayed above, this uses corecursion to produce a list of numbers on demand, starting from the base case of 1 and building new items based on the preceding part of the list. Here the function union is used as an operator by enclosing it in back-quotes. Its case clauses define how it merges two ascending lists into one ascending list without duplicate items, representing sets as ordered lists. Its companion function minus implements set difference: It is possible to generate only the unique multiples, for more efficient operation. Since there are no duplicates, there's no need to remove them: smooth235 = 1 : foldr (\p s -> fix $ mergeBy ( This uses the more efficient function merge which doesn't concern itself with the duplicates (also used in the following next function, mergesort ): mergeBy less xs ys = merge xs ys where merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) | less y x = y : merge (x:xs) ys | otherwise = x : merge xs (y:ys) Each vertical bar ( | ) starts a guard clause with a guard expression before the = sign and the corresponding definition after it, that is evaluated if the guard is true. mergesortBy less [] = [] mergesortBy less xs = head $ until (null . tail) (pairwise $ mergeBy less) [[x] | x -- "Integers above 1 that cannot be divided by a smaller integer above 1" -- primes = { n ∈ [2..] | ~ ∃ d ∈ [2..n-1] ⇒ rem n d = 0 } -- = { n ∈ [2..] | ∀ d ∈ [2..n-1] ⇒ rem n d ≠ 0 } primes = [ n | n rem n d /= 0) [2..(n-1)] ] This finds primes by trial division. Note that it is not optimized for efficiency and has very poor performance. Slightly faster (but still very slow) is this code by David Turner: primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x Much faster is the optimal trial division algorithm primes = 2 : [ n | n 0) . rem n) $ takeWhile (( or an unbounded sieve of Eratosthenes with postponed sieving in stages, primes = 2 : sieve primes [3..] where sieve (p:ps) (span ( (h, t)) = h ++ sieve ps (minus t [p*p, p*p+p..]) or the combined sieve implementation by Richard Bird, -- "Integers above 1 without any composite numbers which -- are found by enumeration of each prime's multiples" primes = 2 : minus [3..] (foldr (\(m:ms) r -> m : union ms r) [] [[p*p, p*p+p ..] | p or an even faster tree-like folding variant with nearly optimal (for a list-based code) time complexity and very low space complexity achieved through telescoping multistage recursive production of primes: primes = 2 : _Y ((3 :) . minus [5,7..] . _U . map (\p -> [p*p, p*p+2*p..])) where -- non-sharing Y combinator: _Y g = g (_Y g) -- (g (g (g (g (...))))) -- big union ~= nub.sort.concat _U ((x:xs):t) = x : (union xs . _U . pairwise union) t Working on arrays by segments between consecutive squares of primes, it is: import Data.Array import Data.List (tails, inits) primes = 2 : [ n | (r:q:_, px) False) True (r+1,q-1) [ (m,()) | p The shortest possible code is probably  nubBy (((>1) .) . gcd) [2..] .  It is quite slow. product xs = prod xs 1 where prod [] a = a prod (x:xs) a = prod xs (a*x) The two equations for the nested function prod are aligned vertically, which allows the semi-colon separator to be omitted. In Haskell, indentation can be used in several syntactic constructs, including do , let , case , class , and instance . The use of indentation to indicate program structure originates in Peter J. Landin's ISWIM language, where it was called the off-side rule. This was later adopted by Miranda, and Haskell adopted a similar (but rather more complex) version of Miranda's off-side rule, which is called "layout". Other languages to adopt whitespace character-sensitive syntax include Python and F#. The use of layout in Haskell is optional. For example, the function product above can also be written: product xs = prod xs 1 where { prod [] a = a; prod (x:xs) a = prod xs (a*x) } The explicit open brace after the where keyword indicates that separate declarations will use explicit semi-colons, and the declaration-list will be terminated by an explicit closing brace. One reason for wanting support for explicit delimiters is that it makes automatic generation of Haskell source code easier. Haskell's layout rule has been criticised for its complexity. In particular, the definition states that if the parser encounters a parse error during processing of a layout section, then it should try inserting a close brace (the "parse error" rule). Implementing this rule in a traditional parsing and lexical analysis combination requires two-way cooperation between the parser and lexical analyser, whereas in most languages, these two phases can be considered independently. add a b = a + b ten1 = 5 + 5 ten2 = (+) 5 5 ten3 = add 5 5 ten4 = 5 `add` 5 Functions which are defined as taking several parameters can always be partially applied. Binary operators can be partially applied using section notation: ten5 = (+ 5) 5 ten6 = (5 +) 5 addfive = (5 +) ten7 = addfive 5 -- This type signature says that empty takes a list containing any type, and returns a Bool empty :: [a] -> Bool empty (x:xs) = False empty [] = True -- Will return a value from a Maybe a, given a default value in case a Nothing is encountered fromMaybe :: a -> Maybe a -> a fromMaybe x (Just y) = y fromMaybe x Nothing = x isRight :: Either a b -> Bool isRight (Right _) = True isRight (Left _) = False getName :: Person -> String getName (Person name _ _) = name getSex :: Person -> Sex getSex (Person _ sex _) = sex getAge :: Person -> Int getAge (Person _ _ age) = age Using the above functions, along with the map function, we can apply them to each element of a list, to see their results: map empty [[1,2,3],[],[2],[1..]] -- returns [False,True,False,False] map (fromMaybe 0) [Just 2,Nothing,Just 109238, Nothing] -- returns [2,0,109238,0] map isRight [Left "hello", Right 6, Right 23, Left "world"] -- returns [False, True, True, False] map getName [Person "Sarah" Female 20, Person "Alex" Male 20, tom] -- returns ["Sarah", "Alex", "Tom"], using the definition for tom above Abstract Types Lists account :: (String, Integer, Double) -- The type of a three-tuple, representing -- a name, balance, and interest rate account = ("John Smith",102894,5.25) Tuples are commonly used in the zip* functions to place adjacent elements in separate lists together in tuples (zip4 to zip7 are provided in the Data.List module): -- The definition of the zip function. Other zip* functions are defined similarly zip :: [x] -> [y] -> [(x,y)] zip (x:xs) (y:ys) = (x,y) : zip xs ys zip _ _ = [] zip [1..5] "hello" -- returns [(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')] -- and has type [(Integer, Char)] zip3 [1..5] "hello" [False, True, False, False, True] -- returns [(1,'h',False),(2,'e',True),(3,'l',False),(4,'l',False),(5,'o',True)] -- and has type [(Integer,Char,Bool)] In the GHC compiler, tuples are defined with sizes from 2 elements up to 62 elements. Records -- A list of a's ([a]) is either an a consed (:) onto another list of a's, or an empty list ([]) data [a] = a : [a] | [] -- Something of type Maybe a is either Just something, or Nothing data Maybe a = Just a | Nothing -- Something of type Either atype btype is either a Left atype, or a Right btype data Either a b = Left a | Right b Users of the language can also define their own abstract data types. An example of an ADT used to represent a person's name, sex and age might look like: data Sex = Male | Female data Person = Person String Sex Int -- Notice that Person is both a constructor and a type -- An example of creating something of type Person tom :: Person tom = Person "Tom" Male 27 import Control.Monad.ST import Data.STRef import Control.Monad sumST :: Num a => [a] -> a sumST xs = runST $ do -- runST takes stateful ST code and makes it pure. summed do -- For each element of the argument list xs .. modifySTRef summed (+x) -- add it to what we have in n. readSTRef summed -- read the value of n, which will be returned by the runST above. main = do putStrLn "What's your name?" name The do-notation eases working with monads. This do-expression is equivalent to, but (arguably) easier to write and understand than, the de-sugared version employing the monadic operators directly: main = putStrLn "What's your name?" >> getLine >>= \ name -> putStr ("Hello, " ++ name ++ "!\n") See also wikibooks:Transwiki:List of hello world programs#Haskell for another example that prints text.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368594340 under CC BY-SA 4.0; modifications have been made.