# Functional FreeST

## Table of contents

## Primitive types and tuples

FreeST has the following primitive types:

`()`

, the unit type, with a single value`()`

`Bool`

, can be`True`

or`False`

`Int`

, for integer numbers`Float`

, for floating-pointer numbers`Char`

, for single characters`String`

, for sequences of characters

From primitive types, other types can be built. **Tuple** is the first type constructor we study. A tuple can have two elements `(Int, String)`

or as many you want `(Bool, Int, (Int, Char), String)`

.

## Functions, functions everywhere

In FreeST, much like in every other functional language, everything is a function (or a composition of functions). To sum numbers is to apply function `(+)`

to two numbers. To sum 1 and 2 is to write `(+) 1 2`

. However, because function `(+)`

is considered an **operator**, we can also write `1 + 2`

.

All functions must have a **signature** (a type), that describes both its parameters and return value. A function’s signature has the syntax `<Parameter#1> -> ... -> <Parameter#n> -> <Return>`

. For example, the type of `(+)`

is `Int -> Int -> Int`

, a function that takes two integers and returns an integer.

To define functions, simply state the function’s name and signature and then its body. Let’s create our own `plus`

function based on the `(+)`

operator:

```
plus : Int -> Int -> Int -- signature
plus x y = x + y -- body
```

The function’s body consists of the name of the function, the variables described in the signature followed by the logic itself. Note that there is **no return** statement, this is because the entire expression is the return itself.

For functions that share signatures, we can define them together separating their names with a comma. For a function `minus`

based on the `(-)`

operator, we have the exact same signature as `plus`

, so we can write:

```
plus, minus : Int -> Int -> Int
plus x y = x + y
minus x y = x - y
```

Functions in FreeST can have their signature and body separated, however we incentivize to **not** write code like this:

```
plus : Int -> Int -> Int
minus : Int -> Int -> Int
minus x y = x - y
plus x y = x + y
```

At first glance, functions can’t have more than one return type. However, functions might need to return two or more values. How do we do this? We take advantage of **tuples** to encapsulate multiple return values inside a single one. To exemplify, Function `makeTwins`

takes an integer and returns it and its twin (a copy!) within a tuple.

```
makeTwins : Int -> (Int, Int)
makeTwins x = (x, x)
```

Not all functions can (or should) be described using a single expression. To prevent this from becoming a limitation, we use `let`

expressions which lets (pun intended) us store values in variables for later use.

```
betterDivision : Int -> Int -> (Int, Int)
betterDivision n div =
let quotient = n / div in
let rest = mod n div in
(quotient, rest)
```

Function `betterDivision`

simply divides a number by another and returns both the quotient and the rest. We could write a single expression `(n / div, mod n div)`

, but this way it is made clear what is what. It might not be the best case to show this concept but it gives you an idea.

Furthermore, it’s through `let`

expressions that we can ‘open’ pairs to access their elements (instead of relying in `fst`

and `snd`

).

```
main : ()
main =
let (quotient, rest) = betterDivision 3 2 in
()
```

For conditional branching, `if`

statements are provided. Note that both the `then`

and `else`

branches must be present, so you can’t write just the `then`

branch.

```
-- Returns the absolute value of an integer
abs' : Int -> Int
abs' x =
if x > 0
then x
else -x
```

## Recursion, recursion, recursion, …

We want to write a function `sumFirstN`

that calculates the sum of the first `n`

natural numbers. Functions such as `sumFirstN`

which require some form of *iteration* are translated to using *loops*. FreeST does not have any type of loop syntax, so how can we write function `sumFirstN`

? The answer is **recursion**.

Trivially, the recursive definition of `sumFirstN`

is: `sumFirstN 0 == 0`

and `sumFirstN n == n + sumFirstN (n-1)`

. In FreeST it translates to:

```
sumFirstN : Int -> Int
sumFirstN n =
if n <= 0
then 0
else n + sumFirstN (n-1)
```

If you need to propagate parameters forward while in recursion, you can do it by changing the function’s signature to have them. An example is a variation of the `sumFirstN`

function that accumulates the sum forward and returns it in the end (when `n`

is 0):

```
sumFirstN' : Int -> Int -> Int
sumFirstN' n curr =
if curr == n
then curr
else curr + sumFirstN' n (curr+1)
```

However, every time we can, we prefer to write `sumFirstN`

instead of `sumFirstN'`

because of simplicity and readability.

## User-defined types

You’re a novice programmer into this fictitious new project and you cross upon this function:

```
f : (Int -> Int) -> Int -> (Int, Int)
f fun x = (x, fun x)
```

What is this? What are its parameters? What is the purpose of function `f`

? Maybe it helps to know that a proper name for this function is `calcFunPoint`

, but it perhaps is not enough. The biggest problem continues to be the **confusing signature**.

Preventing confusing signatures can be done if we create higher-level types that stand in for those we use, but that bare a clearer meaning. A better signature for `calcFunY`

looks like:

```
calcFunY : Function -> Int -> Point
calcFunY fun x = (x, fun x)
```

Using these *abbreviations* (`Function`

and `Point`

) is done by creating two new types:

```
type Function = Int -> Int
type Point = (Int, Int)
```

User-defined types can be used in any place a normal type can, so you can write a type that uses another of your types:

```
type Circle = (Point, Radius)
```

Source code becomes more readable and provides more context to functions when we create and use these types.

## User-defined data types

User-defined types do a lot to improve readability and code organization, but it sometimes is not enough. Remember type `Circle`

:

```
type Radius = Int
type Circle = (Point, Radius)
```

We want to add other shapes such as `Rectangle`

and `Triangle`

. With just types we write:

```
type Rectangle = (Point, Point)
type Triangle = (Point, Point, Point)
```

For now there are no issues. Next we want to write a function `calcArea`

that takes a shape and calculates its area accordingly. What is the signature of such a function? It either receives a `Circle`

, a `Rectangle`

or a `Triangle`

, so it in fact has to be split among three different functions. Good programming practices teach us that it is best to use a super type from which all shapes derive from. We create a new *data type* `Shape`

where all different shapes are represented by different constructors each with their set of parameters.

```
data Shape = Circle Point Radius
| Rectangle Point Point
| Triangle Point Point Point
```

A `calcArea`

function then takes advantage of the `Shape`

data type and a `case`

expression to calculate each case separately.

```
calcArea : Shape -> Int
calcArea shape =
case shape of {
Circle p r -> ...
Rectangle p1 p2 -> ...
Triangle p1 p2 p3 -> ...
}
```

Data structures can also be recursive (in the same way as types). A binary tree of integers is defined as:

```
data IntBinaryTree = Leaf | Node Int IntBinaryTree IntBinaryTree
```