Hi everybody, I'm having to deal w/ rather long(*) lists. Unfortunately I stumbled across some problems in the process. I tried to implement a function that separates a list into two parts according to a list of indices given. (Does anything like that perhaps exist already in the Prelude?) --- snip --- -- Put elems at specified positions in 2nd list. -- Non-existant positions will be ignored. -- The order of the input list won't be altered. select :: [a] -> [Integer] -> ([a],[a]) select xs poss = sAcc xs (sort poss) 0 ([],[]) where sAcc :: [a] -> [Integer] -> Integer -> ([a],[a]) -> ([a],[a]) sAcc [] _ _ (ys,zs) = (ys,zs) sAcc xs [] _ (ys,zs) = (ys++xs, zs) sAcc (x:xs) (pos:poss) curpos (ys,zs) = if (pos == curpos) then sAcc xs poss (curpos+1) (ys, zs++[x]) else sAcc xs (pos:poss) (curpos+1) (ys++[x], zs) --- snap --- Calling a function like the following one, will result in a segfault both under Linux (2.4.7) and Solaris (2.8) w/ hugs-feb-2000. --- snip --- Crash> select [0..500000] [0,1,2,20,418,451596,451616] ( (11290502 reductions, 22129474 cells) Segmentation Fault --- snap --- I suspect it's the (++) that's causing problems here and that it's filling up my C-stack (like stated at http://www.cse.ogi.edu/PacSoft/projects/Hugs/pages/bugsandfeatures.htm). So I tried rewriting the function in order to get rid of the (++). --- snip --- -- Hopefully better implementation of select. select' :: [a] -> [Integer] -> ([a],[a]) select' xs poss = sAcc xs (sort poss) 0 ([],[]) where sAcc :: [a] -> [Integer] -> Integer -> (([a],[a]) -> ([a],[a])) sAcc [] _ _ = trace "hi1" $ id sAcc xs [] _ = trace "hi2" $ (\ (ys,zs) -> (ys++xs,zs)) sAcc (x:xs) (pos:poss) curpos = if (pos == curpos) then (\ (ys,zs) -> ( ys,x:zs)) . (sAcc xs poss (curpos+1)) else (\ (ys,zs) -> (x:ys, zs)) . (sAcc xs (pos:poss) (curpos+1)) --- snap --- Now, something like the above --- snip --- Crash> select' [0..500000] [0,1,2,20,418,451596,451616] (138397 reductions, 244907 cells) ERROR: Control stack overflow --- snap --- will not segfault, but it'll give me a control stack overflow. (Better than a segfault, but still rather undesirable). A second point I discovered is this one: --- snip --- Crash> select' "test" [0..] (35922 reductions, 63905 cells) ERROR: Control stack overflow --- snap --- Instead of just giving me '("","test")'. I considered this case being taken care of by the first pattern in sAcc. Obviously it isn't. So my questions are: 1) Could anybody please explain the behaviour of select and select' to me? To add the icing on the cake: How can I improve select? 2) Why does "select' "test" [0..]" not work? I hope my questions aren't too silly. Any hints would be greatly appreciated. Thanks -- Till (*) At the moment "rather long" means approx. 500,000 elems. But perhaps I'll need even more elements in a list. -- e-mail: reverse(net dot doerges at till) | ENCRYPTED | pgp/gpg: keys via keyserver or my homepage | MAIL IS | www: http://www.doerges.net | WELCOME! |