# Types, containers, and advanced functions

## Important “base” types

We already know basic data types (from base package) such as Data.Char, Bool, or Data.Int and structures like Data.List and Data.Tuple pretty well. But of course, there are more widely used types and we are going to know some more now.

### Maybe

In most programming languages, there is a notion of null or nil or even None value. Such a value is usable, but it leads often to undesired crashes of “Null pointer exception”. As Haskell is type-safe, it does not allow such rogue surprises to happen, but instead deals with a possible “null” situation in a managed way.

If we were to design such a solution, we may use ADTs like that:

data IntOrNull = I Int | NullInt
data StringOrNull = S String | NullString
data ValueOrNull a = Value a | Null

myDiv     :: Int -> Int -> ValueOrNull Int
myDiv x 0 = Null
myDiv x y = Value (x div y)

divString     :: Int -> Int -> String
divString x y = case (myDiv x y) of
Null      -> "Division by zero is not allowed!"
Value res -> "Result: " ++ show res


In Haskell, we have a pretty structure called Maybe which does exactly that for us and there are some functions helping with common usage. It is a very important structure and you will be dealing with it very often. You can find more about in the documentation of Data.Maybe.

It is defined as:

data Maybe a = Nothing | Just a

Prelude Data.Maybe> :type Just 10
Just 10 :: Num a => Maybe a
Prelude Data.Maybe> :type Nothing
Nothing :: Maybe a
Prelude Data.Maybe> fromJust (Just 10)
10
Prelude Data.Maybe> fromJust Nothing
*** Exception: Maybe.fromJust: Nothing
Prelude Data.Maybe> fromMaybe "default" Nothing
"default"
Prelude Data.Maybe> fromMaybe "default" (Just "something")
"something"
Prelude Data.Maybe> catMaybes [Just 6, Just 7, Nothing, Just 8, Nothing, Just 9]
[6,7,8,9]


Is Maybe a good container for the following case? What if we need to propage details about the error in the communication (unknown recipient, timeout, bad metadata, etc.)?

-- Communicator interface
data Message = Message { msgSender    :: String
, msgRecipient :: String
, msgBody      :: String
}

sendAndReceive :: Communicator -> Message -> Maybe Message
sendAndReceive comm msg = sendSync comm msg  -- some library "magic", various errors

printReceivedMessage :: Maybe Message -> String
printReceivedMessage Nothing    = "Unknown error occured during communication."
printReceivedMessage (Just msg) = msgSender msg ++ ": " ++ msgBody msg



### Either

Maybe is also used to signal two types of results: an error (Nothing) and a success (Just value). However, it does not tell what is the error in case of Nothing. There is a standard type for such use cases, and it is called Either:

data Either a b = Left a | Right b


The Left variant holds an error value (such as a message) and the Right variant holds the success result value. There are again several utility functions available (see Data.Either):

Prelude Data.Either> :type Left 7
Left 7 :: Num a => Either a b
Prelude Data.Either> :type Right "Message"
Right "Message" :: Either a [Char]
Prelude Data.Either> lefts [Left 7, Right "Msg1", Left 8, Right "Msg2"]
[7,8]
Prelude Data.Either> rights [Left 7, Right "Msg1", Left 8, Right "Msg2"]
["Msg1","Msg2"]
Prelude Data.Either> partitionEithers [Left 7, Right "Msg1", Left 8, Right "Msg2"]
([7,8],["Msg1","Msg2"])

-- Communicator interface
data Message = Message { msgSender    :: String
, msgRecipient :: String
, msgBody      :: String
}

data CommError = Timeout
| Disconnected
| UnkownRecipient
| GeneralError String
deriving Show

sendAndReceive :: Communicator -> Message -> Either CommError Message
sendAndReceive comm msg = sendSync comm msg  -- some library "magic"

printReceivedMessage :: Either CommError Message -> String
printReceivedMessage (Left  err) = "Error occured during communication: " ++ show err
printReceivedMessage (Right msg) = msgSender msg ++ ": " ++ msgBody msg



### Unit

Although we said there is no null, nil or None, we still have one dummy value/type called “Unit” and it is designated as an empty tuple ().

Prelude> :info ()
data () = ()    -- Defined in ‘GHC.Tuple’
Prelude> :type ()
() :: ()


It is semantically more similar to void from other languages and you can use it wherever you don’t want to use an actual type. For example, using Either to simulate Maybe, you could do Either a (). For more about unit type, read wikipedia.

## Other containers

As in other programming languages or programming theory, there are various types of containers - data types/structures, whose instances are collections of other objects. As for collections with an arbitrary number of elements, we talked about lists, which are simple to use and have a nice syntactic-sugar notation in Haskell. However, there are also other versatile types of containers available in the package containers and others, such as array, vector, and more (use Hoogle or Hackage).

### Sequence

The Seq a is a type from Data.Sequence that represents a finite sequence of values of type a. Sequences are very similar to lists, working with sequences is not so different, but some operations are more efficient - constant-time access to both the front and the rear and Logarithmic-time concatenation, splitting, and access to any element. But in other cases, it can be slower than lists because of overhead created for making operations efficient. The size of a Seq must not exceed maxBound::Int!

Prelude> import Data.Sequence
Prelude Data.Sequence> seq1 = 1 <| 2 <| 15 <| 7 <| empty
Prelude Data.Sequence> seq1
fromList [1,2,15,7]
Prelude Data.Sequence> :type seq1
seq1 :: Num a => Seq a
Prelude Data.Sequence> 3 <| seq1
fromList [3,1,2,15,7]
Prelude Data.Sequence> seq1 |> 3
fromList [1,2,15,7,3]
Prelude Data.Sequence> seq1 >< (fromList [2, 3, 4])
fromList [1,2,15,7,2,3,4]
Prelude Data.Sequence> sort seq1
fromList [1,2,7,15]


### Set

The Set e type represents a set of elements of type e. Most operations require that e be an instance of the Ord class. A Set is strict in its elements. If you know what is set in math and/or programming, you can be very powerful with them.

Prelude> import Data.Set

### Infix and operator-like data constructors

Data constructors can be treated just as functions. You can pass them to a function as a parameter, return them from a function as a result and also use them in infix:

Prelude> data MyTuple a b = MyTupleConstr a b deriving Show
Prelude> :type MyTupleConstr
MyTupleConstr :: a -> b -> MyTuple a b
Prelude> MyTupleConstr 5 "Hi"
MyTupleConstr 5 "Hi"
Prelude> 5 MyTupleConstr "Hi"
MyTupleConstr 5 "Hi"


As we said, for constructors you may create operator starting with a colon (and optionally specify also infix, infixl, or infixr).

Prelude> data MyTuple2 a b = a :@ b deriving Show
Prelude> :type (:@)
(:@) :: a -> b -> MyTuple2 a b
Prelude> 5 :@ "Hi"
5 :@ "Hi"
Prelude> (:@) 5 "Hi"
5 :@ "Hi"


You can try that using operator which doesn’t start with a colon is not possible. But you can always make a synonym and then your code more readable:

Prelude> data MyTuple3 a b = a @@ b deriving Show

<interactive>:15:17: error: Not a data constructor a'
Prelude> (@@) = (:@)
Prelude> :type (@@)
(@@) :: a -> b -> MyTuple2 a b
Prelude> 5 @@ "Hi"
5 :@ "Hi"


Another fine feature is, that operators :@ and @@ can be specified with different associativity and precedence!

GHC has an extension of Generalized Algebraic Data Types (GADTs), where the idea of unifying function and data types is pushed even further. However, as they are a more advanced topic, we leave them to your interest.

### Anonymous functions

An anonymous function is a function without a name. It is a Lambda abstraction and might look like this: \x -> x + 1. Sometimes, it is more convenient to use a lambda expression rather than giving a function a name. You should use anonymous functions only for very simple functions because it decreases readability of the code.

myFunc1 x y z = x * y + z               -- <= just syntactic sugar!
myFunc2 = (\x y z -> x * y + z)         -- <= still syntactic sugar!
myFunc3 = (\x -> \y -> \z -> x * y + z) -- <= desugarized function
mapFunc1 = map myFunc1
mapAFunc1 = map (\x y z -> x * y + z)


Anonymous functions are one of the corner-stones of functional programming and you will meet them in all languages that claim to be at least a little bit “functional”.

## Higher-order functions

Higher order function is a function that takes a function as an argument and/or returns a function as a result. We already saw some of them: (.), curry, uncurry, map, etc. Higher-order functions are a very important concept in functional programming. Learning them and using them properly leads to readable, declarative, concise and safe code. They are used especially in manipulating lists, where they are preferred over traditional recursion today.

### Map and filter

Two widely used functions well-known in the most of functional (but others as well) programming languages are map and filter. In the Prelude module, they are defined for lists, but they work in the same way for other data structures (Data.Sequence, Data.Set, etc., see the previous lecture). When you need to transform a list by applying a function to its every element, then you can use map. If you have a list and you need to make a sublist based on some property of its elements, use filter. The best for understanding is to look at its possible implementation:

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

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter _ []     = []
myFilter p (x:xs)
| p x       = x : myFilter p xs
| otherwise = myFilter p xs


That’s it. Let us have some examples:

Prelude> :type map
map :: (a -> b) -> [a] -> [b]
Prelude> map show [1..5]
["1","2","3","4","5"]
Prelude> map (5*) [1..5]
[5,10,15,20,25]
Prelude> map (length . show . abs) [135, (-15), 0, 153151]
[3,2,1,6]
Prelude> :type filter
filter :: (a -> Bool) -> [a] -> [a]
Prelude> filter (\x -> x mod 7 == 0) [1..50]
[7,14,21,28,35,42,49]


Soon we will get into a generalized function called fmap while discussing the term functor.

### Folds and scans

Maybe you’ve heard about Map/Reduce… We know map, but there is no reduce! Actually, there is, but it is called fold (it is practically a synonym in functional programming). Folds are higher-order functions that process a data structure in some order and build a return value. It (as everything in Haskell) has foundations in math - concretely in Catamorphism of the Category Theory.

So map takes a list a produces another list of the same length, while fold takes a list and produces a single value.

To get into folds in practice, let’s try to implement sum and product functions (if you want to practice on your own, try it with and and or).

mySum :: Num a => [a] -> a
mySum []     = 0
mySum (x:xs) = x + mySum xs

myProduct :: Num a => [a] -> a
myProduct []     = 1
myProduct (x:xs) = x * myProduct xs


Obviously, there are some similarities:

1. initial value for an empty list (0 for sum and 1 in the case of product),
2. use a function and apply it to an element and recursive call to the rest of the list.

Let’s make a generalized higher-order function that also takes an initial value and a function for processing:

process :: (a -> a -> a) -> a -> [a] -> a
process _ initValue    []  = initValue
process f initValue (x:xs) = f x (process f initValue xs)

mySum = process (+) 0
myProduct = process (*) 1


But here we are getting into a problem. Both (+) and (*) use operands and result of the same type - if we want to convert a number to string and join it in one go with process, it is not possible!

*Main> process (\x str -> show x ++ str) "" [1,2,3,4]

<interactive>:18:39: error:
• No instance for (Num [Char]) arising from the literal ‘1’
• In the expression: 1
In the third argument of ‘process’, namely ‘[1, 2, 3, 4]’
In the expression:
process (\ x str -> show x ++ str) "" [1, 2, 3, 4]


The type of the initial value must be the same as the type which is returned by given function. Now we get this:

process :: (a -> b -> b) -> b -> [a] -> b
process _ initValue    []  = initValue
process f initValue (x:xs) = f x (process f initValue xs)

mySum = process (+) 0
myProduct = process (*) 1

myToStrJoin :: (Show a) => [a] -> String
myToStrJoin = process (\x str -> show x ++ str) ""


Now problem is that both (+) and (*) are commutative, but (\x str -> show x ++ str) is not, even type of x and str can be different. What if we need to apply the function in a different order? Now we have to create two variants.

processr :: (a -> b -> b) -> b -> [a] -> b   -- "accumulates" in the RIGHT operand
processr _ initValue    []  = initValue
processr f initValue (x:xs) = f x (processr f initValue xs)

processl :: (b -> a -> b) -> b -> [a] -> b   -- "accumulates" in the LEFT operand
processl _ initValue    []  = initValue
processl f initValue (x:xs) = f (processl f initValue xs) x

mySum = processl (+) 0
myProduct = processl (*) 1

myToStrJoinR :: (Show a) => [a] -> String
myToStrJoinR = processr (\x str -> show x ++ str) ""
myToStrJoinL :: (Show a) => [a] -> String
myToStrJoinL = processl (\str x -> show x ++ str) ""


This is something so generally useful, that it is prepared for you and not just for lists but for every instance of typeclass Foldable - two basic folds foldl/foldr and related scanl/scanr, which capture intermediate values in a list:

Prelude> :type foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
Prelude> :type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
Prelude> foldl (-) 0 [1..10]
-55
Prelude> ((((((((((0-1)-2)-3)-4)-5)-6)-7)-8)-9)-10)
-55
Prelude> scanl (-) 0 [1..10]
[0,-1,-3,-6,-10,-15,-21,-28,-36,-45,-55]
Prelude> foldr (-) 0 [1..10]
-5
Prelude> (1-(2-(3-(4-(5-(6-(7-(8-(9-(10-0))))))))))
-5
Prelude> scanr (-) 0 [1..10]
[-5,6,-4,7,-3,8,-2,9,-1,10,0]


There are some special variants:

Prelude> foldr1 (+) [1..10]
Prelude> foldl1 (*) [1..10]
Prelude> foldr1 (+) []
Prelude> foldl1 (*) []

Prelude> foldl' (*) 0 [1..10]  -- strict evaluation before reduction
Prelude> foldl'1 (*) [1..10]

Prelude> minimum [1,2,63,12,5,201,2]
Prelude> maximum [1,2,63,12,5,201,2]


As an exercise, try to implement foldl by using foldr (spoiler: solution).

## FP in other languages

Functional programming concepts that you learn in a pure functional language may be more or less applicable in other languages, as well, according to the concepts supported and how well they are implemented. Also, some languages provide serious functional constructs, but they are quite cumbersome syntactically, which repels their common usage (yes, we point to you, JavaScript ;-)

### C/C++

C++ is a general purpose object-oriented programming language based on C, which is an imperative procedural language. In both, it is possible to create functions (and procedures). There is no control if a function is pure or not (i.e. making side effects). And in C/C++ you need to deal with mutability, pointers and working with memory on low level (de/allocation). Typing is strict and you can make higher-order functions with “function pointer” types.

int calculate(int(*binOperation)(const int, const int), const int operandA, const int operandB){
return binOperation(operandA, operandB);
}


If you are a normal person and not a bighead, you will most probably use typedef to name the type of such functions so the code is more readable and understandable. In newer versions of C++, there are also anonymous functions, combinators (for_each, transform, filter, …), functors. Then you can of course use simpler functional concepts such as closures or recursion.

typedef int(*binOperation)(const int, const int);  /* I am not a bighead */

int calculate(binOperation bo, const int operandA, const int operandB){
return bo(operandA, operandB);
}
`