2011-04-20 48 views
10

(不重要背景方式/動機)表達的組合物的長鏈在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更好的方法?

+4

三件重要的事情要注意。 'nub'只有'Eq a'約束,而你的版本有'Ord a'約束。 'nub'在無限列表上工作,你的版本沒有。另外,'nub'的最壞情況可能比你的代碼差,但最好的情況比你的代碼更好。最重要的區別是'Ord a'約束。如果你允許的話,你可以寫一些更復雜的東西,最壞的情況是O(n log n),在最好的情況下幾乎和'nub'一樣好,並且在無限列表上工作。但它涉及非列表數據結構。 – Carl 2011-04-20 18:02:42

回答

16

向上突破線,並使用佈局:

mynub = unsort 
     . map head 
     . groupBy ((==) `on` fst) 
     . sortBy (comparing fst) 
     . rememberPosition 
8

線寬很容易解決:)

> mynub = { unsort 
>   . map head 
>   . groupBy (\x y -> fst x == fst y) 
>   . sortBy (comparing fst) 
>   . rememberPosition 
>   } 

,但我幾乎沒有使用閱讀向左向右組成。從上到下有點多。 (。) 箭頭或(>>>)=翻蓋看起來更好給我,但我不知道它是否會成爲習慣

> mynub = { rememberPosition 
>  >>> sortBy (comparing fst) 
>  >>> groupBy (\x y -> fst x == fst y) 
>  >>> map head 
>  >>> unsort 
>   } 
+1

'(>>>)'有點單一,但在'base'庫中定義:http://hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Category.html# v:-62--62--62- – 2011-04-20 04:19:28

+7

爲什麼使用大括號? – Peaker 2011-04-21 12:01:18