Splitting list into sublists in Haskell

Question

How can I split a list into 2 sublists, where first sublist includes elements from begin of initial list and equals to first element, and second sublist contains others elements? I have to resolve this without using Prelude functions.

My base solution is:

partSameElems :: [a] -> ([a],[a])
partSameElems [] = ([],[])
partSameElems (x:xs) = fstList (x:xs) scdList (x:xs)
    where 
        fstList (x:y:xs) = if x == y then x:y:fstList xs {- I need to do Nothing in else section? -} 
        scdList (x:xs) = x:scdList xs

For example: [3,3,3,3,2,1,3,3,6,3] -> ([3,3,3,3], [2,1,3,3,6,3])

Now I can offer my version of solution:

partSameElems :: Eq a => [a] -> ([a],[a])
partSameElems [] = ([],[])
partSameElems (x:xs) = (fstList (x:xs), scdList (x:xs))
where
    fstList [] _ = []
    fstList (x:xs) el = if x == el then x:fstList xs el else []
    scdList [] _ = []
    scdList (x:xs) el = if x /= el then (x:xs) else  scdList xs el

Answer 1

This is easier if you don't try to do it in two passes.

parSameElems [] = ([], [])
parSameElems lst = (reverse revxs, ys)
  where (revxs, ys) = accum [] lst
        accum xs [y] = ((y:xs), [])
        accum xs (y1:y2:ys) | y1 == y2 = accum (y1:xs) (y2:ys)
                            | otherwise = ((y1:xs), (y2:ys))

Not sure you can use guard syntax in where clauses. You will also have to implement reverse yourself since you can't use Prelude, but that's easy.

Note: I haven't actually run this. Make sure you try and debug it.

Also, don't write the type signature yourself. Let ghci tell you. You got it wrong in your first try.

Answer 2

I assume the "without resorting to Prelude function" means it's educational. Probably aimed at working on recursion, given it's manipulation of List data. So let's emphasize this

Recursive algorithms are simpler to express when input and output types are identical. Let's rather say that instead of a list [3,3,3,3,2,1,3,3,6,3], your input data is composed of

• the front list, but at this stage it's empty
• the remainder, at this stage equals to input [3,3,3,2,1,3,3,6,3]
• recursion input is then ([],[3,3,3,2,1,3,3,6,3])

The type of the central function will be ([a],[a]) -> ([a],[a])

Now, each recursion step will take the front element of the remainder and either put if in the front list or stop recursion (you reached the final state and can return the result)

module SimpleRecursion where
moveInFront :: (Eq a) => ([a],[a]) -> ([a],[a])
moveInFront (xs    , []   ) =                ( xs    , [])
moveInFront ([]    , y:ys ) =                moveInFront ( y:[]  , ys)
moveInFront (x:xs  , y:ys ) = if x == y then moveInFront ( y:x:xs  , ys) 
                                        else (x:xs, y:ys)

partSameElems :: (Eq a) => [a] -> ([a],[a])
partSameElems a = moveInFront ([],a)

What we have here is a classical recursion scheme, with - stop condition (x /= y) - recursion clause - coverage of trivial cases

Notes : - writing y:x:xs actually reverses the front list but since all values are equal the result is ok Please don't do that kind of trick in the code of an actual program, it would come back to bite you eventually - the function only works on lists of Equatable data (Eq a) => because the recursion / stop condition is the equality test ==

Answer 3

Another implementation can be

partition [] = ([],[])
partition xa@(x:xs) = (f,s)
              where
                   f = takeWhile (==x) xa
                   s = drop (length f) xa

should be clear what it does.

> partition [3,3,3,3,2,1,3,3,6,3]
([3,3,3,3],[2,1,3,3,6,3])