In this blog post, types and functions were presented in OCaml for modeling streams. This post takes the action to C++.
First, the type definition for a stream.
struct Nil {};
template <class T> class Cons;
template <class T>
using stream = sum_type <
Nil
, recursive_wrapper<Cons<T>>
>;
The definition is in terms of the sum_type<> type from the "pretty good sum" library talked about here.
The definition of Cons<>, will be in terms of "thunks" (suspensions). They're modeled as procedures that when evaluated, compute streams.
template <class T> using stream_thunk = std::function<stream<T>()>;To complete the abstraction, a function that given a suspension, "thaws" it.
template <class T> inline
stream<T> force (stream_thunk<T> const& s) {
return s ();
}
The above choices made, here is the definition for Cons<>.
template <class T>
class Cons {
public:
using value_type = T;
using reference = value_type&;
using const_reference = value_type const&;
using stream_type = stream<value_type>;
private:
using stream_thunk_type = stream_thunk<value_type>;
public:
template <class U, class V>
Cons (U&& h, V&& t) :
h {std::forward<U> (h)}, t {std::forward<V> (t)}
{}
const_reference hd () const { return h; }
stream_type tl () const { return force (t); }
private:
value_type h;
stream_thunk_type t;
};
Next, utility functions for working with streams.
The function hd () gets the head of a stream and tl () gets the stream that remains when the head is stripped off.
template <class T>
T const hd (stream<T> const& s) {
return s.template match<T const&> (
[](Cons<T> const& l) -> T const& { return l.hd (); }
, [](otherwise) -> T const & { throw std::runtime_error { "hd" }; }
);
}
template <class T>
stream<T> tl (stream<T> const& l) {
return l.template match <stream<T>> (
[] (Cons<T> const& s) -> stream <T> { return s.tl (); }
, [] (otherwise) -> stream<T> { throw std::runtime_error{"tl"}; }
);
}
The function take () returns the the first $n$ values of a stream.
template <class T, class D>
D take (unsigned int n, stream <T> const& s, D dst) {
return (n == 0) ? dst :
s.template match<D>(
[&](Nil const& _) -> D { return dst; },
[&](Cons<T> const& l) -> D {
return take (n - 1, l.tl (), *dst++ = l.hd ()); }
);
}
It's time to share a little "hack" I picked up for writing infinite lists.
- To start, forget about streams;
- Write your list using regular lists;
- Ignore the fact that it won't terminate;
- Rewrite in terms of Cons and convert the tail to a thunk.
For example, in OCaml the (non-terminating!) code
let naturals =
let rec loop x = x :: loop (x + 1) in
next 0
leads to this definition of the stream of natural numbers.
let naturals = let rec loop x = Cons (x, lazy (loop (x + 1))) in loop 0
Putting the above to work, a generator for the stream of natural numbers can be written like this.
class natural_numbers_gen {
private:
using int_stream = stream<int>;
private:
int start;
private:
int_stream from (int x) const {
return int_stream{
constructor<Cons<int>>{}, x, [=]() { return this->from (x + 1); }
};
}
public:
explicit natural_numbers_gen (int start) : start (start)
{}
explicit operator int_stream() const { return from (start); }
};
The first $10$ (say) natural numbers can then be harvested like this.
std::vector<int> s;
take (10, stream<int> (natural_numbers_gen{0}), std::back_inserter (s));
The last example, a generator of the Fibonacci sequence. Applying the hack, start with the following OCaml code.
let fibonacci_numbers =
let rec fib a b = a :: fib b (a + b) in
fib 0 1
The rewrite of this code into streams then leads to this definition.
let fibonnaci_sequence = let rec fib a b = Cons (a, lazy (fib b (a + b))) in fib 0 1Finally, casting the above function into C++ yields the following.
class fibonacci_numbers_gen {
private:
using int_stream = stream<int>;
private:
int start;
private:
int_stream loop (int a, int b) const {
return int_stream{
constructor<Cons<int>>{}, a, [=]() {return this->loop (b, a + b); }
};
}
public:
explicit fibonacci_numbers_gen ()
{}
explicit operator int_stream() const { return loop (0, 1); }
};
