All paths

allpaths.hs

module Main where

-- | All paths from the first row down
--
-- >>> allPaths [[4,5]]
-- [[4],[5]]
-- >>> allPaths [[3], [4, 5]]
-- [[3,4],[3,5]]
-- >>> allPaths [[1,2], [3], [4,5]]
-- [[1,3,4],[1,3,5],[2,3,4],[2,3,5]]
-- >>> allPaths [["cat", "dog"], ["bear"], ["cow", "pig"]]
-- [["cat","bear","cow"],["cat","bear","pig"],["dog","bear","cow"],["dog","bear","pig"]]
allPaths :: [[a]] -> [[a]]
allPaths [] = [[]]
allPaths (xs : xss) = [x : subpath | x <- xs, subpath <- allPaths xss]
-- Not using list comprehensions:
{-
allPaths (xs : xss) =
  concatMap (\x ->
    map (\subpath -> x : subpath) subpaths
  ) xs
  where subpaths = allPaths xss
-}

main :: IO ()
main =
  print $ map concat (allPaths [["cat", "dog"], ["bear"], ["cow", "pig"]])