Zip unique list subsets

Main.hs

{-# LANGUAGE ExplicitForAll      #-}
{-# LANGUAGE ScopedTypeVariables #-}

module Main where

import qualified Control.Monad as Monad
import qualified Data.Foldable as Foldable
import qualified Data.HashSet  as HashSet
import qualified Data.List     as List
import           Data.Monoid   ((<>))
import qualified Data.Monoid   as Monoid

combine xs ys = Monoid.mconcat . fmap (\xs' -> HashSet.fromList . fmap (zip xs') $ List.permutations ys) $ powerSet xs
  where powerSet = Monad.filterM $ const [True, False]

combine' :: forall a b. [a] -> [b] -> [[(a, b)]]
combine' [] _  = []
combine' _ []  = []
combine' (x : xs) (y : ys) = concat (mapHole holeFn (y : ys)) ++ combine' xs (y : ys)
  where
  holeFn ls z rs = [(x, z)] : fmap ((x, z) :) (combine' xs (ls ++ rs))

mapHole :: ([a] -> a -> [a] -> b) -> [a] -> [b]
mapHole f = aux f []
  where
  aux _ _ []        = []
  aux f ls (x : rs) = f ls x rs : aux f (ls ++ [x]) rs

printLines :: Show a => Ord a => Foldable f => f a -> IO ()
printLines = Monad.mapM_ print . List.sort . Foldable.toList

main :: IO ()
main = do
  putStrLn "hello world"