Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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.

 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

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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 2 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: