如何獲得的最短名單列表在Haskell

這個函數，它在列表的列表，並返回最短的一個（返回一個空列表，如果列表中的列表爲空）如何獲得的最短名單列表在Haskell

例如最短[ [1,2,9]，[3,4]，[1,2,3,5]] 將返回[3,4]

最短:: [[a]] - > [a]

即將到來的新的haskell任何幫助將不勝感激謝謝

2013-10-26 programming

看來這個問題已經有一些很好的答案。但是，將來，說出你所嘗試過的東西，以及你被卡住的地方和原因是很禮貌的。 –

shortest [y] = y --base case: if there's only one element left, return it. 
shortest (x:y:lst) --extract the first two elements x, y from the list. 
    | length x > length y = *recursion* 
    | otherwise = *recursion*

你可以使用遞歸來解決這個問題。我基本上列出了你的結構，但你應該考慮如何實現遞歸的一部分。記住遞歸發生在函數自己調用時。

提示：使用冒號將最短元素連接回原始列表，以便您可以將其與列表中的下一個元素進行比較。

希望它能幫助！

來源

2013-10-26 15:31:06 yfan

那麼，你當然可以使用遞歸來解決任何問題（否則，不能以其他方式）。但是，如果有更高階的函數將您的負擔從中抽離出來，那麼使用它們通常是一個好主意。如果您對使用'minimumBy'的超短解決方案存在效率問題，則仍然可以使用摺疊，這在這裏相當於您指向的顯式遞歸解決方案。 – leftaroundabout

我明白你的關心。我只是認爲遞歸是考慮到他/她是Haskell新手的一種方式。 @leftaroundabout – yfan

嗯。一方面，我不同意 - Haskell的構建方式使得高階函數特別易於使用，並且它們往往比顯式遞歸更清晰，更易於重構等。 OTOH，在某些時候掌握遞歸方法是不可避免的，甚至可能比褶皺更簡單。至少[Chakravarty＆Keller建議在高級解決方案之前教授遞歸]（http://www.cse.unsw.edu.au/~chak/papers/teaching-prgm.ps.gz），所以...好的 - 同意+1。 – leftaroundabout

Prelude>：m + Data.List
Prelude Data.List>：m + Data.Function
Prelude Data.List Data.Function> minimumBy（compare`on`length）[[1,2,9]， [3,4]，[1,2,3,5]
[3,4]

它是如何工作 - 好，minimum是相當明顯的。但是我們不想通過默認的詞典排序來比較數字列表，而是要指定比較哪個屬性 - 即長度。 compare`on`ᴘʀᴏᴘᴇʀᴛʏ是一個簡單記憶一般伎倆要做到這一點，它使用

Data.Function.on :: (b->b->c) -> (a->b) -> a->a->c 
compare :: Ord a => a -> a -> Ordering

所以(compare`on`)是Ord b => (a->b) -> a->a->Ordering，即我們得到一個比較函數用於任何數據類型，如果我們可以提供的是產生一個可比較的特性功能。在我們的情況下，這是length。

最後，我們需要使用該排序來實際選擇最小元素。執行技巧is Data.List.minimumBy的功能。

注意，該解決方案是不是真的有效的：它將應用length更多，一旦到每個列表。你不應該用它來找到成千上萬的最短列表，每個列表都有數百個元素。當然存在更好的算法，但它們不那麼簡單。

來源

2013-10-26 14:29:59 leftaroundabout

您也可以使用'Data.Ord'中的'比較'功能。然後你可以做'minimumBy（比較長度）[[1,2,9]，[3,4]，[1,2,3,5]]'。這也幾乎讀爲純英文，這很好。 – bheklilr

好點，那就是那種規範。儘管我認爲「通過比較長度最小化」或許更接近普通英語而不是「通過比較長度最小化」，而且它當然更普遍（例如''nubBy（（==）\'長度）'' ）。 – leftaroundabout

我想展開@leftaroundabout提供的解決方案。

Prelude Data.List Data.Function> minimumBy (compare `on` (map . const $ 1)) [[1..],[5..11],[3,4]]

不像原來的解決方案，這一個絕對適用於無限列表。

來源

2013-10-27 10:15:49

不錯！你可以縮短地圖。 const $ 1≡map $ const 1'，也使IMO更清晰。甚至更好，map $ const（）'。 – leftaroundabout

首先您需要比較數據。奧德

import Data.Ord

然後給minimumBy比較功能，通過比較長

minimumBy (comparing (length)) [[1,2,9],[3,4],[1,2,3,5]]

來源

2013-10-31 04:54:15

如何獲得的最短名單列表在Haskell

回答

相關問題