> Хотел бы я знать, как можно добавлять в алгебраические типы (мета-)информацию меньшими усилиями.

Конкретно в окамле -- по слухам, очень просто, но слегка по-читерски: weak hashtables. Функтор Weak.Make, однако есть ещё его модификации (в интернетах), и надо смотреть, что именно нужно. Не подскажу, так как сам не пользовал (а только намеревался).