2
\$\begingroup\$
let  shuffley (numbers:int list) =
    let rec loop numbers acc =
        match numbers with
        | head::tail -> loop (List.rev(tail)) (head::acc)
        | [] -> List.rev(acc)
    loop numbers []
shuffley [1;2;3;4;5;6;7;8]

I am trying to practice some F# and I was wondering if could be a good example of tail recursion or this is just some nonsense.

\$\endgroup\$
3
\$\begingroup\$

As this algorithm is tail recursive lets tackle another problem: having recursion instead of loops often makes it easier to reason about a single step but more difficult to see whether one step is (partially) undoing effects of the previous one.

Here, the remaining numbers are reversed in every step. This is an O(n) operation (n = length of the list), doing this in every step means the overall complexity is O(n2).

It seems the result could also be computed by

  1. splitting the list into a, b
  2. interleaving a and the reversed b

For splitting in linear time, there is a 'trick': moving two 'pointers' while keeping track of the visited elements (acc). The second pointer (ys) always skips two elements while the first one (xs) skips just one. The function needs to be called with (input, input), i.e. both pointers at the first element:

let rec split acc = 
    function 
    | x :: xs, _ :: _ :: ys -> split (x :: acc) (xs, ys)
    | x :: xs, [_] -> split (x :: acc) (xs, [])
    | xs, _ -> List.rev acc, xs

Interleaving is straightforward:

let rec interleave acc = 
    function 
    | h :: t, o -> interleave (h :: acc) (o, t)
    | [], h :: t -> interleave (h :: acc) (t, [])
    | [], [] -> List.rev acc

both functions are of linear complexity, combining them sequentially is O(n) still:

let shuffley' list = 
    let rec interleave acc = 
        function 
        | h :: t, o -> interleave (h :: acc) (o, t)
        | [], h :: t -> interleave (h :: acc) (t, [])
        | [], [] -> List.rev acc

    let rec split acc = 
        function 
        | x :: xs, _ :: _ :: ys -> split (x :: acc) (xs, ys)
        | x :: xs, [_] -> split (x :: acc) (xs, [])
        | xs, _ -> List.rev acc, xs

    let a, b = split [] (list, list)
    interleave [] (a, List.rev b)

On my machine, shuffley [0..10000] (10k) takes about the same time as shuffley' [0..1000000] (1M) (less than a second), whereas shuffley [0..100000] (100k) doesn't even terminate within a minute.

Note that we can now also shuffley' any list, not just ints (due to the removed type annotations). If you want to pass an empty list in F# interactive, just use shuffley' ([] : int list).

I reversed the accumulator and 'real' parameters to make use of the concise functionality.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.