# Applicative programming in Ruby: advanced behaviors

**Part 1 | Part 2**

In the previous post we implemented safe currying on applicative functors. We used a container called `Either`

to create these interfaces. In this post we will go even further and create applicative lists and parsers.

## Applicative array

Let’s take a look how functors can be implemented for lists:

```
class ApplicativeArray < Array
include Functor
def fmap(&fn) = map(&fn.curry)
include Applicative
class << self
def pure(x) = ApplicativeArray.new([x])
end
def ^(other)
ApplicativeArray.new(flat_map { |fn| other.fmap(&fn) })
end
end
```

`Functor#fmap`

is almost a regular map, but it uses `curry`

call functions inside the list partially. `pure`

takes the value and wraps it into the array. Application (`^`

) takes function from another array and applies it to each element of the current array. Let’s try it:

```
def plus(x, y) = x + y
def mult(x, y) = x * y
array_with_functions = ApplicativeArray.new([method(:plus), method(:mult)])
array_with_args = ApplicativeArray.new([2, 7])
array_with_args_2 = ApplicativeArray.new([3, 5])
array_with_functions ^ array_with_args ^ array_with_args_2
# => [5, 7, 10, 12, 6, 10, 21, 35]
```

Why 8 elements?

`plus`

is applied to two elements;`mult`

is applied to same elements, getting 4 partially applied functions;- these functions are applied to each of two elements getting 8 elements in total.

Can we apply functions to the corresponding element only? Sure, in Haskell this type of the list is called `ZipList`

:

```
class Applicative::ZipList
attr_reader :list
def initialize(list) = @list = list
include Applicative::Functor
def fmap(&fn) = @list.map(&fn.curry)
include Applicative::ApplicativeFunctor
class << self
def pure(x) = Applicative::ZipList.new(repeatedly { x })
private
def repeatedly(&block)
Enumerator.new do |y|
loop { y << block.call }
end.lazy
end
end
def ^(other)
eager_list =
if @list.is_a?(Enumerator::Lazy) && other.list.is_a?(Enumerator::Lazy)
@list
else
@list.take(other.list.length)
end
Applicative::ZipList.new(eager_list.zip(other.list).map { |fn, x| fn.curry.(x) })
end
end
```

Implementation is slightly more complex, because we have to handle *endless* lists: we need to do that because `pure`

returns it. Here is an example:

```
plus = lambda { |x, y| x + y }
mult = lambda { |x, y| x * y }
functions = ZipList.new([plus, mult])
args = ZipList.new([2, 7])
args_2 = ZipList.new([3, 5])
(functions ^ args ^ args_2).list # => [5, 35]
```

Let’s try the same thing but using `pure`

, that constructs an endless list for us:

```
functions = ZipList::pure(plus) # endless
args = ZipList::pure(2) # endless
args_2 = ZipList.new([4, 6, 8]) # finite
(functions ^ args ^ args_2).list.eager.to_a # => [6, 8, 10]
```

In this case we get only 3 elements (2 + 4, 2 + 6 and 2 + 8).

### Applicative parser

Let’s take a look at more complex application of applicatives: an applicative *parser*. We start with the new data structure called `Pair`

, which can hold two values:

```
class Pair
attr_reader :fst, :snd
def initialize(fst, snd)
@fst = fst
@snd = snd
end
def deconstruct = [@fst, @snd]
include Applicative::Functor
def fmap(&fn) = Pair.new(fst, fn.(snd))
end
```

It will be a functor, where `fmap`

applies function to the *second* element of the pair, without changing the first one. Now let’s define a class that presents a generic parser:

```
class Parser
def initialize(&parse_fn) = @parse_fn = parse_fn
def parse(s) = @parse_fn.(s)
end
```

`parse_fn`

function should accept and parses some string. When parsing fails it should return `Left`

with error message, otherwise — `Right`

with the `Pair`

. The first element of the `Pair`

is the remaining string, the second element is the thing we just parsed. For instance, here is a parser that looks for a character `'x'`

in the beginning of the string:

```
x_parser = Parser.new do |s|
if s.empty?
Left("unexpected end of input") # because there is no 'x' at the beginning of the empty string
else
char = s[0]
char == 'x' ? Right(Pair.new(s[1..], char)) : Left("unexpected #{char}")
end
end
x_parser.parse("") # => Left("unexpected end of input")
x_parser.parse("ab") # => Left("unexpected a")
x_parser.parse("xab") # => Right("ab", "x")
```

Let’s implement `Functor`

for the parser. `fmap`

accepts some function that can be applied to the result of the parser and constructs a new parser. Note that we do not parse anything, just build a new parser:

```
class Parser
include Applicative::Functor
def fmap(&fn)
Parser.new do |s|
parse(s).fmap { |pair| pair.fmap(&fn) }
end
end
end
x_parser.fmap(&:upcase).parse("xab") # => Right("ab", "X")
```

Let’s add a couple of helpers to build parsers easily:

```
class Parser
class << self
def satisfy(&predicate)
Parser.new do |s|
if s.empty?
Left("unexpected end of input")
else
char = s[0]
predicate.(char) ? Right(Pair.new(s[1..], char)) : Left("unexpected #{char}")
end
end
end
def char(c)
satisfy { |current| c == current }
end
def string(str)
Parser.new do |s|
if s.start_with?(str)
Right(Pair.new(s[str.length..], str))
else
Left("unexpected #{s}, expected #{str}")
end
end
end
end
end
```

Now let’s make our parser `Applicative`

to make it possible to combine parsers:

```
class Parser
include Applicative::ApplicativeFunctor
class << self
def pure(value)
Parser.new { |s| Right(Pair.new(s, value)) }
end
end
def ^(other)
Parser.new do |s|
case parse(s)
in Applicative::Either::Right(Pair(s1, g))
case other.parse(s1)
in Applicative::Either::Right(Pair(s2, a)) then Right(Pair.new(s2, g.(a)))
in left then left
end
in left then left
end
end
end
end
```

`pure`

creates a new parser that always “parses” any value we pass, returning the remaining string as is. Application creates a new parser using following steps:

- if current parser cannot parse a string — we return
`Left`

; - otherwise it returns us the remaining string
`s1`

and the result`a`

, we tries to parse`s1`

with the second parser:- if second parser fails — we return
`Left`

; - otherwise second pair returns us a function
`g`

(because we’re in the`Applicative`

), so we return`Right`

:- the first element is a string that remained from the second parser;
- the second element is a result of calling
`g`

with`a`

.

- if second parser fails — we return

This is how it works:

```
parser = (
Parser.pure(lambda { |a, b| a + b }.curry) ^
Parser.char('A') ^
Parser.string("BC")
)
parser.parse("ABC") # => Right ("", "ABC")
```

As you see, `^`

operates as the `AND`

operator: in this example we ask parser to find us character `A`

followed by string `BC`

. What about `OR`

?

```
module Alternative
def |(other) = raise NotImplementedError
end
class Parser
include Alternative
def |(other)
Parser.new do |s|
case parse(s)
in Applicative::Either::Right(r) then Right(r)
in _
case other.parse(s)
in Applicative::Either::Right(r) then Right(r)
in left then left
end
end
end
end
end
```

The new method `|`

tries to parse with the first parser, if it fails — with the second, and returns the result.

Let’s combine everything together:

```
parser = (
Parser.pure(lambda { |a, b, c| a + b + c }.curry) ^
(Parser.char('A') | Parser.char('B')) ^ # we want A or B ...
Parser.char('C') ^ # ... then C ...
Parser.string("42") # ... then 42
).fmap(&:downcase) # parser is functor, so `fmap` can be used to transform the result
parser.parse("AC42D") # => #<Either::Right:… @value=#<Pair:… @fst="D", @snd="ac">>
parser.parse("BC42D") # => #<Either::Right:… @value=#<Pair:… @fst="D", @snd="bc">>
parser.parse("DCB") # => #<Either::Left:… @error="unexpected D">
```

Impressive, right?

### Traversable

Let’s try to build something *on top* of applicatives.

Imagine that you have some applicative container `f`

which has a function from `a`

to `b`

inside. For instance, this function accepts `Either Int`

and tries to increment it returning `Either Int`

:

```
increment = lambda { |either_value| either_value.fmap { |value| value + 1 } }
increment.(Right(42)) # => Right(43)
increment.(Left("error")) # => Left("error")
```

Then, we have a new module called `Traversable`

. It has a single method called `traverse`

:

```
module Traversable
def traverse(applicative_class, &_fn) =
raise NotImplementedError
end
```

This function accepts some `applicative_class`

(which includes `Applicative`

) and a function we described above. The result of the call should be the instance of *the same* `Applicative`

that contains the instance of the *the same* `Traversable`

. `Traversable`

should contain the value, that was returned by `fn`

applied to the data inside the initial traversable.

That sounds smart, so let’s just write it and run. Here is the implementation for array:

```
class ApplicativeArray < Array
include Traversable
def traverse(applicative_class, &fn)
return applicative_class::pure([]) if empty?
x, *xs = self
applicative_class::pure(lambda { |ta, rest| [ta] + rest }) ^
fn.(x) ^
ApplicativeArray.new(xs).traverse(applicative_class, &fn)
end
end
```

And the example of usage:

```
increment = lambda { |maybe_value| maybe_value.fmap { |value| value + 1 } }
ApplicativeArray.new([Right(1), Right(3), Right(5)])
.traverse(Either, &increment) # => #<Either::Right:... @value=[2, 4, 6]>
ApplicativeArray.new([Right(1), Left("error")])
.traverse(Either, &increment) # => #<Either::Left:... @error=“error">
```

Now we can describe the behavior in the easier way: `traverse`

goes through some data structure containing values in containers, applies the function to the value in container and *extracts* container to the top. In our example, list of `Either Int`

becomes `Either`

list of `Int`

:

- if initial list has only
`Right`

then`Right`

will be outside; - if there are any lefts — the first one will be extracted.

## Outro

In this post we implemented two different applicative functors for lists, created a simple (but yet powerful!) applicative parser and made our lists *traversable*. As you see, applicative functor is a powerful abstraction that helps to describe complex behavior and hide it inside the container.

Hopefully one day we will make something out of it!