Could not deduce (a ~ Set.Set (Set.Set a))

Question

I need help with the following error please. Basically for a given list of items I want to create a function that checks if an item is in that list. In order to do that I turn the list into a set and then create a closure around that set.

toAccept :: Ord a => [a] -> (a -> Bool)
toAccept xs =
    let xset = Set.fromList xs in
    let
    -- accept:: Ord a => a -> Bool
    accept x = Set.member xset x in 
    accept

What I am getting is

Could not deduce (a ~ Set.Set (Set.Set a))
from the context (Ord a)
  bound by the type signature for
             toAccept :: Ord a => [a] -> a -> Bool
  at Tokens.hs:6:13-39
  `a' is a rigid type variable bound by
      the type signature for toAccept :: Ord a => [a] -> a -> Bool
      at Tokens.hs:6:13
Expected type: a -> Bool
  Actual type: Set.Set (Set.Set a) -> Bool
In the expression: accept
In the expression: let accept x = Set.member xset x in accept
In the expression:
  let xset = Set.fromList xs in
  let accept x = Set.member xset x in accept

What am I doing wrong?

@n.m. If he's querying a lot of elements `elem` is `O(n)` each query but `toAccept` is `O(n)` during construction but only `O(log(n))` for each query. — daniel gratzer, Oct 30 '13 at 16:17
you can also just replace your last four lines with ``(`Set.member` xset)``. — Will Ness, Oct 30 '13 at 17:07

score 2 · Accepted Answer · edited May 23 '17 at 10:25

You have your arguments flopped

let accept x = Set.member x xset in accept

As a rule, In haskell functions the datastructure comes last since this makes it amenable to pointfree style. See here for more on this.

A potentially nicer way of writing this is

toAccept' :: Ord a => [a] -> a -> Bool
toAccept' = flip Set.member . Set.fromList

Here we take advantage of Haskell's currying feature, since [a] -> a -> Bool is the same as [a] -> (a -> Bool). We can actually write our function as though it receives two arguments and doesn't take one and returns a function because in Haskell, these options are identical.

Could not deduce (a ~ Set.Set (Set.Set a))

1 Answers1