0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think you need some sort of backtracking, essentially. This might be able to be done purely functionally, but is probably best done with continuations (call/cc or delimited continuations, which are capable of encoding any monadic effect). $\endgroup$ – xuq01 Sep 25 '18 at 18:38
3
$\begingroup$

As far as I know, I think it is possible to build a functional implementation of solve that does behave as a deterministic function, with no side effects. Yes, there might be multiple possible outputs that are all valid. However, I think it's possible to pick an implementation where it always outputs the same answer. (Certainly, the existence of multiple possible outputs doesn't on its own render it impossible to build such an implementation.)

Here is a simpler example, to give you some intuition. Suppose we want to find a solution to $|x|=c$, where $c$ is a constant given in advance. Then there are two solutions ($x=+c$ and $x=-c$). Nonetheless, you can still build a functional program to output a solution to this, i.e., on input $c$, the code returns a solution to $|x|=c$. An example implementation is the identity function (always return whatever the input was). This is functional and has no side effects.

So just because there are multiple valid outputs doesn't require the code to randomly or nondeterministically choose among them. Often you can write code that outputs one of them, and is consistent and deterministic about which one it outputs.

For instance, here is a plausible such implementation for your particular problem:

  1. Solve the linear system "minimize $x_1$ such that $Ax=b$" using linear programming. (Here I write $x_1$ for the first variable of $x$, i.e., I am assuming $x=(x_1,\dots,x_n)$.) (If it has no solution, return "No solution".) Let $u^{(1)}$ denote the resulting such solution.

  2. Solve the linear system "minimize $x_2$ such that $Ax=b$ and $x_1 = u^{(1)}_1$" using linear programming. Let $u^{(2)}$ denote the resulting such solution.

  3. Solve the linear system "minimize $x_3$ such that $Ax=b$ and $x_1 = u^{(1)}_1$ and $x_2 = u^{(2)}_2$" using linear programming. Let $u^{(3)}$ denote the resulting such solution.

  4. Repeat, until you have obtained $u^{(n)}$, where $n$ is the number of variables. Return $u^{(n)}$.

Note that this algorithm returns the lexicographically least solution to $Ax=b$. Because linear programming is in P, I believe each "solve the linear system" step can be implemented with a deterministic, functional algorithm.

$\endgroup$
  • 1
    $\begingroup$ While your example gets the basic point across, it does not quite generalize to solving linear systems over reals because there is no continuous (and thus no computable) function selecting solutions of a linear system. Perhaps that's what the OP has in mind (I can't tell)? $\endgroup$ – Andrej Bauer Sep 26 '18 at 10:10
  • $\begingroup$ @AndrejBauer, Oh, perhaps I missed a crucial detail! I've edited my answer to show the kind of algorithm I had in mind; does it work? $\endgroup$ – D.W. Sep 26 '18 at 13:10
  • $\begingroup$ In 1. did you mean "minimize $|x|$ such that $Ax=b$"? Or is $x_1$ the first component of $x$? $\endgroup$ – Michael Bächtold Sep 26 '18 at 13:49
  • $\begingroup$ @MichaelBächtold, $x_1$ is the first component of $x$. I am assuming $x=(x_1,\dots,x_n)$. I've edited my answer to make that clearer. Sorry to be unclear. $\endgroup$ – D.W. Sep 26 '18 at 14:17
  • 2
    $\begingroup$ @Algeboy, that's not the theme I was trying to convey. I was trying to convey a much more limited statement: the reasoning "because it has multiple valid outputs, therefore it can't be implemented in a functional way / therefore it can't be implemented without side effects" is faulty logic. And implementing such a thing doesn't require monads or loopholes. $\endgroup$ – D.W. Sep 26 '18 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.