Typeclass instances using methods with constrained types

Question

First of all let me apologize, yet I simply couldn't find the answer to my question although I'm pretty sure that this has been asked before. Now:

I would like to write Functor and Monad instances for a binary (search) tree. More precisely, some of the functions like insert or merge require instances of Ord, e.g.:

data Tree a = Empty | Node a (Tree a) (Tree a)
insert :: (Ord a) => Tree a -> a -> Tree a
merge  :: (Ord a) => Tree a -> Tree a -> Tree a

Consequently, the following code doesn't compile:

instance Monad Tree where
  {- ... -}
  Empty >>= f        = Empty
  (Node v l r) >>= f = merge (f v) (merge newL newR)
                       where newL = l >>= f
                             newR = r >>= f

-- No instance for (Ord b) arising from a use of `merge'...

As I didn't know any better, I've tried declaring the Ord constraint on the ADT using DatatypeContexts but that's deprecated and didn't work anyway. Other extensions like FlexibleInstances etc. all seemed useful until I realized they really meant something else.

So, is there a way and how would I go about it? Thank you for your time.

EDIT: Meanwhile I found this useful answer, but it appears as if doing this kind of stuff for typeclasses like Functor is still an issue.

You might this helpful ittc.ku.edu/csdl/fpg/files/Sculthorpe-13-ConstrainedMonad.pdf — Jonathan Fischoff
– Jonathan Fischoff, Commented Jan 9, 2014 at 7:28
The short answer is that it's not really possible to do with the default Monad and Functor type-classes. The constraint cannot hold because in any generic, monadic computation you can simply do return <some non-Ord value>. — shang
– shang, Commented Jan 9, 2014 at 7:34
@JonathanFischoff Thanks a lot, that paper is well worth reading. — fotNelton
– fotNelton, Commented Jan 9, 2014 at 18:06

Ganesh Sittampalam · Accepted Answer · 2014-01-09 07:33:40Z

5

There are various ways you can do this, but none of them are completely clean.

The key term you should look up is "restricted monad".

Here's one example with the rmonad package (which I wrote).

{-# LANGUAGE NoImplicitPrelude, TypeFamilies, GADTs,
             FlexibleInstances, MultiParamTypeClasses #-}

import Control.RMonad.Prelude
import Data.Suitable


data Tree a = Empty | Node a (Tree a) (Tree a)
insert :: (Ord a) => Tree a -> a -> Tree a
insert = undefined
merge  :: (Ord a) => Tree a -> Tree a -> Tree a
merge = undefined

data instance Constraints Tree a where
    TreeConstraints :: Ord a => Constraints Tree a

instance Ord a => Suitable Tree a where
  constraints = TreeConstraints


instance RFunctor Tree where
  fmap f Empty = Empty
  fmap f (Node v l r) = Node (f v) (fmap f l) (fmap f r)    


instance RMonad Tree where
  {- ... -}
  Empty >>= f        = Empty
  (Node v l r) >>= f = withResConstraints $ \TreeConstraints ->
        merge (f v) (merge newL newR)
           where newL = l >>= f
                 newR = r >>= f

See the general documentation for the package here.

Note that RMonad is a different type class to Monad. If you want to have a real Monad instance you can use AsMonad Tree.

answered Jan 9, 2014 at 7:33

Ganesh Sittampalam

29.1k4 gold badges82 silver badges102 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

fotNelton Over a year ago

At first glance, the normalization approach explained in the paper mentioned by Jonathan seems a bit "easier" to me, but admittedly the authors themselves postulate that their approach resembles only a minor difference to rmonad. Guess it'll take some time for me to stomach all this. Thanks a lot so far!

Collectives™ on Stack Overflow

Typeclass instances using methods with constrained types

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related