CODEWITHSUNDEEP
haskelloverloaded-stringsoverloaded-lists
theo
theo

Reputation: 305

Why does IsList require toList?

When using -XOverloadedStrings you can implement IsString which only requires a function fromString. Now if you want to use string literals for pattern matching, you also have to implement Eq, which makes sense:

f :: MyString -> Bool
f "foo" = True
f _ = False

-- equivalent to
f x
  | x == fromString "foo" = True
  | otherwise             = False

But then why does the IsList type class which is used with -XOverloadedLists require that you implement toList? In the wiki the only mentioned use-case of toList is pattern matching. And I get that Eq is not sufficient for list pattern matching. But then toList should be in a different type class that's only required if you'd like to use list pattern matching with your type, just like IsString does not require Eq.

The annoying thing about this to me is that the condition fromList . toList = id has to be met but this simply can't be guaranteed for some types like e.g. an unordered collection which make no guarantees that the order of elements is kept.

This just seems very inconsistent.

Upvotes: 9

Views: 226

Answers (1)

Hans Lub
Hans Lub

Reputation: 5678

What is overloaded in both extensions is merely a notation. The difference between the two notations is that a list can contain variables ([x, y]) while strings cannot: Haskell doesn't do variable interpolation like let x = "apple" in "I like {x} pie")

This difference becomes important when I use either notation inside a pattern: I expect to be able to bind variables in a pattern like

f :: MyList Int -> Bool
f [x, y] = x > y

... while, even though I can use string literals as a pattern

 f :: MyString -> Bool
 f "apple" = True

... those will never bind a variable

To see the difference this makes, suppose that -XOverloadedLists would translate pattern matches exactly like -XOverloadedStrings. The pattern match

f [x,y] = x > y

would be translated as

f z
 | z == fromList [x, y] = x > y

But fromList [x, y] is not a constructor pattern: for a given z, there may be several different values for x and y such that fromList [x, y] == z (In your example, an unordered collection {1, 2} is equal to fromList [1, 2] but also to fromList [2, 1] - so should the result of f {1, 2} be True or False?

This shows that for pattern matching to work, Mylist a needs to be isomorphic to [a], in other words, a toList is needed that satisfies the appropriate laws. We then can find the unique x, y such that z == fromList [x, y] by applying toList to z, so the translation instead is

f z
 | toList z == [x, y] = x > y

Or, with a view pattern (which doesn't even need Eq anymore):

f (toList -> [x,y]) = x > y

So, ultimately, your IsList class without the toList would not allow overloaded list patterns, but still make it possible to denote your unordered collection {1, 2} using list notation [1, 2]. But then we would have -XOverloadedLists and -XOverloadedListPatterns - probably not worth the hassle.

Upvotes: 6

Related Questions