Hugs Permutations Sufficient Space

Question

First of all, yeah I know that I should use ghc instead (but we are forced to use hugs in the course)

So I try to generate all permutations of [1 .. 9] but when evaluating this, hugs throws an error: "ERROR - Garbage collection fails to reclaim sufficient space"

Is there any quickfix or roundabout for this?

Answer 1

It's likely that the problem isn't because of Hugs, but because your permutation function is written in a way which is preventing garbage collection, or just otherwise allocating too much memory.

The following definition of permutations works for [1..9] in both GHC and Hugs for me (although permutations [1..9] in Hugs requires the garbage collector to be called a staggering 58 times on my computer)

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (x:xs) = concatMap insertEverywhere (permutations xs)
  where insertEverywhere [] = [[x]]
        insertEverywhere (y:ys) = (x:y:ys): (map (y:) $ insertEverywhere ys)