Что такое комбинатор в Haskell

Question

В Реальный мир Haskell, они описывают комбинаторы следующим образом:

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

А потом, позже, они заявляют, что maybeIO функция является комбинатором, и ее сигнатура типа выглядит следующим образом:

maybeIO :: IO a -> IO (Maybe a)

Но все, что я вижу, это то, что maybeIO это функция, которая принимает значение, заключенное в IO monad, и возвращает значение в IO monad.Тогда как эта функция становится комбинатором?

Answer 1

На самом деле есть 2 вещи, которые мы могли бы иметь в виду, когда говорим "комбинатор".Это слово немного перегружено.

1. Обычно мы имеем в виду функцию, которая "объединяет" вещи.Например, ваша функция принимает в IO ценность и создает более сложную ценность.Используя эти "комбинаторы", мы можем комбинировать и создавать новые сложные IO значения из относительно небольшого числа примитивных функций для создания IO ценности.

   Например, вместо того, чтобы создавать функцию, которая считывает 10 файлов, мы используем mapM_ readFile.Здесь комбинаторы - это функции, которые мы используем для объединения и создания значений

2. Более строгий термин в области компьютерных наук - это "функция без свободных переменных".Так

    -- The primitive combinators from a famous calculus, SKI calculus.
    id a         = a -- Not technically primitive, genApp const const
    const a b    = a
    genApp x y z = x z (y z)
   

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

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

Answer 2

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

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

approxSqrt x = round (sqrt x)

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

approxSqrt = round . sqrt

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

do
  contents <- readFile "my_file.txt"
  let messages = lines contents
  ...

Но!Что бы мы сделали, если бы у нас была функция, которая считывает файл и возвращает содержимое в виде строк?Тогда мы могли бы сделать

do
  messages <- readFileLines "my_file.txt"
  ...

Как оказалось, у нас есть функция, которая считывает файл, и у нас есть функция, которая принимает большую строку и возвращает список строк в ней.Если бы у нас только было немного клея, чтобы осмысленно соединить эти две функции, мы могли бы создать readFileLines!Но, конечно, поскольку речь идет о Haskell, этот клей легко доступен.

readFileLines = fmap lines . readFile

Здесь мы используем два комбинатора!Мы используем (.) из прошлого, и fmap на самом деле это также очень полезный комбинатор.Мы говорим, что это "поднимает" чистое вычисление в монаду ввода-вывода, и на самом деле мы имеем в виду, что lines имеет сигнатуру типа

lines :: String -> [String]

но fmap lines имеет подпись

fmap lines :: IO String -> IO [String]

так fmap полезно, когда вы хотите объединить чистые вычисления с вычислениями ввода-вывода.

---

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

Answer 3

"Комбинатор" не совсем точно определен при его использовании в Haskell.Правильнее всего использовать его для обозначения функций, которые принимают другие функции в качестве аргументов a la Комбинаторное исчисление но в терминологии Haskell это часто перегружено, чтобы также означать "модификацию" или "комбинацию" функций, особенно Functor или Monad.В этом случае вы могли бы сказать, что комбинатор - это функция, которая "выполняет некоторое действие или значение в контексте и возвращает новое, измененное действие или значение в контексте".

Ваш пример, maybeIO часто называется optional

optional :: Alternative f => f a -> f (Maybe a)
optional fa = (Just <$> fa) <|> pure Nothing

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

Причина, по которой они также называются комбинаторами, связана с тем, как они используются.Типичное место для осмотра optional (и действительно, Alternative как правило) находится в библиотеках комбинаторов синтаксического анализа.Здесь мы, как правило, создаем базовые парсеры, используя простые Parserс нравится

satisfy :: (Char -> Bool) -> Parser Char
anyChar    = satisfy (const True)
whitespace = satisfy isSpace
number     = satisfy isNumeric

а затем мы "модифицируем" их поведение с помощью "комбинаторов".

-- the many and some combinators
many :: Alternative f => f a -> f [a] -- zero or more successes
some :: Alternative f => f a -> f [a] -- one  or more successes

many f = some f <|> pure []
some f = (:) <$> f <*> many f

-- the void combinator forgets what's inside the functor
void :: Functor f => f a -> f ()
void f = const () <$> f

-- from the external point of view, this is another "basic" Parser
-- ... but we know it's actually built from an even more basic one
-- and the judicious application of a few "combinators"
blankSpace = Parser ()
blankSpace = void (many whitespace)

word :: Parser String
word = many (satisfy $ not . isSpace)

Часто мы также вызываем функции, которые объединяют в себе несколько функций/Functors/Monads также "комбинаторы", что, возможно, имеет мнемонический смысл

-- the combine combinator
combine :: Applicative f => f a -> f b -> f (a, b)
combine fa fb = (,) <$> fa <*> fb

-- the ignore-what's-next combinator
(<*) :: Applicative f => f a -> f b -> f a
fa <* fb = const <$> fa <*> fb

-- the do-me-then-forget-me combinator
(*>) :: Applicative f => f a -> f b -> f b
fa *> fb = flip const <$> fa <*> fb

line = Parser String
line = many (satisfy $ \c -> c /= '\n') <* satisfy (=='\n')

Но, в конечном счете, комбинаторы больше связаны с намерением и использованием API, чем с его строгим обозначением.Вы часто будете видеть библиотеки, созданные из "базовых элементов", таких как функции или satisfy которые затем модифицируются и объединяются с набором "комбинаторов".Тот Самый Parser приведенный выше пример является типичным примером, но в целом это очень распространенный шаблон Haskell.