Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 help understanding integral function
Index -> Programming, General Programming -> Functional Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message

PostPosted: 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.
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.
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.


let integral s i =
   let rec loop sum j =
      if j = i then
         loop (sum + s j) (j + 1)
loop 0

a couple relevant functions used in the integral question are:

(+:) : stream -> int -> stream. Add a constant to a stream.
let (+:) s c = (fun i -> s i + c)

(-|) : stream -> stream -> stream. Subtract two streams pointwise.
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 page 12 question 3.8 part 2.

Any help would be greatly appreciated. Thanks in advance.

Mod Edit: Remember to use syntax tags! Thanks :)
[syntax="ocaml"]Code Here[/syntax]

PostPosted: 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
integral : stream -> stream
such that for any stream s,
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

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)

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,

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:   
   Index -> Programming, General Programming -> Functional Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 2 Posts ]
Jump to: