Is there a library function in ATS for randomly permuting a list?

Question

Given a linear list, is there a library function in ATS that shuffles the list randomly to produce a permutation of it:

fun{a:t@ype}
list_vt_permute{n:int}(xs: list_vt(a, n)): list_vt(a, n)

If possible, I would prefer an implementation of list_vt_permute that does not call malloc/free.

Answer 1

Yes, there is such a function declared in prelude/list_vt.sats, which is based on the function array_permute declared in prelude/array.sats.

Note that list_vt_permute calls list_vt_permute$randint for generating random numbers, and it essentially implements the Fisher-Yates algorithm to perform random shuffling. The function list_vt_permute is O(n)-time and it does need to allocate memory for temporary use.

As for a version of list_vt_permute that does not need malloc/free, it can be implemented like mergesort, taking O(n*log(n))-time to finish.