From bc0d9c0cc527738b8a4f79770e44e1c53f9930d0 Mon Sep 17 00:00:00 2001 From: Twan van Laarhoven Date: Tue, 18 Dec 2007 15:49:50 +0000 Subject: [PATCH] Add 'subsequences' and 'permutations' to Data.List --- Data/List.hs | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) diff --git a/Data/List.hs b/Data/List.hs index fce4492..279438f 100644 --- a/Data/List.hs +++ b/Data/List.hs @@ -37,6 +37,9 @@ module Data.List , intersperse -- :: a -> [a] -> [a] , intercalate -- :: [a] -> [[a]] -> [a] , transpose -- :: [[a]] -> [[a]] + + , subsequences -- :: [a] -> [[a]] + , permutations -- :: [a] -> [[a]] -- * Reducing lists (folds) @@ -731,6 +734,24 @@ tails [] = [[]] 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 :: [a] -> [[a]] +subsequences [] = [[]] +subsequences (x:xs) = subsequences xs ++ map (x:) (subsequences xs) + +-- | The 'permutations' function returns the list of all permutations of the argument. +-- +-- > permutations "abc" == ["abc","bac","bca","acb","cab","cba"] +permutations :: [a] -> [[a]] +permutations [] = [[]] +permutations (x:xs) = [zs | ys <- permutations xs, zs <- interleave x ys ] + where interleave :: a -> [a] -> [[a]] + interleave x [] = [[x]] + interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys) + + ------------------------------------------------------------------------------ -- Quick Sort algorithm taken from HBC's QSort library. -- 1.7.10.4