[Haskell-cafe] "translating" recursively defined sequence

[Albert Y. C. Lai]

On 13-03-05 12:19 AM, Christopher Howard wrote:
> Hi. My Haskell is (sadly) getting a bit rusty. I was wondering what
> would be the most straightforward and easily followed "procedure" for
> translating a recursively defined sequence into a Haskell function. For
> example, this one from a homework assignment.
>
> quote:
> --------
> a_1 = 10
> a_(k+1) = (1/5) * (a_k)**2
> --------
>
> (The underscore is meant to represent subscripting what follows it.)

1. decode subscripts back to arguments

a 1 = 10
a (k+1) = (1/5) * (a k)**2

2. normalize LHS arguments

sometimes, some arguments on the LHS (k+1 here) are not accepted by 
Haskell 2010; therefore, we need an equivalent definition with another 
argument form.

a 1 = 10
a k = (1/5) * (a (k-1))**2

3. translate to Haskell
(that's right, the above two steps are pure math, not Haskell)

a 1 = 10
a k = (1/5) * (a (k-1))**2

The result may or may not be an efficient algorithm (which depends on 
how you use it). But it gives the correct answer. An efficient algorithm 
requires further study.

Here is an example where step 3 makes change.

b_0 = 0
b_(k+1) = sqrt k * b_k

1. decode subscripts back to arguments

b 0 = 0
b (k+1) = sqrt k * b k

2. normalize LHS arguments

b 0 = 0
b k = sqrt (k-1) * b (k-1)

3. translate to Haskell

b 0 = 0
b k = sqrt (fromIntegral (k-1)) * b (k-1)