[Haskell-cafe] Call for discussion: OverloadedLists extension
George Giorgidze
giorgidze at gmail.com
Mon Sep 24 14:53:12 CEST 2012
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@haskell.org/msg20447.html
[2] http://www.mail-archive.com/glasgow-haskell-users@haskell.org/msg20518.html
More information about the Haskell-Cafe
mailing list