CODEWITHSUNDEEP
haskellrecursionclosurespermutation
dxuhuang
dxuhuang

Reputation: 1080

Haskell permutation library function - please clarify?

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!

Upvotes: 2

Views: 931

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

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.

Upvotes: 0

mhwombat
mhwombat

Reputation: 8136

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)

Upvotes: 3

Related Questions