I'm kinda new to Haskell and I'm trying to generate all contiguous sublists of a list.
I current have the following:
listSublists :: [a] -> [[a]]
listSublists [] = [[]]
listSublists xs = [xs] ++ listSublists (init xs)
I know the function above would generate sublists with the last element removed but I've no idea how to finish my pseudocode.
My pseudocode is basically,
Take the whole complete list, remove tail. Pass xs of (x:xs) into listSublists
For example, xs = [1,2,3] [xs] ++ listSublists (init xs) would generate [1,2,3,4], [1,2,3], [1,2], [1], [] and I'm trying to continue that with passing in [2,3,4] as xs until the list is exhausted.
Can someone give me some pointers? Or am I thinking in a completely wrong way?
The listSublists function that you have is functionally almost identical to
the inits
function. You are on the right track, in that you can currently list all of
the prefixes of a given list.
What you want to ask is "what is a sublist of a list?" One answer is that it is a suffix of a prefix of the list (i.e. chop off some portion from the end of a list and then chop off some elements off the front of that list, and you have one of the contiguous sublists).
So, if you have your prefixes, then what you want is a way to generate all
the suffixes of a given prefix (i.e. of some list). So, if you have
prefixes :: [a] -> [[a]]
prefixes [] = [[]]
prefixes xs = [xs] ++ prefixes (init xs)
you also want a corresponding function suffixes
suffixes :: [a] -> [[a]]
suffixes [] = [[]]
suffixes xs = [xs] ++ suffixes (??? xs)
I will leave it to you to figure out what to use for ???. With these two
functions, you then just take all the prefixes, and produce all the suffixes
to get all the contiguous sublists
allSublists :: [a] -> [[a]]
allSublists = concat . map suffixes . prefixes
You may want to remove all of the empty lists that will be in the result set, as they are not that interesting of a case.