Возможности Хаскелла

В этой статье описаны возможности языка программирования Haskell .

Примеры

Факториал

Простой пример, который часто используется для демонстрации синтаксиса функциональных языков, — это функция факториала для неотрицательных целых чисел, показанная в Haskell:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n-1)

Или в одну строку:

factorial n = if n > 1 then n * factorial (n-1) else 1

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

Первая строка функции факториал описывает тип этой функции; хотя это необязательно, это считается хорошим стилем чтобы включить его. Его можно прочитать как функцию факториал ( factorial) имеет тип ( ::) от целого числа к целому ( Integer -> Integer). То есть он принимает целое число в качестве аргумента и возвращает другое целое число. Тип определения выводится автоматически, если аннотация типа не указана.

Вторая строка опирается на сопоставление с образцом — важную особенность Haskell. Обратите внимание, что параметры функции заключаются не в круглые скобки, а разделяются пробелами. Если аргумент функции равен 0 (ноль), она вернет целое число 1 (единица). Во всех остальных случаях пробуется третья строка. Это рекурсия , которая выполняет функцию снова, пока не будет достигнут базовый случай.

Используя product функция из Prelude, ряда небольших функций, аналогичных , C стандартной библиотеке и используя синтаксис Haskell для арифметических последовательностей, функция факториала может быть выражена в Haskell следующим образом:

factorial n = product [1..n]

Здесь [1..n] обозначает арифметическую последовательность 1, 2, …, n в виде списка. Использование функции Прелюдия enumFromTo, выражение [1..n] можно записать как enumFromTo 1 n, что позволяет выразить функцию факториала как

factorial n = product (enumFromTo 1 n)

который, используя оператор композиции функции (выраженный в виде точки в Haskell) для составления функции произведения с каррированной функцией перечисления, может быть переписан в бесточечном стиле :

factorial = product . enumFromTo 1

В интерпретаторе Hugs часто необходимо определить функцию и использовать ее в одной строке, разделенной знаком. where или let.. in. Например, чтобы протестировать приведенные выше примеры и увидеть результат 120:

let { factorial n | n > 0 = n * factorial (n-1); factorial _ = 1 } in factorial 5

или

factorial 5 where factorial = product . enumFromTo 1

Интерпретатор GHCi не имеет этого ограничения, и определения функций можно вводить в одну строку (с помощью let синтаксис без in часть), и упоминается позже.

Более сложные примеры

Калькулятор

В исходном коде Haskell ниже: :: можно прочитать как «имеет тип»; a -> b можно прочитать как «является функцией от a до b». (Таким образом, Haskell calc :: String -> [Float] можно прочитать как " calc имеет тип функции от строк до списков чисел с плавающей запятой".) Во второй строке calc = ... знак равенства можно прочитать как «может быть»; таким образом, несколько строк с calc = ... можно прочитать как несколько возможных значений для calc, в зависимости от обстоятельств, указанных в каждой строке.

Простой калькулятор обратной польской записи, выраженный с помощью функции высшего порядка. foldl аргумент f которого определен в предложенииwhere с использованием сопоставления с образцом и класса типа Read :

calc :: String -> [Float]
calc = foldl f [] . words
  where 
    f (x:y:zs) "+" = (y + x):zs
    f (x:y:zs) "-" = (y - x):zs
    f (x:y:zs) "*" = (y * x):zs
    f (x:y:zs) "/" = (y / x):zs
    f (x:y:zs) "FLIP" =  y:x:zs
    f zs w = read w : zs

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

Последовательность Фибоначчи

Следующее определение создает список чисел Фибоначчи в линейном времени:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Бесконечный список создается с помощью корекурсии — последние значения списка вычисляются по требованию, начиная с первых двух элементов 0 и 1. Этот тип определения основан на ленивых вычислениях — важной особенности программирования на Haskell. В качестве примера того, как развивается оценка, ниже показаны значения Fibs и Tail Fibs после вычисления шести элементов и показано, как zipWith (+) создал четыре элемента и приступает к созданию следующего элемента:

fibs         = 0 : 1 : 1 : 2 : 3 : 5 : ...
               +   +   +   +   +   +
tail fibs    = 1 : 1 : 2 : 3 : 5 : ...
               =   =   =   =   =   =
zipWith ...  = 1 : 2 : 3 : 5 : 8 : ...
fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 : ...

Та же функция, написанная с использованием Glasgow Haskell компилятора синтаксиса параллельного понимания списка (расширения GHC необходимо включить с помощью специального флага командной строки, здесь -XParallelListComp , или запустив исходный файл с помощью {-# LANGUAGE ParallelListComp #-}):

fibs = 0 : 1 : [ a+b | a <- fibs | b <- tail fibs ]

или с обычным пониманием списка :

fibs = 0 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ]

или напрямую ссылаясь на самого себя:

fibs = 0 : 1 : next fibs where next (a : t@(b:_)) = (a+b) : next t

С состояния функцией генерации :

fibs = next (0,1) where next (a,b) = a : next (b, a+b)

или с unfoldr:

fibs = unfoldr (\(a,b) -> Just (a, (b, a+b))) (0, 1)

или scanl:

fibs = 0 : scanl (+) 1 fibs

Haskell Использование рекурсии данных с предопределенным комбинатором фиксированных точек :

fibs = fix (\xs -> 0 : 1 : zipWith (+) xs (tail xs))   -- zipWith version
     = fix ((0:) . (1:) . (zipWith (+) <*> tail))      -- same as above, pointfree
     = fix ((0:) . scanl (+) 1)                        -- scanl version

Факториал

Факториал, который мы видели ранее, можно записать как последовательность функций:

factorial n = foldr ((.) . (*)) id [1..n] $ 1
-- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) id )))) 1
--             == (1*) . (2*) . (3*) . (4*) . (5*) . id $ 1
--             ==  1*  (  2*  (  3*  (  4*  (  5*  ( id   1 )))))

factorial n = foldr ((.) . (*)) (const 1) [1..n] $ ()
-- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) (const 1) )))) ()
--             == (1*) . (2*) . (3*) . (4*) . (5*) . const 1 $ ()
--             ==  1*  (  2*  (  3*  (  4*  (  5*  ( const 1   () )))))

factorial n = foldr (($) . (*)) 1 [1..n] = foldr ($) 1 $ map (*) [1..n]
-- factorial 5 == ((1*) $) ( ((2*) $) ( ((3*) $) ( ((4*) $) ( ((5*) $) 1 ))))
--             == (1*) $ (2*) $ (3*) $ (4*) $ (5*) $ 1
--             ==  1*  (  2*  (  3*  (  4*  (  5*    1 ))))

Больше примеров

Числа Хэмминга

Удивительно лаконичная функция, которая возвращает список чисел Хэмминга по порядку:

hamming = 1 : map (2*) hamming `union` map (3*) hamming 
                                 `union` map (5*) hamming

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

Здесь функция union используется как оператор, заключая его в обратные кавычки. Его case Предложения определяют, как он объединяет два возрастающих списка в один возрастающий список без повторяющихся элементов, представляя наборы в виде упорядоченных списков. Его сопутствующая функция minus реализует установленную разницу :

union (x:xs) (y:ys) = case compare x y of LT -> x : union xs (y:ys) EQ -> x : union xs ys GT -> y : union (x:xs) ys union xs [] = xs union [] ys = ys

minus (x:xs) (y:ys) = case compare x y of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs --

Для более эффективной работы можно генерировать только уникальные кратные числа. Поскольку дубликатов нет, удалять их не нужно:

smooth235 = 1 : foldr (\p s -> fix $ mergeBy (<) s . map (p*) . (1:)) [] [2,3,5]
  where
    fix f = x  where x = f x         -- fixpoint combinator, with sharing

Здесь используется более эффективная функция merge который не касается дубликатов (также используется в следующей функции, mergesort ):

mergeBy less xs ys = merge xs ys  where
  merge  xs     []  = xs 
  merge  []     ys  = ys
  merge (x:xs) (y:ys) | less y x  = y : merge (x:xs) ys
                      | otherwise = x : merge xs (y:ys)

Каждая вертикальная полоса ( | ) начинает защитное предложение с защитным выражением перед = знак и соответствующее определение после него, которое оценивается, если предупреждение истинно.

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

Вот сортировка слиянием снизу вверх , определенная с использованием функции высшего порядка until:

mergesortBy less [] = []
mergesortBy less xs = head $
      until (null . tail) (pairwise $ mergeBy less) [[x] | x <- xs]

pairwise f (a:b:t) = f a b : pairwise f t
pairwise f      t  = t

Простые числа

Математическое определение простых чисел можно почти дословно перевести на Haskell:

-- "Integers above 1 that cannot be divided by a smaller integer above 1"
-- primes = { n ∈ [2..] | ~ ∃ d ∈ [2..n-1] ⇒ rem n d = 0  }
--        = { n ∈ [2..] |   ∀ d ∈ [2..n-1] ⇒ rem n d ≠ 0  }

primes = [ n | n <- [2..], all (\d -> rem n d /= 0) [2..(n-1)] ]

Это находит простые числа путем пробного деления . Обратите внимание, что он не оптимизирован по эффективности и имеет очень низкую производительность. Немного быстрее (но все равно очень медленно) это код Дэвида Тернера :

primes = sieve [2..]  where 
         sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]

Гораздо быстрее работает оптимальный алгоритм пробного деления

primes = 2 : [ n | n <- [3..], all ((> 0) . rem n) $ 
                     takeWhile ((<= n) . (^2)) primes]

или неограниченное решето Эратосфена с отложенным поэтапным просеиванием,

primes = 2 : sieve primes [3..]  where
             sieve (p:ps) (span (< p*p) -> (h, t)) = 
                   h ++ sieve ps (minus t [p*p, p*p+p..])

или реализация комбинированного сита Ричарда Берда ,

-- "Integers above 1 without any composite numbers which
--  are found by enumeration of each prime's multiples"
primes = 2 : minus [3..]
               (foldr (\(m:ms) r -> m : union ms r) [] 
                      [[p*p, p*p+p ..] | p <- primes])

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

primes = 2 : _Y ((3 :) . minus [5,7..] . _U 
                       . map (\p -> [p*p, p*p+2*p..]))
  where
    -- non-sharing Y combinator:
    _Y g = g (_Y g)     -- (g (g (g (g (...)))))
    -- big union   ~= nub.sort.concat
    _U ((x:xs):t) = x : (union xs . _U . pairwise union) t

Работая с массивами по сегментам между последовательными квадратами простых чисел, это

import Data.Array
import Data.List (tails, inits)

primes = 2 : [ n |
   (r:q:_, px) <- zip (tails (2 : [p*p | p <- primes]))
                      (inits primes),
   (n, True)   <- assocs ( accumArray (\_ _ -> False) True
                     (r+1,q-1)
                     [ (m,()) | p <- px
                              , s <- [ div (r+p) p * p]
                              , m <- [s,s+p..q-1] ] ) ]

Самый короткий возможный код, вероятно, nubBy (((>1) .) . gcd) [2..]. Это довольно медленно.

Синтаксис

Макет

Haskell позволяет отступы использовать для обозначения начала нового объявления. Например, в предложенииwhere :

product xs = prod xs 1
  where
    prod []     a = a
    prod (x:xs) a = prod xs (a*x)

Два уравнения для вложенной функции prod выровнены по вертикали, что позволяет опустить разделитель точку с запятой. В Haskell отступы можно использовать в нескольких синтаксических конструкциях, включая do, let, case, class, и instance.

Использование отступов для обозначения структуры программы берет свое начало в Питера Дж. Ландина , языке ISWIM где оно называлось правилом оффсайда . Позже это было принято Мирандой , а Хаскелл принял аналогичную (но более сложную) версию правила Миранды «вне игры», которая называется «раскладкой». Другие языки, использующие синтаксис, чувствительный к пробельным символам , включают Python и F# .

Использование макета в Haskell не является обязательным. Например, функция product выше также можно написать:

product xs = prod xs 1
  where { prod [] a = a; prod (x:xs) a = prod xs (a*x) }

Явная открывающая скобка после where Ключевое слово указывает, что в отдельных объявлениях будут использоваться явные точки с запятой, а список объявлений будет завершаться явной закрывающей скобкой. Одной из причин необходимости поддержки явных разделителей является то, что они упрощают автоматическую генерацию исходного кода Haskell .

Правило компоновки Haskell подвергалось критике за его сложность. В частности, в определении указано, что если синтаксический анализатор обнаруживает ошибку синтаксического анализа во время обработки раздела макета, он должен попытаться вставить закрывающую фигурную скобку (правило «ошибки синтаксического анализа»). Реализация этого правила в традиционной комбинации синтаксического и лексического анализа требует двустороннего сотрудничества между синтаксическим анализатором и лексическим анализатором, тогда как в большинстве языков эти две фазы можно рассматривать независимо.

Вызовы функций

Применение функции f к значению x выражается просто f x.

Haskell отличает вызовы функций от инфиксных операторов синтаксически, но не семантически. Имена функций, состоящие из знаков препинания, могут использоваться в качестве операторов, как и имена других функций, если они окружены обратными кавычками; и операторы можно использовать в префиксной записи, если они заключены в круглые скобки.

В этом примере показаны способы вызова функций:

add a b = a + b

ten1 = 5 + 5
ten2 = (+) 5 5
ten3 = add 5 5
ten4 = 5 `add` 5

Функции, которые определены как принимающие несколько параметров, всегда могут быть применены частично. Бинарные операторы можно частично применять, используя обозначение разделов :

ten5 = (+ 5) 5
ten6 = (5 +) 5
  
addfive = (5 +)
ten7 = addfive 5

Список понятий

См. «Понимание списка#Обзор» для примера Haskell.

Сопоставление с образцом

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

-- This type signature says that empty takes a list containing any type, and returns a Bool
empty :: [a] -> Bool
empty (x:xs) = False
empty [] = True

-- Will return a value from a Maybe a, given a default value in case a Nothing is encountered
fromMaybe :: a -> Maybe a -> a
fromMaybe x (Just y) = y
fromMaybe x Nothing  = x

isRight :: Either a b -> Bool
isRight (Right _) = True
isRight (Left _)  = False

getName :: Person -> String
getName (Person name _ _) = name

getSex :: Person -> Sex
getSex (Person _ sex _) = sex

getAge :: Person -> Int
getAge (Person _ _ age) = age

Используя вышеуказанные функции вместе с map функцию, мы можем применить их к каждому элементу списка, чтобы увидеть их результаты:

map empty [[1,2,3],[],[2],[1..]]
-- returns [False,True,False,False]

map (fromMaybe 0) [Just 2,Nothing,Just 109238, Nothing]
-- returns [2,0,109238,0]

map isRight [Left "hello", Right 6, Right 23, Left "world"]
-- returns [False, True, True, False]

map getName [Person "Sarah" Female 20, Person "Alex" Male 20, tom]
-- returns ["Sarah", "Alex", "Tom"], using the definition for tom above

• Абстрактные типы
• Списки

Кортежи

Кортежи в Haskell могут использоваться для хранения фиксированного количества элементов. Они используются для группировки фрагментов данных разных типов:

account :: (String, Integer, Double) -- The type of a three-tuple, representing 
                                     --   a name, balance, and interest rate
account = ("John Smith",102894,5.25)

Кортежи обычно используются в функциях zip* для размещения соседних элементов в отдельных списках вместе в кортежах (от zip4 до zip7 предоставляются в модуле Data.List):

-- The definition of the zip function. Other zip* functions are defined similarly
zip :: [x] -> [y] -> [(x,y)]
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _      _      = []

zip [1..5] "hello"
-- returns [(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')]
-- and has type [(Integer, Char)]

zip3 [1..5] "hello" [False, True, False, False, True]
-- returns [(1,'h',False),(2,'e',True),(3,'l',False),(4,'l',False),(5,'o',True)]
-- and has type [(Integer,Char,Bool)]

В компиляторе GHC кортежи определяются размером от 2 до 62 элементов.

• Рекорды

Пространства имен

В разделе § Более сложные примеры выше: calc используется в двух смыслах, показывая, что существует пространство имен классов типов Haskell, а также пространство имен для значений:

1. Haskell класс типа для calc. Домен . и диапазон могут быть явно обозначены в классе типов Haskell
2. значение Haskell, формула или выражение для calc.

Классы типов и полиморфизм

Алгебраические типы данных

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

-- A list of a's ([a]) is either an a consed (:) onto another list of a's, or an empty list ([])
data [a] = a : [a] | []
-- Something of type Maybe a is either Just something, or Nothing
data Maybe a = Just a | Nothing
-- Something of type Either atype btype is either a Left atype, or a Right btype
data Either a b = Left a | Right b

Пользователи языка также могут определять свои собственные абстрактные типы данных . Пример ADT, используемого для представления имени, пола и возраста человека, может выглядеть так:

data Sex = Male | Female
data Person = Person String Sex Int -- Notice that Person is both a constructor and a type

-- An example of creating something of type Person
tom :: Person
tom = Person "Tom" Male 27

Типовая система

• Типовые классы
• Тип по умолчанию
• Перегруженные литералы
• Полиморфизм высшего рода
• Классы типов с несколькими параметрами
• Функциональные зависимости

Монады и ввод/вывод

• Обзор монадного фреймворка:
• Приложения
  • Монадический ввод-вывод
  • Do-нотация
  • Ссылки
  • Исключения

ST-монада

Монада ST позволяет писать алгоритмы императивного программирования на Haskell с использованием изменяемых переменных (STRefs) и изменяемых массивов (STArrays и STUArrays). Преимущество монады ST заключается в том, что она позволяет писать код, который имеет внутренние побочные эффекты, такие как деструктивное обновление изменяемых переменных и массивов, сохраняя при этом эти эффекты внутри монады. В результате функции, написанные с использованием монады ST, кажутся остальной части программы чистыми. Это позволяет использовать императивный код там, где написание функционального кода может быть непрактично, сохраняя при этом всю безопасность, которую обеспечивает чистый код.

Вот пример программы (взятый с вики-страницы Haskell о монаде ST ), которая принимает список чисел и суммирует их, используя изменяемую переменную:

import Control.Monad.ST
import Data.STRef
import Control.Monad

sumST :: Num a => [a] -> a
sumST xs = runST $ do            -- runST takes stateful ST code and makes it pure.
    summed <- newSTRef 0         -- Create an STRef (a mutable variable)

    forM_ xs $ \x -> do          -- For each element of the argument list xs ..
        modifySTRef summed (+x)  -- add it to what we have in n.

    readSTRef summed             -- read the value of n, which will be returned by the runST above.

СТМ-монада

Основная статья: Параллельный Haskell

Монада STM — это реализация программной транзакционной памяти в Haskell. Он реализован в компиляторе GHC и позволяет изменять изменяемые переменные в транзакциях .

Стрелки

• Аппликативные функторы
• Стрелки

Поскольку Haskell — чисто функциональный язык, функции не могут иметь побочных эффектов. Будучи нестрогим, он также не имеет четко определенного порядка оценки. Это проблема для реальных программ, которым, помимо прочего, необходимо взаимодействовать с окружающей средой. Haskell решает эту проблему с помощью монадических типов , которые используют систему типов для обеспечения правильной последовательности императивных конструкций. Типичным примером является ввод-вывод (I/O), но монады полезны для многих других целей, включая изменяемое состояние, параллелизм и транзакционную память, обработку исключений и распространение ошибок.

Haskell предоставляет специальный синтаксис для монадических выражений, так что программы с побочными эффектами можно писать в стиле, аналогичном современным императивным языкам программирования; никаких знаний математики, лежащей в основе монадического ввода-вывода для этого не требуется . Следующая программа считывает имя из командной строки и выводит приветственное сообщение:

main = do putStrLn "What's your name?"
          name <- getLine
          putStr ("Hello, " ++ name ++ "!\n")

Do-нотация упрощает работу с монадами. Это do-выражение эквивалентно, но (возможно) его легче написать и понять, чем версия без сахара , напрямую использующая монадические операторы:

main = putStrLn "What's your name?" >> getLine >>= \ name -> putStr ("Hello, " ++ name ++ "!\n")

См. также викибуки:Transwiki:Список программ hello world#Haskell, где приведен еще один пример печати текста.

Параллелизм

Определение языка Haskell не включает ни параллелизм , ни параллелизм , хотя GHC поддерживает и то, и другое.

Основная статья: Параллельный Haskell

Concurrent Haskell — это расширение Haskell, поддерживающее потоки и синхронизацию . Реализация Concurrent Haskell в GHC основана на мультиплексировании легких потоков Haskell в несколько тяжелых потоков операционной системы (ОС). так что Concurrent Haskell-программы выполняются параллельно посредством симметричной многопроцессорности . Среда выполнения может поддерживать миллионы одновременных потоков.

Реализация GHC использует динамический пул потоков ОС, позволяя потоку Haskell выполнять блокирующий системный вызов, не блокируя другие запущенные потоки Haskell. Следовательно, легкие потоки Haskell имеют характеристики тяжелых потоков ОС, и программист может не знать деталей реализации.

Недавно, Concurrent Haskell был расширен за счет поддержки программной транзакционной памяти (STM), которая представляет собой абстракцию параллелизма, в которой сложные операции над общими данными выполняются атомарно, как транзакции. Реализация STM от GHC — единственная реализация STM на сегодняшний день, обеспечивающая статическую гарантию времени компиляции, предотвращающую выполнение нетранзакционных операций внутри транзакции. Библиотека Haskell STM также предоставляет две операции, которых нет в других STM: retry и orElse, которые вместе позволяют определять операции блокировки модульным и составным образом .