Creating instances of Abstract Data Types that recursively contain each other

Question

Given two date types defined as follows:

data Foo = Foo Bar String
data Bar = Bar Foo String

How can I make foo and bar such that foo is Foo bar "foo" and bar is Bar foo "bar"?

What about when we change the types to:

data Foo = Foo Bar (MVar String)
data Bar = Bar Foo (MVar String)

Answer 1

Just using a let is enough (let in Haskell is letrec, and supports mutually recursive definitions). The mutually recursive definitions set up cycles in the heap, that look like this:

The MVar initialization doesn't really change things in any meaningful way.

import Control.Concurrent

data Foo = Foo Bar (MVar String)

data Bar = Bar Foo (MVar String)

main = do
    a <- newMVar "foo"
    b <- newMVar "bar"

    let foo = Foo bar a
        bar = Bar foo b

    return ()

Answer 2

Don answered the question as asked, but a slightly more interesting question is how to deal with

data Foo = Foo (MVar Bar) String
data Bar = Bar (MVar Foo) String

Now the two MVars aren't mere bystanders to the recursion, they are accomplices.

This can be done two ways:

1.) Either by doing what you would do in an imperative language like C:

mutation = do
   -- setting up an empty mvar
   bar <- newEmptyMVar
   foo <- newMVar (Foo bar "foo")
   -- and then filling it in
   putMVar bar (Bar foo "foo")
   return (foo, bar)

2.) or by using DoRec (formerly RecursiveDo) and mfix and behind the scenes tie the knot:

{-# LANGUAGE DoRec #-} 

mutual = do
   rec foo <- newMVar (Foo bar "foo")
       bar <- newMVar (Bar foo "foo")
   return (foo, bar)

This translates to something analogous to:

mutual = do
   (foo, bar) <- mfix $ \(foo, bar) -> do
       foo <- newMVar (Foo bar "foo")
       bar <- newMVar (Bar foo "foo")
       return (foo, bar)
  return (foo, bar)