Язык Haskell, подробнее об определениях

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

название вход_1 ... вход_n = правая_часть

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

название вход_1 ... вход_n
  | условие_1 = правая_часть_1
  | условие_2 = правая_часть_2
  ...
  | условие_m = правая_часть_m

Если какой-то из входов функции имеет индуктивно определённый тип данных (например, список), то зачастую приходится в определении использовать несколько уравнений. Например, функция filter определена в стандартной библиотеке примерно следующим образом:

filter _ [] = []  -- название _ традиционно используется для несущественных входов
filter predicate (x:xs)
  | predicate x = x : filter predicate xs
  | True        = filter predicate xs

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

[два:три] = [2,3]

-- или, что совершенно то же самое, так:

два:три:[] = 2:3:[]

Вспомогательные определения

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

-- является ли число n простым?
isPrimeLoop k n
  | k*k > n        = True
  | n `mod` k == 0 = False
  | True           = isPrimeLoop (k+1) n
  
isPrime n 
  | n < 2 = False
  | True  = isPrimeLoop 2 n

Цикл isPrimeLoop сам по себе вряд ли полезен вне функции isPrime. Поэтому довольно логично было бы, если бы его определение не “вылезало” за пределы isPrime. Этого можно добиться одним из двух способов:

isPrime n
  | n < 2 = False
  | True  = isPrimeLoop 2 
  where
    isPrimeLoop k
      | k*k > n        = True
      | n `mod` k == 0 = False
      | True           = isPrimeLoop (k+1)
      
-- или же
isPrime n
  | n < 2 = False
  | True  = 
    let 
      isPrimeLoop k
        | k*k > n        = True
        | n `mod` k == 0 = False
        | True           = isPrimeLoop (k+1)
    in isPrimeLoop 2

Слово where можно поставить в конце уравнения. После него следует блок вспомогательных определений. Напомним, что все определения блока должны начинаться в одной и той же колонке, а их куски, не поместившиеся в одну строчку, должны находиться строго правее этой колонки.

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

Конечные последовательности (кортежи)

Списки используются для моделирования ситуации “произвольное количество однотипных значений”. Часто встречается другая ситуация: “фиксированное количество разнотипных значений”. В качестве примера можно привести операцию divMod из стандартной библиотеки, которая по паре чисел выдаёт одновременно неполное частное и остаток при делении одного на другое. Её тип следующий:

divMod :: Integral a => a -> a -> (a,a)

Запись (a,b) означает тип пар, первый элемент которых имеет тип a, а второй – тип b. Аналогично есть типы (a,b,c), (a,b,c,d) и так далее… Значения таких типов образуются при помощи того же синтаксиса:

(2 :: Int, "Вася")  -- пара типа (Int, String)

Пары лежат в основе (почти) изоморфизма двух моделей понятия “функция двух переменных”, тоже названного в честь Хаскелла Карри:

curry :: ((a,b) -> c) -> (a -> b -> c)
curry f a b = f (a,b)

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

В языке Haskell, как и в классическом лямбда-исчислении, более популярна модель вида a->b->c. В подавляющем большинстве других языков программирования используется модель (a,b)->c. Практическая разница по большей части – в удобстве использования. А вот в математике зачастую эти две модели не слишком изоморфны (говоря математическим языком, многие интересные категории не являются декартово замкнутыми).

Общение со внешним миром

Все функции в языке Haskell являются “чистыми”. “Чистота” функции означает, что на одних и тех же входных данных эта функция всегда выдаст один и тот же результат (если не считать затрату вычислительных ресурсов и порядок вычислений частью результата). Отсюда, на первый взгляд, следует печальный вывод: невозможность написать функцию, результат работы которой зависит, например, от введённых пользователем данных.

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

Действие, которое в результате общения со внешним миром выдаёт результат типа a, имеет тип IO a (IO – от слов input/output). Те действия, которые не имеют никакого полезного с точки зрения программы результата (например, печать текста на экран), имеют тип IO () (как нетрудно догадаться, тип () – просто кортеж нулевой длины).

Действия можно комбинировать друг с другом при помощи двух операций:

pure  :: a -> IO a  -- в силу исторических причин вместо pure часто встречается 
                    -- не слишком удачно названный синоним return
(>>=) :: IO a -> (a -> IO b) -> IO b

Типы этих комбинаторов достаточно точно описывают их назначение. Комбинатор pure превращает объект в “тривиальное действие”, выдающее этот объект в качестве результата. Комбинатор >>= (его ещё называют словом bind, хотя функции с таким названием в стандартной библиотеке нет) из действия x и “генератора действий” g делает действие, состоящее из следующих этапов:

выполнить x, получив результат r
подставить r в g, получив действие g r
выполнить действие g r, вернуть его результат

Например, программа, здоровающаяся с пользователем, может выглядеть так:

module Main where

-- в модуле Main должна быть определена константа main :: IO (), 
-- которая и служит точкой входа в автономную программу

main =
    putStrLn "Введите ваше имя:" >>= \_ ->
    getLine                      >>= \имя ->
    putStr   "Дратути, "         >>= \_ ->
    putStrLn имя

Такую программу можно собрать компилятором ghc, получив исполняемый файл.

Ровно то же самое можно записать при помощи специального слова do:

main = do
    putStrLn "Введите ваше имя:"
    имя <- getLine
    putStr   "Дратути, "
    putStrLn имя

Ничего магического в слове do нет: это просто сокращение. Оно тупо вставляет в нужные места >>= и лямбда-выражения.

Упражнения

Комбинатор >> имеет тип IO a -> IO b -> IO b. Он просто объединяет два действия в одно составное, заключающееся в исполнении двух входных действий друг за другом. В языке СИ, например, этот комбинатор тоже присутствует (и обозначается запятой). Выразите >> через >>=. Если ваш комбинатор называется foo, то программа
```
main = putStr "Hello " `foo` putStrLn "world!"
```
должна печатать “Hello world!”.

a >> b = a >>= (\_ -> b)

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

getContents :: IO String – получает всё, что введено пользователем; считывает только те символы, которые требуются в процессе обработки результата
words :: String -> [String] – разбивает текст на отдельные слова
read :: Read a => String -> a – преобразует текст в значение, для которого такое преобразование определено; при использовании не забудьте явно указать тип результата
show :: Show a => a -> String – преобразует значение в его текстовое представление

main = do
  text <- getContents
  
  let numbers = read <$> words text :: [Integer]
      a:b:_   = numbers
  
  putStrLn $ show $ a+b

Напишите программу, которая получает на вход число N, а затем – N чисел. Программа должна напечатать сумму этих N чисел.

main = do
  text <- getContents
  
  let numbers = read <$> words text :: [Integer]
      n:rest  = numbers
  
  putStrLn $ show $ sum $ take (fromInteger n) rest
  -- fromInteger нужен, поскольку take имеет тип Int -> [a] -> [a]

Напишите программу, которая получает на вход числа (без явно заданного количества) и печатает их сумму. Должна работать аналогично следующей программе на C++:

#include <iostream>

int main() {
  int number = 0;
  int sum    = 0;
  
  while (std::cin >> number) {
    sum += number;
  }
  
  std::cout << number << std::endl;
}

Напоминаем, что стандартный входной поток можно закрыть (в зависимости от используемого терминала) сочетанием клавиш Ctrl-D или Ctrl-Z, Enter.

-- Антипример! Вот так писать программы не очень желательно. Хотя встретить в реальности 
-- подобное можно довольно часто. И оно даже вполне читается, если приглядеться...

main = getContents >>= (putStrLn . show . sum . ((read :: String -> Integer) <$>) . words)