{-|

Module      : SubSeqs
Description : A collection of algorithms to generate sub-sequences
Copyright   : © Frank Jung, 2020
License     : GPL-3

This is a collection of different ways (with different performance) to
create <https://en.wikipedia.org/wiki/Subsequence subsquences>.

= Examples

@
subSeqs1 "abc" should be ["a","ab","abc","ac","b","bc","c"]
subSeqs2 "abc" should be ["a","ab","abc","ac","b","bc","c"]
subSeqs3 "abc" should be ["abc","ab","ac","a","bc","b","c",""]
subSeqs4 "abc" should be ["abc","ab","ac","a","bc","b","c",""]
@

-}

module SubSeqs (subSeqs1, subSeqs2, subSeqs3, subSeqs4) where

import           Control.Monad (filterM)

-- | From Pearls of Functional Algorithm Design.
subSeqs1 :: [a] -> [[a]]
subSeqs1 :: forall a. [a] -> [[a]]
subSeqs1 []  = [[]]
subSeqs1 [a
x] = [[a
x]]
subSeqs1 (a
x:[a]
xs) = [a
x] [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) [[a]]
xss [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]]
xss
  where xss :: [[a]]
xss = [a] -> [[a]]
forall a. [a] -> [[a]]
subSeqs1 [a]
xs

-- | Alternative definition using just 'foldr' and 'map'.
-- For non-empty lists only.
subSeqs2 :: [a] -> [[a]]
subSeqs2 :: forall a. [a] -> [[a]]
subSeqs2 = (a -> [[a]] -> [[a]]) -> [[a]] -> [a] -> [[a]]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\ a
x [[a]]
s -> [a
x] [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: ([a] -> [a]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) [[a]]
s [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [[a]]
s) []

-- | Using list comprehension.
subSeqs3 :: [a] -> [[a]]
subSeqs3 :: forall a. [a] -> [[a]]
subSeqs3 []     = [[]]
subSeqs3 (a
x:[a]
xs) = [a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
subseq | [a]
subseq <- [a] -> [[a]]
forall a. [a] -> [[a]]
subSeqs3 [a]
xs] [[a]] -> [[a]] -> [[a]]
forall a. [a] -> [a] -> [a]
++ [a] -> [[a]]
forall a. [a] -> [[a]]
subSeqs3 [a]
xs

-- | Create a power-set using 'Control.Monad'.
--
-- <https://blog.ssanj.net/posts/2018-04-10-how-does-filterm-work-in-haskell.html This blog>
-- explains 'filterM'.
subSeqs4 :: [a] -> [[a]]
subSeqs4 :: forall a. [a] -> [[a]]
subSeqs4 = (a -> [Bool]) -> [a] -> [[a]]
forall (m :: * -> *) a.
Applicative m =>
(a -> m Bool) -> [a] -> m [a]
filterM ([Bool] -> a -> [Bool]
forall a b. a -> b -> a
const [Bool
True, Bool
False])