data T a = K (T Int) (T a)
f :: T a -> a
f (K x y) = if f x == 1 then f y else undefined
The Haskell 98 Reportの「4.4.1 Type Signatures」より。型シグネチャのありなしで再帰関数の型が変わる例。型シグネチャなしだと T Int -> Int と推論される。型シグネチャはPolymorhpic Recursionをサポートするためにも使われるという話。
もっと自然な例ってないものかなあ。。