Computer Science Canada help understanding integral function |
| Author: | Fonzie [ 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.
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.
Answer.
a couple relevant functions used in the integral question are: (+:) : stream -> int -> stream. Add a constant to a stream.
(-|) : stream -> stream -> stream. Subtract two streams pointwise.
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 :)
|
|||||||||||||
| Author: | rokob [ 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
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
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,
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. |
|||||||||