simultaneous recurrence relations in haskell

Question

Is it possible to set up a system of simultaneous recurrence relations in haskell? I'm trying to implement

a(n)=3a(n-1)+2b(n-1)

b(n) = a(n-1) + 2b(n-1)

Input:

 a n = 3 * a (n-1) + 2 * b (n-1)

Output:

<interactive>:103:25: error: Variable not in scope: b :: t -> a

So, neither can I define a without defining b first, but nor can I define b without defining a first. I'm not sure if doing so is possible?

PS: I'm working in gchi

The term you're looking for is mutual recursion which is possible in haskell. If you're using GHCi, it might help for you to turn on the multiline mode with :set +m and define both at the same time using let — Patrick Haugh
Also note that such definitions will lead to an exponential-complexity algorithm. Don't expect it to reasonably work for large input values. — chi
@chi but doesn't the compiler handle that for us automatically? — Christian Temple
The compiler will not turn an inefficient algorithm into an efficient one. If you need an efficient algorithm, you need to provide it to the compiler. — chi
@chi I don't know if you are expert on Haskell. But Haskell is a purely functional language, meaning that in Haskell you have to define functions recursively, there are no for loops. However, I heard that haskell compiler is intelligent and will determine how to compile efficiently and functions don't call each other in the order you thought. — Christian Temple

Fyodor Soikin Fyodor Soikin · Accepted Answer · 2017-12-28T18:04:57

In Haskell the order of definitions doesn't matter. You can define a before b or b before a, and in both cases they can reference each other just fine:

a n = 3 * a (n-1) + 2 * b (n-1)
b n = a (n-1) + 2 * b (n-1)

If you're working in GHCi (please clarify that), then yes, it won't accept a definition of a alone, because it doesn't know what b is. You can, however, give GHCi both definitions together, by enclosing them in :{ ... :}, like so:

*Prelude> :{                             
*Prelude| a n = 3 * a (n-1) + 2 * b (n-1)
*Prelude| b n = a (n-1) + 2 * b (n-1)    
*Prelude| :}

Finally, I have to note that these definitions, as written, will produce an infinite loop: there are no cases (i.e. no inputs) for which a and b don't call themselves recursively. This means that, once you call any of them, they will just keep calling each other forever.

To fix that, you need to provide a base case - an input, or a set of inputs, where the functions don't call themselves, for example:

a 0 = 1
a n = 3 * a (n-1) + 2 * b (n-1)

b 0 = 1
b n = a (n-1) + 2 * b (n-1)

(I can't tell whether I provided the correct base cases, because I don't know what your original problem is, and so can't say what is "correct" in your context; the base cases I provided are just examples to illustrate how it might be done)

simultaneous recurrence relations in haskell

1 Answers