Haskell: how to define instance Show Set for type Set = Int -> Bool

Question

I am doing the exercise's to Martin Odersky's "Functional Programming Principles in Scala" coursera course in both Scala and Haskell. For the "sets as functions" exercises I have defined a "toString" function:

import Data.List (intercalate)

type Set = Int -> Bool

contains :: Set -> Int -> Bool
contains s elem = s elem

bound = 1000

toString :: Set -> String
toString s =
    let xs = [(show x) | x <- [(-bound) .. bound], contains s x]
    in "{" ++ (intercalate "," xs) ++ "}"

-- toString (\x -> x > -3 && x < 10)
-- => "{-2,-1,0,1,2,3,4,5,6,7,8,9}"

It would be great to be able to define:

instance Show Set where
    show Set = ...

but the definition needs to reference and call the function thqt represents the Set (i.e., see the 'toString' function).

Is there any Haskell magic that can be used to define 'Show Set' ?

UPDATE based on feedback:

After trying the two solutions suggested and reading Difference between `data` and `newtype` in Haskell it seems that using type or newtype gives me the same "performance" (i.e., read above link) but that 'newtype' give me stronger type-safety, e.g., : I can pass ANY Int -> Bool function to functions that take type Set = Int -> Bool but MUST pass a Set' when defined as newtype Set' = Set' (Int -> Bool).

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

import Data.List (intercalate)

bound = 1000

-- ALTERNATE #1

type Set = Int -> Bool

contains :: Set -> Int -> Bool
contains s elem = s elem

intersect :: Set -> Set -> Set
intersect s t = \x -> s x && t x

toString :: Set -> String
toString s =
    let xs = [(show x) | x <- [(-bound) .. bound], contains s x]
    in "{" ++ (intercalate "," xs) ++ "}"

instance Show Set where show = toString

-- ALTERNATE #2

newtype Set' = Set' (Int -> Bool)

contains' :: Set' -> Int -> Bool
contains' (Set' s) elem = s elem

intersect' :: Set' -> Set' -> Set'
intersect' (Set' s) (Set' t) = Set' (\x -> s x && t x)

instance Show Set' where
    show (Set' s) =
        let xs = [(show x) | x <- [(-bound) .. bound], s x]
        in "{" ++ (intercalate "," xs) ++ "}"

anyIntBoolFun1 = \x -> -10 < x
anyIntBoolFun2 = \x ->   x < 0
setIntBoolFun1 = Set' anyIntBoolFun1
setIntBoolFun2 = Set' anyIntBoolFun2

main = do
    putStrLn $ show $ intersect  anyIntBoolFun1 anyIntBoolFun2
    putStrLn $ show $ intersect' setIntBoolFun1 setIntBoolFun2

-- *Main> main
-- {-9,-8,-7,-6,-5,-4,-3,-2,-1}
-- {-9,-8,-7,-6,-5,-4,-3,-2,-1}

Answer 1

You need to make Set a newtype instead of a type synonym, like this:

newtype Set = Set { unSet :: Int -> Bool }

Then you can make it an instance of any class, like Show:

instance Show Set where
    show (Set s) =
        let xs = [(show x) | x <- [(-bound) .. bound], contains s x]
        in "{" ++ (intercalate "," xs) ++ "}"

Answer 2

Yes, it's as easy as

instance Show Set where show = toString

though you will need to turn on TypeSynonymInstances and FlexibleInstances. The complete file would look like this:

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

import Data.List (intercalate)

type Set = Int -> Bool

contains :: Set -> Int -> Bool
contains s elem = s elem

bound = 1000

toString :: Set -> String
toString s =
    let xs = [(show x) | x <- [(-bound) .. bound], contains s x]
    in "{" ++ (intercalate "," xs) ++ "}"

instance Show Set where show = toString

In ghci:

*Main> (\x -> x > -3 && x < 10) :: Set
{-2,-1,0,1,2,3,4,5,6,7,8,9}

However, this has some caveats: namely, polymorphic functions won't match the given instance. (The type ascription :: Set in the ghci sample above is required, for example.)