CODEWITHSUNDEEP
haskell
MERCURY EDITS
MERCURY EDITS

Reputation: 13

How to remove second largest element in a list in haskell?

I have created a program to remove first smallest element but I dont how to do for second largest:

withoutBiggest (x:xs) =
   withoutBiggestImpl (biggest x xs) [] (x:xs)
     where
       biggest :: (Ord a) => a -> [a] -> a
       biggest big [] = big
       biggest big (x:xs) =
         if x < big then
           biggest x xs
         else
           biggest big xs
       withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
       withoutBiggestImpl big before (x:xs) =
         if big == x then
           before ++ xs
         else
             withoutBiggestImpl big (before ++ [x]) xs

Upvotes: 0

Views: 544

Answers (5)

sshine
sshine

Reputation: 16105

You can remove the biggest elements by first finding it and then filtering it:

withoutBiggest :: Ord a => [a] -> [a]
withoutBiggest [] = []
withoutBiggest xs = filter (/= maximum xs) xs

You can then remove the second-biggest element in much the same way:

withoutSecondBiggest :: Ord a => [a] -> [a]
withoutSecondBiggest xs =
  case withoutBiggest xs of
    [] -> xs
    rest -> filter (/= maximum rest) xs

Assumptions made:

  • You want each occurrence of the second-biggest element removed.
  • When there is zero/one element in the list, there isn't a second element, so there isn't a second-biggest element. Having the list without an element that isn't there is equivalent to having the list.
  • When the list contains only values equivalent to maximum xs, there also isn't a second-biggest element even though there may be two or more elements in total.
  • The Ord type-class instance implies a total ordering. Otherwise you may have multiple maxima that are not equivalent; otherwise which one is picked as the biggest and second-biggest is not well-defined.

Upvotes: 0

Alberto Centelles
Alberto Centelles

Reputation: 1253

Here is a solution that removes the n smallest elements from your list:

import Data.List

deleteN :: Int -> [a] -> [a]
deleteN _ []     = []
deleteN i (a:as)
   | i == 0    = as
   | otherwise = a : deleteN (i-1) as

ntails :: Int -> [a] -> [(a, Int)] -> [a]
ntails 0 l _ = l
ntails n l s = ntails (n-1) (deleteN (snd $ head s) l) (tail s)

removeNSmallest :: Ord a => Int -> [a] -> [a]
removeNSmallest n l = ntails n l $ sort $ zip l [0..]

EDIT:

If you just want to remove the 2nd smallest element:

deleteN :: Int -> [a] -> [a]
deleteN _ []     = []
deleteN i (a:as)
   | i == 0    = as
   | otherwise = a : deleteN (i-1) as

remove2 :: [a] -> [(a, Int)] -> [a]
remove2 [] _  = []
remove2 [a] _ = []
remove2 l s = deleteN (snd $ head $ tail s) l

remove2Smallest :: Ord a => [a] -> [a]
remove2Smallest l = remove2 l $ sort $ zip l [0..]

Upvotes: 1

St&#233;phane Laurent
St&#233;phane Laurent

Reputation: 84529

A possibility, surely not the best one.

import Data.Permute (rank)

x = [4,2,3]
ranks = rank (length x) x -- this gives [2,0,1]; that means 3 (index 1) is the second smallest

Then:

 [x !! i | i <- [0 .. length x -1], i /= 1]

Hmm.. not very cool, let me some time to think to something better please and I'll edit my post.

EDIT

Moreover my previous solution was wrong. This one should be correct, but again not the best one:

import Data.Permute (rank, elems, inverse)

ranks = elems $ rank (length x) x
iranks = elems $ inverse $ rank (length x) x

>>> [x !! (iranks !! i) | i <- filter (/=1) ranks]
[4,2]

An advantage is that this preserves the order of the list, I think.

Upvotes: 1

wisn
wisn

Reputation: 1024

Here is a simple solution.

Prelude> let list = [10,20,100,50,40,80]
Prelude> let secondLargest = maximum $ filter (/= (maximum list)) list
Prelude> let result = filter (/= secondLargest) list
Prelude> result
[10,20,100,50,40]
Prelude>

Upvotes: 1

Nicola Gigante
Nicola Gigante

Reputation: 3266

It was not clear if the OP is looking for the biggest (as the name withoutBiggest implies) or what. In this case, one solution is to combine the filter :: (a->Bool) -> [a] -> [a] and maximum :: Ord a => [a] -> a functions from the Prelude.

withoutBiggest l = filter (/= maximum l) l

Upvotes: 0

Related Questions