Move 'oelem' into MonoFoldable

[chris-martin]

Someone on Stack Overflow just asked the question: How can you define an efficient elem implementation for a binary search tree?

I wanted to answer that using MonoFoldable instead of Foldable makes this possible:

data Tree a = Nil | Node (Tree a) a (Tree a)
  deriving Foldable

type instance Element (Tree a) = a

instance Ord a => MonoFoldable (Tree a) where

  -- ...

  oelem x Nil = False
  oelem x (Node l d r)
    | x == d = True
    | x < d = elem x l
    | otherwise = elem x r

But unfortunately, this can't be done because oelem is not part of the class. Is there any reason not to move it there?

[snoyberg]

There's no Eq constraint on MonoFoldable. We'd need a separate MonoEqFoldable, which gets ugly and confusing.

On Fri, Jul 28, 2017 at 2:01 AM, Chris Martin notifications@github.com wrote:

Someone on Stack Overflow https://stackoverflow.com/questions/45361801 just asked the question: How can you define an efficient elem implementation for a binary search tree?

I wanted to answer that using MonoFoldable instead of Foldable makes this possible:

data Tree a = Nil | Node (Tree a) a (Tree a) deriving Foldable type instance Element (Tree a) = a instance Ord a => MonoFoldable (Tree a) where

-- ...

oelem x Nil = False oelem x (Node l d r) | x == d = True | x < d = elem x l | otherwise = elem x r

But unfortunately, this can't be done because oelem is not part of the class. Is there any reason not to move it there?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/snoyberg/mono-traversable/issues/133, or mute the thread https://github.com/notifications/unsubscribe-auth/AADBBz6gk-omN2HU5kqBM6DZKXF7FivRks5sSRbLgaJpZM4Ol8XU .

[chris-martin]

I don't think MonoFoldable would need an Eq constraint; wouldn't the constraint stay on oelem?

class MonoFoldable mono where

    -- ...

    oelem :: Eq (Element mono) => Element mono -> mono -> Bool

[snoyberg]

Give it a shot.

On Fri, Jul 28, 2017 at 8:59 AM, Chris Martin notifications@github.com wrote:

I don't think MonoFoldable would need an Eq constraint; wouldn't the constraint stay on oelem?

class MonoFoldable mono where

-- ...

oelem :: Eq (Element mono) => Element mono -> mono -> Bool

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/snoyberg/mono-traversable/issues/133#issuecomment-318567514, or mute the thread https://github.com/notifications/unsubscribe-auth/AADBB4FVA4RfDfn6xmmxtsztjfafT1NFks5sSXjFgaJpZM4Ol8XU .

[chris-martin]

Would you object to adding an Ord constraint on the Set instance?

Current:

instance MonoFoldable (Set e) where
    olength = Set.size

Proposed:

instance Ord e => MonoFoldable (Set e) where
    olength = Set.size
    oelem = Set.member
    onotElem = Set.notMember

[snoyberg]

I think that's ok

On Fri, Jul 28, 2017, 7:30 PM Chris Martin notifications@github.com wrote:

Would you object to adding an Ord constraint on the Set instance?

Current:

instance MonoFoldable (Set e) where olength = Set.size

Proposed:

instance Ord e => MonoFoldable (Set e) where olength = Set.size oelem = Set.member onotElem = Set.notMember

— You are receiving this because you commented.

Reply to this email directly, view it on GitHub https://github.com/snoyberg/mono-traversable/issues/133#issuecomment-318700699, or mute the thread https://github.com/notifications/unsubscribe-auth/AADBB4bSbssFe5jXAHjsVhTGJipzGbLqks5sSgyfgaJpZM4Ol8XU .