## decorate-sort-undecorate in Haskell — Advanced!

### Saturday, 11th July, 2009

Last in the (unplanned!) series on decorate-sort-undecorate in Haskell, this post reports on the Further Work necessary after the reponses to my initial query on haskell-beginners.

I received many helpful responses, many of which used Haskell language features which were new to me. Here I summarise them and then give a description of the new elements.

**Responses**

*Quoted*[1] http://www.haskell.org/pipermail/beginners/2009-June/001867.html

From http://www.haskell.org/haskellwiki/Blow_your_mind :

`map snd . sortBy (comparing fst) . map (length &&& id)`

Ivan wrote:

> dsuSort decFunc a = map snd (sort (zip (map decFunc a) a))more general:

`dsuSort decFun a = map snd . sortBy (comparing fst) $ zip (map decFun a) a`

[2] http://www.haskell.org/pipermail/beginners/2009-June/001874.html

http://www.haskell.org/pipermail/beginners/2009-June/001876.html

http://www.haskell.org/pipermail/beginners/2009-June/001881.html

In Haskell it’s usually expressed with the decoration in a tuple such that the default sort can be used:

`map snd . sort . map (\x -> (decorate x,x))`

Fancier versions use arrows to make the decorate part cleaner:

`map snd . sort . map (decorate &&& id)`

[3] http://www.haskell.org/pipermail/beginners/2009-June/001876.html

`map snd . sortBy (comparing fst) $ map (\l -> (length l, l)) lists`

with some nice profiling:

Prelude> :set +s Prelude> let lens :: [Int]; lens = [(k^2+3*k-2) `mod` 5431 | k let lists = map (flip replicate ()) lens (0.00 secs, 609084 bytes) Prelude> :m +Data.List Prelude Data.List> :m +Data.Ord Prelude Data.List Data.Ord> let srtl1 = sortBy (comparing length) lists (0.00 secs, 0 bytes) Prelude Data.List Data.Ord> let srtl2 = map snd . sortBy (comparing fst) $ map (\l -> (length l, l)) lists (0.02 secs, 5975640 bytes) Prelude Data.List Data.Ord> length (srtl2 !! 420) 4471 (0.19 secs, 37089168 bytes) Prelude Data.List Data.Ord> length (srtl1 !! 420) 4471 (1.09 secs, 542788 bytes)

*Standardised*The elements new to me were: `.`

, `$`

, `\`

, `&&&`

, `id`

. The difference between `sort`

and `sortBy (comparing fst)`

I've dealt with already. I've made the suggested functions as similar as possible in order to focus on the new elements. All these functions have the same type signature, which I've given just once to improve readibility:

import Data.List -- for sortBy import Data.Ord -- for comparing import Control.Arrow -- for &&& a1 = [[9],[1,1,1,1,1],[2,2,2]] a2 = ["bb", "b", "a", "c", "aa","cc"] dsu1, dsu2, dsu2a, dsu3, dsu3a :: (Ord a) => (a1 -> a) -> [a1] -> [a1] -- see comment 1 dsu1 decFunc xs = map snd . sortBy (comparing fst) $ zip (map decFunc xs) xs dsu2 decFunc = map snd . sortBy (comparing fst) . map (\x -> (decFunc x,x)) dsu2a decFunc xs = map snd . sortBy (comparing fst) . map (\x -> (decFunc x,x)) $ xs dsu3 decFunc = map snd . sortBy (comparing fst) . map (decFunc &&& id) dsu3a decFunc xs = map snd . sortBy (comparing fst) . map (decFunc &&& id) $ xs

**Discussion**

*$*[not in the Real World Haskell index]

$ is an application operator, replacing parentheses around its right-hand side. The following are equivalent:

ds3 xs = sort $ map func xs ds3a xs = sort ( map func xs )

Learn you a Haskell provides a good example and a good quote:

f g z x = ((f g) z) x f $ g $ z x = f (g (z x))

… apart from getting rid of parentheses, $ means that function application can be treated just like another function. That way, we can, for instance, map function application over a list of functions.

ghci> map ($ 3) [(4+), (10*), (^2), sqrt] [7.0,30.0,9.0,1.7320508075688772]

See also:

Haskell 98 Report :: 6.2 Strict Evaluation

Learn you a haskell :: Higher order functions::Function application with $

*(\x -> (f x))*[RWH ch4p99 Anonymous (lambda) functions]

The backslash is a lambda, so:

`(\x -> (f x))`

is the same as the python:

`lambda x: f(x)`

See also:

Learn you a haskell :: Higher order functions :: Lambdas

*.*[RWH ch4p77 Code Reuse Through Composition]

`.`

is an infix function which unites the two functions on either side of it into a composite function, this is called function composition, so:

`(f . g) x = (f (g x))`

Learn you a Haskell has a really excellent explanation and discussion:

Learn you a haskell :: Higher order functions :: Function composition

*&&& and id*[neither is covered in Real World Haskell]

`id`

is the identity function and returns its argument.

`&&&`

, according to Haskell :: Functional Programming with Types, is “the final robot in the Arrow class”. See also the Haskell library documentation for Control.Arrow. I think I’ll come back to `&&&`

later.

**And the winner is, …**

dsu3 & dsu3a are out of the running for the moment, with their robots. As this function is not intended primarily to be a combinator in a larger chain of functions, I like the definitions which include all their arguments, so it’s between dsu1 and dsu2a. Lamda seems to be smuggling in a helper function by the back door, but on the other hand I like the way the dollar just separates off the input list. So — for now — I choose dsu2a:

`dsuSortBy :: (Ord a) => (a1 -> a) -> [a1] -> [a1]`

dsuSortBy decFunc xs = map snd . sortBy (comparing fst) . map (\x -> (decFunc x,x)) $ xs

Saturday, 11th July, 2009 at 11:56 am

> All these functions have the same type signature, which I’ve given just once to improve readibility

Note that when several functions have the same type signature and are conceptually related, you may use the following syntax to avoid repeating this signature :

dsu1, dsu2, dsu2a, dsu3, dsu3a :: (Ord a) => (a1 -> a) -> [a1] -> [a1]

Saturday, 11th July, 2009 at 12:51 pm

Dear Jedaï, Thanks! I’ll put that in.