% Demo ---- >This file gives simple examples to demonstrate the basic concepts introduced in this course. It is not suitable to be read from beginning to end as an introduction to Haskell. (The example functions are not very interesting.) It is more meant as a reference to look up specific concepts. > >The source of the text is a [literate Haskell](http://www.haskell.org/haskellwiki/Literate_programming) file: [Demo.lhs](Demo.lhs) that you can download and load into GHC. ---- Function definition, local declarations ==================================================================================================== Simple function definition \begin{code} -- Double the argument fun1 :: Int -> Int fun1 x = x*2 \end{code} Function with local definitions in a `where`{.haskell} clause: \begin{code} -- Square length of hypotenuse fun2 :: Int -> Int -> Int fun2 x y = x2 + y2 where x2 = x*x y2 = y*y \end{code} Note that everything local to the definition has to be *indented*. Local definitions using `let`{.haskell} (equivalent to `fun2`): \begin{code} -- Square length of hypotenuse fun2' :: Int -> Int -> Int fun2' x y = let x2 = x*x in let y2 = y*y in x2 + y2 \end{code} Using a local function instead (equivalent to `fun2`): \begin{code} -- Square length of hypotenuse fun2'' :: Int -> Int -> Int fun2'' x y = square x + square y where square a = a*a \end{code} In general, a type `a -> b -> c` is for a function that takes an `a` and a `b` as arguments and return a `c` as result (but see the section on [multiple arguments](#functions-with-multiple-arguments)). Function application ==================================================================================================== Functions are applied by just listing the arguments after the function name: ~~~~~~~~~~~~~~~~~~~~ *Main> fun1 10 20 *Main> fun2 3 4 25 ~~~~~~~~~~~~~~~~~~~~ Infix operators --------------- Any function of at least two arguments can be written *infix*, i.e., between its arguments by using back-ticks: ~~~~~~~~~~~~~~~~~~~~ *Main> 3 `fun2` 4 25 *Main> 34 `max` 45 45 ~~~~~~~~~~~~~~~~~~~~ This notation can also be used when defining functions: \begin{code} -- Square length of hypotenuse hyp :: Int -> Int -> Int x `hyp` y = x2 + y2 where x2 = x*x y2 = y*y \end{code} Operators, such as `+`, `*`, `&&`, are normal function (of two arguments). They are written infix by default: ~~~~~~~~~~~~~~~~~~~~ *Main> 1+2 3 *Main> True && False False ~~~~~~~~~~~~~~~~~~~~ This is also the case for user-defined operators (as long as the name is non-alphanumeric); e.g. \begin{code} -- Almost equal (=~) :: Int -> Int -> Bool a =~ b = abs (a-b) < 2 \end{code} It is however possible to use operators in prefix style (operator before its arguments) by surrounding it with parentheses: ~~~~~~~~~~~~~~~~~~~~{.haskell} -- Almost equal (=~) :: Int -> Int -> Bool (=~) a b = abs (a-b) < 2 ~~~~~~~~~~~~~~~~~~~~ Testing: ~~~~~~~~~~~~~~~~~~~~ *Main> 4 =~ 5 True *Main> 4 =~ 7 False *Main> (=~) 4 7 False ~~~~~~~~~~~~~~~~~~~~ Application operator -------------------- When applying several functions in sequence, such as in \begin{code} -- Take the `n` last elements of a list takeLast :: Int -> [a] -> [a] takeLast n s = reverse (take n (reverse s)) \end{code} the parentheses can quickly become unreadable. In that case, the `($)` operator can be used to avoid parentheses: \begin{code} -- Take the `n` last elements of a list takeLast' :: Int -> [a] -> [a] takeLast' n s = reverse $ take n $ reverse s \end{code} As an approximation, `$` can be read as "a parenthesis from here to the end of the expression". Note though that `($)` does not always mix well with other infix operators. If there are problems, try inserting parentheses. Types ==================================================================================================== TODO: Under construction... Type classes ------------ TODO: Under construction... `fun1` could have been given a more general type: ~~~~~~~~~~~~~~~~~~~~{.haskell} fun1 :: Num a => a -> a ~~~~~~~~~~~~~~~~~~~~ Data types ==================================================================================================== This is a redifinition of the standard `Bool` type (using capital letters to avoid name-clashes): \begin{code} data BOOL = TRUE | FALSE \end{code} * `BOOL` is a type * `TRUE` and `FALSE` are constructors for this type: ~~~~~~~~~~~~~~~~~~~~{.haskell} TRUE :: BOOL FALSE :: BOOL ~~~~~~~~~~~~~~~~~~~~ Optional values: \begin{code} data MAYBE a = JUST a | NOTHING \end{code} * `MAYBE` is a parameterized type (a.k.a. "type constructor") * `JUST` and `NOTHING` are constructors for this type: ~~~~~~~~~~~~~~~~~~~~{.haskell} JUST :: a -> MAYBE a NOTHING :: MAYBE a ~~~~~~~~~~~~~~~~~~~~ Recursive type (list of Booleans): \begin{code} data ListBool = EmptyB | AddB Bool ListBool \end{code} * `ListBool` is a type * `EmptyB` and `AddB` are constructors for this type: ~~~~~~~~~~~~~~~~~~~~{.haskell} EmptyB :: ListBool AddB :: Bool -> ListBool -> ListBool ~~~~~~~~~~~~~~~~~~~~ Recursive type (list of integers): \begin{code} data ListInt = EmptyI | AddI Int ListInt \end{code} * `ListInt` is a type * `EmptyI` and `AddI` are constructors for this type: ~~~~~~~~~~~~~~~~~~~~{.haskell} EmptyI :: ListInt AddI :: Int -> ListInt -> ListInt ~~~~~~~~~~~~~~~~~~~~ Even better -- generalization of `ListBool` and `ListInt`: \begin{code} data List a = Empty | Add a (List a) \end{code} * `List` is a parameterized type (type constructor) * `Empty` and `Add` are constructors for this type: ~~~~~~~~~~~~~~~~~~~~{.haskell} Empty :: List a Add :: a -> List a -> List a ~~~~~~~~~~~~~~~~~~~~ * Use `List Bool` instead of `ListBool` * Use `List Int` instead of `ListInt` We will use `BOOL`, `MAYBE` and `LIST` to demonstrate the use of data types. In real code, it is of course better to use the standard `Bool`, `Maybe` and `[]`. Construction ------------ To construct values of our newly introduced types, we have to use the constructors. \begin{code} thisIsFalse = FALSE thisIsTrue = TRUE thisIsJustZero = JUST 0 thisIsNothingAtAll = NOTHING someNumbers :: List Int someNumbers = Add 1 (Add 2 (Add 3 Empty)) -- Corresponds to the list [1,2,3] \end{code} Note that the constructors are given arguments according to their types (see above). `FALSE`, `TRUE` and `NOTHING` have no arguments. `JUST` has one argument and `Add` has two. Pattern matching ---------------- When defining functions that take data types as arguments, we can use *patterns* to distinguish between different inputs; e.g.: \begin{code} -- Check if the argument is `Just 1` isJUST1 :: MAYBE Int -> BOOL isJUST1 (JUST 1) = TRUE isJUST1 _ = FALSE \end{code} Patterns have the same form as ordinary values: The constructors are applied to argument patterns according to their type. In the above example `JUST` is applied to the pattern `1` which matches the integer `1`. Patterns are matched in top-down down order: if a pattern fails, the next pattern below is tried, and so on. A difference between patterns and ordinary values is that patterns may contain wildcards, written as `_`. This is useful, for example, if we just want to check whether the argument is of the form `JUST ...`: \begin{code} -- Check if the argument is of the form `Just ...` isJUST :: MAYBE a -> BOOL isJUST (JUST _) = TRUE isJUST NOTHING = FALSE \end{code} Another difference is that patterns can introduce new variables. This is useful if we are not just interested in knowing that the argument has a certain form, but want to be able to refer to parts of this form. For example, we may not just want to check whether the input has the form `JUST ...` but also be able to refer to the `...` part: \begin{code} -- Check if the argument is of the form `Just ...` fromJUST :: MAYBE a -> a fromJUST (JUST a) = a fromJUST NOTHING = error "fromJUST: NOTHING" \end{code} It is common to have patterns that match on a single constructor at a time. However, this does not have to be the case -- patterns can be arbitrarily deep: \begin{code} -- Check if the argument is the list 1,2,3 is123 :: List Int -> BOOL is123 (Add 1 (Add 2 (Add 3 Empty))) = TRUE is123 _ = FALSE \end{code} The pattern can be read as follows: A list whose first element is 1 and whose tail matches `Add 2 (Add 3 Empty)`. In summary, we see that pattern matching has two purposes: 1. Distinguish between cases, e.g. ~~~~~~~~~~~~~~~~~~~~{.haskell} isJUST (JUST _) = ... isJUST NOTHING = ... ~~~~~~~~~~~~~~~~~~~~ 2. Extract parts of an argument ("destruction"), e.g. ~~~~~~~~~~~~~~~~~~~~{.haskell} -- Add the first two numbers in a list addFirstTwo :: List Int -> Int addFirstTwo (Add a (Add b _)) = a+b ~~~~~~~~~~~~~~~~~~~~ Case expressions ---------------- In the above examples, pattern matching is done on the arguments of functions. If, instead, we want to match against an arbitrary value inside an expression, we can use a *case expression*. We can easily rewrite the above examples using `case`: \begin{code} isJUST' :: MAYBE a -> BOOL isJUST' ma = case ma of JUST _ -> TRUE NOTHING -> FALSE fromJUST' :: MAYBE a -> a fromJUST' ma = case ma of JUST a -> a NOTHING -> error "fromJUST: NOTHING" addFirstTwo' :: List Int -> Int addFirstTwo' as = case as of Add a (Add b _) -> a+b \end{code} (These definitions mean exactly the same thing as the previous versions.) As seen before, we do not actually need to use `case` for these examples. But whenever we need to match against a value that is not a function argument, we have to use case. For example, the following function matches on the words of a string: \begin{code} fun3 :: String -> Int fun3 text = case words text of "Alice" : _ -> 23 "Bob" : "Marley" : _ -> 34 \end{code} Testing: ~~~~~~~~~~~~~~~~~~~~ *Main> fun3 "Bob Marley is back" 34 ~~~~~~~~~~~~~~~~~~~~ If expressions and guards ------------------------- Instead of pattern matching on Boolean values, it is possible to use an *if expression*. For example, we can write \begin{code} -- Absolute value abs' :: Int -> Int abs' a = if a < 0 then -a else a \end{code} instead of \begin{code} abs'' :: Int -> Int abs'' a = case a < 0 of True -> -a False -> a \end{code} (It means the exact same thing.) It is not very convenient to nest if expressions: \begin{code} fun4 :: Int -> String fun4 n = if n < 0 then "negative" else if n < 5 then "quite small" else if n < 100 then "normal" else "big" \end{code} This should be read as if there were a parenthesis starting after each `else`; i.e. ~~~~~~~~~~~~~~~~~~~~{.haskell} if ... then ... else (if ... then ... else (if ... then ... else ...))) ~~~~~~~~~~~~~~~~~~~~ By using *guards*, `fun4` can be rewritten in a way that looks more like conditional equations: \begin{code} fun4' :: Int -> String fun4' n | n < 0 = "negative" | n < 5 = "quite small" | n < 100 = "normal" | otherwise = "big" \end{code} The expressions in the guards (e.g. `n < 0`) must have type `Bool`. The expression `otherwise` is defined to be `True`, so the last case will always be taken, if no other case is taken. It is possible to mix guards and pattern matching: \begin{code} maxOfFirstTwo :: List Int -> Int maxOfFirstTwo (Add a (Add b _)) | a > b = a | otherwise = b \end{code} * Although a more sensible definition would be ~~~~~~~~~~~~~~~~~~~~{.haskell} maxOfFirstTwo (Add a (Add b _)) = max a b ~~~~~~~~~~~~~~~~~~~~ We can also have guards in `case`{.haskell} expressions: \begin{code} firstWordIsFourChars :: String -> Bool firstWordIsFourChars s = case words s of w:_ | length w == 4 -> True _ -> False \end{code} This function returns `True` if the string has at least one word, and this word is four characters long. Built-in lists ==================================================================================================== Instead of the `List` type defined above, one should use Haskell's built-in lists, which have the same structure, but nicer syntax and lots of predefined helper functions. Conceptually, built-in lists are defined as: ~~~~~~~~~~~~~~~~~~~~{.haskell} data [a] = [] | a : [a] ~~~~~~~~~~~~~~~~~~~~ (But this is not a syntactically valid definition.) The interpretation of this type is similar to the interpretation of `List`: * `[]` is a parameterized type (type constructor). * `[]` and `(:)` are constructors for this type: ~~~~~~~~~~~~~~~~~~~~{.haskell} [] :: [a] (:) :: a -> [a] -> [a] ~~~~~~~~~~~~~~~~~~~~ We see that `[a]` corresponds to `List a`; in fact, it is possible to write `[] a` instead of `[a]` which shows the correspondence between `[]` and `List`. The `(:)` constructor is commonly called "cons". Construction ------------ Built-in lists are constructed in the same way as `List` \begin{code} someNumbers2 :: [Int] someNumbers2 = (:) 1 ((:) 2 ((:) 3 [])) \end{code} Since `(:)` is an [infix operator](#infix-operators), we can rewrite this more nicely as \begin{code} someNumbers2' :: [Int] someNumbers2' = 1 : 2 : 3 : [] \end{code} And we can make it even nicer using Haskell's special syntax for built-in lists: \begin{code} someNumbers2'' :: [Int] someNumbers2'' = [1,2,3] \end{code} Haskell also has special syntax for *list enumeration*: ~~~~~~~~~~~~~~~~~~~~ *Main> [0..10] [0,1,2,3,4,5,6,7,8,9,10] *Main> [0,10..100] [0,10,20,30,40,50,60,70,80,90,100] ~~~~~~~~~~~~~~~~~~~~ Pattern matching ---------------- As always, patterns are written in mostly the same way as ordinary expressions. This is true for built-in lists as well. We \begin{code} is_123 :: [Int] -> BOOL is_123 ((:) 1 ((:) 2 ((:) 3 []))) = TRUE is_123 _ = FALSE is_123' :: [Int] -> BOOL is_123' (1 : 2 : 3 : []) = TRUE is_123' _ = FALSE is_123'' :: [Int] -> BOOL is_123'' [1,2,3] = TRUE is_123'' _ = FALSE \end{code} The above three functions all mean the same thing. In this case, the last version is preferred. If the length of the list is not known, we have to use a cons pattern: \begin{code} addFirstTwo :: [Int] -> Int addFirstTwo (a:b:_) = a+b \end{code} Higher-order functions ==================================================================================================== In general, higher-order functions are functions that take functions as arguments or give functions as result. There are many higher-order functions in Haskell's standard libraries. We will not go through them here, but just demonstrate the basic ideas. Functions as arguments ---------------------- It is often convenient to define general functions whose behavior can be controlled by the caller. This is done by making the function take a function as argument. For example, the higher-order function ~~~~~~~~~~~~~~~~~~~~{.haskell} map :: (a -> b) -> [a] -> [b] ~~~~~~~~~~~~~~~~~~~~ takes two arguments: a function `(a -> b)` and a list `[a]`. The result is obtained by applying the function to each element in the argument list: \begin{code} eachEven :: [Int] -> [Bool] eachEven as = map even as \end{code} ~~~~~~~~~~~~~~~~~~~~ *Main> eachEven [1..10] [False,True,False,True,False,True,False,True,False,True] ~~~~~~~~~~~~~~~~~~~~ TODO: Explain `(.)` Functions with multiple arguments --------------------------------- In general, functions have *one* argument and *one* result. The type `a -> b` denotes the type of a function whose argument is of type `a` and whose result is of type `b`. But we often see types with more than one arrow, e.g. ~~~~~~~~~~~~~~~~~~~~{.haskell} (+) :: Int -> Int -> Int ~~~~~~~~~~~~~~~~~~~~ (Here, the [overloaded](#type-classes) type of `(+)` has been specialized to type `Int`.) We usually think of `(+)` as taking two arguments. However, if we write out the implicit parentheses in the type, we get ~~~~~~~~~~~~~~~~~~~~{.haskell} (+) :: Int -> (Int -> Int) ~~~~~~~~~~~~~~~~~~~~ (Note, the type is still the same: The parentheses are there even if they are not written, because `->` is a right-associative operator.) That is: `(+)` takes *one* argument of type `Int` and returns a function `Int -> Int`. We see that `(+)` is actually a higher-order function, since it returns a function as result. So if we want to compute, e.g., 1+2, we can do this by first supplying the argument `1` to `(+)` and then the argument `2`: \begin{code} onePlus :: Int -> Int onePlus = (+) 1 onePlusTwo :: Int onePlusTwo = onePlus 2 \end{code} Luckily, we don't have to write this much code to add two numbers: By substituting the definition of `onePlus` into `onePlusTwo`, we get (see [infix operators](#infix-operators)): \begin{code} onePlusTwo' :: Int onePlusTwo' = ((+) 1) 2 \end{code} which is the same as \begin{code} onePlusTwo'' :: Int onePlusTwo'' = (+) 1 2 \end{code} which is the same as \begin{code} onePlusTwo''' :: Int onePlusTwo''' = 1 + 2 \end{code} Even though `(+)` actually takes only one argument, it is still often useful to think of it as a two-argument function. We take the liberty to do this whenever suitable (as common in the functional programming community). When a function of $n$ arguments is applied to fewer than $n$ arguments, we say that the function is *partially applied*. Switching views --------------- Let us return to the definition of `eachEven`: ~~~~~~~~~~~~~~~~~~~~{.haskell} eachEven :: [Int] -> [Bool] eachEven as = map even as ~~~~~~~~~~~~~~~~~~~~ Here we supply two arguments to `map`, but we now know that `map` [actually only takes one argument](#functions-with-multiple-arguments), which can be seen by writing out all parentheses in its type: ~~~~~~~~~~~~~~~~~~~~{.haskell} map :: (a -> b) -> ([a] -> [b]) ~~~~~~~~~~~~~~~~~~~~ This means that we could just as well have supplied only one argument and let `map` itself return the function: \begin{code} eachEven' :: [Int] -> [Bool] eachEven' = map even \end{code} Now, what is the difference between `eachEven` and `eachEven'` ? * `eachEven` says: The list obtained by applying `eachEven` to `as` is the same as the list obtained by `map even as`. * `eachEven'` says: The function `eachEven'` is the same as the function `map even`. The two definitions mean exactly the same thing! They just take a different view of what is defined. Note that the definition of `eachEven'` is obtained by just deleting `as` on both sides of the definition of `eachEven`. Anonymous functions (lambda) ---------------------------- Use a lambda function `\x -> ... x ...` when you need a local function but don't want to give it a name: \begin{code} mapSquare :: [Integer] -> [Integer] mapSquare = map (\x -> x*x) allPositiveEven :: [Integer] -> Bool allPositiveEven = all (\a -> a>0 && even a) \end{code} These functions could just as well have used a named local function: \begin{code} mapSquare' :: [Integer] -> [Integer] mapSquare' = map square where square x = x*x allPositiveEven' :: [Integer] -> Bool allPositiveEven' = all posEven where posEven a = a>0 && even a \end{code} It is often convenient to construct anonymous functions by [partial application](#functions-with-multiple-arguments): ~~~~~~~~~~~~~~~~~~~~ *Main> map (min 6) [1..10] [1,2,3,4,5,6,6,6,6,6] ~~~~~~~~~~~~~~~~~~~~ Here the function argument to `map` is `min 6` which is a function that returns the minimum of its argument and $6$. If we want to partially apply the second argument of a function, we can use a lambda: ~~~~~~~~~~~~~~~~~~~~ *Main> map (\x -> x `mod` 4) [1..20] [1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0] ~~~~~~~~~~~~~~~~~~~~ Alternatively, we can use [infix notation](#infix-operators) to partially apply the second argument: ~~~~~~~~~~~~~~~~~~~~ *Main> map (`mod` 4) [1..20] [1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0] *Main> map (*2) [1..20] [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40] ~~~~~~~~~~~~~~~~~~~~ Another convenient way of creating anonymous functions is to use function composition `(.)`: ~~~~~~~~~~~~~~~~~~~~ *Main> map ((*2) . abs) [-10 .. 10] [20,18,16,14,12,10,8,6,4,2,0,2,4,6,8,10,12,14,16,18,20] ~~~~~~~~~~~~~~~~~~~~ Here we used the anonymous function `(*2) . abs` which could just as well have been written using lambda: ~~~~~~~~~~~~~~~~~~~~ *Main> map (\x -> abs x * 2) [-10 .. 10] [20,18,16,14,12,10,8,6,4,2,0,2,4,6,8,10,12,14,16,18,20] ~~~~~~~~~~~~~~~~~~~~ Generic programming ==================================================================================================== Haskell provides many ways of writing abstract functions that are meaningful for many different types of data. We are not going to go deep into this area here, but just mention two basic generic functions: ~~~~~~~~~~~~~~~~~~~~{.haskell} mapM :: Monad m => (a -> m b) -> [a] -> m [b] fmap :: Functor f => (a -> b) -> f a -> f b ~~~~~~~~~~~~~~~~~~~~ `mapM` ------ `mapM` is used, for example, to perform some `IO` instruction for each element in a list and collect the results in a list. The following example uses `mapM` \begin{code} collectAnswers :: IO [String] collectAnswers = mapM answer [1..5] where answer q = do putStr $ "What's your answer to question " ++ show q ++ "? " getLine \end{code} In this example, we used `mapM` at the type ~~~~~~~~~~~~~~~~~~~~{.haskell} mapM_ :: (Int -> IO String) -> [Int] -> IO String ~~~~~~~~~~~~~~~~~~~~ (which works because `IO` is an instance of `Monad`). But the nice thing about `mapM` is that it works for *any* monad. For example, we can also use it together with QuickCheck's `Gen` monad. The following generator produces a list of random numbers in increasing intervals: \begin{code} genNums :: Gen [Int] genNums = mapM (\x -> choose (x, x+10)) [0,100 .. 1000] \end{code} ~~~~~~~~~~~~~~~~~~~~ *Main> sample genNums [2,103,202,307,403,502,607,701,800,900,1009] [3,109,205,301,406,506,608,700,807,902,1008] [9,102,203,306,409,502,600,705,806,907,1006] ... ~~~~~~~~~~~~~~~~~~~~ This example used `mapM` at the type ~~~~~~~~~~~~~~~~~~~~{.haskell} mapM_ :: (Int -> Gen Int) -> [Int] -> Gen [Int] ~~~~~~~~~~~~~~~~~~~~ `fmap` ------ `fmap` is a generalization of the `map` function. First of all, it is perfectly fine to use `fmap` instead of `map` for lists: ~~~~~~~~~~~~~~~~~~~~ *Main> map (*2) [1..10] [2,4,6,8,10,12,14,16,18,20] *Main> fmap (*2) [1..10] [2,4,6,8,10,12,14,16,18,20] ~~~~~~~~~~~~~~~~~~~~ The type of `fmap` says that it works for any type constructor `f` in the `Functor` class: ~~~~~~~~~~~~~~~~~~~~{.haskell} fmap :: Functor f => (a -> b) -> f a -> f b ~~~~~~~~~~~~~~~~~~~~ In the above example, we used it at the type ~~~~~~~~~~~~~~~~~~~~{.haskell} fmap :: (Integer -> Integer) -> [] Integer -> [] Integer ~~~~~~~~~~~~~~~~~~~~ (Note that `[] Integer` means the same as `[Integer]`.) Just like for `mapM`, the real benefit of `fmap` comes when we see that it can be used for many other types. For example, it can be used to update a value of type `Maybe`: ~~~~~~~~~~~~~~~~~~~~ *Main> fmap (*2) (Just 3) Just 6 ~~~~~~~~~~~~~~~~~~~~ Similarly, it can be used to update the value of monadic instructions: \begin{code} -- Read the first 50 characters of Demo.lhs readFirst50 :: IO String readFirst50 = fmap (take 50) $ readFile "Demo.lhs" \end{code} ~~~~~~~~~~~~~~~~~~~~ *Main> readFirst50 "% Demo\n\n\n\n