mungobungo October 3, 2012 at 04:08

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
- Expressions
- Useful things to write functions
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.hsand execute:

 ~ runhaskell ./hello.hs
Hello World!

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

Save the file 00_hello_world.lhsand 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 maincreates 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- defs.

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.2this 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 ais a type variable .
This means that fis a function of two arguments, and both arguments, as well as the result, are of the same type.
A type variable acan take on various types of values.
For example Int, Integer, Float...

So rather than hard-code type, both in Cand separately define functions for int, long, float, double, and so on ...
We just create a function in a dynamically typed language.

Generally speaking, it acan be of any type.
String, IntMore complex type, for example Trees, the type of the other functions, etc.
But in our example, the type has a prefix Num a => .

Numthis is a type class .
A type class can be represented as many types.
In Numincludes only those types that behave like numbers.
More strictly, Numit 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 -> ameans:

Let ait be a type belonging to the type class Num.
This is a function that takes in input aand 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 4equivalent (f 3) 4.
Please note that f 3this 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 3can represent both a Fractional (fractional) number of type Float and an integer of type Integer.
Since it 2.4is of type Fractional, it 3also 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 Chars.


'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 xexpression 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 .. elsein 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 evenSumreturns 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 whereor let.
Thus, our function accumSumwill 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 filteraccepts 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 foldlthat allows us to accumulate value. The function foldlimplements 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 foldlgiven 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 evenSumlooks 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 mapsimply 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 = AnotherTypeit's just an alias for the compiler Nameand types AnotherTypelook 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, Fractionaland 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 :+ ythis 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 showInfosand 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 showInfosswap 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 datausually 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 infixris 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, xsis strictly smaller xand
- the right subtree will be created from the list elements xsstrictly large x.


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 ( Eqand 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 treeFromListdoes 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 takeidentical 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 BinTreeinstead 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 mapto 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

Tags: