# /// script
# requires-python = ">=3.12"
# dependencies = [
# "marimo",
# ]
# ///
import marimo
__generated_with = "0.12.9"
app = marimo.App(app_title="Applicative programming with effects")
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
# Applicative programming with effects
`Applicative Functor` encapsulates certain sorts of *effectful* computations in a functionally pure way, and encourages an *applicative* programming style.
Applicative is a functor with application, providing operations to
+ embed pure expressions (`pure`), and
+ sequence computations and combine their results (`apply`).
In this notebook, you will learn:
1. How to view `Applicative` as multi-functor intuitively.
2. How to use `lift` to simplify chaining application.
3. How to bring *effects* to the functional pure world.
4. How to view `Applicative` as a lax monoidal functor.
5. How to use `Alternative` to amalgamate multiple computations into a single computation.
/// details | Notebook metadata
type: info
version: 0.1.3 | last modified: 2025-04-16 | author: [métaboulie](https://github.com/metaboulie)<br/>
reviewer: [Haleshot](https://github.com/Haleshot)
///
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
# The intuition: [Multifunctor](https://arxiv.org/pdf/2401.14286)
## Limitations of functor
Recall that functors abstract the idea of mapping a function over each element of a structure.
Suppose now that we wish to generalise this idea to allow functions with any number of arguments to be mapped, rather than being restricted to functions with a single argument. More precisely, suppose that we wish to define a hierarchy of `fmap` functions with the following types:
```haskell
fmap0 :: a -> f a
fmap1 :: (a -> b) -> f a -> f b
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
```
And we have to declare a special version of the functor class for each case.
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Defining Multifunctor
/// admonition
we use prefix `f` rather than `ap` to indicate *Applicative Functor*
///
As a result, we may want to define a single `Multifunctor` such that:
1. Lift a regular n-argument function into the context of functors
```python
# lift a regular 3-argument function `g`
g: Callable[[A, B, C], D]
# into the context of functors
fg: Callable[[Functor[A], Functor[B], Functor[C]], Functor[D]]
```
3. Apply it to n functor-wrapped values
```python
# fa: Functor[A], fb: Functor[B], fc: Functor[C]
fg(fa, fb, fc)
```
5. Get a single functor-wrapped result
```python
fd: Functor[D]
```
We will define a function `lift` such that
```python
fd = lift(g, fa, fb, fc)
```
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Pure, apply and lift
Traditionally, applicative functors are presented through two core operations:
1. `pure`: embeds an object (value or function) into the applicative functor
```python
# a -> F a
pure: Callable[[A], Applicative[A]]
# for example, if `a` is
a: A
# then we can have `fa` as
fa: Applicative[A] = pure(a)
# or if we have a regular function `g`
g: Callable[[A], B]
# then we can have `fg` as
fg: Applicative[Callable[[A], B]] = pure(g)
```
2. `apply`: applies a function inside an applicative functor to a value inside an applicative functor
```python
# F (a -> b) -> F a -> F b
apply: Callable[[Applicative[Callable[[A], B]], Applicative[A]], Applicative[B]]
# and we can have
fd = apply(apply(apply(fg, fa), fb), fc)
```
As a result,
```python
lift(g, fa, fb, fc) = apply(apply(apply(pure(g), fa), fb), fc)
```
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
/// admonition | How to use *Applicative* in the manner of *Multifunctor*
1. Define `pure` and `apply` for an `Applicative` subclass
- We can define them much easier compared with `lift`.
2. Use the `lift` method
- We can use it much more convenient compared with the combination of `pure` and `apply`.
///
/// attention | You can suppress the chaining application of `apply` and `pure` as:
```python
apply(pure(g), fa) -> lift(g, fa)
apply(apply(pure(g), fa), fb) -> lift(g, fa, fb)
apply(apply(apply(pure(g), fa), fb), fc) -> lift(g, fa, fb, fc)
```
///
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Abstracting applicatives
We can now provide an initial abstraction definition of applicatives:
```python
@dataclass
class Applicative[A](Functor, ABC):
@classmethod
@abstractmethod
def pure(cls, a: A) -> "Applicative[A]":
raise NotImplementedError("Subclasses must implement pure")
@classmethod
@abstractmethod
def apply(
cls, fg: "Applicative[Callable[[A], B]]", fa: "Applicative[A]"
) -> "Applicative[B]":
raise NotImplementedError("Subclasses must implement apply")
@classmethod
def lift(cls, f: Callable, *args: "Applicative") -> "Applicative":
curr = cls.pure(f)
if not args:
return curr
for arg in args:
curr = cls.apply(curr, arg)
return curr
```
/// attention | minimal implementation requirement
- `pure`
- `apply`
///
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""# Instances, laws and utility functions""")
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Applicative instances
When we are actually implementing an *Applicative* instance, we can keep in mind that `pure` and `apply` fundamentally:
- embed an object (value or function) to the computational context
- apply a function inside the computation context to a value inside the computational context
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
### The Wrapper Applicative
- `pure` should simply *wrap* an object, in the sense that:
```haskell
Wrapper.pure(1) => Wrapper(value=1)
```
- `apply` should apply a *wrapped* function to a *wrapped* value
The implementation is:
"""
)
@app.cell
def _(Applicative, dataclass):
@dataclass
class Wrapper[A](Applicative):
value: A
@classmethod
def pure(cls, a: A) -> "Wrapper[A]":
return cls(a)
@classmethod
def apply(
cls, fg: "Wrapper[Callable[[A], B]]", fa: "Wrapper[A]"
) -> "Wrapper[B]":
return cls(fg.value(fa.value))
return (Wrapper,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""> try with Wrapper below""")
@app.cell
def _(Wrapper) -> None:
Wrapper.lift(
lambda a: lambda b: lambda c: a + b * c,
Wrapper(1),
Wrapper(2),
Wrapper(3),
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
### The List Applicative
- `pure` should wrap the object in a list, in the sense that:
```haskell
List.pure(1) => List(value=[1])
```
- `apply` should apply a list of functions to a list of values
- you can think of this as cartesian product, concatenating the result of applying every function to every value
The implementation is:
"""
)
@app.cell
def _(Applicative, dataclass, product):
@dataclass
class List[A](Applicative):
value: list[A]
@classmethod
def pure(cls, a: A) -> "List[A]":
return cls([a])
@classmethod
def apply(cls, fg: "List[Callable[[A], B]]", fa: "List[A]") -> "List[B]":
return cls([g(a) for g, a in product(fg.value, fa.value)])
return (List,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""> try with List below""")
@app.cell
def _(List) -> None:
List.apply(
List([lambda a: a + 1, lambda a: a * 2]),
List([1, 2]),
)
@app.cell
def _(List) -> None:
List.lift(lambda a: lambda b: a + b, List([1, 2]), List([3, 4, 5]))
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
### The Maybe Applicative
- `pure` should wrap the object in a Maybe, in the sense that:
```haskell
Maybe.pure(1) => "Just 1"
Maybe.pure(None) => "Nothing"
```
- `apply` should apply a function maybe exist to a value maybe exist
- if the function is `None` or the value is `None`, simply returns `None`
- else apply the function to the value and wrap the result in `Just`
The implementation is:
"""
)
@app.cell
def _(Applicative, dataclass):
@dataclass
class Maybe[A](Applicative):
value: None | A
@classmethod
def pure(cls, a: A) -> "Maybe[A]":
return cls(a)
@classmethod
def apply(
cls, fg: "Maybe[Callable[[A], B]]", fa: "Maybe[A]"
) -> "Maybe[B]":
if fg.value is None or fa.value is None:
return cls(None)
return cls(fg.value(fa.value))
def __repr__(self):
return "Nothing" if self.value is None else f"Just({self.value!r})"
return (Maybe,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""> try with Maybe below""")
@app.cell
def _(Maybe) -> None:
Maybe.lift(
lambda a: lambda b: a + b,
Maybe(1),
Maybe(2),
)
@app.cell
def _(Maybe) -> None:
Maybe.lift(
lambda a: lambda b: None,
Maybe(1),
Maybe(2),
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
### The Either Applicative
- `pure` should wrap the object in `Right`, in the sense that:
```haskell
Either.pure(1) => Right(1)
```
- `apply` should apply a function that is either on Left or Right to a value that is either on Left or Right
- if the function is `Left`, simply returns the `Left` of the function
- else `fmap` the `Right` of the function to the value
The implementation is:
"""
)
@app.cell
def _(Applicative, B, Callable, Union, dataclass):
@dataclass
class Either[A](Applicative):
left: A = None
right: A = None
def __post_init__(self):
if (self.left is not None and self.right is not None) or (
self.left is None and self.right is None
):
msg = "Provide either the value of the left or the value of the right."
raise TypeError(
msg
)
@classmethod
def pure(cls, a: A) -> "Either[A]":
return cls(right=a)
@classmethod
def apply(
cls, fg: "Either[Callable[[A], B]]", fa: "Either[A]"
) -> "Either[B]":
if fg.left is not None:
return cls(left=fg.left)
return cls.fmap(fg.right, fa)
@classmethod
def fmap(
cls, g: Callable[[A], B], fa: "Either[A]"
) -> Union["Either[A]", "Either[B]"]:
if fa.left is not None:
return cls(left=fa.left)
return cls(right=g(fa.right))
def __repr__(self):
if self.left is not None:
return f"Left({self.left!r})"
return f"Right({self.right!r})"
return (Either,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""> try with `Either` below""")
@app.cell
def _(Either) -> None:
Either.apply(Either(left=TypeError("Parse Error")), Either(right=2))
@app.cell
def _(Either) -> None:
Either.apply(
Either(right=lambda x: x + 1), Either(left=TypeError("Parse Error"))
)
@app.cell
def _(Either) -> None:
Either.apply(Either(right=lambda x: x + 1), Either(right=1))
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Collect the list of response with sequenceL
One often wants to execute a list of commands and collect the list of their response, and we can define a function `sequenceL` for this
/// admonition
In a further notebook about `Traversable`, we will have a more generic `sequence` that execute a **sequence** of commands and collect the **sequence** of their response, which is not limited to `list`.
///
```python
@classmethod
def sequenceL(cls, fas: list["Applicative[A]"]) -> "Applicative[list[A]]":
if not fas:
return cls.pure([])
return cls.apply(
cls.fmap(lambda v: lambda vs: [v] + vs, fas[0]),
cls.sequenceL(fas[1:]),
)
```
Let's try `sequenceL` with the instances.
"""
)
@app.cell
def _(Wrapper) -> None:
Wrapper.sequenceL([Wrapper(1), Wrapper(2), Wrapper(3)])
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
/// attention
For the `Maybe` Applicative, the presence of any `Nothing` causes the entire computation to return Nothing.
///
"""
)
@app.cell
def _(Maybe) -> None:
Maybe.sequenceL([Maybe(1), Maybe(2), Maybe(None), Maybe(3)])
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""The result of `sequenceL` for `List Applicative` is the Cartesian product of the input lists, yielding all possible ordered combinations of elements from each list.""")
@app.cell
def _(List) -> None:
List.sequenceL([List([1, 2]), List([3]), List([5, 6, 7])])
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Applicative laws
/// admonition | id and compose
Remember that
- `id = lambda x: x`
- `compose = lambda f: lambda g: lambda x: f(g(x))`
///
Traditionally, there are four laws that `Applicative` instances should satisfy. In some sense, they are all concerned with making sure that `pure` deserves its name:
- The identity law:
```python
# fa: Applicative[A]
apply(pure(id), fa) = fa
```
- Homomorphism:
```python
# a: A
# g: Callable[[A], B]
apply(pure(g), pure(a)) = pure(g(a))
```
Intuitively, applying a non-effectful function to a non-effectful argument in an effectful context is the same as just applying the function to the argument and then injecting the result into the context with pure.
- Interchange:
```python
# a: A
# fg: Applicative[Callable[[A], B]]
apply(fg, pure(a)) = apply(pure(lambda g: g(a)), fg)
```
Intuitively, this says that when evaluating the application of an effectful function to a pure argument, the order in which we evaluate the function and its argument doesn't matter.
- Composition:
```python
# fg: Applicative[Callable[[B], C]]
# fh: Applicative[Callable[[A], B]]
# fa: Applicative[A]
apply(fg, apply(fh, fa)) = lift(compose, fg, fh, fa)
```
This one is the trickiest law to gain intuition for. In some sense it is expressing a sort of associativity property of `apply`.
We can add 4 helper functions to `Applicative` to check whether an instance respects the laws or not:
```python
@dataclass
class Applicative[A](Functor, ABC):
@classmethod
def check_identity(cls, fa: "Applicative[A]"):
if cls.lift(id, fa) != fa:
raise ValueError("Instance violates identity law")
return True
@classmethod
def check_homomorphism(cls, a: A, f: Callable[[A], B]):
if cls.lift(f, cls.pure(a)) != cls.pure(f(a)):
raise ValueError("Instance violates homomorphism law")
return True
@classmethod
def check_interchange(cls, a: A, fg: "Applicative[Callable[[A], B]]"):
if cls.apply(fg, cls.pure(a)) != cls.lift(lambda g: g(a), fg):
raise ValueError("Instance violates interchange law")
return True
@classmethod
def check_composition(
cls,
fg: "Applicative[Callable[[B], C]]",
fh: "Applicative[Callable[[A], B]]",
fa: "Applicative[A]",
):
if cls.apply(fg, cls.apply(fh, fa)) != cls.lift(compose, fg, fh, fa):
raise ValueError("Instance violates composition law")
return True
```
> Try to validate applicative laws below
"""
)
@app.cell
def _():
id = lambda x: x
compose = lambda f: lambda g: lambda x: f(g(x))
const = lambda a: lambda _: a
return compose, const, id
@app.cell
def _(List, Wrapper) -> None:
print("Checking Wrapper")
print(Wrapper.check_identity(Wrapper.pure(1)))
print(Wrapper.check_homomorphism(1, lambda x: x + 1))
print(Wrapper.check_interchange(1, Wrapper.pure(lambda x: x + 1)))
print(
Wrapper.check_composition(
Wrapper.pure(lambda x: x * 2),
Wrapper.pure(lambda x: x + 0.1),
Wrapper.pure(1),
)
)
print("\nChecking List")
print(List.check_identity(List.pure(1)))
print(List.check_homomorphism(1, lambda x: x + 1))
print(List.check_interchange(1, List.pure(lambda x: x + 1)))
print(
List.check_composition(
List.pure(lambda x: x * 2), List.pure(lambda x: x + 0.1), List.pure(1)
)
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Utility functions
/// attention | using `fmap`
`fmap` is defined automatically using `pure` and `apply`, so you can use `fmap` with any `Applicative`
///
```python
@dataclass
class Applicative[A](Functor, ABC):
@classmethod
def skip(
cls, fa: "Applicative[A]", fb: "Applicative[B]"
) -> "Applicative[B]":
'''
Sequences the effects of two Applicative computations,
but discards the result of the first.
'''
return cls.apply(cls.const(fa, id), fb)
@classmethod
def keep(
cls, fa: "Applicative[A]", fb: "Applicative[B]"
) -> "Applicative[B]":
'''
Sequences the effects of two Applicative computations,
but discard the result of the second.
'''
return cls.lift(const, fa, fb)
@classmethod
def revapp(
cls, fa: "Applicative[A]", fg: "Applicative[Callable[[A], [B]]]"
) -> "Applicative[B]":
'''
The first computation produces values which are provided
as input to the function(s) produced by the second computation.
'''
return cls.lift(lambda a: lambda f: f(a), fa, fg)
```
- `skip` sequences the effects of two Applicative computations, but **discards the result of the first**. For example, if `m1` and `m2` are instances of type `Maybe[Int]`, then `Maybe.skip(m1, m2)` is `Nothing` whenever either `m1` or `m2` is `Nothing`; but if not, it will have the same value as `m2`.
- Likewise, `keep` sequences the effects of two computations, but **keeps only the result of the first**.
- `revapp` is similar to `apply`, but where the first computation produces value(s) which are provided as input to the function(s) produced by the second computation.
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
/// admonition | Exercise
Try to use utility functions with different instances
///
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
# Formal implementation of Applicative
Now, we can give the formal implementation of `Applicative`
"""
)
@app.cell
def _(
ABC,
B,
Callable,
Functor,
abstractmethod,
compose,
const,
dataclass,
id,
):
@dataclass
class Applicative[A](Functor, ABC):
@classmethod
@abstractmethod
def pure(cls, a: A) -> "Applicative[A]":
"""Lift a value into the Structure."""
msg = "Subclasses must implement pure"
raise NotImplementedError(msg)
@classmethod
@abstractmethod
def apply(
cls, fg: "Applicative[Callable[[A], B]]", fa: "Applicative[A]"
) -> "Applicative[B]":
"""Sequential application."""
msg = "Subclasses must implement apply"
raise NotImplementedError(msg)
@classmethod
def lift(cls, f: Callable, *args: "Applicative") -> "Applicative":
"""Lift a function of arbitrary arity to work with values in applicative context."""
curr = cls.pure(f)
if not args:
return curr
for arg in args:
curr = cls.apply(curr, arg)
return curr
@classmethod
def fmap(
cls, f: Callable[[A], B], fa: "Applicative[A]"
) -> "Applicative[B]":
return cls.lift(f, fa)
@classmethod
def sequenceL(cls, fas: list["Applicative[A]"]) -> "Applicative[list[A]]":
"""
Execute a list of commands and collect the list of their response.
"""
if not fas:
return cls.pure([])
return cls.apply(
cls.fmap(lambda v: lambda vs: [v, *vs], fas[0]),
cls.sequenceL(fas[1:]),
)
@classmethod
def skip(
cls, fa: "Applicative[A]", fb: "Applicative[B]"
) -> "Applicative[B]":
"""
Sequences the effects of two Applicative computations,
but discards the result of the first.
"""
return cls.apply(cls.const(fa, id), fb)
@classmethod
def keep(
cls, fa: "Applicative[A]", fb: "Applicative[B]"
) -> "Applicative[B]":
"""
Sequences the effects of two Applicative computations,
but discard the result of the second.
"""
return cls.lift(const, fa, fb)
@classmethod
def revapp(
cls, fa: "Applicative[A]", fg: "Applicative[Callable[[A], [B]]]"
) -> "Applicative[B]":
"""
The first computation produces values which are provided
as input to the function(s) produced by the second computation.
"""
return cls.lift(lambda a: lambda f: f(a), fa, fg)
@classmethod
def check_identity(cls, fa: "Applicative[A]") -> bool:
if cls.lift(id, fa) != fa:
msg = "Instance violates identity law"
raise ValueError(msg)
return True
@classmethod
def check_homomorphism(cls, a: A, f: Callable[[A], B]) -> bool:
if cls.lift(f, cls.pure(a)) != cls.pure(f(a)):
msg = "Instance violates homomorphism law"
raise ValueError(msg)
return True
@classmethod
def check_interchange(cls, a: A, fg: "Applicative[Callable[[A], B]]") -> bool:
if cls.apply(fg, cls.pure(a)) != cls.lift(lambda g: g(a), fg):
msg = "Instance violates interchange law"
raise ValueError(msg)
return True
@classmethod
def check_composition(
cls,
fg: "Applicative[Callable[[B], C]]",
fh: "Applicative[Callable[[A], B]]",
fa: "Applicative[A]",
) -> bool:
if cls.apply(fg, cls.apply(fh, fa)) != cls.lift(compose, fg, fh, fa):
msg = "Instance violates composition law"
raise ValueError(msg)
return True
return (Applicative,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
# Effectful programming
Our original motivation for applicatives was the desire to generalise the idea of mapping to functions with multiple arguments. This is a valid interpretation of the concept of applicatives, but from the three instances we have seen it becomes clear that there is also another, more abstract view.
The arguments are no longer just plain values but may also have effects, such as the possibility of failure, having many ways to succeed, or performing input/output actions. In this manner, applicative functors can also be viewed as abstracting the idea of **applying pure functions to effectful arguments**, with the precise form of effects that are permitted depending on the nature of the underlying functor.
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## The IO Applicative
We will try to define an `IO` applicative here.
As before, we first abstract how `pure` and `apply` should function.
- `pure` should wrap the object in an IO action, and make the object *callable* if it's not because we want to perform the action later:
```haskell
IO.pure(1) => IO(effect=lambda: 1)
IO.pure(f) => IO(effect=f)
```
- `apply` should perform an action that produces a value, then apply the function with the value
The implementation is:
"""
)
@app.cell
def _(Applicative, Callable, dataclass):
@dataclass
class IO(Applicative):
effect: Callable
def __call__(self):
return self.effect()
@classmethod
def pure(cls, a):
return cls(a) if isinstance(a, Callable) else IO(lambda: a)
@classmethod
def apply(cls, fg, fa):
return cls.pure(fg.effect(fa.effect()))
return (IO,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""For example, a function that reads a given number of lines from the keyboard can be defined in applicative style as follows:""")
@app.cell
def _(IO):
def get_chars(n: int = 3):
return IO.sequenceL([
IO.pure(input(f"input the {i}th str")) for i in range(1, n + 1)
])
return (get_chars,)
@app.cell
def _() -> None:
# get_chars()()
return
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""# From the perspective of category theory""")
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Lax Monoidal Functor
An alternative, equivalent formulation of `Applicative` is given by
"""
)
@app.cell
def _(ABC, Functor, abstractmethod, dataclass):
@dataclass
class Monoidal[A](Functor, ABC):
@classmethod
@abstractmethod
def unit(cls) -> "Monoidal[Tuple[()]]":
pass
@classmethod
@abstractmethod
def tensor(
cls, this: "Monoidal[A]", other: "Monoidal[B]"
) -> "Monoidal[Tuple[A, B]]":
pass
return (Monoidal,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
Intuitively, this states that a *monoidal functor* is one which has some sort of "default shape" and which supports some sort of "combining" operation.
- `unit` provides the identity element
- `tensor` combines two contexts into a product context
More technically, the idea is that `monoidal functor` preserves the "monoidal structure" given by the pairing constructor `(,)` and unit type `()`.
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
Furthermore, to deserve the name "monoidal", instances of Monoidal ought to satisfy the following laws, which seem much more straightforward than the traditional Applicative laws:
- Left identity
`tensor(unit, v) ≅ v`
- Right identity
`tensor(u, unit) ≅ u`
- Associativity
`tensor(u, tensor(v, w)) ≅ tensor(tensor(u, v), w)`
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
/// admonition | ≅ indicates isomorphism
`≅` refers to *isomorphism* rather than equality.
In particular we consider `(x, ()) ≅ x ≅ ((), x)` and `((x, y), z) ≅ (x, (y, z))`
///
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Mutual definability of Monoidal and Applicative
We can implement `pure` and `apply` in terms of `unit` and `tensor`, and vice versa.
```python
pure(a) = fmap((lambda _: a), unit)
apply(fg, fa) = fmap((lambda pair: pair[0](pair[1])), tensor(fg, fa))
```
```python
unit() = pure(())
tensor(fa, fb) = lift(lambda fa: lambda fb: (fa, fb), fa, fb)
```
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Instance: ListMonoidal
- `unit` should simply return a empty tuple wrapper in a list
```haskell
ListMonoidal.unit() => [()]
```
- `tensor` should return the *cartesian product* of the items of 2 ListMonoidal instances
The implementation is:
"""
)
@app.cell
def _(B, Callable, Monoidal, dataclass, product):
@dataclass
class ListMonoidal[A](Monoidal):
items: list[A]
@classmethod
def unit(cls) -> "ListMonoidal[Tuple[()]]":
return cls([()])
@classmethod
def tensor(
cls, this: "ListMonoidal[A]", other: "ListMonoidal[B]"
) -> "ListMonoidal[Tuple[A, B]]":
return cls(list(product(this.items, other.items)))
@classmethod
def fmap(
cls, f: Callable[[A], B], ma: "ListMonoidal[A]"
) -> "ListMonoidal[B]":
return cls([f(a) for a in ma.items])
return (ListMonoidal,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""> try with `ListMonoidal` below""")
@app.cell
def _(ListMonoidal):
xs = ListMonoidal([1, 2])
ys = ListMonoidal(["a", "b"])
ListMonoidal.tensor(xs, ys)
return xs, ys
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""and we can prove that `tensor(fa, fb) = lift(lambda fa: lambda fb: (fa, fb), fa, fb)`:""")
@app.cell
def _(List, xs, ys) -> None:
List.lift(lambda fa: lambda fb: (fa, fb), List(xs.items), List(ys.items))
@app.cell(hide_code=True)
def _(ABC, B, Callable, abstractmethod, dataclass):
@dataclass
class Functor[A](ABC):
@classmethod
@abstractmethod
def fmap(cls, f: Callable[[A], B], a: "Functor[A]") -> "Functor[B]":
msg = "Subclasses must implement fmap"
raise NotImplementedError(msg)
@classmethod
def const(cls, a: "Functor[A]", b: B) -> "Functor[B]":
return cls.fmap(lambda _: b, a)
@classmethod
def void(cls, a: "Functor[A]") -> "Functor[None]":
return cls.const_fmap(a, None)
return (Functor,)
@app.cell(hide_code=True)
def _():
import marimo as mo
return (mo,)
@app.cell(hide_code=True)
def _():
from abc import ABC, abstractmethod
from collections.abc import Callable
from dataclasses import dataclass
from typing import TypeVar, Union
return ABC, Callable, TypeVar, Union, abstractmethod, dataclass
@app.cell(hide_code=True)
def _():
from itertools import product
return (product,)
@app.cell(hide_code=True)
def _(TypeVar):
A = TypeVar("A")
B = TypeVar("B")
C = TypeVar("C")
return A, B, C
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
# From Applicative to Alternative
## Abstracting Alternative
In our studies so far, we saw that both `Maybe` and `List` can represent computations with a varying number of results.
We use `Maybe` to indicate a computation can fail somehow and `List` for computations that can have many possible results. In both of these cases, one useful operation is amalgamating all possible results from multiple computations into a single computation.
`Alternative` formalizes computations that support:
- **Failure** (empty result)
- **Choice** (combination of results)
- **Repetition** (multiple results)
It extends `Applicative` with monoidal structure, where:
```python
@dataclass
class Alternative[A](Applicative, ABC):
@classmethod
@abstractmethod
def empty(cls) -> "Alternative[A]":
'''Identity element for alternative computations'''
@classmethod
@abstractmethod
def alt(
cls, fa: "Alternative[A]", fb: "Alternative[A]"
) -> "Alternative[A]":
'''Binary operation combining computations'''
```
- `empty` is the identity element (e.g., `Maybe(None)`, `List([])`)
- `alt` is a combination operator (e.g., `Maybe` fallback, list concatenation)
`empty` and `alt` should satisfy the following **laws**:
```python
# Left identity
alt(empty, fa) == fa
# Right identity
alt(fa, empty) == fa
# Associativity
alt(fa, alt(fb, fc)) == alt(alt(fa, fb), fc)
```
/// admonition
Actually, `Alternative` is a *monoid* on `Applicative Functors`. We will talk about *monoid* and review these laws in the next notebook about `Monads`.
///
/// attention | minimal implementation requirement
- `empty`
- `alt`
///
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## Instances of Alternative
### The Maybe Alternative
- `empty`: the identity element of `Maybe` is `Maybe(None)`
- `alt`: return the first element if it's not `None`, else return the second element
"""
)
@app.cell
def _(Alternative, Maybe, dataclass):
@dataclass
class AltMaybe[A](Maybe, Alternative):
@classmethod
def empty(cls) -> "AltMaybe[A]":
return cls(None)
@classmethod
def alt(cls, fa: "AltMaybe[A]", fb: "AltMaybe[A]") -> "AltMaybe[A]":
if fa.value is not None:
return cls(fa.value)
return cls(fb.value)
def __repr__(self):
return "Nothing" if self.value is None else f"Just({self.value!r})"
return (AltMaybe,)
@app.cell
def _(AltMaybe) -> None:
print(AltMaybe.empty())
print(AltMaybe.alt(AltMaybe(None), AltMaybe(1)))
print(AltMaybe.alt(AltMaybe(None), AltMaybe(None)))
print(AltMaybe.alt(AltMaybe(1), AltMaybe(None)))
print(AltMaybe.alt(AltMaybe(1), AltMaybe(2)))
@app.cell
def _(AltMaybe) -> None:
print(AltMaybe.check_left_identity(AltMaybe(1)))
print(AltMaybe.check_right_identity(AltMaybe(1)))
print(AltMaybe.check_associativity(AltMaybe(1), AltMaybe(2), AltMaybe(None)))
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
### The List Alternative
- `empty`: the identity element of `List` is `List([])`
- `alt`: return the concatenation of 2 input lists
"""
)
@app.cell
def _(Alternative, List, dataclass):
@dataclass
class AltList[A](List, Alternative):
@classmethod
def empty(cls) -> "AltList[A]":
return cls([])
@classmethod
def alt(cls, fa: "AltList[A]", fb: "AltList[A]") -> "AltList[A]":
return cls(fa.value + fb.value)
return (AltList,)
@app.cell
def _(AltList) -> None:
print(AltList.empty())
print(AltList.alt(AltList([1, 2, 3]), AltList([4, 5])))
@app.cell
def _(AltList) -> None:
AltList([1])
@app.cell
def _(AltList) -> None:
AltList([1])
@app.cell
def _(AltList) -> None:
print(AltList.check_left_identity(AltList([1, 2, 3])))
print(AltList.check_right_identity(AltList([1, 2, 3])))
print(
AltList.check_associativity(
AltList([1, 2]), AltList([3, 4, 5]), AltList([6])
)
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
## some and many
/// admonition | This section mainly refers to
- https://stackoverflow.com/questions/7671009/some-and-many-functions-from-the-alternative-type-class/7681283#7681283
///
First let's have a look at the implementation of `some` and `many`:
```python
@classmethod
def some(cls, fa: "Alternative[A]") -> "Alternative[list[A]]":
# Short-circuit if input is empty
if fa == cls.empty():
return cls.empty()
return cls.apply(
cls.fmap(lambda a: lambda b: [a] + b, fa), cls.many(fa)
)
@classmethod
def many(cls, fa: "Alternative[A]") -> "Alternative[list[A]]":
# Directly return empty list if input is empty
if fa == cls.empty():
return cls.pure([])
return cls.alt(cls.some(fa), cls.pure([]))
```
So `some f` runs `f` once, then *many* times, and conses the results. `many f` runs f *some* times, or *alternatively* just returns the empty list.
The idea is that they both run `f` as often as possible until it **fails**, collecting the results in a list. The difference is that `some f` immediately fails if `f` fails, while `many f` will still succeed and *return* the empty list in such a case. But what all this exactly means depends on how `alt` is defined.
Let's see what it does for the instances `AltMaybe` and `AltList`.
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""For `AltMaybe`. `None` means failure, so some `None` fails as well and evaluates to `None` while many `None` succeeds and evaluates to `Just []`. Both `some (Just ())` and `many (Just ())` never return, because `Just ()` never fails.""")
@app.cell
def _(AltMaybe) -> None:
print(AltMaybe.some(AltMaybe.empty()))
print(AltMaybe.many(AltMaybe.empty()))
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""For `AltList`, `[]` means failure, so `some []` evaluates to `[]` (no answers) while `many []` evaluates to `[[]]` (there's one answer and it is the empty list). Again `some [()]` and `many [()]` don't return.""")
@app.cell
def _(AltList) -> None:
print(AltList.some(AltList.empty()))
print(AltList.many(AltList.empty()))
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(r"""## Formal implementation of Alternative""")
@app.cell
def _(ABC, Applicative, abstractmethod, dataclass):
@dataclass
class Alternative[A](Applicative, ABC):
"""A monoid on applicative functors."""
@classmethod
@abstractmethod
def empty(cls) -> "Alternative[A]":
msg = "Subclasses must implement empty"
raise NotImplementedError(msg)
@classmethod
@abstractmethod
def alt(
cls, fa: "Alternative[A]", fb: "Alternative[A]"
) -> "Alternative[A]":
msg = "Subclasses must implement alt"
raise NotImplementedError(msg)
@classmethod
def some(cls, fa: "Alternative[A]") -> "Alternative[list[A]]":
# Short-circuit if input is empty
if fa == cls.empty():
return cls.empty()
return cls.apply(
cls.fmap(lambda a: lambda b: [a, *b], fa), cls.many(fa)
)
@classmethod
def many(cls, fa: "Alternative[A]") -> "Alternative[list[A]]":
# Directly return empty list if input is empty
if fa == cls.empty():
return cls.pure([])
return cls.alt(cls.some(fa), cls.pure([]))
@classmethod
def check_left_identity(cls, fa: "Alternative[A]") -> bool:
return cls.alt(cls.empty(), fa) == fa
@classmethod
def check_right_identity(cls, fa: "Alternative[A]") -> bool:
return cls.alt(fa, cls.empty()) == fa
@classmethod
def check_associativity(
cls, fa: "Alternative[A]", fb: "Alternative[A]", fc: "Alternative[A]"
) -> bool:
return cls.alt(fa, cls.alt(fb, fc)) == cls.alt(cls.alt(fa, fb), fc)
return (Alternative,)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
/// admonition
We will explore more about `Alternative` in a future notebooks about [Monadic Parsing](https://www.cambridge.org/core/journals/journal-of-functional-programming/article/monadic-parsing-in-haskell/E557DFCCE00E0D4B6ED02F3FB0466093)
///
"""
)
@app.cell(hide_code=True)
def _(mo) -> None:
mo.md(
r"""
# Further reading
Notice that these reading sources are optional and non-trivial
- [Applicaive Programming with Effects](https://www.staff.city.ac.uk/~ross/papers/Applicative.html)
- [Equivalence of Applicative Functors and
Multifunctors](https://arxiv.org/pdf/2401.14286)
- [Applicative functor](https://wiki.haskell.org/index.php?title=Applicative_functor)
- [Control.Applicative](https://hackage.haskell.org/package/base-4.21.0.0/docs/Control-Applicative.html#t:Applicative)
- [Typeclassopedia#Applicative](https://wiki.haskell.org/index.php?title=Typeclassopedia#Applicative)
- [Notions of computation as monoids](https://www.cambridge.org/core/journals/journal-of-functional-programming/article/notions-of-computation-as-monoids/70019FC0F2384270E9F41B9719042528)
- [Free Applicative Functors](https://arxiv.org/abs/1403.0749)
- [The basics of applicative functors, put to practical work](http://www.serpentine.com/blog/2008/02/06/the-basics-of-applicative-functors-put-to-practical-work/)
- [Abstracting with Applicatives](http://comonad.com/reader/2012/abstracting-with-applicatives/)
- [Static analysis with Applicatives](https://gergo.erdi.hu/blog/2012-12-01-static_analysis_with_applicatives/)
- [Explaining Applicative functor in categorical terms - monoidal functors](https://cstheory.stackexchange.com/questions/12412/explaining-applicative-functor-in-categorical-terms-monoidal-functors)
- [Applicative, A Strong Lax Monoidal Functor](https://beuke.org/applicative/)
- [Applicative Functors](https://bartoszmilewski.com/2017/02/06/applicative-functors/)
"""
)
if __name__ == "__main__":
app.run()