Two Proposals

[George Giorgidze]

Thanks to all of you for providing feedback on my proposal and for providing alternatives.

In this email, I will try to collect all proposals and give pros and cons for each of those (although I will try to provide a good argumentation, some of them might be subjective).

Inspired by Simon's and Roman's suggestions I will introduce one more proposal, I am afraid.

Proposal (1): my original proposal

Pros:
* Simple and straightforward generalisation similar to fromInteger and fromString.

* Works with arithmetic sequences as well (i.e., for sequences like [1 .. 10], [x .. z], ['a' .. 'z']). Sequences will be desugared as defined in the Haskell standard and the proposed extension would just add the fromList function.

Cons:
* Performance. I share Roman's concerns. What we are overloading here is somewhat different from integer and string literals. Namely, what I was referring as list literals may feature expressions (e.g., a variable bound elsewhere as in f x = [x,x]) and hence may not be evaluated only once. Maybe I should have called it "list notation" and not "list literals". This proposal would result into runtime overheads associated with conversion of lists.

* Programmers may provide partial instances failing at runtime.

(BTW. I agree that FromList is much better name than IsList).


Proposal (2) by Yitz (with improvements suggested by Gábor)
Pros:
* Allows partial instances to fail at compile time
* Allows writing of instances that convert lists at compile time

Cons:
* Consensus is emerging that people do not want to unnecessarily tie the lightweight extension of the list notation overloading to the heavyweight extension of Template Haskell.
* Not clear how to implement this and what would be the impact on quality of error messages.

(The first point is subjective, the second point can be addressed but at this stage I do not know how).


Proposal (3) by Roman: the Cons class

Pros:
* Addresses the runtime conversion issue

Cons:
* Does not support arithmetic sequences (this can be addressed, see below)


Proposal (4) by Simon: avoid classes and desugar to return and mappend
Pros:
* Addresses the runtime conversion issue
* Does not introduce new type classes (at least for the list notation)

Cons:
* Unnecessarily ties the list notation to the concept of monad.
* Does not support arithmetic sequences (this can be addressed, see below)


Proposal (5): one more proposal from me (I am afraid) addressing shortcomings of Proposal (3) and Proposal (4).

Here is the first attempt to generalise Proposal (4):

class Functor f => Pointed f where
  point :: a -> f a

with the following (free) pointed law guaranteed by parametricity:

fmap f . point = point . f

Now the list notation can be desugared as follows:

[] = mempty
[x,y,z] = point x `mappend` point y `mappend` point z

Now this will work for any pointed function that is also a monoid (much larger class of structures than monads that are also monoids). However, Map and Text examples from my original proposal are still ruled out.

The following two classes provide as much flexibility as Proposal (1) but avoid going through lists at runtime.

class Singleton l where
  type Elem l
  singleton :: Elem l -> l

Now the list notation can be desugarred as follows:

[] = mempty
[x,y,z] = singleton x `mappend` singleton y `mappend` singleton z

Also the following class can be used to desugar arithmetic sequences:

class Enum a => GenericEnum f a where
  genericEnumFrom        :: a -> f a
  genericEnumFromThen    :: a -> a -> f a
  genericEnumFromTo      :: a -> a -> f a
  genericEnumFromThenTo  :: a -> a -> a -> f a

as follows:

[ x.. ]	=	genericEnumFrom x
[ x,y.. ]	=	genericEnumFromThen x y
[ x..y ]	=	genericEnumFromTo x y
[ x,y..z ]	=	genericEnumFromThenTo x y z

To summarise:
* Proposal (5) is slightly more involved one compared to Proposal (1). 
* Proposal (5) avoids going through lists at runtime and is as flexible as Proposal (1).

For me both options are acceptable. But it seems Proposal (5) should be more suitable for DPH folks and other applications (other parallel arrays, e.g., GPU and distributed arrays) where going through lists at runtime is not an option for performance reasons.

OK, any thoughts on Proposal (1) vs. Proposal (5)?

Of course if no consensus is reached we should not implement any of those. Having said that, the reason I like this extension is that it has a potential to subsume and potentially displace two GHC extensions (list literal overloading and the DPH array notation) in future. This rarely happens these days :).

Cheers, George

P.S. Lennart, asked about defaulting rules and backwards compatibility. Let us keep this in mind and comeback to it after we decide on how to overload the list notation and arithmetic sequences in the first place.