Что такое комбинатор в Scala или функциональное программирование

Question

Я изучаю Scala и FP, и в книге «Функциональное программирование в Scala» термин Комбинатор упоминается в главе «Функциональное проектирование иБиблиотеки комбинаторов »в главе Комбинаторы определены как:

Оглядываясь назад на наши реализации, мы заметим общий шаблон: каждая из наших функций имеет тип вида RNG => (A,RNG) для некоторого типа A. Функции этого типа называются действиями состояния или переходами состояний, поскольку они преобразуют состояния RNG из одного в другое. Эти действия состояния могут быть объединены с помощью комбинаторов, которые являются функциями высшего порядка, которые мы определим в этом разделе . Поскольку довольно долго и утомительно передавать состояние долго, мы хотим, чтобы наши комбинаторы автоматически передавали состояние от одного действия к следующему.

Так же, как комбинаторы - функции более высокого порядка илифункций высшего порядка или они являются своего рода техникой (схемой проектирования), или опять-таки они являются алгебраическими типами?

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

Answer 1

A Комбинатор на самом деле является гораздо более общей концепцией. Комбинатор - это, буквально, вещь, которая объединяет другие вещи. (Точно так же, как терминатор - это то, что завершает другие вещи.)

Идея Combinator состоит в том, что вещи, которые он объединяет, и вещи, объединенные, имеют один и тот же тип, так что вы можете снова вызывать Combinator наРезультат работы Combinator.

Одна из популярных областей, где всплывают Combinators, - это синтаксический анализ с так называемыми библиотеками Parser Combinator . Идея состоит в том, что вы строите более сложные парсеры из более простых парсеров, используя Combinators для создания комбинаций более простых парсеров.

Например, библиотека Parser Combinator может предоставлять только один простой парсер: парсер, который может анализироватьровно один персонаж. Если вы хотите проанализировать что-то более сложное, библиотека предоставляет пару Combinators:

• . Sequence Combinator принимает два синтаксических анализатора и создает синтаксический анализатор, который распознает строку, распознанную первым синтаксическим анализатором, за которой следует строка, распознаннаявторым синтаксическим анализатором.
• Alternation Combinator принимает два синтаксических анализатора и создает синтаксический анализатор, который распознает строку, распознанную первым синтаксическим анализатором, или строку, распознанную вторым синтаксическим анализатором.
• Комбинатор повторения принимает одинсинтаксический анализатор и создает синтаксический анализатор, который распознает ноль или более повторений строки, распознаваемой входным анализатором.

С этими тремя комбинаторами и основными односимвольными синтаксическими анализаторами вы можете анализировать все обычные языки.

Здесь важно то, что Combinator возвращает новый синтаксический анализатор. Он не не выполняет синтаксический анализатор.

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

Итак, с помощью Combinators у вас всегда есть две вещи:

• набор «примитивов»"определенного" вида "
• набор комбинаторов, которые принимают одно или несколько значений этого конкретного" вида "и возвращают значение того же конкретного" вида "