# Through thorns to Haskell. 1/2

- Transfer
- Tutorial

The first part of a short and hard introduction to Haskell. The second part can be found here

tl; dr : A very short and concise introduction to Haskell.

- Introduction
- Essential minimum from Haskell
- Difficult part

**UPD**If you liked the tutorial, drop a few lines to the author of the original article . The person will be pleased;)

I sincerely believe that every developer should learn Haskell. I don't think everyone should be a super-Haskell-ninja. People just need to be aware of the opportunities that Haskell offers. Learning Haskell expands your consciousness.

Mainstream languages are very similar

- variables
- cycles
- pointers (even if most languages try to hide this fact, it still remains a fact)
- structures, objects, and classes (in most languages)

Haskell is very different from them. This language uses a bunch of concepts that I have not heard about before. Many of these concepts will help you become a better programmer.

But learning Haskell can be tricky. At least it was difficult for me. And in this article I will try to show what I lacked in the process of studying.

This article will be difficult to master. This was done on purpose. There are no easy ways to learn Haskell. This road is difficult and tricky. But I think that is good. Because it is the complexity of Haskell that makes it interesting.

The usual way to learn Haskell is to read two books.

First, “Learn You a Haskell” , and then “Real World Haskell” .

I agree that this is the right approach to learning. But in order to understand what Haskell is all about, you have to read these books very carefully.

On the other hand, this article is a very brief and concise introduction to all the basic aspects of Haskell. I also added some nuances that were missing when I studied Haskell.

The article consists of five parts:

- Introduction: A short example to show that Haskell can be fearless.
- The very basics of Haskell: Haskell syntax and some basic structures.
- The hard part:
- Functional style; Example from the transition from imperative to functional style
- Types; types and standard binary tree example
- Endless structures; work with an endless binary tree!

- Damn hard part:
- We deal with IO; Minimal example
- Analysis of a trick with IO; unobvious trifle that prevented me from understandingIO
- Monads unrealistically powerful abstraction tool

- Application:
- A few more words about endless trees; mathematically oriented discussion of infinite trees

Note: Each time you see a separator with a file name and extension`.lhs`

,

you can download it.

If you save the file as`filename.lhs`

, you can run it with

runhaskell filename.lhs.

Some examples may not work, but most should.

Below you should see a link to the file

01_basic / 10_Introduction /

**00_hello_world.lhs**

## Introduction

### Installation

- Haskell Platform is the standard way to install Haskell.

Utilities:

`ghc`

: Compiler similar to gcc for`C`

.`ghci`

: Haskell Interactive Shell (REPL)`runhaskell`

: Run the program without compiling it. Convenient, but very slow compared to compiled programs.

### No panic

Many books and articles begin acquaintance with Haskell with some esoteric formulas (quick sort, Fibonacci, etc.). I will act differently. I will not immediately show Haskell's superpower. I will concentrate on those things in which Haskell is similar to other programming languages. So, let's start with the familiar “Hello World”.

`main = putStrLn "Hello World!"`

To run it, save this code as

`hello.hs`

and execute:```
~ runhaskell ./hello.hs
Hello World!
```

You can download the source from the link located under the “Introduction”.

Save the file

`00_hello_world.lhs`

and execute:```
~ runhaskell 00_hello_world.lhs
Hello World!
```

01_basic / 10_Introduction /

**00_hello_world.lhs**

01_basic / 10_Introduction /

**10_hello_you.lhs**

And now we

**’ll**write a program that asks for your name and says “Hello, name!”:

```
main = do
print "Как вас зовут?"
name <- getLine
print ("Привет " ++ name ++ "!")
```

To begin with, compare our example with other imperative languages:

```
# Python
print "Как вас зовут?"
name = raw_input()
print "Привет %s!" % name
```

```
# Ruby
puts "Как вас зовут?"
name = gets.chomp
puts "Привет #{name}!"
```

```
// In C
#include
```
int main (int argc, char **argv) {
char name[666]; // <- Демоническая цифирь!
// Что будет, если мое имя длиннее 665 символов?
printf("Как вас зовут?\n");
scanf("%s", name);
printf("Привет %s!\n", name);
return 0;
}

The structure of the programs is very similar, but there are slight syntactic differences. The main part of the tutorial will be devoted to precisely these differences.

In Haskell, each function and object has its own type.

Function Type

`main`

- `IO ()`

. This means that when executed, it

`main`

creates side effects. But do not forget that Haskell can look like a normal imperative language.

01_basic / 10_Introduction /

**10_hello_you.lhs**

01_basic / 10_Introduction /

**20_very_basic.lhs**

### The most basic Haskell

Before we continue, I would like to warn you about some of the special features of Haskell.

*Functionality*

Haskell is a functional language.

If you started with imperative languages, you will have to learn many new things.

Fortunately, many of these concepts will help you program better even in imperative languages.

*Advanced Static Typing*

Instead of standing in your way as in

`C`

, `C++`

or `Java`

, a type system will help you. *Cleanliness*

Generally speaking, your functions will not change anything in the outside world.

On the one hand, this means that functions cannot change the value of a variable, cannot receive data from the user, cannot write on the screen, and cannot launch rockets.

On the other hand, we get easy parallelization of our programs.

Haskell draws a clear line between pure functions and those that produce side effects.

With this approach, it becomes much easier to analyze the properties of your program.

In functionally clean parts of the program, many errors will be excluded at the compilation stage.

Moreover, functionally pure functions follow the basic Haskell law:

A function call with the same parameters always gives the same result.

*Laziness*

Default laziness is a very unusual thing in programming languages.

By default, Haskell only evaluates a value when it is really needed.

As a result, we are able to very easily work with infinite data structures.

The last warning will concern how it is worth reading the code on Haskell.

For me, this is like reading scientific articles.

Some parts may be simple and clear, but if you see the formula, concentrate and read more slowly.

When learning Haskell, it

*really*doesn’t matter if you don’t fully understand some of the syntax features.

If you meet

`>>=`

, `<$>`

,`<-`

or other scary characters, just ignore them and try to understand the general idea of the code.#### Function Definition

You can define functions as follows:

On

`C`

:```
int f(int x, int y) {
return x*x + y*y;
}
```

In Javascript:

```
function f(x,y) {
return x*x + y*y;
}
```

In Python:

```
def f(x,y):
return x*x + y*y
```

On Ruby:

```
def f(x,y)
x*x + y*y
end
```

On Scheme:

```
(define (f x y)
(+ (* x x) (* y y)))
```

And finally, Haskell:

```
f x y = x*x + y*y
```

Very clear. No brackets, no-

`def`

s. Remember that Haskell makes heavy use of functions and types.

And so they are very easy to identify.

The language syntax was thought out to make definitions as simple as possible.

#### Example of creating a new type

Usually when writing programs, you indicate the type of function.

But this is optional.

The compiler is smart enough to do this for you.

Let's play a little.

```
-- Мы определям тип используя ::
f :: Int -> Int -> Int
f x y = x*x + y*y
main = print (f 2 3)
```

```
~ runhaskell 20_very_basic.lhs
13
```

01_basic / 10_Introduction /

**20_very_basic.lhs**

01_basic / 10_Introduction /

**21_very_basic.lhs**

Now try

```
f :: Int -> Int -> Int
f x y = x*x + y*y
main = print (f 2.3 4.2)
```

You will get the error:

```
21_very_basic.lhs:6:23:
No instance for (Fractional Int)
arising from the literal `4.2'
Possible fix: add an instance declaration for (Fractional Int)
In the second argument of `f', namely `4.2'
In the first argument of `print', namely `(f 2.3 4.2)'
In the expression: print (f 2.3 4.2)
```

The problem is that

`4.2`

this is not Int. 01_basic / 10_Introduction /

**21_very_basic.lhs**

01_basic / 10_Introduction /

**22_very_basic.lhs**

One solution would be to not explicitly indicate the type of function

`f`

. Then Haskell will deduce for us the most general suitable type:

```
f x y = x*x + y*y
main = print (f 2.3 4.2)
```

Earned!

Great, we don’t need to create a new function for each data type.

For example, in

`C`

, you would need to create a function for `int`

, for `float`

, for `long`

, for `double`

, etc. But what type should we indicate?

To understand what type Haskell has deduced for us, simply run ghci:

```
% ghci
GHCi, version 7.0.4: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> let f x y = x*x + y*y
Prelude> :type f
f :: Num a => a -> a -> a
```

Hmm ... what kind of weird type is this?

```
Num a => a -> a -> a
```

First, pay attention to the right side

`a -> a -> a`

. To understand it, let's look at a few examples:

Specified type | Value |

`Int` | a type `Int` |

`Int -> Int` | function that takes in `Int` and returns`Int` |

`Float -> Int` | function that takes in `Float` and returns`Int` |

`a -> Int` | type of function that takes any type as input and returns `Int` |

`a -> a` | type of function that takes a type as input `a` and returns a type result`a` |

`a -> a -> a` | type of function that takes two type arguments `a` and returns a type result`a` |

In a type

`a -> a -> a`

, a letter `a`

is *a type variable*.

This means that

`f`

is a function of two arguments, and both arguments, as well as the result, are of the same type. A type variable

`a`

can take on various types of values. For example

`Int`

, `Integer`

, `Float`

... So rather than hard-code type, both in

`C`

and separately define functions for `int`

, `long`

, `float`

, `double`

, and so on ... We just create a function in a dynamically typed language.

Generally speaking, it

`a`

can be of any type. `String`

, `Int`

More complex type, for example `Trees`

, the type of the other functions, etc.But in our example, the type has a prefix

`Num a => `

. `Num`

this is *a type class*.

A type class can be represented as many types.

In

`Num`

includes only those types that behave like numbers. More strictly,

`Num`

it is a class containing types that implement a given set of functions, in particular `(+)`

and `(*)`

. Type classes are a very powerful element of the language.

With their help, we can do amazing things.

But we will talk about this a little later.

So, a record

`Num a => a -> a -> a`

means: Let

`a`

it be a type belonging to the type class `Num`

. This is a function that takes in input

`a`

and returns ( `a -> a`

). Hmm, it's weird.

In fact, in Haskell, no function accepts two arguments as input.

Instead, all functions have only one argument.

But note that a function of two arguments can be represented as a function that takes the first argument and returns a function that takes the second argument as a parameter.

.

That is

`f 3 4`

equivalent `(f 3) 4`

. Please note that

`f 3`

this is also a function:```
f :: Num a :: a -> a -> a
g :: Num a :: a -> a
g = f 3
g y ⇔ 3*3 + y*y
```

You can also use another entry to create the function.

Lambda expressions allow you to create functions without naming them.

They are also called anonymous functions.

We can write:

```
g = \y -> 3*3 + y*y
```

A character is

`\`

used because it is similar to a character `λ`

, but at the same time it is an ASCII character. If functional programming is new to you, at this point your brains begin to boil.

It's time to write a real application.

01_basic / 10_Introduction /

**22_very_basic.lhs**

01_basic / 10_Introduction /

**23_very_basic.lhs**

But before we begin, we need to check that the type system works as it should:

```
f :: Num a => a -> a -> a
f x y = x*x + y*y
main = print (f 3 2.4)
```

This code works because it

`3`

can represent both a Fractional (fractional) number of type Float and an integer of type Integer. Since it

`2.4`

is of type Fractional, it `3`

also appears as a Fractional number. 01_basic / 10_Introduction /

**23_very_basic.lhs**

01_basic / 10_Introduction /

**24_very_basic.lhs**

If we write other types in the function, it will stop working:

```
f :: Num a => a -> a -> a
f x y = x*x + y*y
x :: Int
x = 3
y :: Float
y = 2.4
main = print (f x y) -- не будет работать, поскольку тип x ≠ типу y
```

The compiler signals an error.

Two parameters must be of the same type.

If you think this is a bad idea and the compiler should convert the types for you, you really should watch a great and funny video:

WAT

01_basic / 10_Introduction /

**24_very_basic.lhs**

## Haskell minimum required

I advise you to skim this section quickly.

Think of it as reference material.

Haskell is a very multifaceted language.

Therefore, some things in this section will be skipped.

If necessary, come back here if some things seem strange or incomprehensible to you.

I will use the symbol

`⇔`

to show the equivalence of two expressions. This is a meta-notation, doesn’t exist in Haskell

`⇔`

. The symbol

`⇒`

will be used to show the result of evaluating an expression.### Expressions

##### Arithmetic

```
3 + 2 * 6 / 3 ⇔ 3 + ((2*6)/3)
```

##### brain teaser

```
True || False ⇒ True
True && False ⇒ False
True == False ⇒ False
True /= False ⇒ True (/=) это оператор для неравенства
```

##### Exponentiation

```
x^n для целочисленного n (Int или Integer)
x**y для любого числа y (например Float)
```

`Integer`

has no size limitations, with the exception of the machine’s RAM:```
4^103
102844034832575377634685573909834406561420991602098741459288064
```

Oh yeah!

And you can use rational numbers!

But for this you need to use the module

`Data.Ratio`

:```
$ ghci
....
Prelude> :m Data.Ratio
Data.Ratio> (11 % 15) * (5 % 3)
11 % 9
```

##### Lists

```
[] ⇔ пустой список
[1,2,3] ⇔ Список целых чисел
["foo","bar","baz"] ⇔ Список строк (String)
1:[2,3] ⇔ [1,2,3], (:) присоединяет один элемент
1:2:[] ⇔ [1,2]
[1,2] ++ [3,4] ⇔ [1,2,3,4], (++) склеивает списки
[1,2,3] ++ ["foo"] ⇔ ОШИБКА String ≠ Integral
[1..4] ⇔ [1,2,3,4]
[1,3..10] ⇔ [1,3,5,7,9]
[2,3,5,7,11..100] ⇔ ОШИБКА! компилятор не настолько умен!
[10,9..1] ⇔ [10,9,8,7,6,5,4,3,2,1]
```

##### Lines

In Haskell, strings are a list of

`Char`

s.```
'a' :: Char
"a" :: [Char]
"" ⇔ []
"ab" ⇔ ['a','b'] ⇔ 'a':"b" ⇔ 'a':['b'] ⇔ 'a':'b':[]
"abc" ⇔ "ab"++"c"
```

Note:

In real-world tasks, you will not use a list of characters to work with text.

In most cases, this is used`Data.Text`

.

If you need to work with a stream of ASCII characters, it is worth using`Data.ByteString`

.

##### Tuples

You can set a pair as follows

`(a,b)`

. Elements of a tuple can have various types.

```
-- Все эти кортежи - валидны
(2,"foo")
(3,'a',[2,3])
((2,"a"),"c",3)
fst (x,y) ⇒ x
snd (x,y) ⇒ y
fst (x,y,z) ⇒ ERROR: fst :: (a,b) -> a
snd (x,y,z) ⇒ ERROR: snd :: (a,b) -> b
```

##### We deal with brackets

To get rid of extra brackets, you can use these functions:

`($)`

and `(.)`

.```
-- По умолчанию:
f g h x ⇔ (((f g) h) x)
-- $ заменяет скобки от $
-- до конца выражения
f g $ h x ⇔ f g (h x) ⇔ (f g) (h x)
f $ g h x ⇔ f (g h x) ⇔ f ((g h) x)
f $ g $ h x ⇔ f (g (h x))
-- (.) композиция функций
(f . g) x ⇔ f (g x)
(f . g . h) x ⇔ f (g (h x))
```

01_basic / 20_Essential_Haskell /

**10a_Functions.lhs**

### Useful things to write functions

A little reminder:

```
x :: Int ⇔ x имеет тип Int
x :: a ⇔ x может быть любого типа
x :: Num a => a ⇔ x может быть любого типа a,
который принадлежит классу типов Num
f :: a -> b ⇔ f это функция принимающая на вход a и возвращающая результат типа b
f :: a -> b -> c ⇔ f это функция, принимающая на вход a и возвращающая (b→c)
f :: (a -> b) -> c ⇔ f это функция, принимающая на вход (a→b) и возвращающая c
```

Declaring a function type before defining it is optional.

Haskell itself will infer the most general type.

But specifying the type of function is a rule of thumb.

*Infix entry*

```
square :: Num a => a -> a
square x = x^2
```

Note what is

`^`

used in infix notation. For each infix operator, there is the possibility of prefix writing.

Just enclose the desired operator in brackets.

```
square' x = (^) x 2
square'' x = (^2) x
```

We can remove the

`x`

expression from the left and right sides! This is called η-reduction.

```
square''' = (^2)
```

Please note that we can use a symbol

`'`

in the function name. For instance:

`square`

⇔`square'`

⇔`square''`

⇔`square '''`

*Tests*

```
absolute :: (Ord a, Num a) => a -> a
absolute x = if x >= 0 then x else -x
```

Note: the construction

`if .. then .. else`

in Haskell is more like the operator `¤?¤:¤`

in C. You cannot omit it `else`

. Another function equivalent:

```
absolute' x
| x >= 0 = x
| otherwise = -x
```

Note: alignmentis importantin Haskell programs.

As in Python, misalignment can break code!

## Difficult part

We proceed to the study of the complex part.

### Functional style

In this section, I will show you a small example of Haskell's amazing code refactoring capabilities.

We will select the problem and solve it in the standard imperative way. Then we will begin to improve this code a little. The end result will be much easier to understand and more elegant.

Here is the condition of the problem that we will solve:

Having a list of integers, you need to calculate the sum of even numbers in the list.

example:`[1,2,3,4,5] ⇒ 2 + 4 ⇒ 6`

In order to show the difference between a functional and an imperative approach, we first write an imperative solution (in Javascript):

```
function evenSum(list) {
var result = 0;
for (var i=0; i< list.length ; i++) {
if (list[i] % 2 ==0) {
result += list[i];
}
}
return result;
}
```

But in Haskell there are no variables and loops.

Without using loops, the same result can be obtained using recursion.

Note:

Recursion in imperative languages has a reputation for being a slow tool. But for most functional languages this is not so. In most cases, Haskell optimizes work with recursive functions very qualitatively.

Here is a version of a recursive function written in

`C`

. For simple, I assume that the list of numbers ends with a null value.```
int evenSum(int *list) {
return accumSum(0,list);
}
int accumSum(int n, int *list) {
int x;
int *xs;
if (*list == 0) { // if the list is empty
return n;
} else {
x = list[0]; // let x be the first element of the list
xs = list+1; // let xs be the list without x
if ( 0 == (x%2) ) { // if x is even
return accumSum(n+x, xs);
} else {
return accumSum(n, xs);
}
}
}
```

Take a close look at this code. Because we will translate it to Haskell.

But first, I will show you three simple but very useful functions that we will use:

```
even :: Integral a => a -> Bool
head :: [a] -> a
tail :: [a] -> [a]
```

`even`

parity check.```
even :: Integral a => a -> Bool
even 3 ⇒ False
even 2 ⇒ True
```

`head`

returns the first element of the list:```
head :: [a] -> a
head [1,2,3] ⇒ 1
head [] ⇒ ERROR
```

`tail`

returns all elements of the list, besides the first:```
tail :: [a] -> [a]
tail [1,2,3] ⇒ [2,3]
tail [3] ⇒ []
tail [] ⇒ ERROR
```

Please note that for any non-empty list

`l`

,`l ⇔ (head l):(tail l)`

02_Hard_Part /

**11_Functions.lhs**

So, the first solution to the problem at Haskell.

The function

`evenSum`

returns the sum of all even numbers in the list:```
-- Версия 1
evenSum :: [Integer] -> Integer
evenSum l = accumSum 0 l
accumSum n l = if l == []
then n
else let x = head l
xs = tail l
in if even x
then accumSum (n+x) xs
else accumSum n xs
```

To test the function, simply run

`ghci`

:```
% ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load 11_Functions.lhs
[1 of 1] Compiling Main ( 11_Functions.lhs, interpreted )
Ok, modules loaded: Main.
*Main> evenSum [1..5]
6
```

The following is an example of how the function works (I'm cheating. In the know. We'll come back to the question of lax computing later):

```
*Main> evenSum [1..5]
accumSum 0 [1,2,3,4,5]
1 is odd
accumSum 0 [2,3,4,5]
2 is even
accumSum (0+2) [3,4,5]
3 is odd
accumSum (0+2) [4,5]
4 is even
accumSum (0+2+4) [5]
5 is odd
accumSum (0+2+4) []
l == []
0+2+4
0+6
6
```

From the point of view of an imperative language, everything looks normal. But there is a lot of room for improvement. For starters, we can make the type more general.

```
evenSum :: Integral a => [a] -> a
```

02_Hard_Part /

**11_Functions.lhs**

02_Hard_Part /

**12_Functions.lhs**

The next step may be to use the nested functions defined with

`where`

or `let`

. Thus, our function

`accumSum`

will not pollute the global namespace.```
-- Версия 2
evenSum :: Integral a => [a] -> a
evenSum l = accumSum 0 l
where accumSum n l =
if l == []
then n
else let x = head l
xs = tail l
in if even x
then accumSum (n+x) xs
else accumSum n xs
```

02_Hard_Part /

**12_Functions.lhs**

02_Hard_Part /

**13_Functions.lhs**

Now we use pattern matching.

```
-- Версия 3
evenSum l = accumSum 0 l
where
accumSum n [] = n
accumSum n (x:xs) =
if even x
then accumSum (n+x) xs
else accumSum n xs
```

What is pattern matching? It is simply using values instead of named parameters. (For the most daring, a detailed description of pattern matching can be studied here )

Instead of this code: You can simply write:

`foo l = if l == [] then ` else

```
foo [] =
```
foo l =

But comparison with the sample can do much more. It can analyze the internal data of a complex structure. We can replace

```
foo l = let x = head l
xs = tail l
in if even x
then foo (n+x) xs
else foo n xs
```

on the

```
foo (x:xs) = if even x
then foo (n+x) xs
else foo n xs
```

A very useful feature.

It makes our code more concise and readable.

02_Hard_Part /

**13_Functions.lhs**

02_Hard_Part /

**14_Functions.lhs**

You can simplify writing functions in Haskell by using η-reduction.

For example, instead of such an entry:

```
f x = (какое-то выражение) x
```

can be used

```
f = какое-то выражение
```

We can use this approach to get rid of

`l`

:```
-- Версия 4
evenSum :: Integral a => [a] -> a
evenSum = accumSum 0
where
accumSum n [] = n
accumSum n (x:xs) =
if even x
then accumSum (n+x) xs
else accumSum n xs
```

02_Hard_Part /

**14_Functions.lhs**

02_Hard_Part /

**15_Functions.lhs**

#### Higher Order Functions

To make our function even more beautiful, we can use the FEP (higher order functions).

You ask what kind of animals?

Higher-order functions are functions that take functions as a parameter.

A couple of examples:

```
filter :: (a -> Bool) -> [a] -> [a]
map :: (a -> b) -> [a] -> [b]
foldl :: (a -> b -> a) -> a -> [b] -> a
```

We will move forward in small steps.

```
-- Версия 5
evenSum l = mysum 0 (filter even l)
where
mysum n [] = n
mysum n (x:xs) = mysum (n+x) xs
```

Where

```
filter even [1..10] ⇔ [2,4,6,8,10]
```

The function

`filter`

accepts a type function ( `a -> Bool`

) and a type list as arguments `[a]`

. It returns a list containing only those elements for which the function returned `true`

. Our next step will be to further simplify the cycle. We use a function

`foldl`

that allows us to accumulate value. The function `foldl`

implements a popular programming technique:```
myfunc list = foo initialValue list
foo accumulated [] = accumulated
foo tmpValue (x:xs) = foo (bar tmpValue x) xs
```

The code above can be replaced by:

```
myfunc list = foldl bar initialValue list
```

If you really want to understand what is happening magic, the

implementation is

`foldl`

given below.```
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
```

```
foldl f z [x1,...xn]
⇔ f (... (f (f z x1) x2) ...) xn
```

But since Haskell is a lazy language, it does not compute the value

`(f z x)`

, but pushes it onto the stack. Therefore, we will use

`foldl'`

instead `foldl`

; `foldl'`

it is a *strict (or energetic)*implementation

`foldl`

. If the difference between lazy and strict functions is not obvious to you, do not worry, just read the code, considering that both functions are the same.

Now our version

`evenSum`

looks like this:```
-- Версия 6
-- foldl' не доступна по умолчанию
-- мы должны импортировать ее из модуля Data.List
import Data.List
evenSum l = foldl' mysum 0 (filter even l)
where mysum acc value = acc + value
```

This code can be simplified even further by using lambda expressions, thus eliminating the temporary identifier

`mysum`

.```
-- Версия 7
-- Правилом хорошего тона является
-- импортировать только необходимые функции
import Data.List (foldl')
evenSum l = foldl' (\x y -> x+y) 0 (filter even l)
```

And of course, we can carry out the following replacement

```
(\x y -> x+y) ⇔ (+)
```

02_Hard_Part /

**15_Functions.lhs**

02_Hard_Part /

**16_Functions.lhs**

As a result

```
-- Версия 8
import Data.List (foldl')
evenSum :: Integral a => [a] -> a
evenSum l = foldl' (+) 0 (filter even l)
```

`foldl'`

not the most intuitive feature. But it is definitely worth dealing with. To do this, we carry out a step-by-step analysis:

```
evenSum [1,2,3,4]
⇒ foldl' (+) 0 (filter even [1,2,3,4])
⇒ foldl' (+) 0 [2,4]
⇒ foldl' (+) (0+2) [4]
⇒ foldl' (+) 2 [4]
⇒ foldl' (+) (2+4) []
⇒ foldl' (+) 6 []
⇒ 6
```

Another useful higher order function is this

`(.)`

. The function

`(.)`

corresponds to the mathematical composition.```
(f . g . h) x ⇔ f ( g (h x))
```

We can use it to further η-reduce our function:

```
-- Версия 9
import Data.List (foldl')
evenSum :: Integral a => [a] -> a
evenSum = (foldl' (+) 0) . (filter even)
```

You can do something else to make the code cleaner:

```
-- Версия 10
import Data.List (foldl')
sum' :: (Num a) => [a] -> a
sum' = foldl' (+) 0
evenSum :: Integral a => [a] -> a
evenSum = sum' . (filter even)
```

We discuss the result.

What did we get by applying higher order functions?

The brevity of the code catches your eye. But the main plus is how much easier it became to understand our program. Let's say we want to slightly change our function. Now we want her to return the sum of the squares of all the even numbers in the list.

```
[1,2,3,4] ▷ [1,4,9,16] ▷ [4,16] ▷ 20
```

Adding this change to version 10 is very simple:

```
squareEvenSum = sum' . (filter even) . (map (^2))
squareEvenSum' = evenSum . (map (^2))
squareEvenSum'' = sum' . (map (^2)) . (filter even)
```

We just need to add another “transform function” (Note that it is

`squareEvenSum''`

more efficient than the other two implementations. The order `(.)`

really matters.).```
map (^2) [1,2,3,4] ⇔ [1,4,9,16]
```

The function

`map`

simply applies the parameter function to all elements of the list. We do not need to change anything

*inside*the function definition.

It has become much more modular.

But among other things, she began to behave more "mathematically."

You can use your function like any other.

You can do composition, map, fold and filter using your new function.

We will leave one version of the refactoring as a task to the reader.

If you think that it is difficult to make the code more abstract, then you are very mistaken. For example, this function can be used not only for lists, but also for any recursive types. If you are interested in how - read this fun article:Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire by Meijer, Fokkinga and Paterson .

In our example, we can see how powerful functional programming can be. Unfortunately, in some cases, purely functional languages are not always the best choice. At the very least, a truly universal functional language has not yet been created.

One of the distinguishing features of Haskell lies in the creation of DSLs (Domain-Oriented Languages).

In fact, Haskell is a great tool, even if you want to write programs in an imperative style. When I studied Haskell, this thought was a revelation to me.

But before we get down to talking about Haskell's superpower, we need to discuss another significant aspect -

*Types*.

### Types

tl; dr :

`type Name = AnotherType`

it's just an alias for the compiler`Name`

and types`AnotherType`

look the same.`data Name = NameConstructor AnotherType`

And in this example, the types are different.`data`

can create recursive structures.`deriving`

it is a powerful witchcraft and can create functions for you.

Haskell is a language with strong static typing.

Why is this so important? Because it

*greatly*reduces the number of errors.

In Haskell, most errors can be detected at the compilation stage. And this happens because type compilation is actively used during compilation.

If you use the wrong parameter in the wrong place, the compiler will easily notice this.

#### Type inference

Static typing is necessary to create fast programs.

But most statically typed languages are weak in generalizing concepts.

One of Haskell’s gracious abilities is type

*inference*.

A simple example. Haskell

Function

`square`

:```
square x = x * x
```

This function can

`square`

(square) any value of type Numeral. You can pass a value type to

`Int`

, `Integer`

, `Float`

, `Fractional`

and even `Complex`

. For instance:```
% ghci
GHCi, version 7.0.4:
...
Prelude> let square x = x*x
Prelude> square 2
4
Prelude> square 2.1
4.41
Prelude> -- загружаем модуль Data.Complex
Prelude> :m Data.Complex
Prelude Data.Complex> square (2 :+ 1)
3.0 :+ 4.0
```

`x :+ y`

this is the notation of a complex number ( *x + iy*).

Now compare the amount of code compared to the C program:

```
int int_square(int x) { return x*x; }
float float_square(float x) {return x*x; }
complex complex_square (complex z) {
complex tmp;
tmp.real = z.real * z.real - z.img * z.img;
tmp.img = 2 * z.img * z.real;
}
complex x,y;
y = complex_square(x);
```

For each type you need to write your own function. You can get around this only using metaprogramming techniques. For example using a preprocessor. C ++ offers a more beautiful solution using templates:

`#include `
#include
using namespace std;
template
T square(T x)
{
return x*x;
}
int main() {
// int
int sqr_of_five = square(5);
cout << sqr_of_five << endl;
// double
cout << (double)square(5.3) << endl;
// complex
cout << square( complex(5,3) )
<< endl;
return 0;
}

The C ++ variant looks much better than C.

But for complex variable functions, it will be difficult to maintain the same syntax. An example can be found in

this article

.

In C ++, you must describe a function that can work with different types.

In Haskell, the situation is the opposite.

The function will be as generalized as possible by default.

Haskell type inference gives a sense of freedom that dynamically typed languages represent.

But unlike dynamically typed languages, most errors are caught even before the program runs.

People talk about Haskell like this:

“If it compiles, then it most likely works correctly”

02_Hard_Part /

**21_Types.lhs**

#### Creating New Types

You can create your own types. For example, type synonyms can be declared.

```
type Name = String
type Color = String
showInfos :: Name -> Color -> String
showInfos name color = "Name: " ++ name
++ ", Color: " ++ color
name :: Name
name = "Robin"
color :: Color
color = "Blue"
main = putStrLn $ showInfos name color
```

But it does not protect you much from mistakes.

Try to interchange the two parameters of the function

`showInfos`

and run the program:```
putStrLn $ showInfos color name
```

It will compile and run. You can use Name, Color, and String as interchangeable entities. For the compiler, they are absolutely identical.

Another way to create your own type is to use a keyword

`data`

.```
data Name = NameConstr String
data Color = ColorConstr String
showInfos :: Name -> Color -> String
showInfos (NameConstr name) (ColorConstr color) =
"Name: " ++ name ++ ", Color: " ++ color
name = NameConstr "Robin"
color = ColorConstr "Blue"
main = putStrLn $ showInfos name color
```

If you

`showInfos`

swap parameters, the compiler will begin to swear. The chance to make a mistake has disappeared. But at the cost of increasing the amount of code. Note that type constructors are functions:

```
NameConstr :: String -> Name
ColorConstr :: String -> Color
```

Usage

`data`

usually looks like this:```
data TypeName = ConstructorName [types]
| ConstructorName2 [types]
| ...
```

For

DataTypeName and DataTypeConstructor usually use the same name.

For instance:

```
data Complex = Num a => Complex a a
```

You can also use the syntax of the entries:

```
data DataTypeName = DataConstructor {
field1 :: [type of field1]
, field2 :: [type of field2]
...
, fieldn :: [type of fieldn] }
```

And a bunch of data access functions will be created automatically. Moreover, when writing new values, you can use an arbitrary order of fields.

Example:

```
data Complex = Num a => Complex { real :: a, img :: a}
c = Complex 1.0 2.0
z = Complex { real = 3, img = 4 }
real c ⇒ 1.0
img z ⇒ 4
```

02_Hard_Part /

**22_Types.lhs**

02_Hard_Part /

**23_Types.lhs**

#### Recursive Types

You have already met with a representative of recursive types - with lists. You can create lists from scratch using a more verbose syntax:

```
data List a = Empty | Cons a (List a)
```

For an easier record, you can use an infix type constructor.

```
infixr 5 :::
data List a = Nil | a ::: (List a)
```

The number after

`infixr`

is the operator's priority. If you want to print (

`Show`

), read ( `Read`

), check for equality ( `Eq`

) and compare ( `Ord`

) the values of your new type, you can tell Haskell to automatically print the necessary functions for this.```
infixr 5 :::
data List a = Nil | a ::: (List a)
deriving (Show,Read,Eq,Ord)
```

When you add

`deriving (Show)`

to the description of your type, Haskell automatically creates a function for you `show`

. Soon we will see how you can write your version of the function `show`

.```
convertList [] = Nil
convertList (x:xs) = x ::: convertList xs
```

```
main = do
print (0 ::: 1 ::: Nil)
print (convertList [0,1])
```

Program Output:

```
0 ::: (1 ::: Nil)
0 ::: (1 ::: Nil)
```

02_Hard_Part /

**23_Types.lhs**

02_Hard_Part /

**30_Trees.lhs**

#### Trees

Here is another standard example: binary trees.

```
import Data.List
data BinTree a = Empty
| Node a (BinTree a) (BinTree a)
deriving (Show)
```

Let's write a function that converts a list into an ordered binary tree.

```
treeFromList :: (Ord a) => [a] -> BinTree a
treeFromList [] = Empty
treeFromList (x:xs) = Node x (treeFromList (filter (
```x) xs))

Enjoy the elegance of this feature.

Translating to Russian language:

- an empty list turns into an empty tree.
- the list
`(x:xs)`

will become a tree in which:- the root will be
`x`

- left subtree will be created in the list,
`xs`

is strictly smaller`x`

and - the right subtree will be created from the list elements
`xs`

strictly large`x`

.

- the root will be

```
main = print $ treeFromList [7,2,4,8]
```

You should get something like:

```
Node 7 (Node 2 Empty (Node 4 Empty Empty)) (Node 8 Empty Empty)
```

This is an informative, but not very beautiful representation of our tree.

02_Hard_Part /

**30_Trees.lhs**

02_Hard_Part /

**31_Trees.lhs**

To have some fun, let's write a code for a more beautiful display of our trees. I enjoyed writing a function that can nicely display any trees. If this part seems difficult to you, you can safely skip it.

We need to make small changes.

We will remove

`deriving (Show)`

from the type declaration `BinTree`

. It will also be useful to make BinTree an instance of type classes ( `Eq`

and `Ord`

). This will give us the opportunity to test trees for equality and compare them.```
data BinTree a = Empty
| Node a (BinTree a) (BinTree a)
deriving (Eq,Ord)
```

Without

`deriving (Show)`

, Haskell will not create a method for us `show`

. But we will write our own version

`show`

. To do this, we must indicate that our newly created type `BinTree a`

is an instance of the type class

`Show`

. In code, it looks like this:

```
instance Show (BinTree a) where
show t = ... -- Тут идет объявление вашей функции
```

Here is my version of displaying a binary tree. It’s not as scary as it looks. I adapted it to display much weirder objects.

```
-- говорим что BinTree будет экземпляром Show
instance (Show a) => Show (BinTree a) where
-- перед корнем будет отображаться '<'
-- и напишем : в начале строки
show t = "< " ++ replace '\n' "\n: " (treeshow "" t)
where
-- treeshow pref Tree
-- отображает дерево и начинает каждую строку с pref
-- Мы не будем отображать пустое дерево
treeshow pref Empty = ""
-- Leaf
treeshow pref (Node x Empty Empty) =
(pshow pref x)
-- Правая ветка пустая
treeshow pref (Node x left Empty) =
(pshow pref x) ++ "\n" ++
(showSon pref "`--" " " left)
-- Левая ветка пустая
treeshow pref (Node x Empty right) =
(pshow pref x) ++ "\n" ++
(showSon pref "`--" " " right)
-- Дерево с непустыми правой и левой ветками
treeshow pref (Node x left right) =
(pshow pref x) ++ "\n" ++
(showSon pref "|--" "| " left) ++ "\n" ++
(showSon pref "`--" " " right)
-- отображение дерева с красивыми префиксами
showSon pref before next t =
pref ++ before ++ treeshow (pref ++ next) t
-- pshow заменяет "\n" на "\n"++pref
pshow pref x = replace '\n' ("\n"++pref) (show x)
-- заменяет символ строкой
replace c new string =
concatMap (change c new) string
where
change c new x
| x == c = new
| otherwise = x:[] -- "x"
```

The method

`treeFromList`

does not change.```
treeFromList :: (Ord a) => [a] -> BinTree a
treeFromList [] = Empty
treeFromList (x:xs) = Node x (treeFromList (filter (
```x) xs))

And now we can play around:

```
main = do
putStrLn "Int binary tree:"
print $ treeFromList [7,2,4,8,1,3,6,21,12,23]
```

```
print $ treeFromList [7,2,4,8,1,3,6,21,12,23]
Int binary tree:
< 7
: |--2
: | |--1
: | `--4
: | |--3
: | `--6
: `--8
: `--21
: |--12
: `--23
```

Much better! The root of the tree is displayed with a symbol

`<`

. And each subsequent line begins with `:`

. But we can use another type.

```
putStrLn "\nString binary tree:"
print $ treeFromList ["foo","bar","baz","gor","yog"]
```

```
String binary tree:
< "foo"
: |--"bar"
: | `--"baz"
: `--"gor"
: `--"yog"
```

And since we can test trees for equality and set their order, we can create a tree of trees!

```
putStrLn "\nДвоичное дерево состоящее из двоичных деревьев символов:"
print ( treeFromList
(map treeFromList ["baz","zara","bar"]))
```

```
Двоичное дерево состоящее из двоичных деревьев символов:
< < 'b'
: : |--'a'
: : `--'z'
: |--< 'b'
: | : |--'a'
: | : `--'r'
: `--< 'z'
: : `--'a'
: : `--'r'
```

That is why I have chosen as the prefix of each new line (except the root)

`:`

.```
putStrLn "\nTree of Binary trees of Char binary trees:"
print $ (treeFromList . map (treeFromList . map treeFromList))
[ ["YO","DAWG"]
, ["I","HEARD"]
, ["I","HEARD"]
, ["YOU","LIKE","TREES"] ]
```

Which is equivalent to the following:

```
print ( treeFromList (
map treeFromList
[ map treeFromList ["YO","DAWG"]
, map treeFromList ["I","HEARD"]
, map treeFromList ["I","HEARD"]
, map treeFromList ["YOU","LIKE","TREES"] ]))
```

and as a result:

```
Binary tree of Binary trees of Char binary trees:
< < < 'Y'
: : : `--'O'
: : `--< 'D'
: : : |--'A'
: : : `--'W'
: : : `--'G'
: |--< < 'I'
: | : `--< 'H'
: | : : |--'E'
: | : : | `--'A'
: | : : | `--'D'
: | : : `--'R'
: `--< < 'Y'
: : : `--'O'
: : : `--'U'
: : `--< 'L'
: : : `--'I'
: : : |--'E'
: : : `--'K'
: : `--< 'T'
: : : `--'R'
: : : |--'E'
: : : `--'S'
```

Please note that duplicates are not inserted.

Only one tree corresponding is displayed

`"I","HEARD"`

. We got this feature (almost) for free, because we declared Tree an instance `Eq`

. Look at the beauty and power of this type. We can create trees consisting not only of numbers, lines and symbols, but also of other trees. We can even create a tree whose elements are tree trees!

02_Hard_Part /

**31_Trees.lhs**

02_Hard_Part /

**40_Infinites_Structures.lhs**

### Endless structures

Haskell is often called a

*lazy*language.

But it’s right to say that Haskell is

*not a strict*language . Laziness is just a popular implementation of non-strict languages.

What is a lax language? From the Haskell-wiki:

Reduction (a mathematical term for calculating an expression) goes from the outside to the inside.

if you have an expression`(a+(b*c))`

, then you evaluate first`+`

, and then the inner expression`(b*c)`

For example, using Haskell, you can do this:

```
-- numbers = [1,2,..]
numbers :: [Integer]
numbers = 0:map (1+) numbers
take' n [] = []
take' 0 l = []
take' n (x:xs) = x:take' (n-1) xs
main = print $ take' 10 numbers
```

And the program ends.

How?

Instead of calculating everything

`номера`

, it only calculates the necessary elements. Note the syntax for specifying endless lists in Haskell

```
[1..] ⇔ [1,2,3,4...]
[1,3..] ⇔ [1,3,5,7,9,11...]
```

And most functions will be able to work with such lists. There is even a standard feature

`take`

identical to ours `take'`

. 02_Hard_Part /

**40_Infinites_Structures.lhs**

02_Hard_Part /

**41_Infinites_Structures.lhs**

Let's say we don't mind having an ordered binary tree. Here is an example of an infinite binary tree:

```
nullTree = Node 0 nullTree nullTree
```

A full binary tree with zeros at each node. Now I will prove to you that we can work with this tree using the following function:

```
-- возьмем все элементы BinTree
-- которые находятся на определенной глубине
treeTakeDepth _ Empty = Empty
treeTakeDepth 0 _ = Empty
treeTakeDepth n (Node x left right) = let
nl = treeTakeDepth (n-1) left
nr = treeTakeDepth (n-1) right
in
Node x nl nr
```

Let's see what this program will output:

```
main = print $ treeTakeDepth 4 nullTree
```

This code compiles, starts, stops, and displays the following result:

```
< 0
: |-- 0
: | |-- 0
: | | |-- 0
: | | `-- 0
: | `-- 0
: | |-- 0
: | `-- 0
: `-- 0
: |-- 0
: | |-- 0
: | `-- 0
: `-- 0
: |-- 0
: `-- 0
```

To rock the neurons a bit, make the tree weirder:

```
iTree = Node 0 (dec iTree) (inc iTree)
where
dec (Node x l r) = Node (x-1) (dec l) (dec r)
inc (Node x l r) = Node (x+1) (inc l) (inc r)
```

A similar tree can also be created using higher order functions.

This function is similar to

`map`

, but should work with `BinTree`

instead of a list. Here is one possible implementation of such a function:

```
-- применим функцию к каждому узлу Tree
treeMap :: (a -> b) -> BinTree a -> BinTree b
treeMap f Empty = Empty
treeMap f (Node x left right) = Node (f x)
(treeMap f left)
(treeMap f right)
```

*Hint*: I will no longer get stuck on this topic. If you are interested in seeing a generalization

`map`

to other data structures, look for the functor and functor keywords `fmap`

. Our implementation:

```
infTreeTwo :: BinTree Int
infTreeTwo = Node 0 (treeMap (\x -> x-1) infTreeTwo)
(treeMap (\x -> x+1) infTreeTwo)
```

And the result of execution

```
main = print $ treeTakeDepth 4 infTreeTwo
```

```
< 0
: |-- -1
: | |-- -2
: | | |-- -3
: | | `-- -1
: | `-- 0
: | |-- -1
: | `-- 1
: `-- 1
: |-- 0
: | |-- -1
: | `-- 1
: `-- 2
: |-- 1
: `-- 3
```

02_Hard_Part /

**41_Infinites_Structures.lhs**