help understanding integral function

[Fonzie]

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]

[rokob]

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.