Large lists, heaps, stacks...

[Janis Voigtlaender]

Till Doerges writes:

> 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?)
> ...
> 
>   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?
> 

You might try the following version that does not build up huge data structures 
in accumulating parameters to output them only in the two base cases. Rather, it 
produces partial output as early as possible. For huge lists, however, it might 
still fail, if GC cannot claim enough free space:

select'' :: [a] -> [Integer] -> ([a],[a])
select'' xs poss = sAcc xs (sort poss) 0 
    where sAcc :: [a] -> [Integer] -> Integer -> ([a],[a])
	  sAcc []     _             _       = ([],[])
	  sAcc xs     []            _       = (xs,[])
	  sAcc (x:xs) pl@(pos:poss) curpos  =
	      if (pos == curpos)
	      then let (u,v) = sAcc xs poss (curpos+1) in (u,x:v)
	      else let (u,v) = sAcc xs pl   (curpos+1) in (x:u,v)

--
Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt@tcs.inf.tu-dresden.de