Christopher Howard | 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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Bob Ippolito | 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 <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


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Christopher Howard | 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

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Albert Y. C. Lai | 5 Mar 20:48 2013
Picon

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)
Don Stewart | 5 Mar 20:54 2013
Picon

Re: "translating" recursively defined sequence

Isn't that already valid Haskell? :)

(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


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane