Llaisdy

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.

1. Responses
   1. Quoted
   2. Standardised
2. Discussion
   1. $
   2. (\x -> (f x))
   3. .
   4. &&& and id
3. And the winner is, …

[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)

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

[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 $

[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

[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.

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