Fisher-Yates shuffle in Haskell
First, let me ungolf and simplify your code slightly, so it will be easier for me to read:

import System.Random

pick :: Int -&gt; [a] -&gt; (a,[a])
pick 0 (x:xs) = (x, xs)
pick i (x:xs) = let (y,ys) = pick (i-1) xs
                in (y, x:ys)
pick _ []     = error "pick: Invalid index"

shuffle :: [a] -&gt; IO [a]
shuffle lst = runner (length lst) lst
  where
    runner :: Int -&gt; [a] -&gt; IO [a]
    runner 0 xs = return xs
    runner i xs = do
      r &lt;- randomRIO (0, i-1)
      let (y,ys) = pick r xs
      (y:) &lt;$&gt; runner (i-1) ys


Every call to pick is O(i), since you need to iterate through on average half of the array to extract the value and move it to the front. In when calling pick, i is on average equal to n/2 (where n is the length of the list). runner is called recursively n times.

So in conclusion, pick has time complexity O(n) and shuffle has time complexity O(n^2), which is indeed much worse than linear, but not quite exponential as you feared. There are also some minor issues with your functions not being tail recursive, but that should only affect constant factors and memory usage, not complexity.

This also matches your measurements, since 0.57 * 10^2 ≈ 6.81

If you compare it to the modern method which you linked, that code instead uses a swap operation which is O(1), which gives you the promised O(n) complexity.

On a side-note, your javascript version of the algorithm has the same problem, since Array.splice is an O(n) operation.



So, to your questions:


Can we improve the time complexity while using the list type?

No. Not unless we change the algorithm to something different, which in a way you have already done in both your implementations by not using the swap operation. An O(1) swap operation for lists is not available, since all random access costs O(n). You can however easily fix it in your js-version (see here).

If you do want to use a different algorithm, there are O(n*log n) algorithms that works on lists, which is not quite linear, but it's the best we can get for lists. You could also use the same algorithm with a Map, which has O(log n) swap operations.
Unboxed types and similar gimmicks will only only help with constant factors, not algorithmic complexity. However, what would help a lot is to use a mutable array or vector. They do have an O(1) swap operation. They come in both an IO version and an ST version which can be used from pure functions.


There are a number of different implementations of a random shuffle function on this page, including Fisher-Yates with both a Map (O(n*log n)) and a mutable Array (O(n)).