Infinite lists are infinite
Feb. 7th, 2010 04:05 amSo like I said earlier, by writing everything in ternary, I figured out how to automate the computations I was doing. So, what did I want to write it up in? Certainly not C. So, uh, Haskell, I guess?
I'm thinking now Haskell probably wasn't the right choice, partly because it means I have to figure out how to write my recursions to be not shitty. :P In any case, it's close to done so definitely not changing that now... regarding my use of shitty recursions[0], well, hopefully it shouldn't matter - I don't intend to run this with n>18, anyway, and if it does matter, well, I'm sure I can figure out how to make them better, I just don't feel like doing that first time through if it's not necessary.
Regardless, even though I knew my recursions were shitty, I was quite surprised when one of my initial tests resulted in a stack overflow! This was with n=3, so there really shouldn't have been any opportunity for that. What was going on?
So you see, I wrote this function called "multimax". It just takes a bunch of lists of integers, and returns the list [maximum of 0th elts of the lists, maximum of 1st elts of the lists, ...]. Pretty simple. In fact now that I think of it I could have written this rather more simply, as just multimax = map maximum . transpose. I didn't think of that earlier. Oh well. I wrote it instead as multimax = foldl1 (zipWith max).
Anyway when I tried out what I had written so far, errors started popping up, because if you called multimax on an empty list, well, you were calling foldl1 on an empty list. Crap. So instead of foldl1, let's use foldl, meaning we need a default, for the max of 0 things then, which should be the lowest value in the relevant set... in this case, it should be a list of all -1s. How many -1s? Well, let's just use an infinite list of -1s - then once we do a zipWith, it'll be cut down to the appropriate size.
Do you see the error in my reasoning? The whole problem case is when the original list is empty. In this case, no zipWith is performed - we've still got an infinite list. And so this infinite list got passed around until another function tried to do something with it that resulted in a stack overflow.
...yeah, I think I'm just going to turn that into a special case. (Note that if we write multimax = map maximum . transpose, then multimax [] = []; but I don't want [], I want -1s.)
[0]By which I mean doing things that branch and recompute unnecessarily, like the infamous example "fib n = fib (n-1) + fib (n-2)".
I'm thinking now Haskell probably wasn't the right choice, partly because it means I have to figure out how to write my recursions to be not shitty. :P In any case, it's close to done so definitely not changing that now... regarding my use of shitty recursions[0], well, hopefully it shouldn't matter - I don't intend to run this with n>18, anyway, and if it does matter, well, I'm sure I can figure out how to make them better, I just don't feel like doing that first time through if it's not necessary.
Regardless, even though I knew my recursions were shitty, I was quite surprised when one of my initial tests resulted in a stack overflow! This was with n=3, so there really shouldn't have been any opportunity for that. What was going on?
So you see, I wrote this function called "multimax". It just takes a bunch of lists of integers, and returns the list [maximum of 0th elts of the lists, maximum of 1st elts of the lists, ...]. Pretty simple. In fact now that I think of it I could have written this rather more simply, as just multimax = map maximum . transpose. I didn't think of that earlier. Oh well. I wrote it instead as multimax = foldl1 (zipWith max).
Anyway when I tried out what I had written so far, errors started popping up, because if you called multimax on an empty list, well, you were calling foldl1 on an empty list. Crap. So instead of foldl1, let's use foldl, meaning we need a default, for the max of 0 things then, which should be the lowest value in the relevant set... in this case, it should be a list of all -1s. How many -1s? Well, let's just use an infinite list of -1s - then once we do a zipWith, it'll be cut down to the appropriate size.
Do you see the error in my reasoning? The whole problem case is when the original list is empty. In this case, no zipWith is performed - we've still got an infinite list. And so this infinite list got passed around until another function tried to do something with it that resulted in a stack overflow.
...yeah, I think I'm just going to turn that into a special case. (Note that if we write multimax = map maximum . transpose, then multimax [] = []; but I don't want [], I want -1s.)
[0]By which I mean doing things that branch and recompute unnecessarily, like the infamous example "fib n = fib (n-1) + fib (n-2)".
