мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия
Предыдущая версия
Следующая версияСледующая версия справа и слева
haskell [02/07/2018 14:39] – [3.6 Замечания о скорости работы списочных функций] vlasovhaskell [22/10/2018 01:50] – [5.6 Классы типов и АТД] vlasov
Строка 25: Строка 25:
   - [[http://habrahabr.ru/post/193722/|Haskell в продакте: Отчёт менеджера проекта]]   - [[http://habrahabr.ru/post/193722/|Haskell в продакте: Отчёт менеджера проекта]]
   - [[http://ru-lambda.livejournal.com/3212.html|Haskell: что это такое]]   - [[http://ru-lambda.livejournal.com/3212.html|Haskell: что это такое]]
-  - [[http://dev.by/blogs/main/esli-by-yazyki-programmirovaniya-byli-mashinami|Если бы языки программирования были машинами (шуточное :-))]]+  - [[https://events.dev.by/lenta/main/esli-by-yazyki-programmirovaniya-byli-mashinami|Если бы языки программирования были машинами]], [[https://events.dev.by/lenta/main/esli-by-yazyki-programmirovaniya-byli-religiyami|Если бы языки программирования были религиями]]  (шуточное :-))
   - [[http://anton-k.github.io/ru-haskell-book/book/home.html|Учебник по Haskell. Антон Холомьёв]] (пока лучший учебник на русском!!)   - [[http://anton-k.github.io/ru-haskell-book/book/home.html|Учебник по Haskell. Антон Холомьёв]] (пока лучший учебник на русском!!)
   - [[https://www.ohaskell.guide/|Шевченко Д. О Haskell по-человечески]]   - [[https://www.ohaskell.guide/|Шевченко Д. О Haskell по-человечески]]
Строка 40: Строка 40:
 **Полезные команды** в ghci: **Полезные команды** в ghci:
  
-:q -- выйти из оболочки;+'':q'' -- выйти из оболочки;
  
-:l <имя программы> -- загрузить программу с указанным именем. Программа может не содержать модуля Main, а только определения функций (что мы и будем делать первое время);+'':l <имя программы>'' -- загрузить программу с указанным именем. Программа может не содержать модуля Main, а только определения функций (что мы и будем делать первое время);
  
-:r -- перегрузить текущий модуль;+'':r'' -- перегрузить текущий модуль;
  
-:t <имя функции> -- напечатать сигнатуру функции;+'':t <имя функции>'' -- напечатать сигнатуру функции;
  
-:i <имя функции> -- напечатать сигнатуру функции и указать, в каком файле была определена данная функция;+'':i <имя функции>'' -- напечатать сигнатуру функции и указать, в каком файле была определена данная функция;
  
 Кроме того, надо знать, что выражения в оболочке интерпретатора можно сразу вычислять. Кроме того, надо знать, что выражения в оболочке интерпретатора можно сразу вычислять.
-Наберем 2 + 2 и нажмем Enter, или наберем abs (-2) и нажмем Enter, и т.д.+Наберем 2 + 2 и нажмем Enter, или наберем ''abs (-2)'' и нажмем Enter, и т.д.
  
 Новые функции (пользовательские) можно задавать, как уже писалось выше, в отдельных файлах и подгружать по мере необходимости, либо сразу определять в оболочке: Новые функции (пользовательские) можно задавать, как уже писалось выше, в отдельных файлах и подгружать по мере необходимости, либо сразу определять в оболочке:
Строка 58: Строка 58:
 > let {f :: Int -> Int; f n = n * 2} > let {f :: Int -> Int; f n = n * 2}
 </code> </code>
 +
 +Отметим, что в версиях ''ghc/ghci'', начиная с 8.0.2, ключевое слово ''let'' писать необязательно.
  
 Многострочные записи делают следующим образом: Многострочные записи делают следующим образом:
Строка 76: Строка 78:
 </code> </code>
  
-Для просмотра тех или иных значений функции f можно попробовать набрать f 4, а для просмотра произвольного значения foo набрать show foo.+Для просмотра тех или иных значений функции ''f'' можно попробовать набрать ''f 4'', а для просмотра произвольного значения ''foo'' набрать ''show foo''.
  
  
Строка 90: Строка 92:
 и мы уже вряд ли сможем посчитать факториал с аргументом более 31. и мы уже вряд ли сможем посчитать факториал с аргументом более 31.
  
-Остальной код задан в виде уравнений, которые через сопоставление с образцами (pattern matching) задают нужное значение функции. Образцы рассматриваются по порядку.  +Остальной код задан в виде уравнений, которые через сопоставление с образцами (pattern matching) задают нужное значение функции. Образцы рассматриваются по порядку. Возможно использование рекурсии при описании функции. При вызове функций им передаются из аргументов выражения, вычисляемые по необходимости и это следует учитывать особенно при программировании рекурсивных функций, так возможен большой расход оперативной памяти (частично это как раз преодолевается грамотным использованием так называемой //ленивости вычислений//)
-Возможно использование рекурсии при описании функции. При вызове функций им передается копия аргументов и это следует учитывать особенно при программировании рекурсивных функций, так возможен большой расход оперативной памяти (частично это преодолевается грамотным использованием так называемой //ленивости вычислений//)+
  
 <code haskell> <code haskell>
Строка 136: Строка 137:
 В Haskell возможно описание вычисления функции в В Haskell возможно описание вычисления функции в
 зависимости от условий в более-менее традиционном ключе, для чего зависимости от условий в более-менее традиционном ключе, для чего
-присутствуют операторы if и case. Однако, их применение отлично от+присутствуют операторы ''if'' и ''case''. Однако, их применение отлично от
 аналогичных операторов в императивных языках. (Правильнее их называть аналогичных операторов в императивных языках. (Правильнее их называть
-выражениями с использованием case- и if-then-else-конструкций)+выражениями с использованием ''case-'' и ''if-then-else''-конструкций)
  
 <note>Тем не менее, семантика данного оператора в Haskell похожа на семантику тернарного оператора <note>Тем не менее, семантика данного оператора в Haskell похожа на семантику тернарного оператора
Строка 147: Строка 148:
 </note> </note>
  
-Оператор if предназначен для ветвления вычислительного процесса в +Ключевое слово ''if'' предназначено для указание на ветвление вычислительного процесса в 
-зависимости от условия булевского типа. Части then и else обязательны, они+зависимости от условия булевского типа. Части ''then'' и ''else'' обязательны, они
 в отличие от императивного аналога задают не порядок действий, а функции, в отличие от императивного аналога задают не порядок действий, а функции,
-которые возвращают результат для задаваемой функции. Данный оператор является +которые возвращают результат для задаваемой функции. Данное выражение является 
-частным, более простым случаем применения оператора case. +частным, более простым случаем применения выражений с ''case''
  
 Иными словами, условное выражение вида Иными словами, условное выражение вида
Строка 167: Строка 168:
 </code> </code>
  
-Рассмотрим более сложные примеры с case-выражениями:+Рассмотрим более сложные примеры с ''case''-выражениями:
  
 <code> <code>
Строка 182: Строка 183:
 </code> </code>
  
-Последний пример является комбинацией использования case-выражения с <<охраной>>+Последний пример является комбинацией использования ''case''-выражения с <<охраной>>
 для предотвращения применения функции для отрицательных аргументов. для предотвращения применения функции для отрицательных аргументов.
  
 Стоит также упомянуть, что задание функций уравнениями также возможно  Стоит также упомянуть, что задание функций уравнениями также возможно 
-рассматривать как упрощенную запись с соответствующими case-выражениями.+рассматривать как упрощенную запись с соответствующими ''case''-выражениями.
  
-**__Упражнение__.** Задать функцию sign(x) из предыдущего упражнения, используя ветвления с if и с case.+**__Упражнение__.** Задать функцию ''sign(x)'' из предыдущего упражнения, используя ветвления с ''if'' и ''с case''.
  
-==== 2.2 Карринг и лябда-абстракция ====+==== 2.2 Карринг и лямбда-абстракция ====
  
  
-**Карринг.** Отметим, что в Haskell функции f'(x,y)=x+y и <html>f''&nbsp;x&nbsp;y&nbsp;=&nbsp;x+y</html> -- разные по сути функции. Если f'(x,y) -- это функция от одного переменного (кортежа или вектора (x,y)), то <html>f''&nbsp;x&nbsp;y</html> -- это функция от двух переменных. Тип у них тоже будет разный, и это можно будет узнать командой :t.+**Карринг.** Отметим, что в Haskell функции ''f'(x,y)=x+y'' и ''f%%''%% x y = x+y'' --- разные по сути функции. Если ''f'(x,y)'' --- это функция от одного переменного (кортежа или вектора ''(x,y)''), то ''f%%''%% x y = x+y'' --- это функция от двух переменных. Тип у них тоже будет разный, и это можно будет узнать командой '':t''.
  
 Для чего нужен карринг и такие сложности? С теоретической точки зрения, например, карринг позволяет сводить рассмотрение функций от многих переменных к функциям одной переменной. На практике карринг позволяет задавать функции неполным применением, делать так называемые сечения.  Для чего нужен карринг и такие сложности? С теоретической точки зрения, например, карринг позволяет сводить рассмотрение функций от многих переменных к функциям одной переменной. На практике карринг позволяет задавать функции неполным применением, делать так называемые сечения. 
  
-Рассмотрим выше заданную функцию <html>f''&nbsp;x&nbsp;y</html>, назовем ее более логично <html>add&nbsp;x&nbsp;y</html>.+Рассмотрим выше заданную функцию ''f%%''%% x y'', назовем ее более логично ''add x y''.
  
 <code haskell> <code haskell>
Строка 203: Строка 204:
 </code> </code>
  
-Тогда мы легко можем задать частный случай сложения, функцию-инкремент add1 t = 1+t просто частичным применением уже заданной функции add+Тогда мы легко можем задать частный случай сложения, функцию-инкремент ''add1 t = 1+t'' просто частичным применением уже заданной функции ''add''
  
 <code haskell> <code haskell>
Строка 233: Строка 234:
  
 Если мы подставим в качестве аргумента 4, то увидим разницу значений Если мы подставим в качестве аргумента 4, то увидим разницу значений
-функций <html> duo' и duo''.</html>+функций ''duo%%'%%'' и ''duo%%''%%''.
  
-В следующем, более простом примере, функции padd1 и padd3 эквивалентны, хотя заданы+В следующем, более простом примере, функции ''padd1'' и ''padd3'' эквивалентны, хотя заданы
 различными способами (можно запустить функции для проверки с аргументами 4 и 5): различными способами (можно запустить функции для проверки с аргументами 4 и 5):
  
Строка 252: Строка 253:
 качестве второго аргумента. Например, мы могли бы передать этой функции уже качестве второго аргумента. Например, мы могли бы передать этой функции уже
 готовую функцию, а могли бы задать ее <<на лету>>. Для просмотра результатов готовую функцию, а могли бы задать ее <<на лету>>. Для просмотра результатов
-в ghci наберите show l1 и show l2.+в ''ghci'' наберите ''show l1'' и ''show l2''.
  
 <code haskell> <code haskell>
-l1 = map abs [-1, 2, -4.2] +l1 = map abs [(-1), 2, (-4.2)
-l2 = map (\x -> if x >= 0 then x else negate x) [-1, 2, -4.2]+l2 = map (\x -> if x >= 0 then x else negate x) [(-1), 2, (-4.2)]
 </code> </code>
  
Строка 262: Строка 263:
  
 <code haskell> <code haskell>
-l3 = map ((\x -> if x >= 0 then x else negate x)::(Double -> Double) [-1, 2, -4.2]+l3 =  
 +  map ((\x -> if x >= 0  
 +               then x  
 +               else negate x)::(Double -> Double))  
 +    [(-1), 2, (-4.2)]
 </code> </code>
- 
  
 ==== 2.3 Замыкания (локальные определения)==== ==== 2.3 Замыкания (локальные определения)====
Строка 286: Строка 290:
 применении они очень похожи! применении они очень похожи!
  
-<code>+<code haskell>
 roots' a b c = (x1,x2) where roots' a b c = (x1,x2) where
  d = b^2 - 4*a*c  d = b^2 - 4*a*c
Строка 298: Строка 302:
 При упрощённом подходе мы не отслеживаем случаи, когда старший коэффициент будет равен нулю или дискриминант будет отрицательный. Однако в некоторых случаях это будет приводить к аварийному останову программы в процессе вычисления. Мы можем эти случаи отследить заранее и реагировать, например, более осмысленными предупреждениями: При упрощённом подходе мы не отслеживаем случаи, когда старший коэффициент будет равен нулю или дискриминант будет отрицательный. Однако в некоторых случаях это будет приводить к аварийному останову программы в процессе вычисления. Мы можем эти случаи отследить заранее и реагировать, например, более осмысленными предупреждениями:
  
-<code>+<code haskell>
 roots' a b c | ((a == 0) && (b == 0)) = error "No roots at all!" roots' a b c | ((a == 0) && (b == 0)) = error "No roots at all!"
              | ((a == 0) && (b /= 0)) =  (x,x)  -- let x = -c/b in (x,x)                | ((a == 0) && (b /= 0)) =  (x,x)  -- let x = -c/b in (x,x)  
Строка 379: Строка 383:
 </note> </note>
  
-Вот версия более простого и понятного примера:+<note> 
 +Как показали дальнейшие изыскания, изначальное поведение было обусловлено ещё одной проблемой Haskell, так называемом //ограничением мономорфизма//: 
 +[[https://wiki.haskell.org/Monomorphism_restriction|Monomorphism_restriction]]. В современных версиях ghci это ограничение отключено, но при желании его можно вновь включить и потестировать указанные выше странности: 
 +<code> 
 +Prelude> :set -XMonomorphismRestriction 
 +Prelude> let x = 2 
 +Prelude> x + 2.0 
 + 
 +<interactive>:5:5: error: 
 +    * No instance for (Fractional Integer) 
 +        arising from the literal `2.0' 
 +... 
 +</code> 
 +</note> 
 + 
 + 
 +Вот версия более простого и понятного примера, без странностей ограничения мономорфизма:
  
 <code haskell> <code haskell>
Строка 390: Строка 410:
       In an equation for `it': it = x + y       In an equation for `it': it = x + y
 </code> </code>
-В языках типа Си это соответствовало бы объявлению и инициализации переменных типа Int и Double, а потом совместного их использования в одном арифметическом выражении.+В языках типа Си это соответствовало бы объявлению и инициализации переменных типа int и double, а потом совместного их использования в одном арифметическом выражении.
 ==== 2.6 Использование монады состояния==== ==== 2.6 Использование монады состояния====
  
 Пока без комментариев, вычисление факториала: Пока без комментариев, вычисление факториала:
  
-<code>+<code haskell>
 import Control.Monad.State import Control.Monad.State
  
-fact' :: Integer -> State Integer Integer -- тип состояния - Int, тип результата - тоже Int+fact' :: Integer -> State Integer Integer  
 +-- тип состояния - Integer, тип результата - тоже Integer
 fact' 0 = do fact' 0 = do
     acc <- get -- получаем накопленный результат     acc <- get -- получаем накопленный результат
Строка 407: Строка 428:
     fact' (n - 1) -- продолжаем вычисление факториала     fact' (n - 1) -- продолжаем вычисление факториала
  
--- fact :: Int -> Int+-- fact :: Integer -> Integer
 fact n = fst $ runState (fact' n) 1 -- начальное значение состояния = 1 fact n = fst $ runState (fact' n) 1 -- начальное значение состояния = 1
 </code> </code>
Строка 415: Строка 436:
 **__Задания к уроку__** **__Задания к уроку__**
  
-1. Используя примеры из урока, написать код и исполнить его в ghci, проверить тип полученных функций.+1. Используя примеры из урока, написать код и исполнить его в ''ghci'', проверить тип полученных функций.
    
-2. Сделать тоже самое в отдельном файл и загрузить его в ghci с помощью команды :l.+2. Сделать тоже самое в отдельном файл и загрузить его в ''ghci'' с помощью команды '':l''.
  
-3. Написать код для функций <nowiki>min, max, |x|, [x]</nowiki>, среднего арифметического двух чисел и списка чисел, многочленов, рациональных функций и др. числовых функций. +3. Написать код для функций ''min, max, |x|, [x]'', среднего арифметического двух чисел и списка чисел, многочленов, рациональных функций и др. числовых функций. 
  
 ===== Урок 3. Списки как типы ===== ===== Урок 3. Списки как типы =====
Строка 433: Строка 454:
 (везде ниже ''xs'', ''ys'' и т.п. обозначают список) (везде ниже ''xs'', ''ys'' и т.п. обозначают список)
  
-  * ''xs !! n'' --- получим n-й произвольный элемент списка xs, начиная с нулевого; +  * ''xs !! n'' --- получим n-й произвольный элемент списка ''xs'', начиная с нулевого; 
-  * ''head xs'' --- вернет //первый// элемент списка xs; +  * ''head xs'' --- вернет //первый// элемент списка ''xs''
-  * ''last xs'' --- вернет //последний// элемент списка xs; +  * ''last xs'' --- вернет //последний// элемент списка ''xs''
-  * ''tail xs'' --- вернет список xs без //первого// элемента; +  * ''tail xs'' --- вернет список ''xs'' без //первого// элемента; 
-  * ''init xs'' --- вернет список xs без //последнего// элемента;+  * ''init xs'' --- вернет список ''xs'' без //последнего// элемента;
   * ''reverse xs'' --- вернет обратный список;   * ''reverse xs'' --- вернет обратный список;
-  * ''length xs''  --- вернет длину списка xs;+  * ''length xs''  --- вернет длину списка ''xs'';
  
 ==== 3.2 Добавление к списку === ==== 3.2 Добавление к списку ===
Строка 563: Строка 584:
  
 **Задача 1.** Написать код, генерирующий потенциально бесконечный  **Задача 1.** Написать код, генерирующий потенциально бесконечный 
-список чисел Фиббоначи. Рассмотреть возможности "лобового решения" с бинарной рекурсией и оптимизации. (см. [[haskell:fibb|варианты решения]])+список чисел Фибоначчи. Рассмотреть возможности "лобового решения" с бинарной рекурсией и оптимизации. (см. [[haskell:fibb|варианты решения]])
  
  
Строка 578: Строка 599:
  
 <code haskell> <code haskell>
-import qualiаfied Data.List+import qualified Data.List
 </code> </code>
  
Строка 594: Строка 615:
   * ''union xs ys'' -- возвращает объединение двух списков;   * ''union xs ys'' -- возвращает объединение двух списков;
   * ''intersect xs ys'' -- возвращает пересечение двух списков;         * ''intersect xs ys'' -- возвращает пересечение двух списков;      
-  * ''<nowiki>(\\)</nowiki>'' -- возвращает разность (неассоциативную) двух списков, таким образом: ''<nowiki>(xs ++ ys) \\ xs == ys</nowiki>'';+  * ''<nowiki>(\\)</nowiki>'' -- возвращает разность (неассоциативную) двух списков, таким образом: ''<nowiki>(xs ++ ys) \\ xs == ys</nowiki>'' (если нет общих элементов);
   * ''elem x xs'' -- предикат, возвращающий истину, если элемент ''x'' принадлежит списку ''xs'';   * ''elem x xs'' -- предикат, возвращающий истину, если элемент ''x'' принадлежит списку ''xs'';
   * ''tails xs'' -- функция возвращает список хвостов данного списка, напр.:<code haskell>tails "abc" == ["abc", "bc", "c", ""]</code>   * ''tails xs'' -- функция возвращает список хвостов данного списка, напр.:<code haskell>tails "abc" == ["abc", "bc", "c", ""]</code>
Строка 699: Строка 720:
 </code> </code>
  
 +
 +Более детально об импорте модулей можно прочитать тут: [[https://wiki.haskell.org/Import|wiki.haskell: Import]].
 ==== 4.2 Экспорт модулей ==== ==== 4.2 Экспорт модулей ====
  
Строка 801: Строка 824:
 При сопоставлении с образцом будем писать: При сопоставлении с образцом будем писать:
  
-<code haskell>+<code>
 absPoint' (Point { pointx = x, pointy =y } ) = sqrt (x^2 + y^2) absPoint' (Point { pointx = x, pointy =y } ) = sqrt (x^2 + y^2)
 </code> </code>
Строка 807: Строка 830:
 или или
  
-<code haskell>+<code>
 absPoint'' (Point x y) = sqrt (x^2 + y^2) absPoint'' (Point x y) = sqrt (x^2 + y^2)
 </code> </code>
Строка 1046: Строка 1069:
 (<>) ::  MyAlg -> MyAlg -> MyAlg (<>) ::  MyAlg -> MyAlg -> MyAlg
 O <> x = x O <> x = x
-n <>x = next  (prev n <> x)+n <> x = next  (prev n <> x)
  
 (><) ::  MyAlg -> MyAlg -> MyAlg (><) ::  MyAlg -> MyAlg -> MyAlg
Строка 1156: Строка 1179:
  
  
-**Задание.** Создать собственный класс Logic с операциями &&&, |||, neg --- описывающие сигнатуры и взаимосвязи конъюнкции, дизъюнкции и отрицании. Затем создать тип данных OurBool и воплощения для него класса Logic.+**Задание.** Создать собственный класс Logic с операциями ''&&&,'' ''|||''''neg'' --- описывающие сигнатуры и взаимосвязи конъюнкции, дизъюнкции и отрицании. Затем создать тип данных ''OurBool'' и воплощения для него класса ''Logic''.
  
 Формально класс описывается следующим образом: Формально класс описывается следующим образом:
Строка 1253: Строка 1276:
 </code> </code>
  
-Этот код уже не слишком тривиален (что видно по обилию "грозных заголовков"), он был трудный в отладке. Указаны воплощения класса ``Sosedy`` и функции ``(~~)`` для типов ``Int`` и ``Char``. Кроме того, для класса типов ``RealFloat`` (куда входят типы ``Float`` и ``Double``) указано общее воплощение.+Этот код уже не слишком тривиален (что видно по обилию "грозных заголовков"), он был трудный в отладке. Указаны воплощения класса ''Sosedy'' и функции ''(~~)'' для типов ''Int'' и ``Char``. Кроме того, для класса типов ``RealFloat`` (куда входят типы ``Float`` и ``Double``) указано общее воплощение.
  
 Заметим, что функция ``(~~~)`` будет реализована автоматически. Заметим, что функция ``(~~~)`` будет реализована автоматически.
Строка 1717: Строка 1740:
 </code>  </code> 
  
-Здесь как раз видно, что обычные комбинаторы функции ''$'' и ''.'' имеют соответствующие аналоги для монадических функций: ''<nowiki>>>=</nowiki>'' и ''<nowiki>>=></nowiki>'', но в обратном порядке, как для PipeLine в Unix; если необходим привычный порядок комбинаторов, как в композициях функций, то можно использовать ''<nowiki>=<<</nowiki>'', ''<nowiki><=<</nowiki>''. Правда, если комбинатор ''<nowiki>>>=</nowiki>'' доступен сразу в модуле Prelude, то комбинаторы ''<nowiki>>=></nowiki>'', ''<nowiki><=<</nowiki>'', ''<nowiki>=<<</nowiki>'' доступны либо при подключении модуля ''Control.Monad'', либо требуют простых определений самостоятельно, напр.:+Здесь как раз видно, что обычные комбинаторы функции ''$'' и ''.'' имеют соответствующие аналоги для монадических функций: ''<nowiki>>>=</nowiki>'' и ''<nowiki>>=></nowiki>'', но в обратном порядке, как для PipeLine в Unix; если необходим привычный порядок комбинаторов, как в композициях функций, то можно использовать ''<nowiki>=<<</nowiki>'', ''<nowiki><=<</nowiki>''. Правда, если комбинатор ''<nowiki>>>=</nowiki>'' доступен сразу в модуле ''Prelude'', то комбинаторы ''<nowiki>>=></nowiki>'', ''<nowiki><=<</nowiki>'', ''<nowiki>=<<</nowiki>'' доступны либо при подключении модуля ''Control.Monad'', либо требуют простых определений самостоятельно, напр.:
 <code haskell> <code haskell>
 f >=> g = \x -> (f x >>= g) f >=> g = \x -> (f x >>= g)