[Haskell-cafe] Output order of Data.List.permutations?

[Johannes Waldmann]

> what is the ordering of the output of
> https://hackage.haskell.org/package/base-4.16.0.0/docs/src/Data.OldList.html#permutations
> -
> 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.