home *** CD-ROM | disk | FTP | other *** search
/ PSION CD 2 / PsionCDVol2.iso / Programs / 876 / hugs.sis / ListUtils.hs < prev    next >
Encoding:
Text File  |  2000-09-21  |  895 b   |  26 lines
  1. module ListUtils(
  2.     sums, products,
  3.     subsequences,
  4.     permutations
  5.     ) where
  6.  
  7. sums, products     :: Num a => [a] -> [a]
  8. sums                = scanl (+) 0
  9. products            = scanl (*) 1
  10.  
  11. -- subsequences xs returns the list of all subsequences of xs.
  12. -- e.g., subsequences "abc" == ["","c","b","bc","a","ac","ab","abc"]
  13. subsequences           :: [a] -> [[a]]
  14. subsequences []         = [[]]
  15. subsequences (x:xs)     = subsequences xs ++ map (x:) (subsequences xs)
  16.  
  17. -- permutations xs returns the list of all permutations of xs.
  18. -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"]
  19. permutations           :: [a] -> [[a]]
  20. permutations []         = [[]]
  21. permutations (x:xs)     = [zs | ys <- permutations xs, zs <- interleave x ys ]
  22.   where interleave         :: a -> [a] -> [[a]]
  23.         interleave x []     = [[x]]
  24.         interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys)
  25.  
  26.