2011-04-20 13 views
10

(sin importancia fondo info/motivación)Expresando cadena larga de composiciones en Haskell

I estaba ejecutando una versión diferente de nub, inspirado por el Yesod book's discouragement de usarlo.

map head . group . sort es más eficiente que una llamada a nub. Sin embargo, en nuestro caso, el orden es importante ...

Así que comencé a escribir un "mejor" como la versión sin importancia. Y terminé con esto:

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) 

Esto sin duda hace un montón de trabajo extra, pero debe ser O (n log n) en lugar de O del nudo originales (n). Pero eso está fuera del punto. El problema es es tan largo! Realmente no es tan complicado, pero es largo (y soy una de esas personas que odian ir más allá de 80 columnas, o barras de desplazamiento horizontales en bloques de código StackOverflow).

(la pregunta)

¿Cuáles son mejores formas en Haskell para expresar cadenas largas de la composición de funciones tales como esto?

+4

Tres cosas importantes a tener en cuenta. 'nub' solo tiene una restricción' Eq a', y su versión tiene una restricción 'Ord a'. 'nub' funciona en listas infinitas, su versión no. Además, el peor caso de 'nub' puede ser peor que tu código, pero su mejor caso es mejor que tu código. La diferencia más significativa es la restricción 'Ord a'. Si permite eso, puede escribir algo más complicado que sea O (n log n) el peor de los casos, casi tan bueno como 'nub' en el mejor de los casos, y que trabaje en listas infinitas. Pero implica estructuras de datos sin lista. – Carl

Respuesta

16

romper la línea, y el uso de la disposición:

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

ancho de línea se resuelve fácilmente :)

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

pero apenas estoy acostumbrado a leer la composición de derecha a izquierda. De arriba a abajo es un poco demasiado. (.) Flecha o (>>>) = flip parece más agradable para mí, pero no tengo ni idea de si sería idiomática

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

'(>>>)' es algo unidiomático, pero se define en la biblioteca 'base': http://hackage.haskell.org/packages/archive/base/latest/doc/html/Control-Category.html# v: -62--62--62- –

+7

¿Por qué las llaves? – Peaker

Cuestiones relacionadas