http://d.hatena.ne.jp/lethevert/20070806/p3 を見てて思ったけど Clean じゃなくて Haskell の話なのでコメントじゃなくてこっちに書く。
Haskell の GHC 拡張のひとつに functional dependency (関数従属)というのがあり、こういう場合の問題に対処できます。こんな感じ。
class Measured a v | a -> v where measure :: a -> v instance Measured (Node v a) v
この「| a -> v」の部分は「aを引数に取りvを返す関数」ではなく、型同士の依存関係を関数形式で記述したものです。意味としては「aが決まればvの型が一意に定まる」ことを意味しています。この場合、インタンスにおける (Node v a) と v の関係が定まるため上手く行きます。まだ言語仕様には入っていないので、 GHC なら -fglasgow-exts が必要ですが。
詳しい話はGHCのマニュアルを参照のこと。あれ、論文のリンクが切れてるなあ。ま、タイトルでぐぐれば出てくるでしょう。