
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 asfilename.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 forC
.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 returnsInt |
Float -> Int | function that takes in Float and returnsInt |
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 resulta |
a -> a -> a | type of function that takes two type arguments a and returns a type resulta |
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 usedData.Text
.
If you need to work with a stream of ASCII characters, it is worth usingData.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: alignment is important in 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 compilerName
and typesAnotherType
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 smallerx
and - the right subtree will be created from the list elements
xs
strictly largex
.
- 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