CODEWITHSUNDEEP
haskellset
cealex
cealex

Reputation: 337

Haskell, How to create a ordered data Set a = Set [a]

I need to create a Haskell "data Set"

data Set a = Set [a]

Exercise let's implement a simple Set datatype. A Set is a list of unique elements. The set is always kept ordered.

Implement the functions below. You might need to add class
constraints to the functions' types.

Examples:
member 'a' (Set ['a','b','c'])  ==>  True
add 2 (add 3 (add 1 emptySet))  ==>  Set [1,2,3]
add 1 (add 1 emptySet)  ==>  Set [1]

data Set a = Set [a]
deriving (Show,Eq)

so far I defined :

-- emptySet is a set with no elements
emptySet :: Set a
emptySet = Set []

-- member tests if an element is in a set
member :: Eq a => a -> Set a -> Bool
member _ (Set[]) =  False
member a (Set (x:xs))  
    | (a == x) = True
    | otherwise = member a (Set xs)

but i'm struggling how to define the "add" method, it´s fail in the order test

-- add a member to a set
add ::  Ord a => a -> Set a -> Set a
add a (Set[]) = Set[a] 
add a (Set (x:xs)) 
    | (a > x) && (not ( member a (Set (x:xs)) )) = add a (Set xs)
    | (a <= x) && (not ( member a (Set (x:xs)) )) = Set ( a :(x:xs) )     
    | (not ( member a (Set (x:xs)) )) = Set ((x:xs) ++ [a])
    | otherwise = Set (x:xs)

Tests failed:

*** Failed! Falsified (after 6 tests):
add (Just 0) (Set [Nothing,Just (-5),Just 1,Just 3])
Expected: Set [Nothing,Just (-5),Just 0,Just 1,Just 3]
Was: Set [Just 0,Just 1,Just 3]

so my question is , how to implement the Add method but keep the order correct. or it's easier to using a helper function to order the elements after insert.

Upvotes: 1

Views: 1099

Answers (3)

cealex
cealex

Reputation: 337

the solution that i'm able to found , based on the @amalloy & @chi tips , was

toLista :: Set a -> [a]
-- toLista (Set[]) = [] 
-- toLista (Set (x:xs)) = [x] ++ toLista ( Set (xs))

toLista (Set lista) = lista

add ::  Ord a => a -> Set a -> Set a
add a (Set[]) = Set[a] 
add a (Set (x:xs)) 
    | (a == x) = Set (x:xs)
    | (a < x) = Set ( a :(x:xs) )     
    | otherwise =  Set ( x : toLista ( add a (Set xs) ))

Upvotes: 1

Will Ness
Will Ness

Reputation: 71109

You write

add a (Set (x:xs)) 
    | (a > x) && (not ( member a (Set (x:xs)) )) = add a (Set xs)
  --                                               ^^^^^^^^^^^^^^
....

add a (Set xs) is the result.

Where's x? Shouldn't it be present in the result as well?

Upvotes: 1

amalloy
amalloy

Reputation: 92077

You shouldn't need a member test in each iteration of your add function, because you know the Set is sorted. Simply walk down the list, at each step comparing the element to be added with the front of the set. If the element to be added is equal to the smallest item, then you can stop: the element is already present. If it's less than the smallest item, then you've found its insertion point: if it's smaller than the smallest item, it must be smaller than all items, and thus should be added. Finally if the element to be added is larger than the smallest item, then just keep going until you find its insertion point.

Upvotes: 3

Related Questions