Consider the example of solving for $x$ where $Ax=b$. This is not in general function, there can be more than one solution. So if you make such a solver in a functional style...does this count as a side effect?
def solve(A:Matrix[Float],b:Matrix[Float]):Matrix[Float] = ...
Obviously the solution will be dependent on several internal factors such as the method to solve, e.g. the type of echolonization, or perhaps it uses randomization (Krylov methods for example). And that appears to be all you could expect because solving is not a function. Still, it is evident that the return is a representative of an equivalence class, and so subject to the interpretation that the outputs are representative of an equivalence class then this would be a function -- just we don't want to implement it as some coset of a subspace as that might be slower or impossible.
In purely functional programming is there a loop-hole of sorts for implementing relations -- which interpretted under an equivalence relation, become fucntions, even if we don't explicitly wrap it up that way?
E.g. could I implement a version of the signature above for
solve in Haskell without a monad?