What is a combinator in Scala or functional programming

Question

I am learning Scala and FP, and in the book "Functional Programming in Scala " the term Combinator is mentioned in the chapter "Functional Design and Combinator Libraries" in the chapter Combinators are defined as:

Looking back at our implementations, we’ll notice a common pattern: each of our functions has a type of the form RNG => (A, RNG) for some type A. Functions of this type are called state actions or state transitions because they transform RNG states from one to the next. These state actions can be combined using combinators, which are higher-order functions that we’ll define in this section. Since it’s pretty tedious and repetitive to pass the state a long ourselves, we want our combinators to pass the state from one action to the next automatically.

So is combinators a higher-order functions or a kind of higher-order functions or are they some sort of a technique(design pattern) or again they are some algebraic types?

To make answering more precise the questions is: What are combinators, where do they originate from, where they are used, what is special about them?

• Gsquare: Answers to this question might help

Answer 1

A Combinator is actually a much more general concept. A Combinator is, quite literally, a thing that combines other things. (Just like a Terminator is a thing that terminates other things.)

The idea of a Combinator is that the things it combines and the combined thing have the same type, so that you can invoke the Combinator again on the result of the Combinator.

One of the popular areas where Combinators pop up is in parsing, with so-called Parser Combinator libraries. The idea is that you build more complex parsers out of simpler parsers, by using Combinators to build combinations of simpler parsers.

For example, a Parser Combinator library might only provide one single simple parser: a parser that can parse exactly one character. If you want to parse anything more complex, the library provides a couple of Combinators:

• The Sequence Combinator takes two parsers and produces a parser that recognizes the string recognized by the first parser followed by the string recognized by the second parser.
• The Alternation Combinator takes two parsers and produces a parser that recognizes the string recognized by the first parser or the string recognized by the second parser.
• The Repetition Combinator takes one parser and produces a parser that recognizes zero or more repetitions of the string recognized by the input parser.

With these three Combinators, and the fundamental "one-character" parsers, you can parse all regular languages.

The important thing here is that the Combinator returns a new parser. It does not execute the parser.

In a functional language, both the parsers and the combinators will typically be functions, and so the combinators will be higher-order functions. But, that doesn't have to be the case. E.g. the parsers could be objects and the combinators functions, that makes the combinators just ordinary functions.

So, with Combinators, you always have two things:

• a set of "primitives" of a specific "kind"
• a set of Combinators that take one or more values of that specific "kind" and return a value of that same specific "kind"