CODEWITHSUNDEEP
haskell
Christian Temple
Christian Temple

Reputation: 131

simultaneous recurrence relations in haskell

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

Upvotes: 3

Views: 178

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80765

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)

Upvotes: 7

Related Questions