list - كيفية العثور على جميع العناصر الدنيا في قائمة tuples؟




haskell minimum (4)

كيف يمكنني العثور على الحد الأدنى من العناصر في القائمة؟ الآن لدي قائمة من tuples ، أي

[(10,'a'),(5,'b'),(1,'c'),(8,'d'),(1,'e')]

لذلك أريد الإخراج الذي هو كل العناصر الدنيا للقائمة ، في قائمة جديدة. فمثلا

 [(1,'c'),(1,'e')]

حاولت

minimumBy (comparing fst) xs

ولكن هذا فقط إرجاع العنصر الأدنى الأول.


Oneliner. المفتاح هو الفرز.

Prelude Data.List> let a = [(1,'c'),(2,'b'),(1,'w')]
Prelude Data.List> (\xs@((m,_):_) -> takeWhile ((== m) . fst ) xs) . sortOn fst $ a
[(1,'c'),(1,'w')]

أنت حاولت

minimumBy (comparing fst) xs

والتي يمكن أيضا أن تكون مكتوبة

= head . sortBy (comparing fst) $ xs
= head . sortOn fst $ xs
= head . head . group . sortOn fst $ xs
= head . head . groupBy ((==) `on` fst) . sortOn fst $ xs

يؤدي هذا إلى إرجاع العنصر الأول فقط بدلاً من قائمتهم ، لذلك عليك فقط إسقاط ذلك head الإضافي للحصول على ما تريد:

=        head . groupBy ((==) `on` fst) . sortOn fst $ xs

بالطبع ليس وجود head جيدًا لأنه سيخطئ في إدخال [] . بدلاً من ذلك ، يمكننا استخدام الخيار الآمن ،

= concat . take 1 . groupBy ((==) `on` fst) . sortOn fst $ xs

بالمناسبة أي حل يستدعي minimum غير آمن أيضًا لقائمة الإدخال الفارغة:

> head []
*** Exception: Prelude.head: empty list

> minimum []
*** Exception: Prelude.minimum: empty list

لكن takeWhile آمن:

> takeWhile undefined []
[]

تحرير: بفضل الكسل ، يجب أن يكون التعقيد الزمني الكلي للنسخة النهائية هو O (n) حتى في أسوأ الحالات.


بعد الحصول على الحد الأدنى من القيمة الأولى ، يمكننا تصفية القائمة على هذه العناصر. نظرًا لأنك ترغب في استرداد قائمة من العناصر الدنيا ، يمكننا تغطية القائمة الفارغة أيضًا من خلال إرجاع قائمة فارغة:

minimumsFst :: Ord a => [(a, b)] -> [(a, b)]
minimumsFst [] = []
minimumsFst xs = filter ((==) minfst . fst) xs
    where minfst = minimum (map fst xs)

فمثلا:

Prelude> minimumsFst [(10,'a'),(5,'b'),(1,'c'),(8,'d'),(1,'e')]
[(1,'c'),(1,'e')]

يمكنك القيام بذلك بسهولة أيضًا باستخدام foldr :

minimumsFst :: Ord a => [(a, b)] -> [(a, b)]
minimumsFst xs = go (minfst xs) xs
  where
  go mn ls = foldr (\(x, y) rs -> if (x ==  mn) then (x,y) : rs else rs) [] xs
  minfst ls = minimum (map fst ls)

مع مثالك:

   minimumsFst [(10,'a'),(5,'b'),(1,'c'),(8,'d'),(1,'e')]
=> [(1,'c'),(1,'e')]






minimum