Alternative newtype wrappers for oset

I recently published oset-0.1.1.0 in order to get around some (perceived, by me) shortcomings of ordered-containers. Mainly I was frustrated by the lack of Semigroup and Monoid instances.

In retrospect, I think I should have thought some more before ploughing ahead and implementing them the way I did, mainly because there are ( think) at least two valid, and obvious, possible instances of these type classes for an ordered set. Specifically:

Left-preserving, or left-biased, append: in which duplicate elements on the right-hand side of the append are discarded
Right-preserving, or right-biased, append: in which duplicates elements on the left-hand side of the append are discarded

Therefore, I’m planning to remove the existing Semigroup and Monoid instances and replace them with newtype wrappers providing the desired behaviours. Here’s a sketch of what I intend to do:

	#!/usr/bin/env stack
	-- stack --resolver=lts-12.6 script

	{-# LANGUAGE DuplicateRecordFields #-}
	{-# LANGUAGE StandaloneDeriving #-}

	module Main (main) where

	import Data.List (nub)

	data OSet a = OSet [a]

	deriving instance Show a => Show (OSet a)

	empty :: OSet a
	empty = OSet []

	singleton :: a -> OSet a
	singleton a = OSet [a]

	insert :: Eq a => a -> OSet a -> OSet a
	insert b (OSet as)= OSet (nub (as ++ [b]))

	leftPreservingAppend :: Eq a => OSet a -> OSet a -> OSet a
	leftPreservingAppend (OSet as) (OSet bs) = OSet (nub (as ++ bs))

	rightPreservingAppend :: Eq a => OSet a -> OSet a -> OSet a
	rightPreservingAppend (OSet as) (OSet bs) = OSet (reverse $ nub (reverse bs ++ reverse as))

	toList :: OSet a -> [a]
	toList (OSet as) = as

	newtype LeftPreservingOSet a = LeftPreservingOSet { getOSet :: OSet a }

	instance Eq a => Semigroup (LeftPreservingOSet a) where
	(LeftPreservingOSet as) <> (LeftPreservingOSet bs) = LeftPreservingOSet (leftPreservingAppend as bs)

	instance Eq a => Monoid (LeftPreservingOSet a) where
	mempty = LeftPreservingOSet empty

	deriving instance Show a => Show (LeftPreservingOSet a)

	newtype RightPreservingOSet a = RightPreservingOSet { getOSet :: OSet a }

	instance Eq a => Semigroup (RightPreservingOSet a) where
	(RightPreservingOSet as) <> (RightPreservingOSet bs) = RightPreservingOSet (rightPreservingAppend as bs)

	instance Eq a => Monoid (RightPreservingOSet a) where
	mempty = RightPreservingOSet empty

	deriving instance Show a => Show (RightPreservingOSet a)

	main :: IO ()
	main = do
	print $ (getOSet :: LeftPreservingOSet Int -> OSet Int)
	(LeftPreservingOSet (singleton 5)
	<> LeftPreservingOSet (singleton 3)
	<> LeftPreservingOSet (singleton 2)
	<> LeftPreservingOSet (singleton 5))
	print $ (getOSet :: RightPreservingOSet Int -> OSet Int)
	(RightPreservingOSet (singleton 5)
	<> RightPreservingOSet (singleton 3)
	<> RightPreservingOSet (singleton 2)
	<> RightPreservingOSet (singleton 5))

view raw OSetDemo.hs hosted with ❤ by GitHub

leftPreservingAppend and rightPreservingAppend are not the real implementations but are provided for illustrative purposes only.

blog.rcook.org

Alternative `newtype` wrappers for `oset`

2019-02-05

Related posts

oset-0.4.0.1 released

New packages

View patterns

oset

First package on Hackage

Tags

Haskell

Hackage

oset