2

I implemented worstsort in Rust:

fn bubblesort<T: PartialOrd>(l: &mut [T]) {
    for i in 1..l.len() {
        for j in 0..l.len() - i {
            if l[j + 1] < l[j] {
                l.swap(j + 1, j);
            }
        }
    }
}

fn permutations<T: Clone>(l: &[T]) -> Vec<Vec<T>> {
    if l.len() <= 1 {
        return vec![l.to_vec()];
    }

    let mut res = Vec::new();
    for i in 0..l.len() {
        let mut lcopy = l.to_vec();
        lcopy.remove(i);
        let p = permutations(&lcopy);
        for perm in p {
            let mut fullperm = vec![l[i].clone()];
            fullperm.extend(perm);
            res.push(fullperm);
        }
    }
    res
}

pub fn badsort<T: PartialOrd + Clone>(k: usize, l: &mut [T]) {
    if k == 0 {
        bubblesort(l);
    } else {
        let mut p = permutations(l);
        badsort(k - 1, &mut p);
        l.clone_from_slice(&p[0]);
    }
}

pub fn worstsort<T, F>(l: &mut [T], f: F)
where
    T: PartialOrd + Clone,
    F: FnOnce(usize) -> usize,
{
    badsort(f(l.len()), l);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn badsort_zero() {
        let mut unsorted = vec![8, 3, 5];
        badsort(0, &mut unsorted);
        assert_eq!(unsorted, vec![3, 5, 8]);
    }
    #[test]
    fn worstsort_id() {
        let mut unsorted = vec![8, 3, 5];
        worstsort(&mut unsorted, |n| n);
        assert_eq!(unsorted, vec![3, 5, 8]);
    }
}

It compiles and checks fine, until I tried to write tests that actually calling the worstsort and badsort functions, and cargo test gives an error:

error: reached the recursion limit while instantiating `badsort::<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<std::vec::Vec<i32>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`

I get this error even when calling badsort(0, l), which should just be bubblesort, with no recursive calls whatsoever. My assumption is that rustc is trying to generate monomorphised versions of badsort for every possible usize (I swapped the type to u8 and got the same error), but I don't understand why: it errors whatever the argument is, even when it doesn't recursively call itself at all! I tried setting the recursion limit all the way up to #![recursion_limit="1024"], but it still hits this limit and fails, even with u8.

Is my guess correct? Is there a way to get this (admittedly perverse) code to compile and run at all?

6
  • 1
    badsort calls itself on a Vec<Vec<T>>, which is going to call itself on a Vec<Vec<Vec<Vec<T>>>> which is going to call itself etc etc
    – mcarton
    Mar 1, 2019 at 12:15
  • @mcarton Yes, obviously we're going to hit recursion limits pretty fast once the list is non-trivial. I suppose the compiler isn't smart enough (or isn't smart enough early enough) to figure out that if we never call badsort with k larger than some small value, it doesn't need to generate that many type specialisations.
    – dutchie
    Mar 1, 2019 at 12:50
  • 2
    That's not how static typing works, the compiler doesn't care about the value of the parameter k to resolve the types in your function.
    – mcarton
    Mar 1, 2019 at 12:58
  • Somewhat similar to stackoverflow.com/a/54617718/147192 => static typing doesn't care about "which branch", first the types must line up, and here you have infinite types/functions being instantiated. Mar 1, 2019 at 15:58
  • Ah right, of course. I originally saw this implemented in Haskell, where it works fine, hence my confusion on why this might be something to do with the monomorphisation. I suppose more consideration and thought is required: an interesting learning opportunity!
    – dutchie
    Mar 1, 2019 at 17:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.