On Mon, Jun 21, 2010 at 8:58 PM, prad wrote:

it seems to me that if we consider the list to be already built, we can apply zip successively to get the next part of it, but if we think recursively we start at the beginning at each recursive level and go nowhere.

That's a funny way to say it : to me recursive thinking has always been about assuming I already have a function that works on smaller (in some sense) cases, writing the function knowing that and then figuring what's the base case we're tending toward and handling it non-recursively. That's what recursion is about for me and I've always found easier to think about it like that rather than always expansing the recursive calls (I also find it easier than thinking iteratively nowadays but YMMV). In other words what you describe as your new method to think about infinite structure is the only way I approach recursion (of structure or functions). I would say it's a perfectly valid approach as long as you don't forget to handle the base case (here it's the explicit definition of the first two elements). -- Jedaï

prad wrote:

i'm trying to figure out how to think out the circular definition for an infinite list and would appreciate suggestions.

consider ones = 1 : ones this essentially says 1 : (1 : (1 : (1 : ones))) with ones being given by the original def.

however, i had trouble with this one fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]

The Haskell wikibook has some material on this: http://en.wikibooks.org/wiki/Haskell/Denotational_semantics Basically, the key question is: "What is a recursive definition, anyway?". The answer to that is that any recursively defined value is obtained from a sequence of approximations. We start with the worst approximation called ⊥ ("bottom") which basically means "it's undefined, we don't know what it is". fib_0 = ⊥ To get a better approximation, we apply the definition of fib to that. fib_1 = 1 : 1 : [ a+b | (a,b) <- zip fib_0 (tail fib_0) ] = 1 : 1 : [ a+b | (a,b) <- zip ⊥ (tail ⊥) ] = 1 : 1 : [ a+b | (a,b) <- zip ⊥ ⊥ ] = 1 : 1 : [ a+b | (a,b) <- ⊥ ] = 1 : 1 : ⊥ To get an even better approximation, we once again apply the equation for fib to this approximation: fib_2 = 1 : 1 : [ a+b | (a,b) <- zip fib_1 (tail fib_1) ] = 1 : 1 : [ a+b | (a,b) <- zip (1:1:⊥) (tail (1:1:⊥)) ] = 1 : 1 : [ a+b | (a,b) <- zip (1:1:⊥) (1:⊥) ] = 1 : 1 : [ a+b | (a,b) <- (1,1):⊥ ] = 1 : 1 : 2 : ⊥ and so on and so on. The limit of these approximations fib_0 = ⊥ fib_1 = 1 : 1 : ⊥ fib_2 = 1 : 1 : 2 : ⊥ fib_3 = 1 : 1 : 2 : 3 : ⊥ ... is the infinite list fib = 1 : 1 : 2 : 3 : 5 : ... This is the thinking that you have described, with a minor, but crucial change. Namely, it's not clear that your list elements a,b,c,d, etc. exist a priori, i.e. that the list is already created in this form. For instance, it wouldn't be right to say that the example foo = 1 : 1 : loop where loop = loop can be written as foo = [1,1,a,b,c, ..] because the recursion simply won't progress past foo = 1 : 1 : ⊥ The formulation with ⊥ can handle such cases. In other words, your thinking is right but somewhat restricted to a few particular examples while the method using ⊥ as shown here will *always* apply. The key message to take away is that you also need some way (⊥) to express recursive definitions that might loop forever. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com