Через тернии к Haskell. 1/2 перевод tutorial

Первая часть короткого и жесткого введения в Haskell. Вторую часть можно найти здесь

tl;dr: Очень краткое и сжатое введение в Haskell.

• Введение
  
  • Установка
  • Без паники
  • Самые основы Haskell
    
    • Объявление функций
    • Пример использование типов
    
    
  
  
• Необходимый минимум из Haskell
  
  • Выражения
    
    • Арифметические
    • Логические
    • Возведение в степень
    • Списки
    • Строки
    • Кортежи
    • Разбираемся со скобками
    
    
  • Полезные вещи для записи функций
  
  
• Сложная часть
  
  • Функциональный стиль
    
    • Функции высшего порядка
    
    
  • Типы
    
    • Вывод типов
    • Создание новых типов
    • Рекурсивные типы
    • Деревья
    
    
  • Бесконечные структуры
  
  

UPD. Если туториал вам понравился, черкните пару строк автору оригинальной статьи. Человеку будет приятно ;)

Я искренне верю в то, что каждый разработчик должен изучить Haskell. Я не считаю, что каждый должен быть супер-Haskell-ниндзей. Люди просто должны знать о возможностях, которые открывает Haskell. Изучение Haskell расширяет ваше сознание.


Основа мейнстримовых языков очень похожа

• переменные
• циклы
• указатели (даже если большинство языков пытается скрыть этот факт, он все равно остается фактом)
• структуры, объекты и классы(в большинстве языков)

Haskell сильно от них отличается. Этот язык использует кучу концепций, о которых я раньше не слышал. Многие из этих концепций помогут вам стать лучшим программистом.


Но изучение Haskell-а может быть сложным. По крайней мере оно было сложным для меня. И в этой статье я постараюсь показать, чего мне не хватало в процессе изучения.

Эту статью будет сложно осилить. Это было сделано специально. В изучении Haskell нет простых путей. Эта дорога трудна и заковыриста. Но я думаю, что это и хорошо. Потому что именно сложность Haskell-а делает его интересным.

Обычный метод изучения Haskell-а состоит в прочтении двух книг.
Сначала “Learn You a Haskell”, а потом “Real World Haskell”.

Я согласен с тем, что это правильный подход к обучению. Но для того, чтобы понять, что из себя представляет Haskell, вам придется очень внимательно прочитать эти книги.


С другой стороны, эта статья очень краткое и сжатое ввдение во все основные аспекты Haskell. Я также добавил некоторые нюансы, которых мне не хватало при изучении Haskell.


Статья состоит из пяти частей:

• Введение: короткий пример, чтобы показать, что Haskell может быть нестрашным.
• Самые основы Haskell: синтаксис Haskell-а и некоторые базовые структуры.
• Сложная часть:
  
  • Функциональный стиль; Пример с переходом от императивного к функциональному стилю
  • Типы; типы и стандартный пример с бинарным деревом
  • Бесконечные структуры; работа с бесконечным бинарным деревом!
  
  
• Чертовски сложная часть:
  
  • Разбираемся с IO; Минимальный пример
  • Разбор трюка с IO; неочевидная мелочь, которая мешала мне понятьIO
  • Монады; нереально мощный инструмент абстракции
  
  
• Приложение:
  
  • Еще несколько слов о бесконечных деревьях; математически ориентированное обсуждение бесконечных деревьев
  
  

Замечание: Каждый раз, когда вы увидите разделитель с именем файла и расширением .lhs,
вы можете его скачать.
Если вы сохраните файл как filename.lhs, вы можете запустить его при помощи
runhaskell filename.lhs


Какие-то примеры могут не работать, но большинство должно.
Чуть ниже вы должны увидеть ссылку на файл

---

01_basic/10_Introduction/00_hello_world.lhs

Введение

Установка

• Haskell Platform — это стандартный способ установки Haskell.

Утилиты:

• ghc: Компилятор, похожий на gcc для C.
• ghci: интерактивная оболочка Haskell (REPL)
• runhaskell: Запуск программы без ее компиляции. Удобно, но очень медленно по сравнению со скомпилированными программами.

Без паники

Многие книги и статьи начинают знакомство с Haskell-ом с каких-то эзотерических формул (быстрая сортировка, Фибоначчи и т.п.). Я поступлю по-другому. Я не буду сразу показывать суперсилу Haskell-а. Я сконцентрируюсь на тех вещах, в которых Haskell похож на остальные языки программирования. Итак, давайте начнем с привычного “Hello World”.

main = putStrLn "Hello World!"

Чтобы запустить его, сохраните этот код как hello.hs и выполните:

 ~ runhaskell ./hello.hs
Hello World!

Вы можете скачать исходник по ссылке, которая находится под «Введением»

Сохраняем файл 00_hello_world.lhs и выполняем:

 ~ runhaskell 00_hello_world.lhs
Hello World!

01_basic/10_Introduction/00_hello_world.lhs

---

01_basic/10_Introduction/10_hello_you.lhs

А теперь напишем программу, которая запрашивает ваше имя и говорит “Привет, имярек!”:

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

Для начала, сравним наш пример с другими императивными языками:

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

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

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

Структура программ очень похожа, но есть небольшие синтаксические отличия. Основная часть туториала будет посвящена именно этим отличиям.


В Haskell, каждая функция и объект имеют свой тип.
Тип функции main — IO ().
Это значит, что при выполнении main создает побочные эффекты.

Но не забывайте о том, что Haskell может выглять как обычный императивный язык.

01_basic/10_Introduction/10_hello_you.lhs

---

01_basic/10_Introduction/20_very_basic.lhs

Самый базовый Haskell

Перед тем, как мы продолжим, хотелось бы предупредить вас о некоторых характерных особенностях Haskell.

Функциональность

Haskell — это функциональный язык.
Если вы начинали с императивных языков, вам придется выучить много новых вещей.
К счастью, многие из эти концепций помогут вам лучше программировать даже на императивных языках.

Продвинутая статическая типизация

Вместо того, чтобы стоять на вашем пути как в C, C++ или Java, система типов будет помогать вам.

Чистота

Вообще говоря, ваши функции ничего не будут изменять во внешнем мире.
С одной строны, это значит что функции не могут изменять значение переменной, не могут получать данные от пользователя, не могут писать на экране, не могут запускать ракеты.
С другой стороны, мы получаем легкое распараллеливание наших программ.
Haskell проводит четкую границу между чистыми функциями и функциями, производящими побочные эффекты.
При таком подходе становится намного легче анализировать свойства вашей программы.
В функционально чистых частях программы многие ошибки будут исключены еще на этапе компиляции.


Более того, функционально чистые функции следуют основному закону Haskell-а:

Вызов функции с одними и теми же параметрами всегда даст один и тот же результат.

Ленивость

Ленивость по умолчанию очень необычная вещь в языках программирования.
По умолчания, Haskell вычисляет значение только тогда, когда оно реально необходимо.
Как следствие, мы получаем возможность очень просто работать с бесконечными структурами данных.

Последнее предупреждение будет касаться того, как стоит читать код на Haskell-е.
Для меня этот похоже на чтение научных статей.
Некоторые части могут быть простыми и ясными, но если вы видите формулу, сконцентрируйтесь и читайте медленнее.
При изучении Haskell-а, действительно неважно, если вы не до конца понимаете некоторые особенности синтаксиста.
Если вам встретятся >>=, <$>, <- или другие страшные символы, просто игнорируйте их и постарайтесь понять общую идею кода.

Определение функций

Вы можете определять функции следующим образом:

На C:

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

На Javascript:

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

На Python:

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

На Ruby:

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

На Scheme:

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

И наконец, Haskell:

f x y = x*x + y*y

Очень четко. Ни скобок, ни def-ов.

Не забывайте, что в Haskell интенсивно используются функции и типы.
И поэтому их очень просто определять.
Синтаксис языка был продуман с тем, чтобы сделать определения максимально простыми.

Пример создания нового типа

Обычно при написании программ, вы указываете тип функции.
Но это не обязательно.
Компилятор достаточно умен, чтобы сделать это за вас.

Давайте немного поиграемся.

-- Мы определям тип используя ::
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

Теперь попробуйте

f :: Int -> Int -> Int
f x y = x*x + y*y

main = print (f 2.3 4.2)

Вы получите ошибку:

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)

Проблема заключается в том, что 4.2 это не Int.

01_basic/10_Introduction/21_very_basic.lhs

---

01_basic/10_Introduction/22_very_basic.lhs

Одним из вариантов решения будет не указывать явно тип функцииf.
Тогда Haskell выведет для нас наиболее общий подходящий тип:

f x y = x*x + y*y

main = print (f 2.3 4.2)

Заработало!
Здорово, нам не надо создавать новую функцию для каждого типа данных.
Например в C, вам бы понадобилось создать функцию для int, для float, для long, для double, и т.д.

Но какой тип мы должны указать?
Чтобы понять, какой тип для нас вывел Haskell, просто запустите 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

Хмм… Что это за странный тип?

Num a => a -> a -> a

Сначала обратим внимание на правую часть a -> a -> a.
Чтобы разобраться в ней, давайте рассмотрим несколько примеров:

Указанный тип	Значение
Int	тип Int
Int -> Int	функция, принимающая на вход Int и возвращающая Int
Float -> Int	функция, принимающая на вход Float и возвращающая Int
a -> Int	тип функции, принимающей на вход любой тип и возвращающая Int
a -> a	тип функции, принимающей на вход тип a и возвращающая результат типа a
a -> a -> a	тип функции, принимающей на вход два аргумента типа a и возвращающая результат типа a

В типе a -> a -> a, буква a это переменная типа.
Это значит, что f — функция от двух аргументов, и оба аргумента, а также результат имеют одинаковый тип.
Переменная типа a может принимать значения различных типов.
Например Int, Integer, Float…

Так что вместо того, чтобы жестко задавать тип, как в C и отдельно определять функции для int, long, float, double, и т.п.…
Мы просто создаем одну функцию, как в динамически типизированном языке.

Вообще говоря a может быть любого типа.
String, Int, более сложным типом, например Trees, типом другой функции, и т.д.
Но в нашем примере тип имеет префикс Num a => .

Num это класс типа.
Класс типа можно представить как множество типов.
В Num входят только те типы, которые ведут себя как числа.
Более строго, Num это класс, содержащий типы, реализующие заданный набор функций, в частности (+) и (*).

Классы типов — очень мощный элемент языка.
С их помощью мы можем творить удивительные вещи.
Но об этом мы поговорим чуть позже.

Итак, запись Num a => a -> a -> a означает:

Пусть a это тип, принадлежащий к классу типов Num.
Это функция, принимающая на вход a и возвращающая (a -> a).

Мде, странновато.
На самом деле в Haskell-е ни одна функция не принимает на вход два аргумента.
Вместо этого у всех функций — только один аргумент.
Но обратите внимание, что функцию от двух аргументов можно представить как функцию, принимающую первый аргумент и возвращающую функцию, принимающую второй аргумент в качестве параметра.
.

То есть f 3 4 эквивалентно (f 3) 4.
Обратите внимание на то, что f 3 это тоже функция:

f :: Num a :: a -> a -> a

g :: Num a :: a -> a
g = f 3

g y ⇔ 3*3 + y*y

Для создания функция также можно использовать другую запись.
Лямбда-выражения позволяют создавать функции не присваивая им имен.
Их также назызвают анонимными функциями.
Мы можем записать:

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

Символ \ используется потому, что он похож на символ λ, но в то же время он ASCII символ.

Если функциональное программирование вам в новинку, к этому моменту ваши мозги начинают закипать.
Самое время написать реальное приложение.

01_basic/10_Introduction/22_very_basic.lhs

---

01_basic/10_Introduction/23_very_basic.lhs

Но прежде, чем мы начнем, надо проверить, что система типов работает как следует:

f :: Num a => a -> a -> a
f x y = x*x + y*y

main = print (f 3 2.4)

Этот код работает потому, что 3 может представлять как Fractional (дробное) число типа Float, так и целое типа Integer.
Поскольку 2.4 имеет тип Fractional, 3 тоже представляется в виде Fractional числа.

01_basic/10_Introduction/23_very_basic.lhs

---

01_basic/10_Introduction/24_very_basic.lhs

Если мы пропишем в функции другие типы, она перестанет работать:

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

Компилятор сигнализирует об ошибке.
Два параметра должны иметь одинаковый тип.

Если вы считаете, что это плохая идея, и комплятор должен преобразовать типы за вас, вам действительно стоит посмотреть отличное и смешное видео:
WAT

01_basic/10_Introduction/24_very_basic.lhs

Необходимый минимум Haskell

Я советую вам бегло просмотреть этот раздел.
Думайте о нем, как о справочном материале.
Haskell — очень многоплановый язык.
Поэтому какие-то вещи в этом разделе будет пропущены.
По необходимости возвращайтесь сюда, если какие-то вещи покажутся вам странными или непонятными.

Я буду использовать символ ⇔, чтобы показать эквивалентность двух выражений.
Это мета-нотация, в Haskell не существует ⇔.
Символ ⇒ будет использоваться для того, чтобы показать результат вычисления выражения.

Выражения

Арифметические

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

Логические

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

Возведение в степень

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

Integer не имеет ограничений по величине, за исключением оперативной памяти машины:

4^103
102844034832575377634685573909834406561420991602098741459288064

О да!
А еще можно использовать рациональные числа!
Но для этого необходимо использовать модуль Data.Ratio:

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

Списки

[]                      ⇔ пустой список
[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]

Строки

В Haskell-е строки это список Char-ов.

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

Замечание:
В реальных задачах вы не будете использовать список символов для работы с текстом.
В большинстве случаев для этого используется Data.Text.
Если вам небходимо работать с потоком ASCII-символов, стоит использовать Data.ByteString.

Кортежи

Задать пару можно следующим образом (a,b).
Элементы кортежа могут иметь различные типы.

-- Все эти кортежи - валидны
(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

Разбираемся со скобками

Чтобы избавиться от лишних скобок, вы можете воспользоваться этими функциями: ($) и (.).

-- По умолчанию:
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

Полезные вещи для записи функций

Небольшое напоминание:

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 

Объявлять тип функции перед ее определеним необязательно.
Haskell сам выведет наиболее общий тип.
Но указание типа функции — правило хорошего тона.

Инфиксная запись

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

Обратите внимание, что ^ используется в инфиксной нотации.
Для каждого инфиксного оператора существует возможность префиксной записи.
Просто заключите нужный оператор в скобки.

square' x = (^) x 2

square'' x = (^2) x

Мы можем убрать x из левой и правой части выражения!
Это называется η-редукция.

square''' = (^2)

Обратите внимание, что мы можем использовать символ ' в имени функции.
Например:

square ⇔ square' ⇔ square'' ⇔ square '''

Тесты

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

Обратите внимание: конструкция if .. then .. else в Haskell-е больше похожа на оператор
¤?¤:¤ в C. Вы не можете опустить else.

Еще один эквивалент функции:

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

Внимание: выравнивание важно в программах на Haskell-е.
Как и в Python-е, неправильное выравнивание может сломать код!

Сложная часть

Приступим к изучению сложной части.

Функциональный стиль

В этом разделе я покажу вам небольшой пример удивительных возможностей Haskell по рефакторингу кода.
Мы выберем проблему и решим ее стандартным императивным способом. Потом начнем понемногу улучшать этот код. Конечный результат будет гораздо проще для понимании и более элегантным.


Вот условие задачи, которую мы будем решать:

Имея список целых чисел, необходимо посчитать сумму четных чисел в списке.

пример:
[1,2,3,4,5] ⇒ 2 + 4 ⇒ 6

Для того, чтобы показать разницу между функциональным и императивным подходом, сначала напишем императивное решение (на 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;
}

Но в Haskell-е отсутствуют переменные и циклы.
Без использования циклов тот же результат можно получить, используя рекурсию.

Замечание:
Рекурсию в императивных языках имеет репутацию медленного инструмента. Но для большинства функциональных языков это не так. В большинстве случаев, Haskell очень качественно оптимизирует работу с рекурсивными функциями.

Вот версия рекурсивной функции, написанной на C. Для просты, я предполагалю, что список чисел заканчивается нулевым значением.

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);
        }
    }
}

Внимательно посмотрите на этот код. Потому что мы будем переводить его на Haskell.
Но прежде я покажу вам три простые, но очень полезные функции, которые мы будем использовать:

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

even проверка на четность.

even :: Integral a => a -> Bool 
even 3 ⇒ False
even 2 ⇒ True

head возвращает первый элемент списка:

head :: [a] -> a
head [1,2,3] ⇒ 1
head []      ⇒ ERROR

tail возвращает все элементы списка, окромя первого:

tail :: [a] -> [a]
tail [1,2,3] ⇒ [2,3]
tail [3]     ⇒ []
tail []      ⇒ ERROR

Обратите внимание, что для любого непустого списка l,
l ⇔ (head l):(tail l)

---

02_Hard_Part/11_Functions.lhs

Итак, первое решение задачи на Haskell-е.
Функция evenSum возвращает сумму всех четных чисел в списке:

-- Версия 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

Чтобы протестировать функцию, просто запустите 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

Ниже представлен пример работы функции (Я жульничаю. В курсе. К вопросу о нестрогих вычислениях мы вернемся позже):

*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

С точки зерния императивного языка все выглядит нормально. Но тут кроется большой простор для улучшений. Для начала, мы можем сделать тип более общим.

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

02_Hard_Part/11_Functions.lhs

---

02_Hard_Part/12_Functions.lhs

Следующим шагом может быть использование вложенных функций, определенных при помощи where или let.
Таким образом наша функция accumSum не будет загрязнять глобальное пространство имен.

-- Версия 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

А теперь используем сопоставление с образцом.

-- Версия 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

Что такое сопоставление с образцом (pattern matching)? Это просто ипользование значений вместо именованных параметров. (Для самых смелых подробное описание сопоставления с образцом можно изучитьздесь)

Вместо такого кода: foo l = if l == [] then <x> else <y>
Можно просто написать:

foo [] =  <x>
foo l  =  <y>

Но сопоставление с образцом может гораздо большее. Оно может анализировать внутренние данные сложной структуры. Мы можем заменить

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

на

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

Очень полезная возможность.
Она делает наш код более кратким и читаемым.

02_Hard_Part/13_Functions.lhs

---

02_Hard_Part/14_Functions.lhs

Вы можете упростить запись функций в Haskell-е применяя η-редукцию.
Например, вместо такой записи:

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

можно использовать

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

Мы можем использовать этот подход для того, чтобы избавиться от 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

Функции Высшего Порядка

Чтобы сделать нашу функцию еще более красивой, мы можем применить ФВП (функции высшего порядка).
Вы спрашиваете, что это за звери?
Функции высшего порядка — это функции, принимающие функции в качестве параметра.

Пара примеров:

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

Будем продвигаться небольшими шагами.

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

где

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

Функция filter принимает в качестве аргументов функцию типа (a -> Bool) и список типа [a]. Она возвращает список, содержащий только те элементы, для которых функция вернула true.

Следующим нашим действием будет дальнейшее упрощение цикла. Мы используем функцию foldl, которая позволяет аккумулировать значение. Функция foldl реализует популярный прием программирования:

myfunc list = foo initialValue list
    foo accumulated []     = accumulated
    foo tmpValue    (x:xs) = foo (bar tmpValue x) xs

Код выше можно заменить на:

myfunc list = foldl bar initialValue list

Если вы действительно хотите разобраться в происходящей магии,
реализация foldl приведена ниже.

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

Но поскольку Haskell ленивый язык, он не вычисляет значение (f z x), а запихивает его в стек.
Поэтому мы будем использовать foldl' вместо foldl;
foldl' это строгая (или энергичная) реализация foldl.

Если для вас не очевидна разность между ленивыми и строгими функциями, не беспокойтесь, просто читайте код, считая что обе функции одинаковы.


Теперь наша версия evenSum выглядит так:

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

Этот код можно упростить еще больше, используя лямбда-выражения.Таким образом мы избавимся от временного идентификатора mysum.

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

И конечно, мы можем провести следующую замену

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

02_Hard_Part/15_Functions.lhs

---

02_Hard_Part/16_Functions.lhs

В итоге

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

foldl' не самая интуитивно понятная функция. Но с ней обязательно стоит разобраться.

Для этого проведем пошаговый анализ:

  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

Другая полезная функция высшего порядка это (.).
Функция (.) соответствует математической композиции.

(f . g . h) x ⇔  f ( g (h x))

Мы можем ее использовать, чтобы еще дальше η-редуцировать нашу функцию:

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

Можно сделать еще кое-что, чтобы код стал чище:

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

Обсудим получившийся результат.
Что мы получили, применив функции высшего порядка?

В глаза бросается краткость кода. Но основной плюс в том, насколько проще стало понимать нашу программу. Допустим, мы хотим немного изменить нашу функцию. Теперь нам хочется, чтобы она возвращала сумму квадратов всех четных чисел в списке.

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

Добавить это изменение в версию 10 очень просто:

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

Нам надо просто добавить еще одну “преобразовывающую функцию” (Обратите внимание, что squareEvenSum'' эффективнее двух других реализаций. Порядок (.) действительно имеет значение.).

map (^2) [1,2,3,4] ⇔ [1,4,9,16]

Функция map просто применяет функцию-параметр ко всем элементам списка.

Нам ничего не надо менять внутри определения функции.
Она стала гораздо более модульной.
Но помимо всего прочего, она стала себя вести более «математически».
Вы можете использовать свою функцию как и любую другую.
Вы можете делать композицию, map, fold и filter, используя вашу новую функцию .

Рефакторинг версии один оставим в качестве задания читателю ☺.

Если вы думаете, что сделать код более абстрактным сложно, то вы сильно ошибаетесь.Например, эту функцию можно использовать не только для списков, но и для любых рекурсивных типов. Если вам интересно как — почитайте эту забавную статью: Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire by Meijer, Fokkinga and Paterson.

На нашем примере можно увидеть, насколько мощным может быть функциональное программирование. К сожалению в некоторых случаях чисто функциональные языки не всегда самый лучший выбор. По крайней мере, действительно универсальный функциональный язык еще не создан.

Одна из отличительных особенностей Haskell лежит в создании DSL-ей (Доменно Ориентированных Языков).


На самом деел, Haskell является отличным инструментом, даже если вы хотите писать программы в императивном стиле. Когда я изучал Haskell, эта мысль стала для меня откровением.


Но перед тем, как мы перейдем к разговорам о суперсиле Haskell-а, нам надо обсудить еще один существенный аспект — Типы.

Типы

tl;dr:

• type Name = AnotherType это просто псевдоним, для компилятора типы Name и AnotherType выглядят одинаково.
• data Name = NameConstructor AnotherType А в этом примере типы отличаются.
• data может создавать рекурсивные структуры.
• deriving это сильное колдунство и может создавать функции за вас.

Haskell — язык со строгой статической типизацией.

Почему это так важно? Потому что это сильно уменьшает количество ошибок.
В Haskell, большинство ошибок можно обнаружить еще на этапе компиляции. И происходит это потому, что во время компиляции активно применяется вывод типов.
Если вы используете не тот параметр не в том месте, компилятор это легко заметит.

Вывод типов

Статическая типизация необходима для создания быстрых программ
Но большинство статически типизированных языков слабы в обобщении концепций.

Одна из благодатных возможностей Haskell-а вывод типов.

Простой пример.
Функция square на языке Haskell:

square x = x * x

Эта функция может square(возвести в квадрат) любое значение типа Numeral.
Вы можете передать туда значение типа Int, Integer, Float, Fractional и даже Complex. Например:

% 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 это запись комплексного числа (x + iy).

Теперь сравните количество кода по сравнению с программой на C:

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);

Для каждого типа надо писать свою функцию. Обойти это можно только используя техники метапрограммирования. Например используя препроцессор. C++ предлагает более красивый вариант решения, используя шаблоны:

#include <iostream>
#include <complex>
using namespace std;

template<typename T>
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<double>(5,3) )
         << endl;
    return 0;
}

Вариант на C++ выглядит гораздо лучше C.
Но для функций комплексной переменной будет сложно сохранить такой же синтаксис. Пример можно найти в
этой статье
.

В C++ вы должны описать функцию, которая может работать с разными типами.
В Haskell ситуация противоположная.
Функция будет максимально обобщенной по умолчанию.

Вывод типов Haskell дает ощущение свободы, которое представляют динамически типизированные языки.
Но в отличие от динамически типизированных языков, большинство ошибок, отлавливаются еще до момента выполнения программы.
Люди говорят про Haskell так:

“Если оно компилируется, то оно скорее всего работает правильно”

---

02_Hard_Part/21_Types.lhs

Создание новых типов

Вы можете создавать свои собственные типы. Например, можно объявлять синонимы типов.

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

Но это не сильно защитит вас от ошибок.
Попробуйте поменять местами два параметра функции showInfos и запустить программу:

 putStrLn $ showInfos color name

Она скомпилируется и запустится. Вы можете использовать Name, Color и String как взаимозаменяемые сущности. Для компилятора они абсолютно идентичны.
Другой способ создать собственный тип — использовать ключевое слово 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

Если в showInfos поменять параметры местами, компилятор начнет ругаться. Возможность ошибиться исчезла. Но ценой увеличения количества кода.

Обратите внимание, что конструкторы типа — это функции :

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

Использование data обычно выглядит так:

data TypeName =   ConstructorName  [types]
                | ConstructorName2 [types]
                | ...

Для
DataTypeName и DataTypeConstructor обычно используют одно и то же имя.
Например:

data Complex = Num a => Complex a a

Также можно использовать синтаксис записей:

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

И куча функций доступа к данным будет создана автоматически. Более того, при записи новых значений вы можете использовать произвольный порядок полей.

Пример:

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

Рекурсивные типы

Вы уже встречались с представителем рекурсивных типов — со списками. Можно создать списки с нуля, используя более многословный синтаксис:

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

Для более простой записи можно использовать инфиксный конструктор типа.

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

Число после infixr — это приоритет оператора .

Если вы хотите печатать (Show), считывать (Read), проверять на равенство (Eq) и сравнивать (Ord) значения вашего нового типа, вы можете сказать Haskell-у, чтобы он автоматически вывел необходимые для этого функции.

infixr 5 :::
data List a = Nil | a ::: (List a) 
              deriving (Show,Read,Eq,Ord)

Когда вы добавляете deriving (Show) к описанию вашего типа, Haskell автоматичесеи создает для вас фукнцию show. Скоро мы увидим, как можно написать свою версию функции show.

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

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

Вывод программы:

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

02_Hard_Part/23_Types.lhs

---

02_Hard_Part/30_Trees.lhs

Деревья

Вот еще один стандартный пример: двоичные деревья.

import Data.List

data BinTree a = Empty
                 | Node a (BinTree a) (BinTree a)
                              deriving (Show)

Давайте напишем функцию, которая преобразует список в упорядоченное двоичное дерево.

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

Оцените элегантность этой функции.
Перевод на русский язык:

• пустой список превращается в пустое дерево.
• список (x:xs) станет деревом, в котором:
  
  • корнем будет x
  • левое поддерево будет создано из элементов списка xs строго меньших x а
  • правое поддерево будет создано из элементов списка xs строго больших x.
  
  

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

Должно получиться что-то вроде:

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

Это информативное, но не очень красивое представление нашего дерева.

02_Hard_Part/30_Trees.lhs

---

02_Hard_Part/31_Trees.lhs

Чтобы немного развлечься, давайте напишем код для более красивого отображения наших деревьев. Я получил большое удовольствие от написания функции, которая может красиво отображать любые деревья. Если эта часть покажется вам сложной — можете спокойно ее пропустить.

Нам необходимо сделать небольшие изменения.
Мы уберем deriving (Show) из объявления типа BinTree. Также будет полезно сделать BinTree экземпляром классов типов (Eq и Ord). Это даст нам возможность проверять деревья на равенство и сравнивать их.

data BinTree a = Empty
                 | Node a (BinTree a) (BinTree a)
                  deriving (Eq,Ord)

Без deriving (Show), Haskell не создаст для нас метод show.
Но мы напишем свою собственную версию show. Чтобы это сделать, мы должны указать, что наш свежесозданный тип BinTree a
является экземпляром класса типов Show.
В коде это выглядит так:

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

Вот моя версия отображения бинарного дерева. Она не так страшна, как выглядит.Я адаптировал ее для отображения гораздо более странных объектов.

-- говорим что  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"

Метод treeFromList не изменяется.

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

А теперь мы можем поиграться:

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

Гораздо лучше! Корень дерева отображается при помощи символа<. И каждая последующая строка начинается с :.
Но мы можем использовать и другой тип.

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

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

А поскольку мы можем проверять деревья на равенство и задавать их порядок, мы можем создать дерево деревьев!

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

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

Именно поэтому в качестве префикса каждой новой линии (кроме корня) я выбрал :.

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

Что эквивалентно следующему:

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

и в результате:

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'

Обратите внимание, что дубликаты не вставляются.
Отображается только одно дерево, соответствующее "I","HEARD". Мы получили эту возможность (практически) бесплатно, потому что объявили Tree экземпляром Eq.

Посмотрите на красоту и мощь этого типа. Мы можем создавать деревья состоящие не только из чисел, строк и символов, но так же из других деревьев. Мы можем даже создать дерево, элементами которого будут деревья деревьев!


02_Hard_Part/31_Trees.lhs

---

02_Hard_Part/40_Infinites_Structures.lhs

Бесконечные структуры

Haskell часто называют ленивым языком.

Но правильно говорить, что Haskell это не строгий язык. Ленивость это просто популярная реализация нестрогих языков.

Что такое нестрогий язык? Из Haskell-wiki:

Редукция (математический термин для вычисления выражения) идет снаружи внутрь.

если у вас есть выражение (a+(b*c)), то сначала вы вычисляете +, а потом внутреннее выражение (b*c)

Например используя Haskell можно сделать так:

-- 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

И программа завершается.

Каким образом?

Вместо того, чтобы вычислять все номера, она вычисляет только необходимые элементы.

Обратите внимание на синтаксис для задания бесконечных списков в Haskell

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

И большинство функций сможет работать с такими списками. Существует даже стандартная функция take идентичная нашей take'.

02_Hard_Part/40_Infinites_Structures.lhs

---

02_Hard_Part/41_Infinites_Structures.lhs

Допустим, мы не против иметь упорядоченное двоичное дерево. Вот пример бесконечного двоичного дерева:

nullTree = Node 0 nullTree nullTree

Полноценное двоичное дерево с нулями в каждом узле. Теперь я докажу вам, что мы можем работать с этим деревом, используя следующую функцию:

-- возьмем все элементы 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

Давайте посмотрим, что выведет эта программа:

main = print $ treeTakeDepth 4 nullTree

Этот код компилируется, запускается, останавливается и выводит следующий результат:

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

Чтобы немного раскачать нейроны, сделаем дерево более странным:

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) 

Подобное дерево также можно создать используя функции высшего порядка.
Эта функция похожа на map, но должна работать с BinTree вместо списка.
Вот одна из возможных реализаций такой функции:

-- применим функцию к каждому узлу 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)

Подсказка: Я больше не буду зацикливаться на этой теме. Если вам интересно увидеть обобщение map на другие структуры данных, ищите по ключевым словам functor(функтор) и fmap.

Наша реализация:

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

И результат выполнения

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