Lazy Permutations in Haskell

Combinatorial.hs

module Combinatorial (
    combine,
    permutations,
    matrices,
) where


-- inserts a value in a list at every possible position
combine :: t -> [t] -> [[t]]
combine x []     = [[x]]
combine x (y:ys) = (x:y:ys) : map (y:) (combine x ys)

-- generate all permutations of a list
permutations :: [t] -> [[t]]
permutations []     = [[]]
permutations (x:xs) = permutations xs >>= combine x

-- all n*n chaotic permutations matrices with no repeated values in rows or columns
matrices :: Int -> [[[Int]]]
matrices n = let pls = possibleLines n in
    pls >>= \(row, _) -> possibleArrays n row pls


-- generate an association list for all possible line permutation pairings
possibleLines :: Int -> [([Int],[[Int]])]
possibleLines n = let perms = permutations [1..n] in
    perms >>= (\row -> map (\all -> (row, (filterPos row all))) [perms])

-- filter all rows which have the nth element equal to a reference row's for all n
filterPos :: Eq t => [t] -> [[t]] -> [[t]]
filterPos ref rest = aux ref rest 0 where
    aux [] ys _     = ys
    aux (x:xs) ys n = aux xs (filter (\y -> y !! n /= x) ys) (n+1)

-- generate all possible arrays with n lines from allowed line pairings
possibleArrays :: Int -> [Int] -> [([Int],[[Int]])] -> [[[Int]]]
possibleArrays 2 row allowed = maybe [] makeArray (lookup row allowed) where
    makeArray lines = map (\line -> [row, line]) lines
possibleArrays m row allowed = maybe [] (makeArray (restrict allowed row)) (lookup row allowed) where
    -- edit possible lines (pls) by filtering incompatible lines
    restrict pls line = map (\(r, ps) -> (r, filterPos line ps)) pls
    -- append row after recursively building array list of size m-1
    makeArray pls [] = []
    makeArray pls ys = ys >>= \y -> map (row:) (possibleArrays (m-1) y pls)