5 Mar 06:19 2013

## "translating" recursively defined sequence

```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.)

--

--
frigidcode.com

```
```_______________________________________________
```
5 Mar 06:36 2013

### Re: "translating" recursively defined sequence

I suppose it depends on your definition of straightforward but you can use the iterate function from Data.List to quickly define sequences like this.

a = iterate (\x -> (1/5) * (x**2)) 10

On Mon, Mar 4, 2013 at 9:19 PM, 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.)

_______________________________________________

```_______________________________________________
```
5 Mar 08:01 2013

### Re: "translating" recursively defined sequence

```On 03/04/2013 08:36 PM, Bob Ippolito wrote:
> I suppose it depends on your definition of straightforward but you can
> use the iterate function from Data.List to quickly define sequences like
> this.
>
> a = iterate (\x -> (1/5) * (x**2)) 10
>
>
> On Mon, Mar 4, 2013 at 9:19 PM, Christopher Howard
> <christopher.howard <at> frigidcode.com
> <mailto:christopher.howard <at> frigidcode.com>> 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.)
>
>     --
>     frigidcode.com <http://frigidcode.com>
>
>

Very cool! Thanks!

--

--
frigidcode.com

```
```_______________________________________________
```
5 Mar 20:48 2013

### Re: "translating" recursively defined sequence

```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)
```
5 Mar 20:54 2013

### Re: "translating" recursively defined sequence

(remove the underscore).

On Mar 5, 2013 5:21 AM, "Christopher Howard" <christopher.howard <at> frigidcode.com> 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.)

--
frigidcode.com

_______________________________________________
```_______________________________________________