public
Created

Overloaded lists proposal

  • Download Gist
overloaded-lists.md
Markdown

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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.