# Re: the forward method [dynamic vs. static typing]

Ken Shan <ken@digitas.harvard.edu> writes:
> > You need a pointer:
> >
> > template <class T>
> > struct super_list
> > {
> >     T t;
> >     super_list<vector<T> > *children;
> > };
> >
> > works perfectly well.  (Implementation of cool algorithms using
> > polymorphic recursion left to the reader.)
> >
> > Or do you consider this not faithful to your intentions?
>
> No, that is perfectly faithful to my intentions, but I can't write an
> (instantiable) template for << :
>
>     template <class T>
>     struct super_list
>     {
> 	T t;
> 	super_list<vector<T> > *children;
>     };
>
>     template <class T>
>     ostream &
>     operator<<(ostream &os, super_list<T> const &c)
>     {
> 	os << "{";
> 	os << c.t;
> 	if (c.children)
> 	{
> 	    os << ",";
> 	    os << *(c.children);
> 	}
> 	os << "}";
> 	return os;
>     }
>
> Instantiating the function template puts the compiler into a recursion
> that is depth-bounded only by fiat.
>
> So, I'm not sure what cool algorithms using polymorphic recursion can be
> implemented...?

That printing code is not faithful to your intention, which was

data SuperList a = SuperList a (SuperList [a])

The code you wrote reflects the intention

data SuperList a = SuperList a (Maybe (SuperList [a]))

which is quite different.

C++'s NULL is a value, not a type, so it is impossible, as you correct
indicate, to write a function template using an encoding of Maybe in
which NULL is a Nothing and a pointer is a Maybe.

C++ doesn't have sum types, unfortunately, so there are a couple of
choices if one is to write printing code that works.

One method is to use the run time "open sum" pattern to the Maybe.
This simply means defining

template <typename T>
struct Maybe {
// ...
};

template <typename T>
struct Nothing : public Maybe<T> {
};

template <typename T>
struct Just : public Maybe<T> {
T *value;
};

etc., and then only working with Maybe in the function template, and
then using dynamic dispatch, by introducing a
virtual void print(ostream &os)
in Maybe and having operator<< on Maybe just call print on itself.

The new C++ type is then

template <typename T>
class SuperList {
public:
T *t;
Maybe<SuperList<vector<T> > > *children;
};

The other is to use the compile time "open sum" pattern, to enable use
of type inference.  The following works.

// C++ translation of
//
// data SuperList a = SuperList a (Maybe (SuperList [a]))

#include <iostream>
#include <vector>

using namespace std;

template <template <typename> class Container, typename T>
ostream &
operator<<(ostream &os, Container<T> const &c)
{
typename Container<T>::const_iterator it = c.begin();
os << "[";
if (it != c.end()) {
for (;;) {
os << *it;
++it;
if (it == c.end()) {
break;
}
os << ", ";
}
}
os << "]";
return os;
}

struct Nil {
};

// Intention: U will be either SuperList<vector<T > or Nil.
template <typename T, typename U>
class SuperList {
public:
// Store a pointer, just for the heck of it.
T *t;
U *children;
public:
SuperList(T *t, U *children)
: t(t), children(children)
{}
};

// Constructors.
template <typename T, typename U>
SuperList<T, U> *
makeList(T *t, U *children)
{
return new SuperList<T, U>(t, children);
}

Nil *
nil()
{
return new Nil();
}

template <typename T, typename U>
ostream &
operator<<(ostream &os, SuperList<T, U> const *s)
{
os << "SuperList ("
<< *(s->t)
<< ", Just ("
<< s->children
<< "))";
return os;
}

// Specialization.
template <typename T>
ostream &
operator<<(ostream &os, SuperList<T, Nil> const *s)
{
os << "SuperList ("
<< *(s->t)
<< ", Nil)";
return os;
}

#ifdef __GNUC__
#define DECLARE(var, exp) typeof(exp) var = exp
#else
#error "Get thee a typeof!"
#endif

// For checking the nasty type.
#include <typeinfo>

int main()
{
int pi[6] = { 3, 1, 4, 1, 5, 9 };
int e[6] = { 2, 7, 1, 8, 2, 8 };
vector<int> v(&pi[0], &pi[6]);
vector<int> xs(&pi[0], &pi[6]);
vector<int> ys(&e[0], &e[6]);
vector<vector<int> > lv;
lv.push_back(xs);
lv.push_back(ys);

DECLARE(t, makeList(new int(1),
makeList(&v,
makeList(&lv,
nil()))));
cout << typeid(t).name() << endl;
cout << t << endl;
}

--
Franklin