# Pretty's implementation

This is a brief summary of some interesting parts of Pretty's implementation.

## 1 Tagged unions

The Haskell code in Wadler's paper makes frequent use of tagged unions (or "algebraic data types").

A simple example of a tagged union in Haskell is

```data Shape
= Circle Double
| Rectangle Double Double

area :: Shape -> Double
area (Rectangle length width) = length * width
```

The way Pretty encodes a type like `Shape` in C++ is through a reference-counted pointer to a polymorphic class.

```namespace detail {
class Impl {
public:
virtual ~Impl() = default;
virtual double area() const = 0;
};
} // namespace detail

class Shape final {
public:
struct Circle{};
struct Rectangle{};

Shape(Rectangle, double width, double length);
Shape(Shape&&) = delete;

double area() const {
return _impl->area();
}

private:
std::shared_ptr<detail::Impl const> _impl;
};
```

With this encoding, instances of `Shape` are immutable and relatively cheap to copy.

Each kind of shape is a subclass of `detail::Impl`:

```namespace detail {

class CircleImpl final : public Impl {
public:

double area() const override {
}
private:
};

class RectangleImpl final : public Impl {
// etc.
};

} // namespace detail
```

Helper functions make it easy to create instances of `Shape`:

```Shape circle(double radius) {
}
```

In Pretty, one of the cases of the `Doc` class is `nil` (the empty document). We represent this case not with a subclass of `DocImpl` but instead with the reference-counting pointer set to `nullptr`. This way, it's straightforward for instances of `Doc` to be movable.

## 2 Laziness

In Haskell, values are evaluated lazily. This is a crucial aspect of Wadler's implementation.

In Pretty's implementation, most values are not lazy (they're "strict"). Instead, only the "left" document of the `union` combinator is evaluated lazily. I believe this is sufficient to achieve the same asymptotic running time as the Haskell version.

Lazy evaluation is achieved via this simple class:

```template <typename T>
using Ptr = std::shared_ptr<T const>;

template <typename T>
class LazyPtr final {
public:
template <typename F>
explicit LazyPtr(F f) : _f{std::move(f)} {
}

Ptr<T> const &force() const {
if (_f != nullptr) {
_ptr = _f();
_f = nullptr;
}

return _ptr;
}

private:
mutable std::function<Ptr<T>()> _f;
mutable Ptr<T> _ptr{nullptr};
};
```

## 3 Concepts

Concepts are a new feature of C++20.

One use of concepts in Pretty is for overload resolution in template functions. For example, consider the `fill` function:

```template <std::same_as<Doc>... Ds>
Doc fill(Ds const &...ds);

template <std::input_iterator I>
Doc fill(I begin, I end);
```

Created: 2021-10-19 Tue 19:55