It's better to base recursion at the length 1 or 0. It's usually trivial and reduces the chance of making an error. In your case, the code doesn't work for lists of length 1, and this can be easily fixed by setting the base case to perms' _ [x] = [[x]]
.
The costly operations in your code are repeated traversals of the input list. In particular, length xs
is called every time, and as lists in Haskell are lazy linked lists, it costs you O(n). You could pass the length of the list as another argument instead.
Similarly last
and init
are O(n). You could use splitAt
to traverse the list just once, or even better, rotate the other way around, something like shift (y:ys) = ys ++ [y]
where you need to traverse the list just once (for ++
) and pattern matching is also somewhat safer than using partial functions such as init
/head
/last
/..., especially if you cover all cases and use -fwarn-incomplete-patterns
. You might also consider using Seq
which has O(1) costs for manipulating its ends and O(log n) splitting/merging sequences in the middle, but has higher constant factor.
Another source of inefficiencies could be the ++
in the otherwise
branch, as ++
needs to traverse the whole left argument. You might again try out Seq
, or constructing the result using difference lists, which eliminates this problem.
You could solve several of these problems by introducing a helper function that'd return all possible splits of an input list, something like
splits :: [a] -> [(a, [a])]
for example splits [1,2,3]
= [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])]
. And then recursively process the second part, prepending the picked element to all sub-results.
It's good that you provided the type of the top-level function.
Also (\a -> x : a)
can be abbreviated to (x :)
using η-reduction.
Below is code based on the above ideas, with some more optimizations (to improve sub-list sharing), left as an exercise to analyze:
perms :: [a] -> [[a]]
perms = go []
where
go rs [] = [rs]
go rs xs = concatMap (\(y, ys) -> go (y : rs) ys) (splits xs)
splits :: [a] -> [(a, [a])]
splits = go []
where
go ys [] = []
go ys (x : xs) = (x, ys ++ xs) : go (x : ys) xs