Redefining monad list instance

Question

I am attempting to redefine the monad list instance using newtype to create a wrapped list type, so as to allow this to be done at all, since it seems the Prelude definitions are unable to be overridden.

So far I have the following:

newtype MyList a = MyList { unMyList :: [a] }
    deriving Show

myReturn :: a -> [a]
myReturn x = [x]

myBind ::  [a] -> (a -> [b]) -> [b]
myBind m f = concat $ map f m

instance Monad MyList where
    return x = MyList [x]
    xs >>= f = undefined

As a beginner in Haskell, I am at a loss to know how to define the >>= operator for the instance, using my function for the definition of bind.

Should the myReturn and myBind functions have types using MyList rather than plain type variables? How does one do the packing and unpacking necessary to define >>= properly?

I am getting stuck on the function argument to map f, where f :: a -> [b], but it seems I need f :: a -> MyList b, but then map won't accept that as an argument.

Apologies for the confusion. All assistance appreciated.

[I am aware there is a similar question here: Redefine list monad instance but I'm afraid I cannot follow the answers there.]

Why would you want to wrap lists in such a way? Why not make a new singly linked list using data List t = Empty | t :+ (List t), and then redefine it that way - surely that's a more practical exercise, and just as challenging? — AJF

bheklilr bheklilr · Accepted Answer · 2014-12-03T16:35:19

You simply need to unwrap your MyList type, operate on it, then wrap it back up:

instance Monad MyList where
    return x = MyList [x]
    (MyList xs) >>= f = MyList . concat . map unMyList . map f $ xs

You can (and should) condense this to MyList $ concatMap (unMyList . f) xs, but I've left it expanded for illustrative purposes. You could simplify this definition by defining your own map and concat functions for MyList:

myMap :: (a -> b) -> MyList a -> MyList b
myMap f (MyList xs) = MyList $ map f xs

myConcat :: MyList (MyList a) -> MyList a
myConcat (MyList xs) = MyList $ concat $ map unMyList xs

myConcatMap :: (a -> MyList b) -> MyList a -> MyList b
myConcatMap f xs = myConcat $ myMap f xs

instance Monad MyList where
    return x = MyList [x]
    xs >>= f = myConcatMap f xs

And now it looks like the normal list instance:

instance Monad [] where
    return x = [x]
    xs >>= f = concatMap f xs

Redefining monad list instance

1 Answers