Michael Snoyman | 23 Sep 06:06 2012

Call for discussion: OverloadedLists extension

(Prettier formatting available at: https://gist.github.com/3761252)

Many of us use the OverloadedStrings language extension on a regular
basis. It provides the ability to keep the ease-of-use of string
literal syntax, while getting the performance and correctness
advantages of specialized datatypes like ByteString and Text. I think
we can get the same kind of benefit by allowing another literal syntax
to be overloaded, namely lists.

## Overly simple approach

The simplest example I can think of is allowing easier usage of Vector:

    [1, 2, 3] :: Vector Int

In order to allow this, we could use a typeclass approach similar to
how OverloadedStrings works:

    class IsList a where
        fromList :: [b] -> a b
    instance IsList Vector where
        fromList = V.fromList
    foo :: Vector Int
    foo = fromList [1, 2, 3]

## Flaws

However, such a proposal does not allow for constraints, e.g.:

    instance IsList Set where
(Continue reading)

Heinrich Apfelmus | 23 Sep 10:51 2012
Picon

Re: Call for discussion: OverloadedLists extension

Michael Snoyman wrote:
> (Prettier formatting available at: https://gist.github.com/3761252)
> 
> Many of us use the OverloadedStrings language extension on a regular
> basis. It provides the ability to keep the ease-of-use of string
> literal syntax, while getting the performance and correctness
> advantages of specialized datatypes like ByteString and Text. I think
> we can get the same kind of benefit by allowing another literal syntax
> to be overloaded, namely lists.

Actually, I am already somewhat reserved about the  OverloadedStrings 
proposal.

The core point of the OverloadedSomething extensions is that they 
address a syntactic issue, namely that we can write

   "example"

instead of

   (pack "example")

The extension does this by making the literal polymorphic.

Unfortunately, making literals polymorphic does not always achieve the 
desired effect of reducing syntax. In fact, they can instead increase 
syntax! In other words, I would like to point out that there is a 
trade-off involved: is it worth introducing a small syntactic reduction 
at the cost of both a small additional conceptual complexity and some 
syntactic enlargement elsewhere?
(Continue reading)

Michael Snoyman | 23 Sep 13:49 2012

Re: Call for discussion: OverloadedLists extension

On Sun, Sep 23, 2012 at 10:51 AM, Heinrich Apfelmus
<apfelmus <at> quantentunnel.de> wrote:
> Michael Snoyman wrote:
>>
>> (Prettier formatting available at: https://gist.github.com/3761252)
>>
>> Many of us use the OverloadedStrings language extension on a regular
>> basis. It provides the ability to keep the ease-of-use of string
>> literal syntax, while getting the performance and correctness
>> advantages of specialized datatypes like ByteString and Text. I think
>> we can get the same kind of benefit by allowing another literal syntax
>> to be overloaded, namely lists.
>
>
> Actually, I am already somewhat reserved about the  OverloadedStrings
> proposal.
>
> The core point of the OverloadedSomething extensions is that they address a
> syntactic issue, namely that we can write
>
>   "example"
>
> instead of
>
>   (pack "example")
>
> The extension does this by making the literal polymorphic.
>
> Unfortunately, making literals polymorphic does not always achieve the
> desired effect of reducing syntax. In fact, they can instead increase
(Continue reading)

Chris Smith | 23 Sep 17:51 2012
Picon

Re: Call for discussion: OverloadedLists extension

Michael Snoyman <michael <at> snoyman.com> wrote:
> That said, it would be great to come up with ways to mitigate the
> downsides of unbounded polymorphism that you bring up. One idea I've
> seen mentioned before is to modify these extension so that they target
> a specific instance of IsString/IsList, e.g.:
>
> {-# STRING_LITERALS_AS Text #-}
>
> "foo" ==> (fromString "foo" :: Text)

That makes sense for OverloadedStrings, but probably not for
OverloadedLists or overloaded numbers... String literals have the
benefit that there's one type that you probably always really meant.
The cases where you really wanted [Char] or ByteString are rare.  On
the other hand, there really is no sensible "I always want this"
answer for lists or numbers.  It seems like a kludge to do it
per-module if each module is going to give different answers most of
the time.

--

-- 
Chris
Michael Snoyman | 23 Sep 17:59 2012

Re: Call for discussion: OverloadedLists extension

On Sun, Sep 23, 2012 at 5:51 PM, Chris Smith <cdsmith <at> gmail.com> wrote:
> Michael Snoyman <michael <at> snoyman.com> wrote:
>> That said, it would be great to come up with ways to mitigate the
>> downsides of unbounded polymorphism that you bring up. One idea I've
>> seen mentioned before is to modify these extension so that they target
>> a specific instance of IsString/IsList, e.g.:
>>
>> {-# STRING_LITERALS_AS Text #-}
>>
>> "foo" ==> (fromString "foo" :: Text)
>
> That makes sense for OverloadedStrings, but probably not for
> OverloadedLists or overloaded numbers... String literals have the
> benefit that there's one type that you probably always really meant.
> The cases where you really wanted [Char] or ByteString are rare.  On
> the other hand, there really is no sensible "I always want this"
> answer for lists or numbers.  It seems like a kludge to do it
> per-module if each module is going to give different answers most of
> the time.
>
> --
> Chris

Note that I wasn't necessarily advocating such a pragma. And a lot of
my XML code actually *does* use two IsString instances at the same
time, e.g.:

    Element ("img" :: Name) (singleton ("href" :: Name) ("foo.png" ::
Text)) [NodeComment ("No content inside an image" :: Text)]

(Continue reading)

Brandon Allbery | 23 Sep 18:09 2012
Picon

Re: Call for discussion: OverloadedLists extension

Maybe what's needed is a way to mutate the lexer by adding new kinds of literals; Unicode offers a number of paired brackets and quote-like characters.  Although that is likely to get into readability issues especially if you do have a mixture of [Char], ByteString, and Text for some reason.  (Map vs. [] is probably easy enough but add another one or two in and the sam problem rears its head quickly.)

--
brandon s allbery                                      allbery.b <at> gmail.com
wandering unix systems administrator (available)     (412) 475-9364 vm/sms

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Heinrich Apfelmus | 25 Sep 18:21 2012
Picon

Re: Call for discussion: OverloadedLists extension

Michael Snoyman wrote:
> 
> Note that I wasn't necessarily advocating such a pragma. And a lot of
> my XML code actually *does* use two IsString instances at the same
> time, e.g.:
> 
>     Element ("img" :: Name) (singleton ("href" :: Name) ("foo.png" ::
> Text)) [NodeComment ("No content inside an image" :: Text)]

In this particular case, would it make sense to use smart constructors 
instead?

The idea is that you can put the polymorphism in two places: either make 
the "output" polymorphic, or make the "input" polymorphic. The latter 
would correspond to a type

    element :: (IsString name, IsString s, IsMap map)
        => name -> map name s -> [Element]
    element name map = Element (toName name) (toMap map)

One benefit would be that the function will accept any list as a map, 
not just list literals.

Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com
Michael Snoyman | 26 Sep 23:12 2012

Re: Call for discussion: OverloadedLists extension

On Tue, Sep 25, 2012 at 6:21 PM, Heinrich Apfelmus
<apfelmus <at> quantentunnel.de> wrote:
> Michael Snoyman wrote:
>>
>>
>> Note that I wasn't necessarily advocating such a pragma. And a lot of
>> my XML code actually *does* use two IsString instances at the same
>> time, e.g.:
>>
>>     Element ("img" :: Name) (singleton ("href" :: Name) ("foo.png" ::
>> Text)) [NodeComment ("No content inside an image" :: Text)]
>
>
> In this particular case, would it make sense to use smart constructors
> instead?
>
> The idea is that you can put the polymorphism in two places: either make the
> "output" polymorphic, or make the "input" polymorphic. The latter would
> correspond to a type
>
>    element :: (IsString name, IsString s, IsMap map)
>        => name -> map name s -> [Element]
>    element name map = Element (toName name) (toMap map)
>
> One benefit would be that the function will accept any list as a map, not
> just list literals.

Just to clarify: this would be a *replacement* for OverloadedStrings
usage, right? If used in conjunction with OverloadedStrings, we'd run
into the too-much-polymorphism issue you describe in your initial
email in this thread, since `element "foo'` would become `element
(fromString "foo")` which would become `Element ((toName . fromString)
"foo")`, and `toName . fromString` makes it ambiguous what the
intermediate data type is.

Assuming this is meant are a replacement, I see two downsides.
Firstly, this would work for construction, but not for deconstruction.
Currently, I can do something like:

handleList :: Element -> Element
handleList (Element "ul" _ _) = ...
handleList e = e

The other is that we've only solved one specific case by providing a
replacement function. In order to keep code just as terse as it is
now, we'd have to provide a whole slew of replacement functions. For
example, consider the code:

handleList (Element "ul" attrs _) = case Map.lookup "class" attrs of ....

If we get rid of OverloadedStrings, then we need to either provide a
replacement `lookup` function which performs the conversion from
String to Name, or change all lookup calls to explicitly perform that
lookup.

Michael
Heinrich Apfelmus | 28 Sep 15:11 2012
Picon

Re: Call for discussion: OverloadedLists extension

Michael Snoyman wrote:
> Heinrich Apfelmus wrote:
>> Michael Snoyman wrote:
>>>
>>> Note that I wasn't necessarily advocating such a pragma. And a lot of
>>> my XML code actually *does* use two IsString instances at the same
>>> time, e.g.:
>>>
>>>     Element ("img" :: Name) (singleton ("href" :: Name) ("foo.png" ::
>>> Text)) [NodeComment ("No content inside an image" :: Text)]
>>
>> In this particular case, would it make sense to use smart constructors
>> instead?
>>
>> The idea is that you can put the polymorphism in two places: either make the
>> "output" polymorphic, or make the "input" polymorphic. The latter would
>> correspond to a type
>>
>>    element :: (IsString name, IsString s, IsMap map)
>>        => name -> map name s -> [Element]
>>    element name map = Element (toName name) (toMap map)
>>
>> One benefit would be that the function will accept any list as a map, not
>> just list literals.
> 
> Just to clarify: this would be a *replacement* for OverloadedStrings
> usage, right? If used in conjunction with OverloadedStrings, we'd run
> into the too-much-polymorphism issue you describe in your initial
> email in this thread, since `element "foo'` would become `element
> (fromString "foo")` which would become `Element ((toName . fromString)
> "foo")`, and `toName . fromString` makes it ambiguous what the
> intermediate data type is.

Yes, indeed, it would be an alternative approach.

> Assuming this is meant are a replacement, I see two downsides.
> Firstly, this would work for construction, but not for deconstruction.
> Currently, I can do something like:
> 
> handleList :: Element -> Element
> handleList (Element "ul" _ _) = ...
> handleList e = e

Good point. On the other hand, there is another extension, ViewPatterns, 
which solves the problem of pattern matching on abstract data types in 
full generality, allowing things like

   handleList (viewAsStrings -> Element "ul" _ _) = ...

While more intrusive, the benefit of this extension is that a lot of 
other code could likely become neater as well.

> The other is that we've only solved one specific case by providing a
> replacement function. In order to keep code just as terse as it is
> now, we'd have to provide a whole slew of replacement functions. For
> example, consider the code:
> 
> handleList (Element "ul" attrs _) = case Map.lookup "class" attrs of ....
> 
> If we get rid of OverloadedStrings, then we need to either provide a
> replacement `lookup` function which performs the conversion from
> String to Name, or change all lookup calls to explicitly perform that
> lookup.

Ah, I see. Since the  Name  type is abstract, I feel it's alright to add 
the polymorphism to functions like  element , but  Map.lookup  is indeed 
a problem.

One option would be to make a new type  NameMap  specifically for  Name 
  as key, but that seems a little overkill. The other option is to bite 
the bullet and add the conversion by hand  Map.lookup (name "class") .

In this case, I think I would go with a lightweight first option and 
simply give a new name to the  Map.lookup  combination and use the 
opportunity to sneak in some polymorphism.

    getAttribute name = Map.lookup (toText name)

In my experience, turning all data types into abstractions works quite 
well, but I can see that you can't avoid an annoying conversion if you 
just want to use a quick  Map.lookup .

Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com
Roman Cheplyaka | 23 Sep 17:34 2012

Re: Call for discussion: OverloadedLists extension

* Heinrich Apfelmus <apfelmus <at> quantentunnel.de> [2012-09-23 10:51:26+0200]
> Unfortunately, making literals polymorphic does not always achieve
> the desired effect of reducing syntax. In fact, they can instead
> increase syntax! In other words, I would like to point out that there
> is a trade-off involved: is it worth introducing a small syntactic
> reduction at the cost of both a small additional conceptual
> complexity and some syntactic enlargement elsewhere?

Can't you just disable the extension when you realise that it
makes your life harder?

Roman
Heinrich Apfelmus | 24 Sep 15:57 2012
Picon

Re: Call for discussion: OverloadedLists extension

Roman Cheplyaka wrote:
> * Heinrich Apfelmus <apfelmus <at> quantentunnel.de> [2012-09-23 10:51:26+0200]
>> Unfortunately, making literals polymorphic does not always achieve
>> the desired effect of reducing syntax. In fact, they can instead
>> increase syntax! In other words, I would like to point out that there
>> is a trade-off involved: is it worth introducing a small syntactic
>> reduction at the cost of both a small additional conceptual
>> complexity and some syntactic enlargement elsewhere?
> 
> Can't you just disable the extension when you realise that it
> makes your life harder?

I thought so, too, but there is actually a "social" catch.

Namely, a library/DSL can be designed with that extension in mind and 
advocate its use. The [scotty][] library is an example for this.

In particular, the  RoutePattern  type is made an instance of  IsString 
  and the example code uses it extensively. If I want to disable the 
extension, I have to translate the example code first. When learning a 
library for the first time, this can be rather confusing.

   [scotty]: http://hackage.haskell.org/package/scotty

Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com
George Giorgidze | 24 Sep 14:53 2012
Picon

Re: Call for discussion: OverloadedLists extension

Hi Michael,

Here at the University of Tübingen, I am co-supervising (together with
Jeroen Weijers) a student project implementing the OverloadedLists
extension for GHC. Achim Krause is the student who is working on the
project. We took into consideration earlier discussions on this topic
[1,2] before embarking on the project.

Achim has worked on two approaches.

The first approach is very simple, both from the user's and the
extension implementor's perspective (it follows the implementation of
OverloadedStrings closely) and typechecks and desugars lists like

[] ; [x,y,z] ;  ['a' .. 'z'] ;

as

fromList [] ;  fromList [x,y,z] ; fromList ['a' .. 'z'] ;

where fromList is whatever is in scope with that name. That said, we
do provide the FromList type class that can be used to overload
fromList. In the following I give the definition of the class, as well
as, example instances:

class FromList l where
  type Item l
  fromList :: [Item l] -> l

instance FromList [a] where
  type Item [a] = a
  fromList = id

instance (Ord a) => FromList (Set a) where
  type Item (Set a) = a
  fromList = Set.fromList

instance (Ord k) => FromList (Map k v) where
  type Item (Map k v) = (k,v)
  fromList = Map.fromList

instance FromList (IntMap v) where
  type Item (IntMap v) = (Int,v)
  fromList = IntMap.fromList

instance FromList Text where
  type Item Text = Char
  fromList = Text.pack

This approach has already been implemented by Achim as patch against GHC head.

This approach is very simple, but can be inefficient as it may result
into unnecessary construction of lists at runtime. This can be a
serious issue when constructing large structures from arithmetic
sequences (e.g., from the [ .. ] notation) or when using non-literal
expressions (e.g., variables) inside the square brackets.

Our second approach to OverloadedLists is to avoid the construction of
lists altogether. By typechecking and desugaring lists like

[] ; [x,y,z] ;  ['a' .. 'z'] ;

as

mempty ; singleton x `mappend` singleton y `mappend` singleton z ;
genericEnumFromTo 'a' 'z' ;

We  provide the Singleton and GenericEnum type classes for overloading
singleton and genericEnum(..) functions. In the following, I give the
definitions of the classes, as well as, example instances:

-- Singleton class

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

-- Singleton instances

instance Singleton [a] where
  type SingletonItem [a] = a
  singleton a = [a]

instance (Ord a) => Singleton (Set a) where
  type SingletonItem (Set a) = a
  singleton = Set.singleton

instance (Ord k) => Singleton (Map k v) where
  type SingletonItem (Map k v) = (k,v)
  singleton (k,v) = Map.singleton k v

instance Singleton (IntMap v) where
  type SingletonItem (IntMap v) = (Int,v)
  singleton (k,v) = IntMap.singleton k v

instance Singleton Text where
  type SingletonItem Text = Char
  singleton = Text.singleton

-- GenericEnum class

class GenericEnum l where
  type EnumItem l
  genericEnumFrom        :: EnumItem l -> l
  genericEnumFromThen    :: EnumItem l -> EnumItem l -> l
  genericEnumFromTo      :: EnumItem l -> EnumItem l -> l
  genericEnumFromThenTo  :: EnumItem l -> EnumItem l -> EnumItem l -> l

-- GenericEnum instances

instance (Enum a) => GenericEnum [a] where
  type EnumItem [a] = a
  genericEnumFrom        = enumFrom
  genericEnumFromThen    = enumFromThen
  genericEnumFromTo      = enumFromTo
  genericEnumFromThenTo  = enumFromThenTo

instance (Ord a,Enum a) => GenericEnum (Set a) where
  type EnumItem (Set a) = a
  genericEnumFrom       a     = Set.fromList (enumFrom a)
  genericEnumFromThen   a b   = Set.fromList (enumFromThen a b)
  genericEnumFromTo     a b   = Set.fromList (enumFromTo a b)
  genericEnumFromThenTo a b c = Set.fromList (enumFromThenTo a b c)

instance (Ord k,Enum (k,v)) => GenericEnum (Map k v) where
  type EnumItem (Map k v) = (k,v)
  genericEnumFrom       a     = Map.fromList (enumFrom a)
  genericEnumFromThen   a b   = Map.fromList (enumFromThen a b)
  genericEnumFromTo     a b   = Map.fromList (enumFromTo a b)
  genericEnumFromThenTo a b c = Map.fromList (enumFromThenTo a b c)

instance (Enum (Int,v)) => GenericEnum (IntMap v) where
  type EnumItem (IntMap v) = (Int,v)
  genericEnumFrom       a     = IntMap.fromList (enumFrom a)
  genericEnumFromThen   a b   = IntMap.fromList (enumFromThen a b)
  genericEnumFromTo     a b   = IntMap.fromList (enumFromTo a b)
  genericEnumFromThenTo a b c = IntMap.fromList (enumFromThenTo a b c)

instance GenericEnum Text where
  type EnumItem Text = Char
  genericEnumFrom       a     = Text.pack (enumFrom a)
  genericEnumFromThen   a b   = Text.pack (enumFromThen a b)
  genericEnumFromTo     a b   = Text.pack (enumFromTo a b)
  genericEnumFromThenTo a b c = Text.pack (enumFromThenTo a b c)

Note that the GenericEnum instances can be implemented more
efficiently, but for now I give simple definitions that go through
lists.

Our second approach avoids the construction of intermediate lists at
runtime and directly constructs the target data structure for which
the list notation is used.

We will release GHC patches for both approaches, meanwhile the
feedback from the community on the approaches that we took would be
very much appreciated. Which one those would you prefer? or would you
suggest a different one.

Note that we intend to make fromList in the first approach and
singleton, genericEnum(..), mempty and mapped rebindable. This means
that the definitions of the type classes that overload this functions
can be easily changed. Having said that, altering the changes that
Achim already made to the GHC source code (including typechecking and
desugaring rules) will be more work and we hope that one of the
approaches that we took will be acceptable for the community.

Cheers, George

[1] http://www.mail-archive.com/glasgow-haskell-users <at> haskell.org/msg20447.html
[2] http://www.mail-archive.com/glasgow-haskell-users <at> haskell.org/msg20518.html

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Michael Snoyman | 24 Sep 15:33 2012

Re: Call for discussion: OverloadedLists extension

On Mon, Sep 24, 2012 at 2:53 PM, George Giorgidze <giorgidze <at> gmail.com> wrote:
> Hi Michael,
>
> Here at the University of Tübingen, I am co-supervising (together with
> Jeroen Weijers) a student project implementing the OverloadedLists
> extension for GHC. Achim Krause is the student who is working on the
> project. We took into consideration earlier discussions on this topic
> [1,2] before embarking on the project.
>
> Achim has worked on two approaches.
>
> The first approach is very simple, both from the user's and the
> extension implementor's perspective (it follows the implementation of
> OverloadedStrings closely) and typechecks and desugars lists like
>
> [] ; [x,y,z] ;  ['a' .. 'z'] ;
>
> as
>
> fromList [] ;  fromList [x,y,z] ; fromList ['a' .. 'z'] ;
>
> where fromList is whatever is in scope with that name. That said, we
> do provide the FromList type class that can be used to overload
> fromList. In the following I give the definition of the class, as well
> as, example instances:
>
> class FromList l where
>   type Item l
>   fromList :: [Item l] -> l
>
> instance FromList [a] where
>   type Item [a] = a
>   fromList = id
>
> instance (Ord a) => FromList (Set a) where
>   type Item (Set a) = a
>   fromList = Set.fromList
>
> instance (Ord k) => FromList (Map k v) where
>   type Item (Map k v) = (k,v)
>   fromList = Map.fromList
>
> instance FromList (IntMap v) where
>   type Item (IntMap v) = (Int,v)
>   fromList = IntMap.fromList
>
> instance FromList Text where
>   type Item Text = Char
>   fromList = Text.pack
>
> This approach has already been implemented by Achim as patch against GHC head.
>
> This approach is very simple, but can be inefficient as it may result
> into unnecessary construction of lists at runtime. This can be a
> serious issue when constructing large structures from arithmetic
> sequences (e.g., from the [ .. ] notation) or when using non-literal
> expressions (e.g., variables) inside the square brackets.
>
> Our second approach to OverloadedLists is to avoid the construction of
> lists altogether. By typechecking and desugaring lists like
>
> [] ; [x,y,z] ;  ['a' .. 'z'] ;
>
> as
>
> mempty ; singleton x `mappend` singleton y `mappend` singleton z ;
> genericEnumFromTo 'a' 'z' ;
>
> We  provide the Singleton and GenericEnum type classes for overloading
> singleton and genericEnum(..) functions. In the following, I give the
> definitions of the classes, as well as, example instances:
>
> -- Singleton class
>
> class Singleton l where
>   type SingletonItem l
>   singleton :: SingletonItem l -> l
>
> -- Singleton instances
>
> instance Singleton [a] where
>   type SingletonItem [a] = a
>   singleton a = [a]
>
> instance (Ord a) => Singleton (Set a) where
>   type SingletonItem (Set a) = a
>   singleton = Set.singleton
>
> instance (Ord k) => Singleton (Map k v) where
>   type SingletonItem (Map k v) = (k,v)
>   singleton (k,v) = Map.singleton k v
>
> instance Singleton (IntMap v) where
>   type SingletonItem (IntMap v) = (Int,v)
>   singleton (k,v) = IntMap.singleton k v
>
> instance Singleton Text where
>   type SingletonItem Text = Char
>   singleton = Text.singleton
>
> -- GenericEnum class
>
> class GenericEnum l where
>   type EnumItem l
>   genericEnumFrom        :: EnumItem l -> l
>   genericEnumFromThen    :: EnumItem l -> EnumItem l -> l
>   genericEnumFromTo      :: EnumItem l -> EnumItem l -> l
>   genericEnumFromThenTo  :: EnumItem l -> EnumItem l -> EnumItem l -> l
>
> -- GenericEnum instances
>
> instance (Enum a) => GenericEnum [a] where
>   type EnumItem [a] = a
>   genericEnumFrom        = enumFrom
>   genericEnumFromThen    = enumFromThen
>   genericEnumFromTo      = enumFromTo
>   genericEnumFromThenTo  = enumFromThenTo
>
> instance (Ord a,Enum a) => GenericEnum (Set a) where
>   type EnumItem (Set a) = a
>   genericEnumFrom       a     = Set.fromList (enumFrom a)
>   genericEnumFromThen   a b   = Set.fromList (enumFromThen a b)
>   genericEnumFromTo     a b   = Set.fromList (enumFromTo a b)
>   genericEnumFromThenTo a b c = Set.fromList (enumFromThenTo a b c)
>
> instance (Ord k,Enum (k,v)) => GenericEnum (Map k v) where
>   type EnumItem (Map k v) = (k,v)
>   genericEnumFrom       a     = Map.fromList (enumFrom a)
>   genericEnumFromThen   a b   = Map.fromList (enumFromThen a b)
>   genericEnumFromTo     a b   = Map.fromList (enumFromTo a b)
>   genericEnumFromThenTo a b c = Map.fromList (enumFromThenTo a b c)
>
> instance (Enum (Int,v)) => GenericEnum (IntMap v) where
>   type EnumItem (IntMap v) = (Int,v)
>   genericEnumFrom       a     = IntMap.fromList (enumFrom a)
>   genericEnumFromThen   a b   = IntMap.fromList (enumFromThen a b)
>   genericEnumFromTo     a b   = IntMap.fromList (enumFromTo a b)
>   genericEnumFromThenTo a b c = IntMap.fromList (enumFromThenTo a b c)
>
> instance GenericEnum Text where
>   type EnumItem Text = Char
>   genericEnumFrom       a     = Text.pack (enumFrom a)
>   genericEnumFromThen   a b   = Text.pack (enumFromThen a b)
>   genericEnumFromTo     a b   = Text.pack (enumFromTo a b)
>   genericEnumFromThenTo a b c = Text.pack (enumFromThenTo a b c)
>
> Note that the GenericEnum instances can be implemented more
> efficiently, but for now I give simple definitions that go through
> lists.
>
> Our second approach avoids the construction of intermediate lists at
> runtime and directly constructs the target data structure for which
> the list notation is used.
>
> We will release GHC patches for both approaches, meanwhile the
> feedback from the community on the approaches that we took would be
> very much appreciated. Which one those would you prefer? or would you
> suggest a different one.
>
> Note that we intend to make fromList in the first approach and
> singleton, genericEnum(..), mempty and mapped rebindable. This means
> that the definitions of the type classes that overload this functions
> can be easily changed. Having said that, altering the changes that
> Achim already made to the GHC source code (including typechecking and
> desugaring rules) will be more work and we hope that one of the
> approaches that we took will be acceptable for the community.
>
> Cheers, George
>
> [1] http://www.mail-archive.com/glasgow-haskell-users <at> haskell.org/msg20447.html
> [2] http://www.mail-archive.com/glasgow-haskell-users <at> haskell.org/msg20518.html

Hi George,

It's very exciting to hear that this work has already been starting,
thank you for letting me know. Your first approach is more inline with
my initial proposal, though that doesn't mean I necessarily prefer it.

I'm certainly interested having a more efficient implementation
available, but I wonder if this second approach isn't a premature
optimization. GHC rewrite rules provide a lot of power in this
department: both ByteString and Text are able to avoid the
intermediate String and build their representations from the buffers
GHC creates. In my own work in conduit, I was able (with some help
from Joachim Breitner[1]) to remove the intermediate list structure,
and I'd be surprised if it's not possible to do the same thing with
calls to `fromList`.

That said, I haven't actually tried implementing any of this in real
code, and it could be that there are serious performance advantages to
the second approach. I'm quite happy with either implementation making
it into GHC.

Michael

[1] http://www.haskell.org/pipermail/haskell-cafe/2012-April/100793.html
Simon Peyton-Jones | 25 Sep 10:01 2012
Picon

Re: Call for discussion: OverloadedLists extension

| Here at the University of Tübingen, I am co-supervising (together with
| Jeroen Weijers) a student project implementing the OverloadedLists
| extension for GHC. Achim Krause is the student who is working on the
| project. We took into consideration earlier discussions on this topic
| [1,2] before embarking on the project.
| 
| Achim has worked on two approaches.

Your second approach is this:

| [x,y,z] 
| 
| as
| 
| singleton x `mappend` singleton y `mappend` singleton z ;

This approach is not good for long literal lists, because you get tons of executable code where the user
thought he was just defining a data  structure.  And long literal lists are an important use-case.

One other possibility is to use a variant of what GHC does for literal strings. Currently
	"foo"
turns into	
	unpackCString "foo"#
where "foo"# is a statically allocate C string, and the "unpackCString" unpacks it lazily.

Maybe we could make a literal [a,b.c] turn into
	unpack [a,b,c]#
where 
	[a,b,c]#
is a statically-allocated vector?  See http://hackage.haskell.org/trac/ghc/ticket/5218, which is
stalled awaiting brain cycles from someone.

I'm maxed out at the moment.  I'd be very happy if you guys were able to make progress; I'm happy to advise.  Open
a ticket, start a wiki page, etc!

Simon

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Sjoerd Visscher | 25 Sep 19:57 2012

Re: Call for discussion: OverloadedLists extension

So, in order not to have to rely on rewrite rules, would it be a good idea to add unpackCString to the IsString class?

import GHC.Base (unpackCString#, Addr#)

class IsString a where
    fromString :: String -> a
    unpackCString :: Addr# -> a
    unpackCString addr = fromString (unpackCString# addr)

For lists something similar could probably be done.

Sjoerd

On Sep 25, 2012, at 10:01 AM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:

> | Here at the University of Tübingen, I am co-supervising (together with
> | Jeroen Weijers) a student project implementing the OverloadedLists
> | extension for GHC. Achim Krause is the student who is working on the
> | project. We took into consideration earlier discussions on this topic
> | [1,2] before embarking on the project.
> | 
> | Achim has worked on two approaches.
> 
> Your second approach is this:
> 
> | [x,y,z] 
> | 
> | as
> | 
> | singleton x `mappend` singleton y `mappend` singleton z ;
> 
> This approach is not good for long literal lists, because you get tons of executable code where the user
thought he was just defining a data  structure.  And long literal lists are an important use-case.
> 
> One other possibility is to use a variant of what GHC does for literal strings. Currently
> 	"foo"
> turns into	
> 	unpackCString "foo"#
> where "foo"# is a statically allocate C string, and the "unpackCString" unpacks it lazily.
> 
> Maybe we could make a literal [a,b.c] turn into
> 	unpack [a,b,c]#
> where 
> 	[a,b,c]#
> is a statically-allocated vector?  See http://hackage.haskell.org/trac/ghc/ticket/5218, which is
stalled awaiting brain cycles from someone.
> 
> I'm maxed out at the moment.  I'd be very happy if you guys were able to make progress; I'm happy to advise. 
Open a ticket, start a wiki page, etc!
> 
> Simon
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
wren ng thornton | 27 Sep 02:07 2012

Re: Call for discussion: OverloadedLists extension

On 9/25/12 1:57 PM, Sjoerd Visscher wrote:
>> Maybe we could make a literal [a,b,c] turn into
>> 	unpack [a,b,c]#
>> where
>> 	[a,b,c]#
>> is a statically-allocated vector?

I'm kinda surprised this isn't already being done. Just doing this seems 
like it'd be a good undertaking, regardless of whether we get overloaded 
list literals. Just storing the literal as a C-like array and inflating 
it to a list/array/vector at runtime seems like it should be a big win 
for code that uses a lot of literals.

--

-- 
Live well,
~wren
Mario Blažević | 28 Sep 20:48 2012

Re: Call for discussion: OverloadedLists extension

On 12-09-26 08:07 PM, wren ng thornton wrote:
> On 9/25/12 1:57 PM, Sjoerd Visscher wrote:
>>> Maybe we could make a literal [a,b,c] turn into
>>>     unpack [a,b,c]#
>>> where
>>>     [a,b,c]#
>>> is a statically-allocated vector?
>
> I'm kinda surprised this isn't already being done. Just doing this seems
> like it'd be a good undertaking, regardless of whether we get overloaded
> list literals. Just storing the literal as a C-like array and inflating
> it to a list/array/vector at runtime seems like it should be a big win
> for code that uses a lot of literals.

Why?

	I'm surprised that this is an issue at all. If list literals you are 
talking about are constant, wouldn't GHC apply constant folding and 
construct the list only the first time it's needed?
wren ng thornton | 30 Sep 05:47 2012

Re: Call for discussion: OverloadedLists extension

On 9/28/12 2:48 PM, Mario Blažević wrote:
> On 12-09-26 08:07 PM, wren ng thornton wrote:
>> On 9/25/12 1:57 PM, Sjoerd Visscher wrote:
>>>> Maybe we could make a literal [a,b,c] turn into
>>>>     unpack [a,b,c]#
>>>> where
>>>>     [a,b,c]#
>>>> is a statically-allocated vector?
>>
>> I'm kinda surprised this isn't already being done. Just doing this seems
>> like it'd be a good undertaking, regardless of whether we get overloaded
>> list literals. Just storing the literal as a C-like array and inflating
>> it to a list/array/vector at runtime seems like it should be a big win
>> for code that uses a lot of literals.
>
> Why?
>
>      I'm surprised that this is an issue at all. If list literals you
> are talking about are constant, wouldn't GHC apply constant folding and
> construct the list only the first time it's needed?

The problem is: if the list is stored naively in the .data segment (as 
apparently it is), then we have to store all the pointer structure as 
well as the data. This hugely bloats the disk footprint for programs.

That is, all the reasons why String=[Char] is bad at runtime are also 
reasons why this representation is bad at objectcode time. For most 
lists, the pointer structure is a considerable portion of the total 
memory cost. During runtime this overhead is (or at least may be) 
unavoidable due to the dynamic nature of program execution; but there's 
no reason to have this overhead in the compiled format of the program 
since it's trivial to generate it from a compact representation (e.g., 
storing lists as C-style arrays + lengths).

The only conceivable benefit of storing lists on disk using their heap 
representation is to allow treating the .data segment as if it were part 
of the heap, i.e., to have zero-cost inflation and to allow GC to ignore 
that "part of the heap". However, for lists, I can't imagine this 
actually being beneficial in practice. This sort of thing is more 
beneficial for large structures of static data (e.g., sets, maps,...). 
But then for large static data, we still usually want a non-heap 
representation (e.g., cache-oblivious datastructures), since we're 
liable to only look at the data rather than to change it. It's only when 
we have lots of static "mutable" data that it makes sense to take heap 
snapshots.

--

-- 
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Bryan O'Sullivan | 25 Sep 19:17 2012

Re: Call for discussion: OverloadedLists extension

On Mon, Sep 24, 2012 at 5:53 AM, George Giorgidze <giorgidze <at> gmail.com> wrote:

Our second approach to OverloadedLists is to avoid the construction of
lists altogether. By typechecking and desugaring lists like

[] ; [x,y,z] ;  ['a' .. 'z'] ;

as

mempty ; singleton x `mappend` singleton y `mappend` singleton z ;
genericEnumFromTo 'a' 'z' ;

This is very interesting.

As Michael mentions later, we already have mechanisms in place to work around the creation of constant strings for the Text and ByteString types, and they rely on a combination of GHC rewrite rules and knowledge about the internal representation of constant strings used by GHC. We are fortunate that GHC uses a very efficient representation to store constant strings, so doing the translation is efficient.

Constant lists are another story entirely (for good reason); the generated object files are bloated and poorly laid out, when for simple types (integers and whatnot), I'd really like to see a packed array in the .data section.

I would be interested to see if an approach that avoids list construction can also aim to achieve a more efficient object file layout, with the implied goal being to make fast translation to the runtime representation easily achievable.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
wren ng thornton | 27 Sep 02:02 2012

Re: Call for discussion: OverloadedLists extension

On 9/24/12 8:53 AM, George Giorgidze wrote:
> We will release GHC patches for both approaches, meanwhile the
> feedback from the community on the approaches that we took would be
> very much appreciated. Which one those would you prefer? or would you
> suggest a different one.

The first one is much cleaner, and more closely mirrors the other 
overloaded literals. It seems that in most cases the intermediate list 
should be eliminated via build/foldr fusion. Did you do any testing to 
figure out why that fusion wasn't happening? (I.e., *why* is the generic 
approach faster?)

The only other thing I'll mention is that for overloadable strings, part 
of the reason why they're so fast is that string literals are stored a 
la C, and so the conversion to ByteString and Text requires minimal 
work. I wonder if you might be able to leverage a similar technique for 
representing list literals as vectors, which are then inflated to 
lists/vectors/sets/whatever at runtime.

--

-- 
Live well,
~wren
Roman Leshchinskiy | 24 Sep 17:50 2012
Picon
Picon

Re: Call for discussion: OverloadedLists extension

Michael Snoyman wrote:
>
> The simplest example I can think of is allowing easier usage of Vector:
>
>     [1, 2, 3] :: Vector Int
>
> In order to allow this, we could use a typeclass approach similar to
> how OverloadedStrings works:
>
>     class IsList a where
>         fromList :: [b] -> a b
>     instance IsList Vector where
>         fromList = V.fromList
>     foo :: Vector Int
>     foo = fromList [1, 2, 3]

I remember a similar discussion a few years ago. The question of whether
or not overloading list literals a good idea notwithstanding, the problem
with this is that fromList for vectors is highly inefficient. So if
something like this gets implemented and if vector/array literals are one
of the main motivations then I really hope there will be no lists
involved.

Roman
Simon Peyton-Jones | 24 Sep 19:19 2012
Picon

Re: Call for discussion: OverloadedLists extension

|  I remember a similar discussion a few years ago. The question of whether
|  or not overloading list literals a good idea notwithstanding, the problem
|  with this is that fromList for vectors is highly inefficient. So if
|  something like this gets implemented and if vector/array literals are one
|  of the main motivations then I really hope there will be no lists
|  involved.

Would you like to remind us why it is so inefficient?  Can't the vector construction be a fold over the list? 
Ah... you need to know the *length* of the list, don't you?  So that you can allocate a suitably-sized
vector.  Which of course we do for literal lists.

So what if fromList went
	fromList :: Int -> [b] -> a b
where the Int is the length of the list?

Simon
Paul Visschers | 25 Sep 09:19 2012
Picon

Re: Call for discussion: OverloadedLists extension

Would that also work for vectors that have their length in their type? And while we are at it, how about overloaded tuples?


Paul

On Mon, Sep 24, 2012 at 7:19 PM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:
|  I remember a similar discussion a few years ago. The question of whether
|  or not overloading list literals a good idea notwithstanding, the problem
|  with this is that fromList for vectors is highly inefficient. So if
|  something like this gets implemented and if vector/array literals are one
|  of the main motivations then I really hope there will be no lists
|  involved.

Would you like to remind us why it is so inefficient?  Can't the vector construction be a fold over the list?  Ah... you need to know the *length* of the list, don't you?  So that you can allocate a suitably-sized vector.  Which of course we do for literal lists.

So what if fromList went
        fromList :: Int -> [b] -> a b
where the Int is the length of the list?

Simon


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Roman Leshchinskiy | 25 Sep 10:25 2012
Picon
Picon

Re: Call for discussion: OverloadedLists extension

Simon Peyton-Jones wrote:
> |  I remember a similar discussion a few years ago. The question of
> whether
> |  or not overloading list literals a good idea notwithstanding, the
> problem
> |  with this is that fromList for vectors is highly inefficient. So if
> |  something like this gets implemented and if vector/array literals are
> one
> |  of the main motivations then I really hope there will be no lists
> |  involved.
>
> Would you like to remind us why it is so inefficient?  Can't the vector
> construction be a fold over the list?  Ah... you need to know the *length*
> of the list, don't you?  So that you can allocate a suitably-sized vector.
>  Which of course we do for literal lists.
>
> So what if fromList went
> 	fromList :: Int -> [b] -> a b
> where the Int is the length of the list?

That's part of a problem. There are really two aspects to it. Firstly, a
naive list-based implementation would be a loop. But when I write ([x,y]
:: Vector Double) somewhere in an inner loop in my program, I *really*
don't want a loop with two iterations at runtime - I want just an
allocation and two writes. I suppose this could be solved by doing
something like this:

  {-# INLINE fromList #-}
  fromList [] = V.empty
  fromList [x] = V.singleton x
  fromList [x,y] = ...
  -- and so on up to 8? 16? 32?
  fromList xs = fromList_loop xs

But it's ugly and, more importantly, inlines a huge term for every literal.

The other problem is with literals where all values are known at compile
time. Suppose I have ([2.5,1.4] :: Vector Double) in an inner loop. Here,
I don't want a complicated CAF for the constant vector which would have to
be entered on every loop iteration. I'd much rather just have a pointer to
the actual data somewhere in memory and use that. This is more or less
what happens for strings at the moment, even though you have to use
rewrite rules to get at the pointer which, in my opinion, is neither ideal
nor really necessary. IMO, the "right" design shouldn't rely on rewrite
rules. Also, strings give you an Addr# whereas vector supports ByteArray#,
too.

Since enumerated literals have been mentioned in a different post, I'll
just mention that the Enum class as it is now can't support those
efficiently for arrays because there is no way to determine either the
length or the nth element of [x..y] in constant time. This would have to
be fixed.

Roman
Simon Peyton-Jones | 25 Sep 10:31 2012
Picon

Re: Call for discussion: OverloadedLists extension


| pointer to the actual data somewhere in memory and use that. This is
| more or less what happens for strings at the moment, even though you
| have to use rewrite rules to get at the pointer which, in my opinion, is
| neither ideal nor really necessary. IMO, the "right" design shouldn't
| rely on rewrite rules. Also, strings give you an Addr# whereas vector
| supports ByteArray#, too.

If it's not necessary, I wonder if you have an idea for the "right" design?  

I find it a lot easier to see what is wrong with the current situation than to think of solutions.

Simon
Roman Leshchinskiy | 25 Sep 10:51 2012
Picon
Picon

Re: Call for discussion: OverloadedLists extension

Simon Peyton-Jones wrote:
>
> | pointer to the actual data somewhere in memory and use that. This is
> | more or less what happens for strings at the moment, even though you
> | have to use rewrite rules to get at the pointer which, in my opinion, is
> | neither ideal nor really necessary. IMO, the "right" design shouldn't
> | rely on rewrite rules. Also, strings give you an Addr# whereas vector
> | supports ByteArray#, too.
>
> If it's not necessary, I wonder if you have an idea for the "right"
> design?

For strings, we could have something like this:

data StringPtr

stringFromStringPtr :: StringPtr -> Int -> String
unsafeStringPtrToPtr :: StringPtr -> Ptr CChar

class IsString a where
  fromString :: String -> a
  fromStringPtr :: StringPtr -> Int -> a
  fromStringPtr p n = fromString $ stringFromStringPtr p n

"abc" would then desugar to fromStringPtr (address of "abc") 3. Note that
we couldn't just use Ptr CChar instead of StringPtr because stringFromPtr
would only be safe if the data that the pointer references never changes.

It's much trickier for general-purpose arrays. It's also much trickier to
support both Ptr and ByteArray. I'd have to think about how to do that.

Roman
Aleksey Khudyakov | 25 Sep 10:49 2012
Picon

Re: Call for discussion: OverloadedLists extension

> That's part of a problem. There are really two aspects to it. Firstly, a
> naive list-based implementation would be a loop. But when I write ([x,y]
> :: Vector Double) somewhere in an inner loop in my program, I *really*
> don't want a loop with two iterations at runtime - I want just an
> allocation and two writes. I suppose this could be solved by doing
> something like this:
>
Some time ago I played with function fromList and rewrite rules.
For statically known lists it's possible to rewrite

fromList [a,b,c] → cons a $ cons b $ cons c $ empty

Latter is compiled down to single allocation and three writes.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Simon Peyton-Jones | 24 Sep 18:29 2012
Picon

Re: Call for discussion: OverloadedLists extension

|  Many of us use the OverloadedStrings language extension on a regular
|  basis. It provides the ability to keep the ease-of-use of string
|  literal syntax, while getting the performance and correctness
|  advantages of specialized datatypes like ByteString and Text. I think
|  we can get the same kind of benefit by allowing another literal syntax
|  to be overloaded, namely lists.	

Interestingly, Achim Krause, George Giorgidze and Jeroen Weijers have been thinking about this very
question.  They have most of an implementation too. I'm ccing them so they can post a status update.

Your email broadens the topic somewhat; I don't think we'd considered overloading for maps too, though I
can see it makes sense.  I'd much prefer the type-family solution (with a single-parameter type class) to
the fundep one, if we go that route.

This topic deserves its own page on the GHC wiki, if someone wants to start one.

If we can evolve a design consensus, I'm happy to incorporate the result in GHC.

Simon

|  -----Original Message-----
|  From: haskell-cafe-bounces <at> haskell.org [mailto:haskell-cafe-
|  bounces <at> haskell.org] On Behalf Of Michael Snoyman
|  Sent: 23 September 2012 05:07
|  To: Haskell Cafe
|  Subject: [Haskell-cafe] Call for discussion: OverloadedLists extension
|  
|  (Prettier formatting available at: https://gist.github.com/3761252)
|  
|  Many of us use the OverloadedStrings language extension on a regular
|  basis. It provides the ability to keep the ease-of-use of string
|  literal syntax, while getting the performance and correctness
|  advantages of specialized datatypes like ByteString and Text. I think
|  we can get the same kind of benefit by allowing another literal syntax
|  to be overloaded, namely lists.	
|  
|  ## Overly simple approach
|  
|  The simplest example I can think of is allowing easier usage of Vector:
|  
|      [1, 2, 3] :: Vector Int
|  
|  In order to allow this, we could use a typeclass approach similar to
|  how OverloadedStrings works:
|  
|      class IsList a where
|          fromList :: [b] -> a b
|      instance IsList Vector where
|          fromList = V.fromList
|      foo :: Vector Int
|      foo = fromList [1, 2, 3]
|  
|  ## Flaws
|  
|  However, such a proposal does not allow for constraints, e.g.:
|  
|      instance IsList Set where
|          fromList = Set.fromList
|  
|      No instance for (Ord b)
|        arising from a use of `Set.fromList'
|      In the expression: Set.fromList
|      In an equation for `fromList': fromList = Set.fromList
|      In the instance declaration for `IsList Set'
|  
|  Additionally, it provides for no means of creating instances for
|  datatypes like Map, where the contained value is not identical to the
|  value contained in the original list. In other words, what I'd like to
|  see is:
|  
|      [("foo", 1), ("bar", 2)] :: Map Text Int
|  
|  ## A little better: MPTC
|  
|  A simplistic approach to solve this would be to just use MultiParamTypeClasses:
|  
|      class IsList input output where
|          fromList :: [input] -> output
|      instance IsList a (Vector a) where
|          fromList = V.fromList
|      foo :: Vector Int
|      foo = fromList [1, 2, 3]
|  
|  Unfortunately, this will fail due to too much polymorphism:
|  
|      No instance for (IsList input0 (Vector Int))
|        arising from a use of `fromList'
|      Possible fix:
|        add an instance declaration for (IsList input0 (Vector Int))
|      In the expression: fromList [1, 2, 3]
|      In an equation for `foo': foo = fromList [1, 2, 3]
|  
|  This can be worked around by giving an explicit type signature on the
|  numbers in the list, but that's not a robust solution. In order to
|  solve this properly, I think we need either functional dependencies or
|  type families:
|  
|  ## Functional dependencies
|  
|      class IsList input output | output -> input where
|          fromList :: [input] -> output
|      instance IsList a (Vector a) where
|          fromList = V.fromList
|      instance Ord a => IsList a (Set a) where
|          fromList = Set.fromList
|      instance Ord k => IsList (k, v) (Map k v) where
|          fromList = Map.fromList
|  
|      foo :: Vector Int
|      foo = fromList [1, 2, 3]
|  
|      bar :: Set Int
|      bar = fromList [1, 2, 3]
|  
|      baz :: Map String Int
|      baz = fromList [("foo", 1), ("bar", 2)]
|  
|  ## Type families
|  
|      class IsList a where
|          type IsListInput a
|          fromList :: [IsListInput a] -> a
|      instance IsList (Vector a) where
|          type IsListInput (Vector a) = a
|          fromList = V.fromList
|      instance Ord a => IsList (Set a) where
|          type IsListInput (Set a) = a
|          fromList = Set.fromList
|      instance Ord k => IsList (Map k v) where
|          type IsListInput (Map k v) = (k, v)
|          fromList = Map.fromList
|  
|      foo :: Vector Int
|      foo = fromList [1, 2, 3]
|  
|      bar :: Set Int
|      bar = fromList [1, 2, 3]
|  
|      baz :: Map String Int
|      baz = fromList [("foo", 1), ("bar", 2)]
|  
|  ## Conclusion
|  
|  Consider most of this proposal to be a strawman: names and techniques
|  are completely up to debate. I'm fairly certain that our only two
|  choices to implement this extension is a useful way is fundeps and
|  type families, but perhaps there's another approach I'm missing. I
|  don't have any particular recommendation here, except to say that
|  fundeps is likely more well supported by other compilers.
|  
|  _______________________________________________
|  Haskell-Cafe mailing list
|  Haskell-Cafe <at> haskell.org
|  http://www.haskell.org/mailman/listinfo/haskell-cafe
George Giorgidze | 6 Nov 15:59 2012
Picon

Re: Call for discussion: OverloadedLists extension

I have created a wiki page about the current implementation of the
OverloadedLists extension:

http://hackage.haskell.org/trac/ghc/wiki/OverloadedLists

The link to the GHC branch that provides a preliminary implementation
of the extension is given in the wiki page.

The wiki page documents what works already and how the extension can
be extended/improved further.

We would welcome contributions. If you would like to make a change in
the current design and implementation of the extension, please
document it (e.g., on the wiki page) and/or send us a GHC patch or a
pull request.

Please also comment whether you would like to see this extension
included in GHC.

Cheers, George

On 24 September 2012 18:29, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:
> |  Many of us use the OverloadedStrings language extension on a regular
> |  basis. It provides the ability to keep the ease-of-use of string
> |  literal syntax, while getting the performance and correctness
> |  advantages of specialized datatypes like ByteString and Text. I think
> |  we can get the same kind of benefit by allowing another literal syntax
> |  to be overloaded, namely lists.
>
> Interestingly, Achim Krause, George Giorgidze and Jeroen Weijers have been thinking about this very
question.  They have most of an implementation too. I'm ccing them so they can post a status update.
>
> Your email broadens the topic somewhat; I don't think we'd considered overloading for maps too, though I
can see it makes sense.  I'd much prefer the type-family solution (with a single-parameter type class) to
the fundep one, if we go that route.
>
> This topic deserves its own page on the GHC wiki, if someone wants to start one.
>
> If we can evolve a design consensus, I'm happy to incorporate the result in GHC.
>
> Simon
>
>
> |  -----Original Message-----
> |  From: haskell-cafe-bounces <at> haskell.org [mailto:haskell-cafe-
> |  bounces <at> haskell.org] On Behalf Of Michael Snoyman
> |  Sent: 23 September 2012 05:07
> |  To: Haskell Cafe
> |  Subject: [Haskell-cafe] Call for discussion: OverloadedLists extension
> |
> |  (Prettier formatting available at: https://gist.github.com/3761252)
> |
> |  Many of us use the OverloadedStrings language extension on a regular
> |  basis. It provides the ability to keep the ease-of-use of string
> |  literal syntax, while getting the performance and correctness
> |  advantages of specialized datatypes like ByteString and Text. I think
> |  we can get the same kind of benefit by allowing another literal syntax
> |  to be overloaded, namely lists.
> |
> |  ## Overly simple approach
> |
> |  The simplest example I can think of is allowing easier usage of Vector:
> |
> |      [1, 2, 3] :: Vector Int
> |
> |  In order to allow this, we could use a typeclass approach similar to
> |  how OverloadedStrings works:
> |
> |      class IsList a where
> |          fromList :: [b] -> a b
> |      instance IsList Vector where
> |          fromList = V.fromList
> |      foo :: Vector Int
> |      foo = fromList [1, 2, 3]
> |
> |  ## Flaws
> |
> |  However, such a proposal does not allow for constraints, e.g.:
> |
> |      instance IsList Set where
> |          fromList = Set.fromList
> |
> |      No instance for (Ord b)
> |        arising from a use of `Set.fromList'
> |      In the expression: Set.fromList
> |      In an equation for `fromList': fromList = Set.fromList
> |      In the instance declaration for `IsList Set'
> |
> |  Additionally, it provides for no means of creating instances for
> |  datatypes like Map, where the contained value is not identical to the
> |  value contained in the original list. In other words, what I'd like to
> |  see is:
> |
> |      [("foo", 1), ("bar", 2)] :: Map Text Int
> |
> |  ## A little better: MPTC
> |
> |  A simplistic approach to solve this would be to just use MultiParamTypeClasses:
> |
> |      class IsList input output where
> |          fromList :: [input] -> output
> |      instance IsList a (Vector a) where
> |          fromList = V.fromList
> |      foo :: Vector Int
> |      foo = fromList [1, 2, 3]
> |
> |  Unfortunately, this will fail due to too much polymorphism:
> |
> |      No instance for (IsList input0 (Vector Int))
> |        arising from a use of `fromList'
> |      Possible fix:
> |        add an instance declaration for (IsList input0 (Vector Int))
> |      In the expression: fromList [1, 2, 3]
> |      In an equation for `foo': foo = fromList [1, 2, 3]
> |
> |  This can be worked around by giving an explicit type signature on the
> |  numbers in the list, but that's not a robust solution. In order to
> |  solve this properly, I think we need either functional dependencies or
> |  type families:
> |
> |  ## Functional dependencies
> |
> |      class IsList input output | output -> input where
> |          fromList :: [input] -> output
> |      instance IsList a (Vector a) where
> |          fromList = V.fromList
> |      instance Ord a => IsList a (Set a) where
> |          fromList = Set.fromList
> |      instance Ord k => IsList (k, v) (Map k v) where
> |          fromList = Map.fromList
> |
> |      foo :: Vector Int
> |      foo = fromList [1, 2, 3]
> |
> |      bar :: Set Int
> |      bar = fromList [1, 2, 3]
> |
> |      baz :: Map String Int
> |      baz = fromList [("foo", 1), ("bar", 2)]
> |
> |  ## Type families
> |
> |      class IsList a where
> |          type IsListInput a
> |          fromList :: [IsListInput a] -> a
> |      instance IsList (Vector a) where
> |          type IsListInput (Vector a) = a
> |          fromList = V.fromList
> |      instance Ord a => IsList (Set a) where
> |          type IsListInput (Set a) = a
> |          fromList = Set.fromList
> |      instance Ord k => IsList (Map k v) where
> |          type IsListInput (Map k v) = (k, v)
> |          fromList = Map.fromList
> |
> |      foo :: Vector Int
> |      foo = fromList [1, 2, 3]
> |
> |      bar :: Set Int
> |      bar = fromList [1, 2, 3]
> |
> |      baz :: Map String Int
> |      baz = fromList [("foo", 1), ("bar", 2)]
> |
> |  ## Conclusion
> |
> |  Consider most of this proposal to be a strawman: names and techniques
> |  are completely up to debate. I'm fairly certain that our only two
> |  choices to implement this extension is a useful way is fundeps and
> |  type families, but perhaps there's another approach I'm missing. I
> |  don't have any particular recommendation here, except to say that
> |  fundeps is likely more well supported by other compilers.
> |
> |  _______________________________________________
> |  Haskell-Cafe mailing list
> |  Haskell-Cafe <at> haskell.org
> |  http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>

Gmane