LazyCart.hs

{-------------------------------------------------------------------------------
  Lazy n-ary cartesian product

  Most of these functions (except for 'cart' itself) are taken from
  "Generics.Deriving.Enum", which in turn are taken from Mark Jones' talk
  at AFP 2008.
-------------------------------------------------------------------------------}

-- | n-ary lazy cartesian product
ncart :: HList [] as -> [HList Identity as]
ncart HL.Nil         = [HL.Nil]
ncart (xs HL.:& xss) = diag [ [ Identity hd HL.:& tl
                              | tl <- ncart xss
                              ]
                            | hd <- xs
                            ]

-- | Diagonalization of nested lists. Ensure that some elements from every
-- sublist will be included. Handles infinite sublists.
diag :: [[a]] -> [a]
diag = concat . foldr skew [] . map (map (\x -> [x]))

skew :: [[a]] -> [[a]] -> [[a]]
skew []     ys = ys
skew (x:xs) ys = x : combine (++) xs ys

combine :: (a -> a -> a) -> [a] -> [a] -> [a]
combine _ xs     []     = xs
combine _ []     ys     = ys
combine f (x:xs) (y:ys) = f x y : combine f xs ys