Discussion on: Write a program or script to find Lucky Numbers

import Control.Monad.State
import Control.Monad.Loops(untilM)
import qualified Data.Vector.Unboxed as V
import Data.Vector.Unboxed((!)) -- this one unqualified, please!

type Index = Int
type Vec = V.Vector

-- To delete every nth element from a list:
-- The state is the remaining list with elements to delete

-- take n elements and leave the rest as state
takeM :: V.Unbox a => Int -> State (Vec a) (Vec a)
takeM = state . V.splitAt

-- input list in state empty?
end :: V.Unbox a => State (Vec a) Bool
end = get >>= return . V.null

-- take n-1 elements and drop the nth. Repeat until the end of the list.
deleteEveryNth :: V.Unbox a => Int -> Vec a -> Vec a
deleteEveryNth n = V.concat . evalState (takeM (n-1) <* takeM 1 `untilM` end)

-- To iterate the deletion passes with different step widths:
-- The step width can be found at index i, then do a deletion pass over xs

deleteUnlucky :: (Vec Int,Index) -> (Vec Int,Index)
deleteUnlucky (xs,i) = (deleteEveryNth (xs!i) xs, i+1)

outOfRange :: (Vec Int,Index) -> Bool
outOfRange (xs,i) = i >= len || xs!i > len
  where len = V.length xs

luckyNumbers n =
  fst $ until outOfRange deleteUnlucky (V.fromList [1,3..n],1)

main =
  let l = luckyNumbers 1000000
  in print (l, V.length l)

PS C:\Users\Heiko\Documents\Programmieren\Haskell> .\GluecklicheZahlen-Vector.exe +RTS -s
71918
   4,586,444,408 bytes allocated in the heap
      31,005,008 bytes copied during GC
       9,441,112 bytes maximum residency (35 sample(s))
       2,704,656 bytes maximum slop
              24 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      7189 colls,     0 par    0.016s   0.037s     0.0000s    0.0003s
  Gen  1        35 colls,     0 par    0.000s   0.011s     0.0003s    0.0046s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.547s  (  0.536s elapsed)
  GC      time    0.016s  (  0.048s elapsed)
  EXIT    time    0.000s  (  0.002s elapsed)
  Total   time    0.562s  (  0.585s elapsed)

  %GC     time       2.8%  (8.1% elapsed)

  Alloc rate    8,386,641,203 bytes per MUT second

  Productivity  97.2% of total user, 91.8% of total elapsed

PS C:\Users\Heiko\Documents\Programmieren\Haskell>