{-# LANGUAGE TemplateHaskell #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  Data.Permutation
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- Data type for representing a Permutation
--
--------------------------------------------------------------------------------
module Data.Permutation where

import           Control.DeepSeq
import           Control.Lens
import           Control.Monad (forM)
import           Control.Monad.ST (runST)
import qualified Data.Foldable as F
import           Data.Maybe (catMaybes)
import qualified Data.Traversable as T
import qualified Data.Vector as V
import qualified Data.Vector.Generic as GV
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Unboxed.Mutable as UMV
import           GHC.Generics (Generic)

--------------------------------------------------------------------------------

-- | Orbits (Cycles) are represented by vectors
type Orbit a = V.Vector a

-- | Cyclic representation of a permutation.
data Permutation a = Permutation { Permutation a -> Vector (Orbit a)
_orbits  :: V.Vector (Orbit a)
                                 , Permutation a -> Vector (Int, Int)
_indexes :: UV.Vector (Int,Int)
                                               -- ^ idxes (fromEnum a) = (i,j)
                                               -- implies that a is the j^th
                                               -- item in the i^th orbit
                                 }
                   deriving (Int -> Permutation a -> ShowS
[Permutation a] -> ShowS
Permutation a -> String
(Int -> Permutation a -> ShowS)
-> (Permutation a -> String)
-> ([Permutation a] -> ShowS)
-> Show (Permutation a)
forall a. Show a => Int -> Permutation a -> ShowS
forall a. Show a => [Permutation a] -> ShowS
forall a. Show a => Permutation a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Permutation a] -> ShowS
$cshowList :: forall a. Show a => [Permutation a] -> ShowS
show :: Permutation a -> String
$cshow :: forall a. Show a => Permutation a -> String
showsPrec :: Int -> Permutation a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Permutation a -> ShowS
Show,Permutation a -> Permutation a -> Bool
(Permutation a -> Permutation a -> Bool)
-> (Permutation a -> Permutation a -> Bool) -> Eq (Permutation a)
forall a. Eq a => Permutation a -> Permutation a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Permutation a -> Permutation a -> Bool
$c/= :: forall a. Eq a => Permutation a -> Permutation a -> Bool
== :: Permutation a -> Permutation a -> Bool
$c== :: forall a. Eq a => Permutation a -> Permutation a -> Bool
Eq,(forall x. Permutation a -> Rep (Permutation a) x)
-> (forall x. Rep (Permutation a) x -> Permutation a)
-> Generic (Permutation a)
forall x. Rep (Permutation a) x -> Permutation a
forall x. Permutation a -> Rep (Permutation a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Permutation a) x -> Permutation a
forall a x. Permutation a -> Rep (Permutation a) x
$cto :: forall a x. Rep (Permutation a) x -> Permutation a
$cfrom :: forall a x. Permutation a -> Rep (Permutation a) x
Generic)
makeLenses ''Permutation

instance NFData a => NFData (Permutation a)

instance Functor Permutation where
  fmap :: (a -> b) -> Permutation a -> Permutation b
fmap = (a -> b) -> Permutation a -> Permutation b
forall (t :: * -> *) a b. Traversable t => (a -> b) -> t a -> t b
T.fmapDefault

instance F.Foldable Permutation where
  foldMap :: (a -> m) -> Permutation a -> m
foldMap = (a -> m) -> Permutation a -> m
forall (t :: * -> *) m a.
(Traversable t, Monoid m) =>
(a -> m) -> t a -> m
T.foldMapDefault

instance T.Traversable Permutation where
  traverse :: (a -> f b) -> Permutation a -> f (Permutation b)
traverse a -> f b
f (Permutation Vector (Orbit a)
os Vector (Int, Int)
is) = (Vector (Orbit b) -> Vector (Int, Int) -> Permutation b)
-> Vector (Int, Int) -> Vector (Orbit b) -> Permutation b
forall a b c. (a -> b -> c) -> b -> a -> c
flip Vector (Orbit b) -> Vector (Int, Int) -> Permutation b
forall a. Vector (Orbit a) -> Vector (Int, Int) -> Permutation a
Permutation Vector (Int, Int)
is (Vector (Orbit b) -> Permutation b)
-> f (Vector (Orbit b)) -> f (Permutation b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Orbit a -> f (Orbit b))
-> Vector (Orbit a) -> f (Vector (Orbit b))
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
T.traverse ((a -> f b) -> Orbit a -> f (Orbit b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
T.traverse a -> f b
f) Vector (Orbit a)
os


elems :: Permutation a -> V.Vector a
elems :: Permutation a -> Vector a
elems = [Vector a] -> Vector a
forall (v :: * -> *) a. Vector v a => [v a] -> v a
GV.concat ([Vector a] -> Vector a)
-> (Permutation a -> [Vector a]) -> Permutation a -> Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (Vector a) -> [Vector a]
forall (v :: * -> *) a. Vector v a => v a -> [a]
GV.toList (Vector (Vector a) -> [Vector a])
-> (Permutation a -> Vector (Vector a))
-> Permutation a
-> [Vector a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Permutation a -> Vector (Vector a)
forall a. Permutation a -> Vector (Orbit a)
_orbits

size      :: Permutation a -> Int
size :: Permutation a -> Int
size Permutation a
perm = Vector (Int, Int) -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
GV.length (Permutation a
permPermutation a
-> Getting (Vector (Int, Int)) (Permutation a) (Vector (Int, Int))
-> Vector (Int, Int)
forall s a. s -> Getting a s a -> a
^.Getting (Vector (Int, Int)) (Permutation a) (Vector (Int, Int))
forall a. Lens' (Permutation a) (Vector (Int, Int))
indexes)

-- | The cycle containing a given item
cycleOf        :: Enum a => Permutation a -> a -> Orbit a
cycleOf :: Permutation a -> a -> Orbit a
cycleOf Permutation a
perm a
x = Permutation a
permPermutation a
-> Getting (Endo (Orbit a)) (Permutation a) (Orbit a) -> Orbit a
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Orbit a) -> Const (Endo (Orbit a)) (Vector (Orbit a)))
-> Permutation a -> Const (Endo (Orbit a)) (Permutation a)
forall a a.
Lens
  (Permutation a)
  (Permutation a)
  (Vector (Orbit a))
  (Vector (Orbit a))
orbits((Vector (Orbit a) -> Const (Endo (Orbit a)) (Vector (Orbit a)))
 -> Permutation a -> Const (Endo (Orbit a)) (Permutation a))
-> ((Orbit a -> Const (Endo (Orbit a)) (Orbit a))
    -> Vector (Orbit a) -> Const (Endo (Orbit a)) (Vector (Orbit a)))
-> Getting (Endo (Orbit a)) (Permutation a) (Orbit a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Orbit a))
-> Traversal' (Vector (Orbit a)) (IxValue (Vector (Orbit a)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (Permutation a
permPermutation a -> Getting (Endo Int) (Permutation a) Int -> Int
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Int, Int) -> Const (Endo Int) (Vector (Int, Int)))
-> Permutation a -> Const (Endo Int) (Permutation a)
forall a. Lens' (Permutation a) (Vector (Int, Int))
indexes((Vector (Int, Int) -> Const (Endo Int) (Vector (Int, Int)))
 -> Permutation a -> Const (Endo Int) (Permutation a))
-> ((Int -> Const (Endo Int) Int)
    -> Vector (Int, Int) -> Const (Endo Int) (Vector (Int, Int)))
-> Getting (Endo Int) (Permutation a) Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Int, Int))
-> Traversal' (Vector (Int, Int)) (IxValue (Vector (Int, Int)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (a -> Int
forall a. Enum a => a -> Int
fromEnum a
x)(((Int, Int) -> Const (Endo Int) (Int, Int))
 -> Vector (Int, Int) -> Const (Endo Int) (Vector (Int, Int)))
-> ((Int -> Const (Endo Int) Int)
    -> (Int, Int) -> Const (Endo Int) (Int, Int))
-> (Int -> Const (Endo Int) Int)
-> Vector (Int, Int)
-> Const (Endo Int) (Vector (Int, Int))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Int -> Const (Endo Int) Int)
-> (Int, Int) -> Const (Endo Int) (Int, Int)
forall s t a b. Field1 s t a b => Lens s t a b
_1)


-- | Next item in a cyclic permutation
next     :: GV.Vector v a => v a -> Int -> a
next :: v a -> Int -> a
next v a
v Int
i = let n :: Int
n = v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
GV.length v a
v in v a
v v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
GV.! ((Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
n)

-- | Previous item in a cyclic permutation
previous     :: GV.Vector v a => v a -> Int -> a
previous :: v a -> Int -> a
previous v a
v Int
i = let n :: Int
n = v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
GV.length v a
v in v a
v v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
GV.! ((Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Int -> Int -> Int
forall a. Integral a => a -> a -> a
`mod` Int
n)

-- | Lookup the indices of an element, i.e. in which orbit the item is, and the
-- index within the orbit.
--
-- runnign time: \(O(1)\)
lookupIdx        :: Enum a => Permutation a -> a -> (Int,Int)
lookupIdx :: Permutation a -> a -> (Int, Int)
lookupIdx Permutation a
perm a
x = Permutation a
permPermutation a
-> Getting (Endo (Int, Int)) (Permutation a) (Int, Int)
-> (Int, Int)
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Int, Int) -> Const (Endo (Int, Int)) (Vector (Int, Int)))
-> Permutation a -> Const (Endo (Int, Int)) (Permutation a)
forall a. Lens' (Permutation a) (Vector (Int, Int))
indexes((Vector (Int, Int) -> Const (Endo (Int, Int)) (Vector (Int, Int)))
 -> Permutation a -> Const (Endo (Int, Int)) (Permutation a))
-> (((Int, Int) -> Const (Endo (Int, Int)) (Int, Int))
    -> Vector (Int, Int)
    -> Const (Endo (Int, Int)) (Vector (Int, Int)))
-> Getting (Endo (Int, Int)) (Permutation a) (Int, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Int, Int))
-> Traversal' (Vector (Int, Int)) (IxValue (Vector (Int, Int)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix (a -> Int
forall a. Enum a => a -> Int
fromEnum a
x)

-- | Apply the permutation, i.e. consider the permutation as a function.
apply        :: Enum a => Permutation a -> a -> a
apply :: Permutation a -> a -> a
apply Permutation a
perm a
x = let (Int
c,Int
i) = Permutation a -> a -> (Int, Int)
forall a. Enum a => Permutation a -> a -> (Int, Int)
lookupIdx Permutation a
perm a
x
               in Vector a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
next (Permutation a
permPermutation a
-> Getting (Endo (Vector a)) (Permutation a) (Vector a) -> Vector a
forall s a. HasCallStack => s -> Getting (Endo a) s a -> a
^?!(Vector (Vector a) -> Const (Endo (Vector a)) (Vector (Vector a)))
-> Permutation a -> Const (Endo (Vector a)) (Permutation a)
forall a a.
Lens
  (Permutation a)
  (Permutation a)
  (Vector (Orbit a))
  (Vector (Orbit a))
orbits((Vector (Vector a) -> Const (Endo (Vector a)) (Vector (Vector a)))
 -> Permutation a -> Const (Endo (Vector a)) (Permutation a))
-> ((Vector a -> Const (Endo (Vector a)) (Vector a))
    -> Vector (Vector a)
    -> Const (Endo (Vector a)) (Vector (Vector a)))
-> Getting (Endo (Vector a)) (Permutation a) (Vector a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Index (Vector (Vector a))
-> Traversal' (Vector (Vector a)) (IxValue (Vector (Vector a)))
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Int
Index (Vector (Vector a))
c) Int
i


-- | Find the cycle in the permutation starting at element s
orbitFrom     :: Eq a => a -> (a -> a) -> [a]
orbitFrom :: a -> (a -> a) -> [a]
orbitFrom a
s a -> a
p = a
s a -> [a] -> [a]
forall a. a -> [a] -> [a]
: ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
s) ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. [a] -> [a]
tail ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate a -> a
p a
s)

-- | Given a vector with items in the permutation, and a permutation (by its
-- functional representation) construct the cyclic representation of the
-- permutation.
cycleRep        :: (GV.Vector v a, Enum a, Eq a) => v a -> (a -> a) -> Permutation a
cycleRep :: v a -> (a -> a) -> Permutation a
cycleRep v a
v a -> a
perm = Int -> [[a]] -> Permutation a
forall a. Enum a => Int -> [[a]] -> Permutation a
toCycleRep Int
n ([[a]] -> Permutation a) -> [[a]] -> Permutation a
forall a b. (a -> b) -> a -> b
$ (forall s. ST s [[a]]) -> [[a]]
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s [[a]]) -> [[a]])
-> (forall s. ST s [[a]]) -> [[a]]
forall a b. (a -> b) -> a -> b
$ do
    MVector s Bool
bv    <- Int -> Bool -> ST s (MVector (PrimState (ST s)) Bool)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> a -> m (MVector (PrimState m) a)
UMV.replicate Int
n Bool
False -- bit vector of marks
    [Maybe [a]]
morbs <- [Int] -> (Int -> ST s (Maybe [a])) -> ST s [Maybe [a]]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [Int
0..(Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)] ((Int -> ST s (Maybe [a])) -> ST s [Maybe [a]])
-> (Int -> ST s (Maybe [a])) -> ST s [Maybe [a]]
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
               Bool
m <- MVector (PrimState (ST s)) Bool -> Int -> ST s Bool
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UMV.read MVector s Bool
MVector (PrimState (ST s)) Bool
bv (a -> Int
forall a. Enum a => a -> Int
fromEnum (a -> Int) -> a -> Int
forall a b. (a -> b) -> a -> b
$ v a
v v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
GV.! Int
i)
               if Bool
m then Maybe [a] -> ST s (Maybe [a])
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe [a]
forall a. Maybe a
Nothing -- already visited
                    else do
                      let xs :: [a]
xs = a -> (a -> a) -> [a]
forall a. Eq a => a -> (a -> a) -> [a]
orbitFrom (v a
v v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
GV.! Int
i) a -> a
perm
                      MVector (PrimState (ST s)) Bool -> [Int] -> ST s ()
forall (t :: * -> *) (m :: * -> *).
(Foldable t, PrimMonad m) =>
MVector (PrimState m) Bool -> t Int -> m ()
markAll MVector s Bool
MVector (PrimState (ST s)) Bool
bv ([Int] -> ST s ()) -> [Int] -> ST s ()
forall a b. (a -> b) -> a -> b
$ (a -> Int) -> [a] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map a -> Int
forall a. Enum a => a -> Int
fromEnum [a]
xs
                      Maybe [a] -> ST s (Maybe [a])
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe [a] -> ST s (Maybe [a]))
-> ([a] -> Maybe [a]) -> [a] -> ST s (Maybe [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Maybe [a]
forall a. a -> Maybe a
Just ([a] -> ST s (Maybe [a])) -> [a] -> ST s (Maybe [a])
forall a b. (a -> b) -> a -> b
$ [a]
xs
    [[a]] -> ST s [[a]]
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([[a]] -> ST s [[a]])
-> ([Maybe [a]] -> [[a]]) -> [Maybe [a]] -> ST s [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Maybe [a]] -> [[a]]
forall a. [Maybe a] -> [a]
catMaybes ([Maybe [a]] -> ST s [[a]]) -> [Maybe [a]] -> ST s [[a]]
forall a b. (a -> b) -> a -> b
$ [Maybe [a]]
morbs
  where
    n :: Int
n  = v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
GV.length v a
v

    mark :: MVector (PrimState m) Bool -> Int -> m ()
mark    MVector (PrimState m) Bool
bv Int
i = MVector (PrimState m) Bool -> Int -> Bool -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UMV.write MVector (PrimState m) Bool
bv Int
i Bool
True
    markAll :: MVector (PrimState m) Bool -> t Int -> m ()
markAll MVector (PrimState m) Bool
bv   = (Int -> m ()) -> t Int -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (MVector (PrimState m) Bool -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MVector (PrimState m) Bool -> Int -> m ()
mark MVector (PrimState m) Bool
bv)


-- | Given the size n, and a list of Cycles, turns the cycles into a
-- cyclic representation of the Permutation.
toCycleRep      :: Enum a => Int -> [[a]] -> Permutation a
toCycleRep :: Int -> [[a]] -> Permutation a
toCycleRep Int
n [[a]]
os = Vector (Orbit a) -> Vector (Int, Int) -> Permutation a
forall a. Vector (Orbit a) -> Vector (Int, Int) -> Permutation a
Permutation ([Orbit a] -> Vector (Orbit a)
forall a. [a] -> Vector a
V.fromList ([Orbit a] -> Vector (Orbit a))
-> ([[a]] -> [Orbit a]) -> [[a]] -> Vector (Orbit a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> Orbit a) -> [[a]] -> [Orbit a]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> Orbit a
forall a. [a] -> Vector a
V.fromList ([[a]] -> Vector (Orbit a)) -> [[a]] -> Vector (Orbit a)
forall a b. (a -> b) -> a -> b
$ [[a]]
os) (Int -> [[a]] -> Vector (Int, Int)
forall a. Enum a => Int -> [[a]] -> Vector (Int, Int)
genIndexes Int
n [[a]]
os)


genIndexes      :: Enum a => Int -> [[a]] -> UV.Vector (Int,Int)
genIndexes :: Int -> [[a]] -> Vector (Int, Int)
genIndexes Int
n [[a]]
os = (forall s. ST s (MVector s (Int, Int))) -> Vector (Int, Int)
forall a. Unbox a => (forall s. ST s (MVector s a)) -> Vector a
UV.create ((forall s. ST s (MVector s (Int, Int))) -> Vector (Int, Int))
-> (forall s. ST s (MVector s (Int, Int))) -> Vector (Int, Int)
forall a b. (a -> b) -> a -> b
$ do
                                MVector s (Int, Int)
v <- Int -> ST s (MVector (PrimState (ST s)) (Int, Int))
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
UMV.new Int
n
                                ((Int, (Int, Int)) -> ST s ()) -> [(Int, (Int, Int))] -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ ((Int -> (Int, Int) -> ST s ()) -> (Int, (Int, Int)) -> ST s ()
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((Int -> (Int, Int) -> ST s ()) -> (Int, (Int, Int)) -> ST s ())
-> (Int -> (Int, Int) -> ST s ()) -> (Int, (Int, Int)) -> ST s ()
forall a b. (a -> b) -> a -> b
$ MVector (PrimState (ST s)) (Int, Int)
-> Int -> (Int, Int) -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UMV.write MVector s (Int, Int)
MVector (PrimState (ST s)) (Int, Int)
v) [(Int, (Int, Int))]
ixes'
                                MVector s (Int, Int) -> ST s (MVector s (Int, Int))
forall (f :: * -> *) a. Applicative f => a -> f a
pure MVector s (Int, Int)
v
  where
    f :: a -> [a] -> [(Int, (a, b))]
f a
i [a]
c = (a -> b -> (Int, (a, b))) -> [a] -> [b] -> [(Int, (a, b))]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (\a
x b
j -> (a -> Int
forall a. Enum a => a -> Int
fromEnum a
x,(a
i,b
j))) [a]
c [b
0..]
    ixes' :: [(Int, (Int, Int))]
ixes' = [[(Int, (Int, Int))]] -> [(Int, (Int, Int))]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[(Int, (Int, Int))]] -> [(Int, (Int, Int))])
-> [[(Int, (Int, Int))]] -> [(Int, (Int, Int))]
forall a b. (a -> b) -> a -> b
$ (Int -> [a] -> [(Int, (Int, Int))])
-> [Int] -> [[a]] -> [[(Int, (Int, Int))]]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> [a] -> [(Int, (Int, Int))]
forall b a a.
(Num b, Enum a, Enum b) =>
a -> [a] -> [(Int, (a, b))]
f [Int
0..] [[a]]
os