CODEWITHSUNDEEP
haskellpattern-matching
Derek Thurn
Derek Thurn

Reputation: 15365

Haskell Pattern Matching on the Empty Set

I'm changing some Haskell code from using lists to sets. I understand everything required, I think, but I'm not sure how to pattern match on sets. Lists have this nice literal syntax that seems hard to emulate with the Set constructor. For example, I might have some code like this:

foo [] = []
foo x = other_thing

How can I write this code so it uses Sets instead of lists?

Upvotes: 23

Views: 5375

Answers (2)

Thomas Eding
Thomas Eding

Reputation: 1

import qualified Data.Set as Set

foo set
  | Set.null set = bar
  | otherwise = baz

Upvotes: 36

C. A. McCann
C. A. McCann

Reputation: 77384

Well, you can't.

Set is an abstract data type[0] that deliberately hides its internal representation, primarily to maintain invariants of the data structure that can't be statically-enforced by the type system (specifically, the standard library Data.Set.Set is a binary search tree).

Losing the ability to pattern match on an abstract data type is an unpleasant bit of collateral damage, but oh well. Your options are roughly:

  • Use boolean predicates and guards, e.g. null, as in trinithis's answer.
  • Convert the Set to a list. Most of the time this is silly but if you want to iterate through the set anyway, it works well enough.
  • Enable GHC's ViewPatterns extension, which provides syntactic sugar for using accessor functions where a pattern match would normally go.
  • Avoid making these sort of checks in the first place--if you have a Set, treat it like a set, and work with it as a whole for mapping, filtering, etc. Not always possible, but can lead to cleaner code with fewer explicit conditionals/iterations.

View patterns would let you write something that looks like this:

foo (setView -> EmptySet) = []
foo (setView -> NonEmpty set) = other_thing

...where setView is a function you write. Not really much of a gain here, but can be nice for more complex pseudo-patterns

For avoiding explicit checks, besides well-known set operations such as union and intersection, consider making use of the filter, partition, map, and fold functions in Data.Set.

[0]: See this paper (warning: PDF) for the definition of the term as I'm using it.

Upvotes: 37

Related Questions