I think the sweet spot is to use exceptions for bugs. If the error is expected, make it data.
Now the library programmer has to guess whether when you - the application programmer try to Wibble a Foozle - will have ensured all the Foozles can be Wibbled, and so not being able to Wibble the Foozle is an exceptional condition, or whether you want to just try to Wibble every Foozle and get an error return if it can't be Wibbled...
One option is for every such condition you bifurcate the API. Instead of three types with a total of eight methods, maybe there are six conditions for two of those methods, and so now it is three types with over 100 methods... ouch. Good bye documentation and product quality.
Meanwhile, for a function doing numerous file copies and network calls I would throw an exception, as the number of possible failure cases are almost limitless. (Like you surely not want to have an ADT that models FileSystemFullErrors and whatnot).
It so happens that in this particular example one is pure and the other is side-effecting, but I'm not convinced that's a hard rule here.
frob1 :: Foo -> Bar -> R
frob2 :: (Foo, Bar) -> R
frob3 :: FooBar -> R
data FooBar = FooBar { foo :: Foo, bar :: Bar }