Powerset construction for comparing runtime and memory performance characteristics between Rust, Haskell, and Python

powerset.hs

module Main where

main :: IO ()
main = do
    mapM_ print xs where
        xs = powerset [(1 :: Integer)..24]

powerset :: [a] -> [[a]]
powerset = pset [] where
    pset :: [a] -> [a] -> [[a]]
    pset result [] = [reverse result]
    pset result (x : xs) = pset result xs ++ pset (x : result) xs

powerset.py

#!/usr/bin/env python3

def main():
    for xs in gen(tuple(range(1, 25))):
        print(xs)

def gen(xs):
    def rec(result, xs):
        if len(xs) == 0:
            yield result
        else:
            yield from rec(result, xs[1:])
            yield from rec(result + (xs[0],), xs[1:])
    yield from rec((), xs)

if __name__ == "__main__":
    main()

powerset.rs

fn main() {
    let xs: Vec<_> = (1..=24).collect();
    let mut print = |xs: &[i32]| println!("{xs:?}");
    powerset(&xs, &mut print);
}

fn powerset<A, F>(xs: &[A], f: F)
where
    A: Copy,
    F: FnMut(&[A]),
{
    fn rec<A, F>(result: &mut Vec<A>, remaining: &[A], f: &mut F)
    where
        A: Copy,
        F: FnMut(&[A]),
    {
        if remaining.len() == 0 {
            f(&result);
        } else {
            rec(result, &remaining[1..], f);
            result.push(remaining[0]);
            rec(result, &remaining[1..], f);
            result.pop();
        }
    }
    let mut f = f;
    rec(&mut Vec::new(), &xs, &mut f)
}

Rust and Haskell tie for fastest around 3x the speed of Python. However, the RSS high watermark for rust is about 1/10th that of Haskell and Rust (which are about the same).

Importantly, the Haskell memory usage does not seem to scale exponentially with the number of items in the powerset. (This was actually the underlying intention of the test--to ensure that I wasn't accidentally retaining memory and that the lazy list behaved the same as a Python generator in essence.)