what is the ordering of the output of https://hackage.haskell.org/package/base-4.16.0.0/docs/src/Data.OldList.html... - and why is it not lexicographic?
OK I think I know what's happening. 1. This function works on infinite lists: it will permute finite prefixes, in increasing length, while keeping the infinite suffix. map (take 5) $ take 3 $ permutations [1 .. ] -- infinite! [[1,2,3,4,5],[2,1,3,4,5],[3,2,1,4,5]] This specification is incompatible with lexicographic order. We could aim for inverse-lexicographic decrease (i.e., `reverse $ map reverse $ permutations xs` is increasing) but currently, it's not. 2. The program is equivalent (try it!) to permutations xs0 = xs0 : do (is', t:ts) <- splits xs0 xs <- permutations $ reverse is' -- reverse not needed, see below (pre, p:ost) <- splits xs return $ pre <> (t : p : ost <> ts) with this auxiliary function (that I sometimes wish was in Data.List) splits xs = zip (inits xs) (tails xs) splits "bar" = [("","bar"),("b","ar"),("ba","r"),("bar","")] That is the form of the program that I have a chance to understand, and prove correct. But - 3. This program contains several "append" (<>). Some are visible, some are hidden in the do notation (?), and in Data.List.inits. A series of uglification steps now transforms each "append" into a function with an extra accumulating parameter, and fuses some of these function calls. E.g., "interleave" (from the source code) is actually this function interleave t ts xs r = ( map (<> ts) $ do (pre, p:ost) <- splits xs return $ pre <> [t] <> p:ost ) <> r Accumulation will reverse lists. Where reversal is not allowed, a parameter xs :: [a] is replaced by the function (xs <>) :: [a] -> [a] . In one place, reversal is kept (because it is irrelevant), and that's why it appears in the above - and contributes to the exotic order of output. Truly a work of art. - I still wonder * can we document this (perhaps find the original documentation)? * was this necessary (or can the compiler do these transformations)? - J.