# Functor instance for Set?

8 messages
Open this post in threaded view
|
Report Content as Inappropriate

## Functor instance for Set?

 Hi I was always  under the impression that the fact that Data.Set.Set can not be made an instance of Functor was a sort of unavoidable limitation. But if we look at the definition of Data.Set.map: map :: (Ord a, Ord b) => (a->b) -> Set a -> Set b map f = fromList . List.map f . toList we see that 1) "Ord a" is not really used and 2) "Ord b" is only needed for the final fromList. Since every interesting function in Data.Set requires an Ord dictionary anyway, one could implement fmap using only the "List.map f . toList" part and leave the "fromList" to the successive function calls. It appears to me, then, that if "Set a" were implemented as the sum of a list of a and a BST, it could be made an instance of Functor, Applicative and even Monad without affecting asymptotic complexity (proof of concept below). Am I right here? Would the overhead be significant? The one downside I can think of is that one would have to sacrifice the Foldable instance. Thanks, Daniel import qualified Data.Set as Internal import Data.Monoid import Control.Applicative data Set a = This (Internal.Set a) | List [a] toInternal :: Ord a => Set a -> Internal.Set a toInternal (This s) = s toInternal (List s) = Internal.fromList s toAscList :: Ord a => Set a -> [a] toAscList (This s)   = Internal.toAscList s toAscList (List s) = Internal.toAscList \$ Internal.fromAscList s toList :: Set a -> [a] toList (This s) = Internal.toList s toList (List s) = s -- Here we break the API by requiring (Ord a). -- We could require (Eq a) instead, but this would force us to use -- nub in certain cases, which is horribly inefficient. instance Ord a => Eq (Set a) where   l == r = toInternal l == toInternal r instance Ord a => Ord (Set a) where   compare l r = compare (toInternal l) (toInternal r) instance Functor Set where   fmap f = List . map f . toList instance Applicative Set where   pure = singleton   f <*> x = List \$ toList f <*> toList x instance Monad Set where   return  = pure   s >>= f = List \$ toList s >>= (toList . f) empty :: Set a empty = This Internal.empty singleton :: a -> Set a singleton = This . Internal.singleton insert :: Ord a => a -> Set a -> Set a insert a = This . Internal.insert a . toInternal delete :: Ord a => a -> Set a -> Set a delete a = This . Internal.delete a . toInternal instance Ord a => Monoid (Set a) where     mempty = This mempty     mappend (This l) (This r) = This (mappend l r)     mappend l r = This . Internal.fromAscList \$ mergeAsc (toAscList l) (toAscList r)       where mergeAsc :: Ord a => [a] -> [a] -> [a]             mergeAsc [] ys = ys             mergeAsc xs [] = xs             mergeAsc ls@(x:xs) rs@(y:ys) = case compare x y of                                              EQ -> x : mergeAsc xs ys                                              LT -> x : mergeAsc xs rs                                              GT -> y : mergeAsc rs ys _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Functor instance for Set?

 On 2012-02-29 19:54, Daniel Gorín wrote: > Hi > > ... > > It appears to me, then, that if "Set a" were implemented as the sum of a list > of a and a BST, it could be made an instance of Functor, Applicative and even > Monad without affecting asymptotic complexity (proof of concept below). Am I > right here? Would the overhead be significant? The one downside I can think > of is that one would have to sacrifice the Foldable instance. A problem is that you lose complexity guarantees. Consider for example:      let ints = [0..1000000]      let setA = Set.fromList ints      let setB = fmap id setA      let slow = all (`Set.member` setB) ints Each call to Set.member in slow will take O(n) instead of the expected O(log n), which means that this code takes O(n^2) instead of O(n*log n). The problem is that you keep converting the same set from a list to a tree over and over again. Twan _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Functor instance for Set?

 In reply to this post by Daniel Gorín On 29 February 2012 19:54, Daniel Gorín <[hidden email]> wrote: > I was always  under the impression that the fact that Data.Set.Set can not be made an instance of Functor was a sort of unavoidable limitation. I guess the way forward is to start using ConstraintKinds and TypeFamilies: {-# LANGUAGE ConstraintKinds, TypeFamilies, FlexibleInstances #-} import Prelude hiding (Functor, fmap) import Data.Set (Set) import qualified Data.Set as Set (map) import GHC.Exts (Constraint) class Functor f where     type FunctorConstraint f :: * -> Constraint     type FunctorConstraint f = Empty     fmap :: (FunctorConstraint f b) => (a -> b) -> f a -> f b class Empty a instance Empty a instance Functor Set where     type FunctorConstraint Set = Ord     fmap = Set.map     -- Note that the unnecessary 'Ord a' constraint needs to be dropped from:     -- Set.map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b Regards, Bas _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Functor instance for Set?

Open this post in threaded view
|
Report Content as Inappropriate

## Re: Functor instance for Set?

 In reply to this post by Bas van Dijk-2 On Thu, 2012-03-01 at 09:31 +0100, Bas van Dijk wrote: > On 29 February 2012 19:54, Daniel Gorín <[hidden email]> wrote: > > I was always  under the impression that the fact that Data.Set.Set can not be made an instance of Functor was a sort of unavoidable limitation. > > I guess the way forward is to start using ConstraintKinds and TypeFamilies: [...] This doesn't really solve the problem I was looking at (namely, making an ordered-tree-based implementation of a Set type an instance of the standard Functor class) but I find it very interesting nevertheless. I need to look at this ConstraintKinds extension in more detail.... Thanks, Daniel _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Functor instance for Set?

 In reply to this post by Bas van Dijk-2 On 01/03/12 09:31, Bas van Dijk wrote: > class Functor f where >      type FunctorConstraint f :: * ->  Constraint >      type FunctorConstraint f = Empty > >      fmap :: (FunctorConstraint f b) =>  (a ->  b) ->  f a ->  f b > > class Empty a > instance Empty a Do you really need this Empty class? That seems inconvenient. I had hoped you would be able to write something like      type FunctorConstraint f :: * ->  Constraint      type FunctorConstraint f a = () Twan _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Functor instance for Set?

 On Thu, Mar 1, 2012 at 1:20 PM, Twan van Laarhoven <[hidden email]> wrote: > On 01/03/12 09:31, Bas van Dijk wrote: >> >> class Functor f where >>     type FunctorConstraint f :: * ->  Constraint >>     type FunctorConstraint f = Empty >> >>     fmap :: (FunctorConstraint f b) =>  (a ->  b) ->  f a ->  f b >> >> class Empty a >> instance Empty a > > > Do you really need this Empty class? Depends on what you want. You do need it if you want to be able to use 'FunctorConstraint f' itself as a type of kind * -> Constraint, for example to say type FunctorWithoutConstraint f = (Functor f, FunctorConstraint f ~ Empty). > That seems inconvenient. I had hoped > you would be able to write something like > > >    type FunctorConstraint f :: * ->  Constraint >    type FunctorConstraint f a = () > See this thread: http://www.mail-archive.com/glasgow-haskell-users@.../msg20792.html_______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries