Agfdhyk

Recently, I'm playing around with Haskell monad and trying to learn about this concept.

Let's say there is a tree data type declared which can have multiple sub-trees.

data MyTree a = MyTree a [MyTree a]

And I'm trying to implement a function that returns "Nothing" if the tree contains any "Nothing" value in the tree. Else, extract all m value and returns a wrapped tree.

So the function type signature has the following.

check :: Monad m => MyTree (m a) -> m (MyTree a)

And here is my current implementation.

check (MyTree v ) = v >>= (v' -> return (MyTree v' ))

check (MyTree v (x:xs)) =

  v >>= (v' -> check x >>= (t' -> return (MyTree v' [t'])))

I use a bind operator on v so that I can get a pure value of it. Then I call the "check" function recursively with the head value from the list. Finally, I wrap the final results.

I tested with some samples and got the following results.

> test1 = MyTree (Just 1) [MyTree (Just 2) [MyTree (Just 3) ]]

> check test1

Just (MyTree 1 [MyTree 2 [MyTree 3 ]])



> test2 = MyTree (Just 1) [MyTree (Just 2) , MyTree (Just 3) ]

> check test2

-- expected: Just (MyTree 1 [MyTree 2 , MyTree 3 ]

-- actual:   Just (MyTree 1 [MyTree 2 ])

So, the current implementation has a problem when the input tree has multiple sub-trees. And I have realized that the problem is that I'm only using x but not xs. I wrapped my head around to think of the right approach and still figuring out. It will be very helpful if anyone has an idea for this.

Your check function is better known as a method of the Traversable class.

class (Functor t, Foldable t) => Traversable t where

  -- The main method

  traverse

    :: Applicative f

    => (a -> f b) -> t a -> f (t b)

  traverse f = sequenceA . fmap f



  -- An alternative

  sequenceA

    :: Applicative f

    => t (f a) -> f (t a)

  sequenceA = traverse id



  -- (Mostly) legacy methods

  mapM

    :: Monad m

    => (a -> m b) -> t a -> m (t b)

  mapM = traverse



  sequence

    :: Monad m

    => t (m a) -> m (t a)

  sequence = sequenceA

Specifically, check is sequence for MyTree. So we will get it if we write a Traversable MyTree instance. But let's first take a step back in two directions. Traversable is a subclass of both Functor and Foldable, and that is no coincidence. It's possible to implement both fmap and foldMap using traverse. But more to the point, the structures of fmap, foldMap and traverse tend to look almost identical! So let's start with those easier ones.

instance Functor MyTree where

  fmap f (MyTree a ts) = MyTree (f a) _

What goes in that blank? We have a list of subtrees and we need to generate a new one, so a good bet is

  fmap f (MyTree a ts) = MyTree (f a) (fmap _ ts)

Now the blank has type MyTree a -> MyTree b, so we just call fmap recursively:

  fmap f (MyTree a ts) = MyTree (f a) (fmap (fmap f) ts)

And we're done. Now let's turn to Foldable.

foldMap f (MyTree a ts) = _

Well, we're going to need to apply f to a to get a value in the monoid, then fold up the subtrees and combine the results. This ends up looking quite a bit like fmap, as promised.

foldMap f (MyTree a ts) = f a <> foldMap (foldMap f) ts

So now we get to Traversable. It's going to be pretty similar to fmap, but we need to combine results using Applicative operations somewhat like we combined foldMap results using Monoid operations.

instance Traversable MyTree where

   traverse f (MyTree a ts) = _

We have

a :: a

ts :: [MyTree a]

f :: a -> f b

Obviously, we're going to want to apply f to a. Following the pattern for fmap and foldMap, we're going to calculate traverse (traverse f) ts. So let's see where that gets us:

traverse f (MyTree a ts) = _ (f a) (traverse (traverse f) ts)

Now GHC will tell us that

_ :: f b -> f [MyTree b] -> f (MyTree b)

We need to take the b result from the first action and the [MyTree b] result from the second action and apply the MyTree constructor to put them together. We can do this using liftA2:

traverse f (MyTree a ts) = liftA2 MyTree (f a) (traverse (traverse f) ts)

Once you've gotten the hang of writing Functor, Foldable, and Traversable instances, doing so tends to get pretty dull. So GHC has an extension that lets the compiler write them for you.

{-# language DeriveTraversable #-}



module MyModule where



data MyTree a = MyTree a [MyTree a]

  deriving (Functor, Foldable, Traversable)

And you're done.