Comprehensions with ‘Order by’ and ‘Group by’

Comprehensive Comprehensions, Phil Wadler and Simon Peyton Jones

"The new constructs proposed here are more general than the constructs in the other languages, because they work with any function of a given type, rather than being limited to specific functions. Parametricity of these functions plays an important role in ensuring the semantics of such constructs is independent of particular details of how tuples of bindings are represented."

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

It seems strange to me to

It seems strange to me to encourage people to use the 'Order by' keyword for other things than sorting, just becourse the type system allows it.

Type of groupWith

They give the type
(a -> b) -> [a] -> [[a]]
I've always imagined the type as
(a -> k) -> [a] -> Map k [a]
because you always need the value you grouped by later.

With the type in the paper you have to reconstruct the grouping value, which might not always be as simple as the dept.

Actually, the same goes for sorting, so maybe the following functions might work best:
by :: (a -> k) -> [a] -> [(k, a)]
sortByFirst :: [(k, a)] -> [(k, a)]
groupByFirst :: [(k, a)] -> Map k [a]

But it is harder to merge this with list comprehension syntax.

iterate

What does iterate do in Haskell, it is used in at least one example and probably in the LIMIT equivalent (order using take).

iterate f x = x:iterate f (f x)


iterate f x = x:iterate f (f x)

e.g.

iterate (1+) 0 = [0..] = [0,1,2,3,4,...

Unconstructive Criticism

I really, really hope that this never gets into Haskell. It looks ugly. It's too "magical" for my tastes (and thus, I see it being confusing for many in all but trivial cases). Along those lines, I see it easily abused (much more significant than merely abusable.) I feel it would lead people away from many more natural solutions (though I will readily admit that it may often be a natural solution itself.) It's too inflexible, I'd rather see a new library of combinators or some such (which I also feel would be more Haskelly/natural.) I like ending my comments with parenthetical remarks (as you can see.)

Use records

Their examples in chapter 2 can be done much easier if you use records.

map (\(name,salary) -> name)
(sortWith (\(name,salary) -> salary)
[ (name,salary)
| (name, salary, dept) <- employees
, salary < 50 ])

becomes

map name (sortWith salary [ e | e <- employees, salary(e) < 50 ])

and

let
depts =
nub [ dept
| (name,dept,salary) <- employees ]
in
[ (dept,
sum [ salary
| (name,dept’,salary) <- employees
, dept == dept’])
| dept <- depts ]

becomes

[(dept (head group), sum (map salary group)) | group <- groupWith dept employees]

Is there a better way?

To me, the major benefit of comprehensions is that they enable us to express frequent programming patterns by referring to simple things with variables, rather than combining higher-order functions.

Philip and Simon's new extensions further enable us to express frequent programming patterns pointfully. Still, this scheme feels a bit arbitrary. I wonder if there is a nicer generalization, perhaps less directly mapped to SQL.

Sjoerd gets to the core of the issue, that records make for cleaner comprehensions than pattern-matched algebraic data types. With idiomatic Haskell ADTs, you frequently must invent redundent local names for tupled elements in an ADT.

I was secretly hoping monad comprehensions would...

...come back one day. This extension seems incompatible with monad comprehensions and would dash my hopes that they could ever reappear.

Look at Michael Adams reply

Look at Michael Adams reply in the wiki talkpage.

I may be too late

...to beat this dead thread, but anyway:

We propose an extension to list comprehensions that makes it easy to express the kind of queries one would write in SQL

I do not argue that in practice one often wants to query algebraic data structures. However, I see a slight mismatch between the context of SQL and comprehensions. SQL is used to formulate a proposition about desired result, which is then analysed by optimizer to obtain a query plan (a proof of the proposition, if you like). In order to do something similar in Haskell, one has either (A) to be able to inspect arbitrary code by optimizer, or (B) to give up embedding Haskell code into query DSL (hi, Philippa!), or (C) to strike some middle ground and only allow optimizer/plan builder built into the compiler (the way usually proposed for comprehensions and extensions to them).
Plan C sounds limiting and totalitarian, plan B will require to build DSL from scratch without reusing wealth of language features from Haskell, plan A - well, does Template Haskell allows something like this?

There's another middle

There's another middle ground, which is to treat anything pure as a black box but otherwise do a conventional analysis - it's easy enough to build the corresponding AST if you've got GADTs, for example. This leaves you unable to spot expensive predicates but you can still support hints from the user.