CODEWITHSUNDEEP
haskell
user2908235
user2908235

Reputation: 21

All subsequences from a single string

How do you extract every possible substring from a single string? I have come up with a kind of cumbersome way and want to find a simpler one.

subStrings :: String -> [String]
subStrings xs = xs : takeEl xs

takeEl :: String -> [String]
takeEl xs = nub (concat [y : (takeEl y) | y <- takeEl'])
  where 
    takeEl' = [del y xs | y <- [0..(length xs - 1)]]

del :: Int -> [a] -> [a]
del k xs = take k xs ++ drop (k+1) xs

I would like to explain a little further with an example: if I use the function on "abc", I want it to create a list including the elements below, with no permutations (if "ab" is there "ba" is not necessary).

`["abc", "a","b","c","ab","ac","bc",""]`

So concat inits . tails will not be enough since it won't give me "ac".

Upvotes: 2

Views: 2573

Answers (5)

Harshith Vasireddy
Harshith Vasireddy

Reputation: 11

If you don't want to use functions outside Prelude, use this:

substrings x = [drop b (take a x) | a <- [1..length x], b <- [0..a-1]]

This is definitely not the most efficient method. Just a quick and dirty one-liner for performance-insensitive tasks

However, OP's original question meant subsequences and not substrings.

Upvotes: 0

Petr
Petr

Reputation: 63359

Looks like what you're after isn't the list of all subsequences, but the list of all subsets (keeping the original order) - a power set. This can be accomplished by a nice trick in the list monad:

filterM (const [False, True]) "abc"

yields

["","c","b","bc","a","ac","ab","abc"]

The trick is that we non-deterministically filter the given list in the list monad, branching to both keep and remove a particular element.

Upvotes: 1

nickie
nickie

Reputation: 5808

EDIT: The following computes substrings, which was mentioned in the original question, not subsequences.

If you're looking for something quick (and not necessarily as efficient as possible), here's what I would suggest:

import Data.List (inits, tails)

nonEmptySubstrings :: [a] -> [[a]]
nonEmptySubstrings = concatMap (tail . inits) . tails

The tail is needed to eliminate the empty substring altogether; it would otherwise occur multiple times. If you want it too, you'll have to add it extra.

substrings :: [a] -> [[a]]
substrings = ([] :) . nonEmptySubstrings

Example:

Prelude Data.List> nonEmptySubstrings "abcd"
["a","ab","abc","abcd","b","bc","bcd","c","cd","d"]
Prelude Data.List> substrings "abcd"
["","a","ab","abc","abcd","b","bc","bcd","c","cd","d"]

Upvotes: 3

Daniel Wagner
Daniel Wagner

Reputation: 152817

The Data.List module offers subsequences, which is the correct name for this. (Substrings are contiguous.)

Upvotes: 5

daniel gratzer
daniel gratzer

Reputation: 53881

You can do this by taking the possible heads of all tails, or all possible tails of all heads.

This works since all substrings are uniquely determined by 2 things, position and length. When you drop all possible heads with tails, you're taking the string starting from every possible position with the longest possible length, then applying inits to all of these returns all possible lengths, combining these gives all possible substrings. The idea for the reverse is trivially similar.

So you can use nickie's

concatMap inits . tails

Or

concatMap tails . inits

And since >>= is the same as concatMap, you could write

tails <=< inits -- From control.monad

Upvotes: 2

Related Questions