Breaking a list on a given value into a list of sublists

Question

The multipleLists function needs to remove a given value from a list and return a list of lists. These sub lists group each element until it hits the value that needs to be removed. when this happens, a new sub list starts.

input:           multipleLists 'b' "abcabc"
expected output: ["a","ca","c"]
actual output:   ["a","c","a","c"]

input:           multipleLists 1 [0,1,2,3,4,1,3,4]
expected output: [[0],[2,3,4],[3,4]]
actual output:   [[0],[2],[3],[4],[3],[4]]

I think there is something wrong in the otherwise case but I'm a bit stuck.

Here is my code:

multipleLists :: Eq a => a -> [a] -> [[a]]
multipleLists value list = case list of 
    [] -> [] 
    [x] -> [[x]]
    x:xs 
        | value == x -> multipleLists value xs 
        | otherwise ->  [x] : (multipleLists value xs)

is your first example wrong? Shouldn't that be `["a","ca","c"]` — Random Dev, Jun 06 '21 at 06:46

Mark Saving · Answer 1 · 2021-06-06T01:52:18.643

2

multipleListsAllowEmpty value list = 
    let (beginning, end) = break (value ==) list
    in beginning : case end of
        [] -> []
        (_:xs) -> multipleListsAllowEmpty value xs

multipleLists value = filter (not . null) . multipleListsAllowEmpty

Here, we import break from Data.List.

We can express multipleListsAllowEmpty even more compactly by

maybeTail [] = Nothing
maybeTail (_:xs) = Just xs

multipleListsAllowEmpty value = 
    toList . unfoldr (fmap maybeTail . break (value ==))

where we import unfoldr and toList from Data.List.NonEmpty.

edited Jun 06 '21 at 01:52

answered Jun 06 '21 at 01:39

Mark Saving

1,752
7
11

is there a way to do it without importing anything? – waterbottle334 Jun 06 '21 at 02:46
your `unfoldr`-based code doesn't typecheck. it does if you replace `fmap` with `traverse`, but then it skips the last group in the output. – Will Ness Jun 06 '21 at 07:00

Random Dev · Accepted Answer · 2021-06-06T07:06:09.760

Here is a modified version of yours using an accumulator - it does not use anything external besides reverse (which you could remove by changing the way the accumulator is build-up):

multipleLists :: Eq a => a -> [a] -> [[a]]
multipleLists value = go []
  where
  go [] [] = []
  go [] (x:xs)
    | x == value = go [] xs
    | otherwise = go [x] xs
  go acc [] = [reverse acc]
  go acc (x:xs)
    | x == value = reverse acc : go [] xs
    | otherwise = go (x:acc) xs

your examples (see my comment above):

> multipleLists 'b' "abcabc"
["a","ca","c"]

> multipleLists (1 :: Int) [0,1,2,3,4,1,3,4]
[[0],[2,3,4],[3,4]]

score 1 · Answer 3 · answered Jun 06 '21 at 15:21

What is the intended value of multipleLists 0 [0, 0]?

Is it [] or [[]] or [[], []]?

Here are two solutions that treat these cases differently, both based on a right fold.

splitList :: Eq a => a -> [a] -> [[a]]
splitList x = tail . foldr sx [[]] . (x:)
  where
    sx y ws@(zs:zss) | y == x    = [] : ws
                     | otherwise = (y:zs) : zss

multipleLists :: Eq a => a -> [a] -> [[a]]
multipleLists x = filter (not . null) . foldr sx [[]] . (x:)
  where 
    sx y ws@(zs:zss) | y == x    = [] : ws
                     | otherwise = (y:zs) : zss

[related](https://stackoverflow.com/a/14403413/849891) – Will Ness Jun 06 '21 at 20:03 — Will Ness, Jun 06 '21 at 20:03

Breaking a list on a given value into a list of sublists

3 Answers3