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 (i1) 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/ocamlusers/attachments/20080415/e1558252/answers0001.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] 






Sponsor Sponsor



rokob

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' = (x1x0,x2x1,x3x2,...).
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, x1x0, x2x1+x1x0,x3x2+x2x1+x1x0,...). 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(i1) + s(i2) + y(i2)
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 nontail recursive functions and those that are tail recursive. 






