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 0leads 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 1The 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); } };