From dbf158f2f20f9c7eb56e5d1e156478d0a4623fcf Mon Sep 17 00:00:00 2001 From: Twan van Laarhoven Date: Wed, 2 Jan 2008 23:16:29 +0000 Subject: [PATCH] 'subsequences' is now more lazy and also faster --- Data/List.hs | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) diff --git a/Data/List.hs b/Data/List.hs index 279438f..4cc9fdf 100644 --- a/Data/List.hs +++ b/Data/List.hs @@ -736,10 +736,19 @@ tails xxs@(_:xs) = xxs : tails xs -- | The 'subsequences' function returns the list of all subsequences of the argument. -- --- > subsequences "abc" == ["","c","b","bc","a","ac","ab","abc"] +-- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"] subsequences :: [a] -> [[a]] -subsequences [] = [[]] -subsequences (x:xs) = subsequences xs ++ map (x:) (subsequences xs) +subsequences xs = [] : nonEmptySubsequences xs + +-- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument, +-- except for the empty list. +-- +-- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"] +nonEmptySubsequences :: [a] -> [[a]] +nonEmptySubsequences [] = [] +nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs) + where f ys r = ys : (x : ys) : r + -- | The 'permutations' function returns the list of all permutations of the argument. -- -- 1.7.10.4