help understanding integral function
Author |
Message |
Fonzie
|
Posted: Sat Feb 14, 2009 7:48 pm Post subject: help understanding integral function |
|
|
I'm doing a question in my ocaml book, and I'm having trouble understanding the given solution. Here's the problem/solution:
A stream is an infinite sequence of values supporting an operation hd(s) that returns the first value in the stream s, and tl(s) that returns a new stream with the first element removed. One way to implement a stream is to represent it as a function over the nonnegative integers. Given a stream s : int -> int, the first element is (s 0), the second is (s 1), etc. The operations are defined as follows.
Ocaml: | let hd s = s 0
let tl s = (fun i -> s (i + 1)) |
For this exercise, we?ll assume that we?re working with streams of integers, so the type
stream is int -> int. We?ll write a stream as a sequence (x0, x1, x2, . . .).
2. A ?derivative? function can be defined as follows.
Ocaml: | let derivative s = tl s (-|) s | Define a function integral : stream -> stream such that, for any stream s, integral (derivative s) = s (+:) c for some constant c.
Answer.
Ocaml: | let integral s i =
let rec loop sum j =
if j = i then
sum
else
loop (sum + s j) (j + 1)
in
loop 0 |
a couple relevant functions used in the integral question are:
(+:) : stream -> int -> stream. Add a constant to a stream.
Ocaml: | let (+:) s c = (fun i -> s i + c) |
(-|) : stream -> stream -> stream. Subtract two streams pointwise.
Ocaml: | let (-|) s1 s2 = (fun i -> s1 i - s2 i) |
So, as far as I can tell this function requires an input for s (a stream), i (how many elements of the stream to include in the integration?), and j (which element to return?). The function then adds all the elements between and including j and (i-1) and returns the sum. I don't understand how this means it's returning the value of an element of the stream after integration.
If you want to see the question/solution unedited go to http://mailman.cs.bham.ac.uk/archives/ocaml-users/attachments/20080415/e1558252/answers-0001.pdf page 12 question 3.8 part 2.
Any help would be greatly appreciated. Thanks in advance.
Mod Edit: Remember to use syntax tags! Thanks :) code: | [syntax="ocaml"]Code Here[/syntax] |
|
|
|
|
|
![](images/spacer.gif) |
Sponsor Sponsor
![Sponsor Sponsor](templates/subSilver/images/ranks/stars_rank5.gif)
|
|
![](images/spacer.gif) |
rokob
![](http://compsci.ca/v3/uploads/user_avatars/9597129584d8b48ede7769.png)
|
Posted: Thu Mar 24, 2011 8:29 am Post subject: Re: help understanding integral function |
|
|
I recently worked through this exercise as well. After working through the exercises in this chapter, I decided to look around to see if recursion is really the right way to go about this solution, because I don't have solutions for the book.
The integral function is not returning the value of an element of the stream, it is returning another stream (i.e. a function). The exercise is in my mind meant to demonstrate the first class nature of functions in Ocaml. Integral takes a function and returns a function, although I think the solution you gave is wrong anyway. I say this because the question asks to define a function Ocaml: | integral : stream -> stream | such that for any stream s, Ocaml: | integral (derivative s) = s +: c | for some constant c.
Writing out the "math" helps to understand the solution here. Take a stream s = (x0,x1,x2,x3,...), and take the derivative to get s' = (x1-x0,x2-x1,x3-x2,...).
So you want a function that takes s' and returns s up to a constant. Well, you can use the fact that summing s' is a telescoping series. Therefore, you basically are going to return s -| x0, so in fact you know what the constant is. In other words sIntegral = integral s' = (0, x1-x0, x2-x1+x1-x0,x3-x2+x2-x1+x1-x0,...). I wrote the function as
Ocaml: |
let integral s =
let rec y i =
if(i=0) then 0 else if(i=1) then hd s else
s(i-1) + s(i-2) + y(i-2)
in
y
|
This version at least makes sense to me. integral is a function that takes a stream s as input and returns the recursive function y. This recursive function will then represent the integrated stream as a function. As an example,
Ocaml: |
let s1 n = 2*n + 1;;
let s1' = derivative s1;;
let s1int = integral s1';;
let zeroS = s1 -| (s1int +: (hd s1) );;
|
You will find that s1int matches s1 up to the constant hd s1. Therefore, the last line will be a stream of all zeros. The only issue I have with this form of integration is that s1 and s1int are not really equivalent up to a constant. In the above, s1 10000000;; evaluates to a number, but s1int 10000000;; causes the recursion to overflow the stack. This depends on the big number you use and the machine, but the point being, the stream returned by the integral is a recursive function and the original stream is not.
I know this post is somewhat old, but I still thought this was an interesting question. This is my first foray into functional programming and I have to say the questions in this chapter of that book really piqued my interest.
**** Edit
So this question was in Chapter 3. When I got to Chapter 5, I discovered tail recursion. My method is incorrect and my issue with the stack overflow was a result of not using a tail recursive function. The given solution is tail recursive, so I withdraw my previous comment that the solution given is incorrect. At least I have a very good understanding now of the difference between non-tail recursive functions and those that are tail recursive. |
|
|
|
|
![](images/spacer.gif) |
|
|