Haskell permutation library function - please clarify?

Question

This is the code for the permutations function in Haskell's Data.List module:

permutations            :: [a] -> [[a]]
permutations xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

Can someone take the time to explain to me how this code works?

My confusion stems from the fact that I am highly used to writing functions that have no external dependencies (even if they are nested inside another function), especially if they are recursive. With the presence of permutations inside perms as well as t and ts inside interleave', I am lost as far as the flow of the function is concerned.

Thanks!

There are a lot of different ways to write permutations. This one isn't the fastest. But it has one interesting property that the fastest version doesn't. — Carl
– Carl, Commented Jun 25, 2013 at 15:54

mhwombat · Accepted Answer · 2013-06-25 16:30:11Z

First, I'll move rewrite the code in a form that's probably easier for you to understand, with the internal function definitions moved outside the main function. Note that I had to add some parameters to interleave and interleave' so that they could "see" all the same variables they had access to when they were defined within other functions.

I also added type signatures for clarity.

permutations :: [a] -> [[a]]
permutations xs0 =  xs0 : perms xs0 []

The function perms takes two lists, and creates every possible permutation of the elements in both lists -- but not including the original order. For example:

λ> perms "ab" "XY"
["aXYb","XaYb","aYXb","YaXb","baXY","abXY","aXbY","bXaY","XbaY","XabY","bYXa","YbXa","YXba","bXYa","XbYa","XYba","bYaX","YbaX","YabX","baYX","abYX","aYbX"]

So when we invoke it with an empty second list, as permutations does, it gives us all the other possible permutations of the input elements. All we have to do is tack on the original sequence, and we have out answer. (If you look at permutations, above, you'll see that's exactly what it does.)

λ> perms "abc" ""
["bac","cba","bca","cab","acb"]

Here's the definition or perms.

perms :: [a] -> [a] -> [[a]]
perms []     _  = []
perms (t:ts) is = foldr (interleave (t:ts)) (perms ts (t:is)) (permutations is)

The function interleave takes two lists, and generates every possible way to shuffle them together (as you would a pack of cards). It then appends the third list onto the list of possible shuffles. For example:

λ> interleave "ab" "XY" ["@", "#"]
["aXYb","XaYb","@","#"]

Here's its definition:

interleave :: [t] -> [t] -> [[t]] -> [[t]]
interleave (t:ts) xs r  = let (_,zs) = interleave' (t:ts) id xs r in zs

interleave' :: [t] -> ([t] -> a) -> [t] -> [a] -> ([t], [a])
interleave' (_:ts) _ []     r = (ts, r)
interleave' (t:ts) f (y:ys) r  = let (us,zs) = interleave' (t:ts) (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

Thanks! If I were implementing this function and had known what I was doing, I would have probably written it like this; relying on capturing outside variables, namely on pattern bindings that can change or not even exist in another call is just plain confusing!

גלעד ברקן · Accepted Answer · 2013-06-25 17:00:03Z

0

Try to think of any recursive call as simply a call to the same function but with different parameters (hopefully, otherwise you may have an infinite loop), then try to follow the logic of a very simple example, like permutations [], permutations [1] or permutations [1,2].

Look for when the inner expressions reduce to the base case, which is where no more recursion happens. For example interleave' has the base-case interleave' _ [] and perms has perms [] _ = [].

Although I may get a bit lost myself trying to follow the windings of this function, I'm sure you will find that some expressions will reach the base-case and unfolding from there, you will be able to evaluate the recursive calls that led there.

answered Jun 25, 2013 at 17:00

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Collectives™ on Stack Overflow

Haskell permutation library function - please clarify?

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related