Императивный Haskell

Haskell достаточно сильно отличается от типичных императивных языков программирования: недоступность явного оператора присваивания (роднящая Haskell с такими языками как Erlang, Prolog и Clojure), статическая система типов (отличающая Haskell от вышеупомянутых языков) и ленивые вычисления по-умолчанию (среди языков программирования общего назначения – достаточно уникальное явление) накладывают свою специфику на решение типичных для программирования задач.

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

Условное ветвление

В большинстве императивных языков явное ветвление осуществляется одним из двух способов: конструкцией if .. else .. наподобие

# Python

if foo:
  command1
  command2
else if bar:
  command3
  command4
else if baz:
  command5
else:
  command6

или же существенно реже встречающейся таблицей переходов:

// C

switch foo {
  case 1:
    command1
    command2
    break;
  
  case 3:
    command3
    command4
    break;
  
  default:
    command5
    break;
}

Хотя в Haskell и присутствует выражение if .. then .. else .., аналогичное тернарному оператору .. ? .. : .. языка C, используется оно обычно с той же частотой, что и упомянутый тернарный оператор в C (довольно редко). Чаще можно увидеть case-выражения или же уравнения с несколькими правыми частями. А поскольку тип Bool в Haskell определён как

data Bool = True | False

то периодически вместо if foo then bar else baz используется

case foo of
    True  -> bar
    False -> baz

В императивных частях кода (внутри do-блоков) можно увидеть комбинаторы when и unless из модуля Control.Monad:

when True  bar = bar
when False _   = pure ()

unless = when . not

Неструктурированные переходы

Они же – оператор goto и его более «мягкие» аналоги типа return, break и continue. Haskell не поощряет написание императивного кода. Тем не менее, библиотека mtl предоставляет типы Cont и ContT (о том, как они определены, см. следующую главу), позволяющие эмулировать поведение этих операторов.

Этот раздел, вероятно, следует читать после прочтения нескольких следующих.

Типичный код на императивном языке

k = 2
while k < n:
    if n % k == 0: break
    k += 1

if k < n: print('Делитель нашёлся!')

Код на Haskell с использованием Cont (буквальный перевод):

loop n k break = do
    when (n `mod` k == 0) $ break k
    loop n (k+1) break

check n = do
    k <- flip runCont id $ callCC (loop n 2)
    when (k < n) $ putStrLn "Делитель нашёлся!"

И, наконец, как надо:

unless (null $ dropWhile ((0 /=) . mod n) [2..n-1]) $
    putStrLn "Делитель нашёлся!"

Скажем несколько слов о том, что такое runCont/runContT и как их использовать. Комбинатор runCont добавляет к вычислению монадный интерфейс (см. следующую главу) и операцию callCC. Операция callCC передаёт в функцию операцию преждевременного завершения (аналог return в императивных языках). В отличие от императивных языков, операция преждевременного завершения может быть передана ещё какой-нибудь функции.

Комбинатор runContT «надевает» на монадный интерфейс свой монадный интерфейс, отвечающий за изменение ячейки. Действия внутреннего монадного интерфейса можно преобразовывать в действия внешнего комбинатором lift модуля Control.Monad.Trans:

// довольно дурацкий пример на C++

bool hasEven(vector<int> &numbers) {
  for (auto n : numbers) {
    if (n % 2 == 0) {return true;}
  }
  
  return false;
}

int findEven(vector<int> &numbers) {
  for (auto n : numbers) {
    if (n % 2 == 0) {return n;}
  }
  return 0;
}


int main() {
  int n;
  cin >> n;
  
  vector<int> numbers(n);
  for (unsigned i = 0; i != n; i++) {
    cin >> numbers[i];
  }
  
  if (hasEven(numbers)) {
    cout << "Первое чётное число: " << findEven(numbers) << endl;
  } else {
    cout << "Нечётных чисел не найдено" << endl;
  }
}

-- Почти дословный перевод на Haskell.
-- Единственная разница: вместо массива -- список.

hasEven numbers break = do
    for_ numbers $ \n -> when (n `mod` 2 == 0) (break True)
    break False

findEven numbers break = do
    for_ numbers $ \n -> when (n `mod` 2 == 0) (break n)
    break 0
    
main = do
    text <- getContents
    let n:rest  = read <$> words text :: [Int]
        numbers = take n rest
    
    flip runContT pure $ do
        found <- callCC (hasEven numbers)
        case found of
            True -> do
                x <- callCC (findEven numbers)
                lift $ putStrLn ("Первое чётное число: " ++ x)
            False -> lift $ putStrLn "Нечётных чисел не найдено"

Структурированные переходы

Они же – циклы. Большая часть циклов относится к одному из двух видов:

проход по последовательности элементов с аккумулированием результата
проход по последовательности элементов с каким-то действием на каждом элементе

Типичный пример первого:

squares_sum = 0
for i in range(n):
  squares_sum += n**2

Типичный пример второго:

for i,n in enumerate(numbers):
  print(i,"->",n)

Циклы первого типа в Haskell в большинстве случаев выражаются комбинатором foldl' (из модуля Data.Foldable):

let squaresSum = foldl' (\a x -> a + x^2) 0 [0..n-1]

Циклы второго типа в Haskell выражаются комбинаторами traverse_ или for_ (из того же модуля Data.Foldable):

for_ (zip [0..] numbers) $ \(i,n) -> do
    putStrLn $ show i ++ " -> " ++ show n

-- Комбинатор traverse_ отличается от for_ только порядком аргументов:
-- traverse_ x y = for_ y x

Изменяемые переменные

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

Для однопоточного приложения в подавляющем большинстве случаев достаточно комбинаторов runState и runStateT из модуля Control.Monad.State.Strict пакета mtl. Первый из них добавляет к вычислению монадный интерфейс и одну ячейку:

let (_, sum) = flip runState 0 $ do
        for_ [1..10] $ \x -> modify (\s -> s+x)

Второй «надевает» на монадный интерфейс свой монадный интерфейс, отвечающий за изменение ячейки. Действия внутреннего монадного интерфейса можно преобразовывать в действия внешнего комбинатором lift модуля Control.Monad.Trans:

main = do
    text <- getLine
    let n = read text :: Integer
    
    (_, sum) <- flip runStateT 0 $ do
        for_ [1..n] $ \x -> do
            currentSum <- get
            lift $ putStrLn ("Current sum is " ++ show currentSum)
            modify $ \s -> s + x
    
    putStrLn ("Result is " ++ sum)

Помимо комбинаторов runState/runStateT есть аналогичные комбинаторы runReader/runReaderT (из модуля Control.Monad.Reader), предоставляющие неизменяемую ячейку, считать значение которой можно действием ask.

Для многопоточных приложений приходится использовать более сложные виды ячеек. Чаще всего встречаются IORef, MVar и TVar. В частности, о первой из них пойдёт речь в главе, посвящённой написанию веб-сервера.

Массивы

Де факто стандартной для языка Haskell реализацией массивов являются модули, предоставляемые пакетом vector. У этого пакета довольно сложная структура, требующая пояснений.

Массивы разделяются на два класса:

неизменяемые: операции над ними определены в модуле Data.Vector.Generic
изменяемые: операции над ними определены в модуле Data.Vector.Generic.Mutable

Оба этих модуля следует импортировать в qualified-режиме. Перечислим важнейшие операции над неизменяемыми массивами:

создание: generate n f создаёт массив длины n с элементами f(0), f(1), … f(n-1)
длина: length v – длина массива v
доступ: v ! i – элемент массива v с номером i
изменение: v // [(i1,x1),(i2,x2) ...] ставит на места i1, i2, … значения x1, x2, …
преобразование в изменяемый массив: thaw v – изменяемая копия массива v

Операции над изменяемыми массивами имеют другие названия:

создание: new n создаёт массив длины n, заполненный чем повезёт
длина: length v – длина массива v
доступ: read v i – элемент массива v с номером i
изменение: write v i x – запись по номеру i значения x; modify v i f – изменение элемента с номером i при помощи функции f; swap v i j – обмен элементов с номерами i и j
преобразование в неизменяемый массив: freeze v – неизменяемая копия массива v; операция определена в модуле Data.Vector.Generic

Естественно, это далеко не все операции. Полный их список следует смотреть в документации.

Все эти операции работают с представителями классов Vector и MVector. Конкретные представители этих классов нужно импортировать из соответствующих модулей. Перечислим наиболее важные типы:

Vector a (модуль Data.Vector) – неизменяемый массив элементов произвольного типа
IOVector a (модуль Data.Vector.Mutable) – изменяемый массив элементов произвольного типа
Vector a (модуль Data.Vector.Unboxed) – неизменяемый массив с элементами одного из базовых типов (например Int, Float и т.д.)
IOVector a (модуль Data.Vector.Unboxed.Mutable) – изменяемый массив с элементами одного из базовых типов (например Int, Float и т.д.)

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

// сначала на C++

void bubbleSort(vector<int> &v) {
  bool changed = true;
  
  while (changed) {
    changed = false;
    
    for (unsigned i = 1; i != v.size(); i++) {
      if (v[i-1] > v[i]) {
        swap(v[i-1],v[i]);
        changed = true;
      }
    }
  }
}


int main() {
  int n;
  cin >> n;
  
  vector<int> numbers(n);
  for (unsigned i = 0; i != numbers.size(); i++) {
    cin >> numbers[i];
  }
  
  bubbleSort(numbers);
  
  for (unsigned i = 0; i != numbers.size(); i++) {
    cout << numbers[i] << ' ';
  }
  cout << endl;
}

Теперь её почти дословный перевод на Haskell (изменён только ввод данных):

{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.State.Strict
import Control.Monad.Trans
import Data.Foldable
import Data.Vector.Unboxed(Vector)
import Data.Vector.Unboxed.Mutable(IOVector)
import qualified Data.Vector.Generic         as V
import qualified Data.Vector.Generic.Mutable as M


whileState action = do
    s <- get
    when s (action >> whileState action)
    

bubbleSort numbers = flip runStateT True $
    whileState $ do
        put False
        for_ [1 .. M.length numbers - 1] $ \i -> do
            x <- lift $ M.read numbers (i-1)
            y <- lift $ M.read numbers i
            when (x > y) $ do
                lift $ M.swap numbers (i-1) i 
                put True
            
    
main = do
    text <- getContents
    let n:rest = read <$> words text :: [Int]
        xs = take n rest
    
    numbers <- V.thaw $ (V.fromList xs :: Vector Int)
    
    bubbleSort (numbers :: IOVector Int)
    
    for_ [0 .. M.length numbers - 1] $ \i -> do
        x <- M.read numbers i
        putStr $ show x ++ " "
    
    putStrLn ""

Словари и множества

В РАЗРАБОТКЕ