Haskell で、ある再帰直和型 T に対し、 T -> T のような関数があり、既に実装されているとします。たとえば、

data T = Z
       | One T
       | Two T T
       | Three T T T
       | ..  -- 沢山あります

f :: T -> T
f Z             = Z
f (One t)       = One (f t)
f (Two t1 t2)   = Two (f t2) (f t1)  -- 単純なトラバーサルではない
f (Three Z Z Z) = error "Three 0s are illegal"
f .. -- ずっと続きます

一部のケースは、ありえない入力だということで、 error を使って例外を飛ばしています。

この関数を T -> Maybe T や T -> Either String T のように型を変えて「行儀を良くして」例外を投げないようにしたいのですが、どのようにするのが一番良いのか、が質問です。

f :: T -> Either String T
f Z             = return Z
f (One t)       = liftM One (f t)
f (Two t1 t2)   = liftM2 Two (f t2) (f t1)
f (Three Z Z Z) = fail "Three 0s are illegal"
f ..

などのようにモナドなり、アプリカティブファンクターなり、使用すると書けるのは判るのですが、コンストラクタ数が多い直和型の場合、追加コードを書いていて鬱々としてきます。

通常の Haskell では IO 関連だと例外は catch できるのですが、この場合、元の関数は IO を使いませんから、 IO 汚染させたくありません。非IO でも例外を catch できる言語では間違いなく例外を使う例なので当惑しています。

元のソースコードのをできるだけ変更せずに Either化や Maybe化したいのですが、 Haskell では無理なのでしょうか。