How to move all occurrences of the first element of the list to the end of the list in Haskell?

user_7212677 0
Viewed 141

I want to extract the first element and all of its occurrences from a list and put them in the end of a list in Haskell

What I have now is this.

relegate [] = []
relegate (x:xs) = xs ++ [x]

With input [3 ,1 ,4 ,3 ,5 ,3 ,8] it returns me [1,4,3,5,3,8,3] but I wanted instead to return this list [1 ,4 ,5 ,8 ,3 ,3 ,3].

haskell
2 Answers

Right now you're just adding x to the end, which will only move the first occurrence, not all of them. You should instead find all equal elements, and remove them from the list. This can be done with partition in Data.List, which takes a predicate function and gets a list of elements that matches the predicate and a list that doesn't:

import Data.List

relegate :: (Eq a) => [a] -> [a]
relegate [] = []
relegate l@(x:_) = nonMatching ++ matching
    where (nonMatching, matching) = partition (/= x) l

Or, more pointfree:

import Data.List

relegate :: (Eq a) => [a] -> [a]
relegate [] = []
relegate l = uncurry (++) $ partition (/= head l) l
user_59231390

This algorithm requires to first determine that first element x, and then enumerate over the list, here we will yield all elements that are different from x, and keep track of the number of times we have found an element that is equal to x, and when we reach the end of the list, we replicate x the number of times we encountered x in the list:

relegate :: Eq a => [a] -> [a]
relegate [] = []
relegate (x:xs) = go xs 1
    where go [] n = replicate n x
          go (y:ys) m
              | x == y = go ys (m+1)
              | otherwise = y : go ys m

This of course assumes that if x == y, then x and y are the same element. If that is not the case, you should work with an accumulator that keeps track of the equal elements.

user_675790
Related