1.md · ikoHSE/sc-lectures · git.iko.soy

git.iko.soy/ikoHSE/sc-lectures

on master help sign in

ikoHSE/sc-lectures/1.md

1184 lines 22 kB history raw

1---

2theme: superblack

3author: Ilya Kostyuchenko

4---

6# Функциональное программирование

9:::{.notes}

10Функциональное программирование это не про использование map filter

11reduce. Функциональное программирование это вообще ортогонально к ооп.

12ИМХО проблема с ООП -- наследование (которое тоже ортогонально к ООП)

13-- нет разграничения между абстракцией и реализацией. и вообще

14обзывание это функциональным программированием -- не совсем правильно.

15то, что мы сейчас будем пытаться сделать -- сделать код более

16переиспользуемым. сделать наши данные максимально тупыми =>

17переиспользуемыми. пытаться комбинировать слишком умные куски -- не

18получится -- слишком сложно. мы хотим сделать простые куски, которые

19просто комбинировать и еще чтобы компилятор проверял эти наши комбинации

20на валидность.

21:::

23---

25<section data-background="images/synthwave.jpeg">

26<h1>Программировать можно без боли</h1>

27</section>

29---

31Функциональное программирование -- метапрограммирование над эффектами.

33---

35## Эффекты?

37```{ .java .fragment }

38class Cafe {

39 Coffee buyCoffee(CreditCard cc, Payments p) {

40 Coffee cup = new Coffee();

41 p.charge(cc, cup.price);

42 return cup;

43 }

45```

47---

49![](images/coffee-with-effects.png){width=450}

51---

53```{ .java }

54class Cafe {

55 Pair<Coffee, Charge> buyCoffee(CreditCard cc) {

56 Coffee cup = new Coffee();

57 return new Pair(cup, cup.price);

58 }

60```

62---

64<table>

65 <tr>

66 <td>

67 ![](images/coffee-without-effects.png){width=450}

68 </td>

69 <td>

70 ![](images/coffee-without-effects-list.png){width=450 .fragment}

71 </td>

72 </tr>

73</table>

76---

78Функциональное программирование:

80> функции -- это тоже данные.

82`Int -> Bool` (функция) -- ровно такие же данные как и `Int`. Их также

83можно складывать в структуры, передавать как аргументы и т. п.

85---

87# нотация

89---

91<table width="100%">

92 <tr>

93 <td>

94 ```java

95 int x;

96 ```

97 </td>

98 <td>

99 ```haskell

100 x :: Int

101 ```

102 </td>

103 </tr>

104 <tr class="fragment">

105 <td>

106 ```java

107 int f(int x)

108 ```

109 </td>

110 <td>

111 ```haskell

112 f :: Int -> Int

113 ```

114 </td>

115 </tr>

116 <tr class="fragment">

117 <td>

118 ```java

119 static <T> T f(T x)

120 ```

121 </td>

122 <td>

123 ```haskell

124 f :: a -> a

125 ```

126 </td>

127 </tr>

128</table>

130---

132<table width="100%">

133 <tr>

134 <td>

135 ```java

136 static <T> T f(T x)

137 ```

138 </td>

139 <td>

140 ```haskell

141 f :: a -> a

142 ```

143 </td>

144 </tr>

145 <tr>

146 <td class="fragment">

147 ```java

148 f(x);

149 ```

150 </td>

151 <td class="fragment">

152 ```haskell

153 f x

154 ```

155 </td>

156 </tr>

157 <tr class="fragment">

158 <td>

159 ```java

160 f(x, y);

161 ```

162 </td>

163 <td>

164 ```{.fragment .haskell}

165 f x y

166 ```

168 ```{.fragment .haskell}

169 f x y = (f x) y

170 ```

171 </td>

172 </td>

173 </tr>

174</table>

176:::{.notes}

177Left-associative

178Currying

179:::

181---

183<table width="100%">

184 <tr>

185 <td>

186 ```java

187 static <T> T f(T x)

188 static <T> T g(T x)

189 ```

190 </td>

191 <td>

192 ```haskell

193 f :: a -> a

194 g :: a -> a

195 ```

196 </td>

197 </tr>

198 <tr>

199 <td class="fragment">

200 ```java

201 f(g(x));

202 g(f(x));

203 ```

204 </td>

205 <td class="fragment">

206 ```haskell

207 f (g x)

208 g (f x)

209 ```

210 </td>

211 </tr>

212</table>

214---

216# Композиция

218---

220```haskell

221f :: a -> a

222g :: a -> a

223```

225``` {.fragment .haskell}

226f (g x)

227```

229``` {.fragment .haskell}

230(f . g) x == f (g x)

231```

233``` {.fragment .haskell}

234h = f . g

235h x == f (g x)

236```

238---

240```haskell

241f :: a -> a

242g :: a -> a

243```

245```haskell

246h :: a -> a

247h = f . g

248```

250```{ .haskell .fragment }

251f x = x * 2

252g x = x - 3

254(f . g) 5

255-- 4

256```

258

260:::{.notes}

261моноид -- у тебя есть две штуки одного типа и ты можешь получить еще

262одну штуку такого же типа. Это очень простой способ рождения сложности

263из простоты причем тип h выводится из определения. Нам его указывать не

264надо. если у нас изначальные маленькие кусочки хорошо описаны, то

265порожденные большие кусочки будут автоматически хорошо описанными.

266:::

268<!-- ---

270## Моноид

272[Бинарная асоциативная операция]{.fragment}

274```{.fragment .haskell}

275(.) :: (a -> a) -> (a -> a) -> (a -> a)

276```

278[Нейтральный элемент]{.fragment}

280```{.fragment .haskell}

281id :: a -> a

282id x = x

283``` -->

285---

287# Haskell

289---

291### Чисто функциональный

293Все что функция может сделать -- посмотреть на свои аргументы это

294вернуть значение.

296:::{.notes}

297Нельзя просто произвольно распечатать строку в консоль, нельзя просто

298произвольно отправить запрос на бд, нельзя просто произвольно изменить

299глобальную переменную.

300:::

302---

304### Referential transparency

306##### (Любую константу можно заменить на само значение)

308```{.java .fragment}

309int x = 8;

310int y = x++;

311System.out.println(y + " might be the same as " + y);

312```

314```{.java .fragment}

315int x = 8;

316System.out.println(x++ + " might be the same as " + x++);

317```

319:::notes

320Сильно упрощает рефакторинг и понимание кода.

321:::

323---

325# Immuatble

327## Совсем immutable

329Можно не думать о порядке выражений.

331---

333### Нет переменных, циклов и условных переходов

335[Зато есть константы и нормальная рекурсия (А переходов вообще нет)]{.fragment}

337---

339### Очень ленивый

341```{.haskell .fragment}

342xs = [4, 1, 3, 2]

343xs' = sort xs

344print xs

345```

347:::fragment

348`xs'` не нужен чтобы распечатать `xs`, поэтому сортироваться ничто

349не будет. (Зачем делать то, что можно не делать)

350:::

352---

354Если хотите быстро и просто потыкаться, тут есть интерктивная штука:

356[haskell.org](https://www.haskell.org)

358---

360# Синтаксис

362---

364# Функции

366---

368```{ .haskell }

369add2 :: Int -> Int

370add2 x = x + 2

371````

373Все функции и константы всегда обозначаются словами с маленькой буквы

374без пробелов.

376(Константы это просто функции с нулем аргументов.)

378:::notes

379Мы буквально говорим что функция на таком-то аргументе равна чему-то.

380:::

382---

384## Pattern matching

386```haskell

387fixBuz :: Int -> String

388fixBuz 3 = "Fiz"

389fixBuz 5 = "Buz"

390fixBuz 15 = "FizBuz"

391fixBuz _ = "Some other number"

392```

394Так матчить можно произвольные структуры произвольного уровня

395вложенности.

397`_` -- специальное название константы, которое говорит

398что вам все равно что в ней лежит.

400:::notes

401функции объявляются в несколькро строк. Первая -- обьявленик типа

402функции, а последующие -- реализация. В общем случае тип можно не

403указывать, но указывать тип у высказыванй на самом верхнем уровне (не

404вложенные) считается хорошим тоном и улучшает выведение типов и ошибки

405компиляции. У функции может быть несколько реализаций: какая из них

406вызовется зависит от значений передаваемых аргументов. матчинг

407произхводится сверху вниз. если в аргемантах написано слово с маленькой

408буквы, то значение аргумента биндится на эту константу.

409:::

411---

413## Структуры

415---

417## Произведение типов

419##### (обычные поля структур)

421:::notes

422После констрктора можно укзать существующие типы, которые в нем

423храняться.

424:::

426```haskell

427data PersonType = Person String Int

428```

430```{.haskell .fragment}

431vasya :: PersonType

432vasya = Person "Vasya" 8

433-- тип можно не укзывать

434petya = Person "Petya" 5

435```

437```{.haskell .fragment}

438getName :: PersonType -> String

439getName (Person name _) = name

440```

442```{.haskell .fragment}

443greetPerson :: PersonType -> String

444greetPerson p = "Hello, " ++ getName p

445```

447```{.haskell .fragment}

448greetPerson petya

449-- "Hello, Petya"

450```

452---

454```{ .haskell }

455vasya = Person "Vasya" 8

456petya = Person "Petya" 5

457```

459```{ .haskell .fragment }

460matchVasya :: PersonType -> Bool

461matchVasya (Person "Vasya" _) = True

462matchVasya _ = False

463```

465```{ .haskell .fragment }

466matchVasya vasya

467-- True

469matchVasya petya

470-- False

471```

474---

476```haskell

477data Foo = Bar

479qux :: Foo

480qux = Bar

481```

483`Foo` -- тип структуры. `Bar` -- конструктор структуры.

485Тут у `Foo` всего одно значение `Bar`.

487---

489## Еще немного функций

491```{ .haskell .fragment }

492greetPerson :: PersonType -> String

493greetPerson p = "Hello, " ++ getName p

494```

496```{.fragment .haskell }

497greetPerson :: PersonType -> String

498greetPerson p = "Hello, " ++ name

499 where

500 name = getName p

501```

503```{.fragment .haskell }

504greetPerson :: PersonType -> String

505greetPerson p = "Hello, " ++ name

506 where

507 getName' (Person name _) = name

508 name = getName' p

509```

511---

513```{ .haskell }

514data PersonType = Person String Int

516getName :: PersonType -> String

517getName (Person name _) = name

518```

520```{.fragment .haskell }

521greetName :: String -> String

522greetName name = "Hello, " ++ name

523```

525```{.fragment .haskell }

526greetPerson :: PersonType -> String

527greetPerson p = greetName (getName p)

528```

530```{.fragment .haskell }

531greetPerson :: PersonType -> String

532greetPerson = greetName . getName

533```

535```{.fragment .haskell }

536greetPerson petya

537-- "Hello, Petya"

538```

540```{.fragment .haskell }

541(greetName . getName) petya

542-- "Hello, Petya"

543```

545---

547## Суммы типов

549:::notes

550Функции нескольких аргументов -- странный синтаксис -- потом расскажу. А пока используем тюпли!

552В большинстве других языков этого нет и используются всякие странные кодирования типо нулевые указатели, и никто не просит тебя их проверять, что очень плохо.

553:::

555```{ .fragment .haskell }

556data Bool = False | True

557```

559```{ .fragment .haskell }

560x :: Bool

561x = True

562y = False

563```

565```{ .fragment .haskell }

566ifThenElse :: (Bool, a, a) -> a

567```

569```{ .fragment .haskell }

570ifThenElse (True, a, _) = a

571ifThenElse (False, _, b) = b

572```

574```{ .fragment .haskell }

575ifThenElse (True, "Hello", "World")

576-- "Hello"

577```

579```{ .fragment .haskell }

580ifThenElse (False, "Hello", "World")

581-- "World"

582```

584---

586```{ .haskell }

587data CircleType = Circle Double Double Double

588data RectangleType = Rectangle Double Double Double Double

589```

591```{ .fragment .haskell }

592data Shape =

593 CircleShape CircleType | RectangleShape RectangleType

594```

596```{ .fragment .haskell }

597surface :: Shape -> Double

598```

600```{ .fragment .haskell }

601surface (CircleShape (Circle _ _ r)) =

602 pi * r ^ 2

603```

605```{ .fragment .haskell }

606surface (RectangleShape (Rectangle x1 y1 x2 y2)) =

607 (abs (x2 - x1)) * (abs (y2 - y1))

608```

610```{ .fragment .haskell }

611shape = CircleShape (Circle 0 0 2)

612surface shape

613-- 12.566370614359172

614```

616```{ .fragment .haskell }

617otherShape = RectangleShape (Rectangle 1 2 3 4)

618surface otherShape

619-- 4.0

620```

622---

624# И еще немного функций

626---

628## Лямбда-выражения

630```{ .haskell .fragment }

631add8 :: Int -> Int

632```

634```{ .haskell .fragment }

635add8 x = x + 8

636```

638```{ .haskell .fragment }

639add8 = \x -> x + 8

640```

642[λ -- `\` (λ печатать тяжело)]{.fragment}

644```{ .haskell .fragment }

645foo :: (Int -> Int) -> Int

646```

648```{ .haskell .fragment }

649foo add8

650```

652```{ .haskell .fragment }

653foo (\x -> x + 8)

654```

656---

658### Давайте придумаем синтаксис для функции нескольких аргументов!

660---

662```{ .haskell }

663x, y :: Int

664x = 42

665y = 69

666```

668```{ .haskell .fragment }

669xPlusY :: Int

670xPlusY = add x y

671```

673[Применение функции -- лево-ассоциативно]{.fragment}

675```{ .haskell .fragment }

676xPlusY = (add x) y

677```

679```{ .haskell .fragment }

680xPlusY = f y

681f = add x

682```

684```{ .haskell .fragment }

685f :: Int -> Int

686```

688```{ .haskell .fragment }

689add :: Int -> (Int -> Int)

690```

692---

694```{ .haskell }

695add :: Int -> (Int -> Int)

696```

698[Тип `->` -- право-ассоциативный]{.fragment}

700```{ .haskell .fragment }

701add :: Int -> Int -> Int

702```

704```{ .haskell .fragment }

705add a b = a + b

706```

708```{ .haskell .fragment }

709add = \a b -> a + b

710```

712---

714Любая функция берет строго один аргумент.

716Функция нескольких аргументов все равно берет строго одтн аргумент и

717возвращает функцию, которая берет следующий.

719*(И из-за того, что применение функции лево-ассоциативно, вызов таких не

720трубует особого синтаксиса.)*

722---

724### Currying

726```{ .haskell .fragment }

727add :: Int -> Int -> Int

728add a b = a + b

729```

731```{ .haskell .fragment }

732add8 :: Int -> Int

733```

735```{ .haskell .fragment }

736add :: Int -> (Int -> Int)

737```

739```{ .haskell .fragment }

740add8 = add 8

741```

743```{ .haskell .fragment }

744add8 3

745-- 11

746```

748---

750### Funny fact

752[Оператор (например `+`) -- функция, название которой не содержит буквы и цифры.]{.fragment}

754```{ .haskell .fragment }

755x +&+ y = x + y

756```

758```{ .haskell .fragment }

7598 +&+ 9

760-- 17

761```

763---

765### Funny fact 2

767[Оператор можно превратить в функцию, окружив его скобками.]{.fragment}

769```{ .haskell .fragment }

7708 +&+ 9

771-- 17

772```

774```{ .haskell .fragment }

775(+&+) 8 9

776-- 17

777```

779```{ .haskell .fragment }

780add :: Int -> Int -> Int

781add x y = x + y

782```

784```{ .haskell .fragment }

785add = (+&+)

786```

788```{ .haskell .fragment }

789add = (+)

790```

792---

794### Funny fact 3

796[Функцию можно превратить в оператор, окружив ее обратными кавычками.]{.fragment}

799```{ .haskell .fragment }

800add :: Int -> Int -> Int

801add x y = x + y

802```

804```{ .haskell .fragment }

805add 8 9

806-- 17

807```

809```{ .haskell .fragment }

8108 `add` 9

811-- 17

812```

814---

816# Список

818---

820### Односвязный список

822```{ .haskell .fragment }

823data IntList = Nil | Cons Int IntList

824```

826```{ .haskell .fragment }

827Cons :: Int -> IntList -> IntList

828Nil :: IntList

829```

831```{ .haskell .fragment }

832nums :: IntList

833nums = 1 `Cons` (2 `Cons` (3 `Cons` Nil))

834```

836```{ .haskell .fragment }

837sum :: IntList -> Int

838```

840```{ .haskell .fragment }

841sum (Cons x xs) = x + sum xs

842```

844```{ .haskell .fragment }

845sum Nil = 0

846sum (Cons x xs) = x + sum xs

847```

849```{ .haskell .fragment }

850sum nums

851-- 6

852```

854---

856```{ .haskell }

857take :: Int -> IntList -> IntList

858```

860```{ .haskell .fragment }

861take _ Nil = Nil

862take 0 _ = Nil

863take n (Cons x xs) = Cons x (take (n - 1) xs)

864```

866```{ .haskell .fragment }

867nums :: IntList

868nums = 1 `Cons` (2 `Cons` (3 `Cons` Nil))

869```

871```{ .haskell .fragment }

872take 2 nums

873-- Cons 1 (Cons 2 Nil)

874take 1029 nums

875-- Cons 1 (Cons 2 (Cons 3 Nil))

876take 0 nums

877-- Nil

878```

880---

882```{ .haskell }

883repeat :: Int -> IntList

884```

886```{ .haskell .fragment }

887repeat n = Cons n (repeat n)

888```

890```{ .haskell .fragment }

891repeat 8

892-- Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (...

893```

895```{ .haskell .fragment }

896(take 3 . repeat) 8

897-- Cons 8 (Cons 8 (Cons 8 Nil))

898```

900```{ .haskell .fragment }

901(sum . take 3 . repeat) 8

902-- 24

903```

905---

907<table width="100%">

908 <tr>

909 <td>

910 Наша самодеятельность

911 </td>

912 <td>

913 В стандартной библиотеке

914 </td>

915 </tr>

916 <tr class="fragment">

917 <td>

918 ```haskell

919 IntList

920 ```

921 </td>

922 <td>

923 ```haskell

924 [Int]

925 ```

926 </td>

927 <tr class="fragment">

928 <td>

929 ```haskell

930 Nil

931 ```

932 </td>

933 <td>

934 ```haskell

935 []

936 ```

937 </td>

938 </tr>

939 <tr class="fragment">

940 <td>

941 ```haskell

942 Cons

943 ```

944 </td>

945 <td>

946 ```haskell

947 :

948 ```

949 </td>

950 </tr>

951 <tr class="fragment">

952 <td>

953 ```haskell

954 Cons 3 (Cons 4 Nil)

955 ```

956 </td>

957 <td>

958 ``` {.fragment .haskell }

959 3 : 4 : []

960 ```

962 ``` {.fragment .haskell }

963 [3, 4]

964```

965 </td>

966 </tr>

967</table>

969---

971```{ .haskell }

972data IntList = Nil | Cons Int IntList

973```

975```{ .haskell .fragment }

976data [Int] = [] | Int : [Int]

977```

979---

981`repeat`, `sum` и `take` тоже есть в стандартной библиотеке.

983---

985```{ .haskell }

986repeat 8

987-- [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, ...

988```

990```{ .haskell .fragment }

991[8 ..]

992-- [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

993```

995```{ .haskell .fragment }

996[8 .. 11]

997-- [8, 9, 10, 11]

998```

1000```{ .haskell .fragment }

1001[8 .. 8]

1002-- [8]

1005```{ .haskell .fragment }

1006[8 .. 5]

1007-- []

1012# QuickSort

1016```{ .haskell }

1017quicksort :: [Int] -> [Int]

1020```{ .haskell .fragment}

1021quicksort (x:xs) =

1022 quicksort smaller ++ [x] ++ quicksort larger

1023 where

1024 smaller = filter (< x) xs

1025 larger = filter (>= x) xs

1030```{ .haskell }

1031filter :: (Bool -> Int) -> [Int] -> [Int]

1034```{ .haskell .fragment}

1035filter f (x:xs) =

1036 if f x

1037 then x:(filter f xs)

1038 else filter f xs

1041```{ .haskell .fragment}

1042filter _ [] = []

1043filter f (x:xs) =

1044 if f x

1045 then filter f xs

1046 else x:(filter f xs)

1051```{ .haskell }

1052quicksort :: [Int] -> [Int]

1053quicksort (x:xs) =

1054 quicksort smaller ++ [x] ++ quicksort larger

1055 where

1056 smaller = filter (< x) xs

1057 larger = filter (>= x) xs

1058 filter _ [] = []

1059 filter f (x:xs) =

1060 if f x

1061 then filter f xs

1062 else x:(filter f xs)

1067```{ .haskell }

1068quicksort :: [Int] -> [Int]

1069quicksort [] = []

1070quicksort (x:xs) =

1071 quicksort smaller ++ [x] ++ quicksort larger

1072 where

1073 smaller = filter (< x) xs

1074 larger = filter (>= x) xs

1075 filter _ [] = []

1076 filter f (x:xs) =

1077 if f x

1078 then filter f xs

1079 else x:(filter f xs)

1082```{ .haskell .fragment}

1083quicksort [2, 1, 3, 4]

1084-- [1, 2, 3, 4]

1089`filter` тоже есть в стандартной библиотеке.

1093# Еще немного структур

1097## Параметрический полиморфизм

1099### (Дженерики)

1101```{ .haskell .fragment }

1102data IntList = Cons Int IntList | Nil

1105:::notes

1106Мы научиоись делать список интов. А что если мы хотим сделать просто список. Чего-нибудь.

1109```{ .haskell .fragment }

1110data List a = Cons a (List a) | Nil

1113```{ .java .fragment }

1114class List<T> { ...

1117```{ .haskell .fragment }

1118ints :: List Int

1119ints = Cons 1 (Cons 2 (Cons 3 Nil))

1122```{ .haskell .fragment }

1123-- Типы как всегда можно не писать

1124strings :: List String

1125strings = Cons "one" (Cons "two" (Cons "three" Nil))

1130```{ .haskell }

1131things = Cons "one" (Cons 2 Nil)

1134```fragment

1135 • Couldn't match type ‘Int’ with ‘String’

1136 Expected type: List String

1137 Actual type: List Int

1138 |

113910 | things = Cons "one" (Cons 2 Nil)

1140 | ^^^^^^^^^^^^

1143```{ .haskell .fragment }

1144data List a = Cons a (List a) | Nil

1147[`a` должен всегда быть `a`.]{.fragment}

1151```{ .haskell }

1152take :: Int -> IntList -> IntList

1153take _ Nil = Nil

1154take 0 _ = Nil

1155take n (Cons x xs) = Cons x (take (n - 1) xs)

1158```{ .haskell .fragment }

1159take :: Int -> List a -> List a

1160take _ Nil = Nil

1161take 0 _ = Nil

1162take n (Cons x xs) = Cons x (take (n - 1) xs)

1165:::notes

1166Поменялся только тип!

1171# Где и как смотреть "стандартную библиотеку"

11751. [Hackage](https://hackage.haskell.org/package/base)

1177 (Там вам нужен только пакет `base`. Ссылка ведет прямо на него.)

1178 Еще если там нажать `s`, то будет поиск.

11802. [Hoogle](https://hoogle.haskell.org)

1182 Это поиск по типам. Например: `Int -> [Int] -> [Int]` (Тут

1183 вам опять же нужен только пакет `base`. Нужно чтобы справа было

1184 \"package:base\".)