我是 Haskell 的新手，我想從給定的元素中提取最大元素，List以便最終得到最大元素x和剩余串列xs（不包含 x）。可以假設串列的元素是唯一的。
我要實作的函式型別有點像這樣：
maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
值得注意的是，第一個引數是一個將元素轉換為可比較形式的函式。此外，此功能是非總的，因為它會失敗給一個空的List.
我目前的方法無法將剩余串列中的元素保持在適當的位置，這意味著[5, 2, 4, 6]它回傳(6, [2, 4, 5])而不是(6, [5, 2, 4]). 此外，感覺應該有一個更好看的解決方案。
compareElement :: (Ord b) => (a -> b) -> a -> (b, (a, [a])) -> (b, (a, [a]))
compareElement p x (s, (t, ts))
| s' > s = (s', (x, t:ts))
| otherwise = (s, (t, x:ts))
where s' = p x
maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement p (t:ts) = snd . foldr (compareElement p) (p t, (t, [])) $ ts
更新
感謝@Ismor 的回答和@chi 的評論的幫助，我更新了我的實作，我對結果感到滿意。
maxElement :: (Ord b) => (a -> b) -> [a] -> Maybe (b, a, [a], [a])
maxElement p =
let
f x Nothing = Just (p x, x, [], [x])
f x (Just (s, m, xs, ys))
| s' > s = Just (s', x, ys, x:ys)
| otherwise = Just (s, m, x:xs, x:ys)
where s' = p x
in
foldr f Nothing
結果是Nothing給定串列為空時或Maybe (_, x, xs, _). 我可以用最初預期的型別撰寫另一個“包裝器”函式并在后臺呼叫maxElement，但我相信這也可以。
uj5u.com熱心網友回復：
這個答案更像是個人建議而不是正確的答案。根據經驗，每當您發現自己嘗試使用累加器撰寫回圈時（如本例中），請嘗試以這種形式撰寫
foldr updateAccumulator initialAccumulator --use foldl' if it is better for your use case`
然后，按照型別完成它，如下所示
第1步
undefined在需要的地方寫。你知道這個函式應該是這樣的
maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = foldr updateAccumulator initalAccumulator xs
where
updateAccumulator = undefined
initialAccumulator = undefined
第2步
“追型別”。這意味著使用maxElementandfoldr的型別可以推匯出updateAccumulatorand的型別initialAccumulator。盡量減少多型性。在這種情況下：
- 你懂
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b - 你知道你
Foldable的[]所以替換起來會更容易 - 因此
foldr :: (a -> b -> b) -> b -> [a] -> b - 因為你想
foldr生產(a, [a])你知道b ~ (a, [a]) - 等等......繼續下去，直到你知道你的函式有什么型別。您可以使用GHC輸入孔在這個程序中，這是一個很不錯的功能
maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = foldr updateAccumulator initalAccumulator xs
where
-- Notice that you need to enable an extension to write type signature in where clause
-- updateAccumulator :: a -> (a, [a]) -> (a, [a])
updateAccumulator newElement (currentMax, currentList) = undefined
-- initialAccumulator :: (a, [a])
initialAccumulator = undefined
第 3 步
現在，寫下函式應該更容易了。下面我留下一些不完整的部分供大家填寫
maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = foldr updateAccumulator initalAccumulator xs
where
-- updateAccumulator :: a -> (a, [a]) -> (a, [a])
updateAccumulator newElement (currentMax, currentList) =
if f newElement > f currentMax
then undefined -- How does the accumulator should look when the new element is bigger than the previous maximum?
else undefined
-- initialAccumulator :: (a, [a])
initialAccumulator = undefined -- Tricky!, what does happen if xs is empty?
希望這能澄清一些疑問，并理解我沒有給你一個完整的答案。
uj5u.com熱心網友回復：
我不知道您是否試圖避免使用某些庫函式，但是Data.List有一個maximumBy并且deleteBy完全符合您的要求：
import Data.Function (on)
import Data.List (deleteBy, maximumBy)
import Data.Ord (comparing)
maxElement :: (Ord b) => (a -> b) -> [a] -> (a, [a])
maxElement f xs = (max, remaining) where
max = maximumBy (comparing f) xs
remaining = deleteBy ((==) `on` f) max xs
uj5u.com熱心網友回復：
感謝@Ismor 的回答和@chi 的評論的幫助，我更新了我的實作，我對結果感到滿意。
maxElement :: (Ord b) => (a -> b) -> [a] -> Maybe (b, a, [a], [a])
maxElement p =
let
f x Nothing = Just (p x, x, [], [x])
f x (Just (s, m, xs, ys))
| s' > s = Just (s', x, ys, x:ys)
| otherwise = Just (s, m, x:xs, x:ys)
where s' = p x
in
foldr f Nothing
當給定串列為空時，結果要么是 Nothing，要么是 Maybe (_, x, xs, _)。我可以使用最初預期的型別撰寫另一個“包裝器”函式并在后臺呼叫 maxElement，但我相信這也可以。
uj5u.com熱心網友回復：
在輸入串列上構造所有“拉鏈”的串列，然后取出maximumBy (comparing (\(_,x,_) -> foo x))它，foo您的Ord b => a -> b函式在哪里，然后將前半部分反向附加到第二部分，并將其與中間元素一起放在一個元組中。
串列xs上的拉鏈是一個三元組(revpx, x, suffx)，其中xs == reverse revpx [x] suffx：
> :t comparing (\(_,x,_) -> x)
comparing (\(_,x,_) -> x)
:: Ord a => (t, a, t1) -> (t, a, t1) -> Ordering
構建拉鏈串列是一項基本練習（請參閱picks3那里的功能）。
關于您編輯的解決方案，它可以編碼為一個foldrover thetails所以它更清楚那里發生了什么：
maxElement :: (Ord b) => (a -> b) -> [a] -> Maybe (b, a, [a])
maxElement p [] = Nothing
maxElement p xs = Just $ foldr f undefined (tails xs)
where
f [x] _ = (p x, x, [])
f (x:xs) (b, m, ys)
| b' > b = (b', x, xs) -- switch over
| otherwise = (b, m, x:ys)
where b' = p x
它也更簡潔一些，因為它不會無緣無故地回傳輸入串列的副本，就像您的版本那樣，因為它將它用于內部目的。
這兩種方式實際上都在模擬一個paramorphism。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/359169.html
上一篇：使用Haskell的Control.Monad.Random.Class.fromList和System.Random