Конспекты лекций «Haskell как первый язык программирования». Часть2

  • Tutorial
Привет Habr! Сегодня мы поговорим о полиморфизме функций, операторах и карринге. Напоминаю, что лекции рассчитаны на новичков, а конспект предпологает сжатую форму изложения. Если все еще интересно…

Первая часть

Полиморфизм

Функция полиморфна, если она способна оперировать разными типами данных. Самая простая полиморфная функция — функция тождественности:
id     :: a -> a
id x   =  x

Наиболее часто полиморфизм используют для работы со списками (оно и понятно):
length :: [a] -> Int
length []        =  0
length (_:l)     =  1 + length l

Областью определения данной функции (вычисляющей, очевидно, длину списка) является список переменных типа a. Такую конструкция в просторечии называют просто: «список ашек». Функция примет на вход любой список. Большинство функций в прелюдии являются полиморфными. Не поленитесь — загляните. А, пока, вот еще пример:
filter :: (a -> Bool) -> [a] -> [a]
filter p []                 = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs

Функция filter оставляет в списке только элементы удовлетворяющие некоторому условию.

Как видите, полиморфный тип может быть и областью значения функции:
error            :: String -> a

В данном случае функция error принимает на вход строку об ошибке и возвращает переменную типа а.
Очень интересно определена полиморфная функция без параметров — undefined:
undefined        :: a
undefined        =  error "Prelude.undefined"

Эту функцию-константу употребляют для обозначения неопределенной величины любого типа.

Операторы

Функцию которую можно расположить между аргументами называют инфиксной или, просто, оператором. (Слово аргументы употреблено условно, мы помним, что в Haskell нет функций двух аргументов).
Синтаксис Haskell допускает использовать следующие знаки для построения операторов:
«: # $ % * + — =. / \ < >?! @ ^ | »
Операторы можно составлять как угодно, за исключением следующих комбинаций:
« :: =… — @ \ | < — -> ~ => »
Кроме того, что имена оперраторов заключаются в круглые скобки, определение функции такое же как и в префиксной нотации. Пример:
(%%) :: Int -> Int -> (Int, Int)
(%%) x y = (div x y, rem x y)

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

По ассоциативности операторы делятся на ассоциативные, ассоциативные справа, ассоциативные слева и неассоциативные.
Некоторый условный оператор "\/":
  • ассоциативен справа, если выражение a \/ b \/ c вычисляют как a \/ (b \/ c)
  • ассоциативен слева, если выражение a \/ b \/ c вычисляют как (a \/ b) \/ c
  • ассоциативен, если выражение a \/ b \/ c можно вычислять в любом порядке
  • неассоциативен, если выражение a \/ b \/ c запрещено записывать без скобок

В Haskell:
  • infixr – ассоциативность справа
  • infixl – ассоциативность слева
  • infix – неассоциативный оператор

Итак, как мы напишем оператор с учетом приоритета и ассоциативности:
infixr 7 --ассоциативность справа, приоритет 7
(\/) :: Bool -> Bool -> Bool
(\/) x y = ...


Приоритеты и ассоциативность стандартных операторов из прелюдии:
infixr 9  .
infixl 9  !!
infixr 8  ^, ^^, **
infixl 7  *, /, `quot`, `rem`, `div`, `mod`, :%, %
infixl 6  +, -
infixr 5  :, ++
infix  4  ==, /=, <, <=, >=, >, `elem`, `notElem`
infixr 3  &&
infixr 2  ||
infixl 1  >>, >>=
infixr 1  =<<
infixr 0  $, $!, `seq`

Карринг

Итак, почему же в Haskell нет функции двух и более аргументов? Рассмотрим функцию:
plus :: (Integer, Integer) -> Integer
plus (x, y) = x + y

Функция plus, имеет один аргумент. Этот аргумент — пара чисел.
Обычно же функции в Haskell записывают в виде:
plus :: Integer -> Integer -> Integer
plus x  y  = x + y

И у этой функции тоже один аргумент (а не два, как можно было бы подумать), этот аргумент — число типа Integer. Таким образом, появляется возможность применять аргументы по одному. В этом и состоит принцип каррирования (по имени американского логика Haskell B. Curry). Если «скормить» такой функции число, то получим еще одну функцию. В этом несложно убедиться на простом примере:
successor :: Integer -> Integer
successor = plus 1

Этот прием называют частичным применением функции.

В прелюдии определены специальные функции curry и uncurry, приводящие функции к карринговой форме и обратно:
curry            :: ((a, b) -> c) -> a -> b -> c
curry f x y      =  f (x, y)

uncurry          :: (a -> b -> c) -> ((a, b) -> c)
uncurry f p      =  f (fst p) (snd p)

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

Похожие публикации

Комментарии 10

    +3
    Частичное применение и каррирование — не одно и то же.
    Частичное применение — это когда есть функция f(x, y), фиксируем (применяем), например, y — получаем g(x).
    Каррирование — это когда функия f(x,y) преобразуется к (g(x))(y).
      0
      Вы правы, неверно написал. Уже поправил.
      0
      В определении функции для обозначения любого типа именно «а» используется, или можно "[x]", например, записать для обозначения любого списка?

      У вас infifr 7 написано — это опечатка или есть такое слово?

      Не совсем понятен код для функций curry и uncurry (что они делают понятно).
      Ведь по объявлению у каждой из них один аргумент, а в определении указано соответственно 3 и 2. Как так?
        0
        infifr — опечатка.
        Переменная типа — любая строчная буква или даже слово из строчных букв. Принято использовать первые буквы алфавита a b c…

        В Haskell аргумент всегда один, если функция не константа.
        Посмотрите еще раз на объявление:
        curry :: ((a, b) -> c) -> a -> b -> c
        А если я напишу вот так (что одно и тоже):
        curry :: ((a, b) -> c) -> (a -> b -> c)
        Берем на вход такую функцию (a, b) -> c и получаем такую a -> b -> c

        uncurry :: (a -> b -> c) -> ((a, b) -> c)
        На входе функция a -> b -> c на выходе (a, b) -> c
          0
          А определения функций не перепутаны местами случайно?
          Если да, видимо это с толку сбило.
        +1
        Про операторы можно дополнить следующее. Если имя функции состоит из спецсимволов, то по умолчанию она употребляется как оператор (то есть стоит между аргументами), если из букв-цифр, то как обычная функция (то есть все ее аргументы стоят справа от имени). Существует способ изменить поведение по умолчанию: взяв имя из спецсимволов в скобки, получаем обычную функцию, а заключив обычное имя в обратные кавычки, получаем инфиксную.

        Причем, это работает не только в вызове функции, но и в определении. Например:
        (%%) :: Int -> Int -> (Int, Int)
        x %% y = (div x y, rem x y)       -- это определение, а не вызов
        


        mod :: Int -> Int -> Int       -- NB: на самом деле библиотечное определение mod не такое; оно использует класс
        x `mod` y = ...
        

        Отдельно стоит отметить синтаксис «частичное применение» оператора:
        (+ 2) -- то же самое, что \x -> x + 2
        (2 `mod`) -- то же самое, что mod 2
        
          +1
          Хоть определения каррирования выдернуты из Прелюдии как есть, лучше преобразовать их в одну форму:

          curry            :: ((a, b) -> c) -> (a -> b -> c)
          uncurry          :: (a -> b -> c) -> ((a, b) -> c)
          

          или так
          curry            :: ((a, b) -> c) -> a -> b -> c
          uncurry          :: (a -> b -> c) -> (a, b) -> c
          

          В принципе наличие скобок не важно, и обе записи валидны:

          a -> b -> c -> d -> f    ===   a -> (b -> (c -> (d -> f)))
          


          Слово «операторы» редко применяется в Хаскеле. «инфиксная фукнция» используется чаще.
          Дело в том, что любую функцию можно записать и в префиксной, и в инфиксной записи

          add x y = x + y       -- prefix 'add', infix  '+'
          
          add x y = (+) x y     -- prefix 'add', prefix '+'
          
          x `add` y = (+) x y   -- infix  'add', prefix '+'
          
          x `add` y = x + y     -- infix  'add', infix  '+'
          
          
          add2 x = (+ 2)
          
          add2 x = (2 +)
          
          add2 x = (`add` 2)
          
          add2 x = (2 `add`)
          
          
            0
            Эта ваша уже третья статья, а читать ее все также не интересно и неприятно.
            Объясните хоть людям что такое операторы, раз у вас статья о введении в программирование.

            Какую цель вы преследуете в серии этих статей?
              +1
              Хм. Что такое оператор проходят в школе. Этот термин к программированию относится лишь косвенно. Я думал, что это понятие известно читателям хабра.
              Кому неприятно читать статью? Вам?
              Цель преследую только одну — поделиться тем, что мне интересно с другими. Все стати в плюсе. А процентное отношение плюсов к минусам растет. Отсюда напрашивается два вывода:
              1. Статья кому-то полезна
              2. Качество статей повышается
              Кроме того, хабр саморегулирующееся сообщество и, если бы статьи были «не интересными и неприятными» я бы уже был лишен возможности тут писать, уж поверьте.
              0
              Операторы можно составлять как угодно, за исключением следующих комбинаций:
              « :: =… — @ \ | < — -> ~ => »

              Однако следующий код работает:
              (=...)::Int->[Char]->[Char]
              a =... b = show a ++ ' ' : b
              

              Проверяю:
              ghci> :l src
              [1 of 1] Compiling Main ( src.hs, interpreted )
              Ok, modules loaded: Main.
              ghci> let a = 123
              ghci> let b = «asdf»
              ghci> a =… b
              «123 asdf»
              ghci> (=...) a b
              «123 asdf»
              ghci>

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое