(不重要背景方式/動機)表達的組合物的長鏈在Haskell
我正在執行不同版本的nub
,通過使用它的Yesod book's discouragement啓發。
map head . group . sort
比致電nub
更高效。然而,在我們的情況下,順序很重要...
所以我開始寫一個「更好的」凸起類似的訂單不重要的版本。我結束了與此:
mynub = unsort . map head . groupBy (\x y -> fst x == fst y) . sortBy (comparing fst) . rememberPosition
rememberPosition = flip zip [0..]
unsort = map fst . sortBy (comparing snd)
這肯定做了很多額外的工作,但它應該是爲O(n log n)的,而不是原來的結點的爲O(n )。但那不是重點。問題是,它太長了!它並沒有那麼複雜,但它很長(我是那些討厭在80列以上或StackOverflow代碼塊中的水平滾動條之上的人)之一。
(問題)
什麼是表達功能組成的長鏈,如這在Haskell更好的方法?
三件重要的事情要注意。 'nub'只有'Eq a'約束,而你的版本有'Ord a'約束。 'nub'在無限列表上工作,你的版本沒有。另外,'nub'的最壞情況可能比你的代碼差,但最好的情況比你的代碼更好。最重要的區別是'Ord a'約束。如果你允許的話,你可以寫一些更復雜的東西,最壞的情況是O(n log n),在最好的情況下幾乎和'nub'一樣好,並且在無限列表上工作。但它涉及非列表數據結構。 – Carl 2011-04-20 18:02:42