I try to write a function that gets a list of Integers and should filter it so that the returned list contains only the numbers which match a certain pattern. Unfortunately the order must remain the same. I have implemented a infinite list, that returns all valid numbers in ordered sequence and use it in an list comprehension. This works fine and fast in ghci, but my problem is, that with bigger lists in hugs, which we are required to use in my university course, it results in a Control stack overflow, which i don't comprehend.
I have written minimal examples which should demonstrate my problem:
import Data.List
aList = map (1000*) [0..] -- a example list...
-- works only with lists with a max length of 4093 e.g. [0..4092] but is fast.
-- (with [0..4093] it results in a Control stack overflow)
inaList :: [Integer] -> [Integer]
inaList list = [x| x<-list,elem x cap_aList]
where list_max = maximum list
cap_aList = takeWhile (<=list_max) aList -- should be computed only once?
-- seems to works even with [0..100000] but is really really slow
-- does not exactly what i want.
inaList_working :: [Integer] -> [Integer]
inaList_working list = [x| x<-list,elem x $take 1000 aList ]
-- works with max [0..4092] and is slow.
inaList_2 :: [Integer] -> [Integer]
inaList_2 list = [x| x<-list,elem x $takeWhile (<=(fromIntegral $maximum list)) aList ]
-- works fast but with max [0..4091].
inaList_3 :: [Integer] -> [Integer]
inaList_3 list = [x| x<-list,elem x cap_aList ]
where list_max = maximum list
toTake = findPos list_max aList
cap_aList = take toTake aList
findPos :: Integer -> [Integer] -> Int
findPos i (n:nx)
| i>=n = 1 + findPos i nx
| otherwise = 0
There is no difference if i use aList = map (8*) [0..] instead of aList = map (1000*) [0..].
It only takes a bit longer to finish because it has to do more comparisons, but does not result in a crash.
Therefore it seems the length of the list for elem does not impact the length of the Control stack?
I have no idea why the Control stack overflow occurs.
Even [x| x<-liste,foldl' (||) False $map (==x) cap_aList] results in the same error.
If it is used with normal lists the list comprehension works flawless, but if used with takeWhile (see inaList and inaList_2) it runs into a Control stack overflow or segmentation fault.
If take is used with a computed value (see inaList_3) it also crashes. With a "static" take (see inaList_working) it suddenly works.
I thought, that the where clause should usually be computed only once or never. Then why does it make a difference how the list was build?
And shouldn't hugs try to reduce/compute the Control stack if it is full?
Unfortunately most of the documentation seems to apply only to ghc.
So why does this Control stack overflow occur in this case, how can it be avoided and how can i determine how the control stack looks like/is populated? Are there multiple control stacks?
I hope someone can explain whats going on.