Создание экземпляров абстрактных типов данных, которые рекурсивно содержат друг друга - PullRequest
Новая
       21

Создание экземпляров абстрактных типов данных, которые рекурсивно содержат друг друга

5 голосов
/ 28 апреля 2011

С учетом двух типов дат, определенных следующим образом: 

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

Как можно сделать foo и bar такими, чтобы foo было Foo bar "foo", а bar было Bar foo "bar"?

Как насчет того, когда мы меняем типы на: 

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

Ответы [ 3 ]

7 голосов
/ 28 апреля 2011

Достаточно просто использовать let (let в Haskell равно letrec и поддерживает взаимно рекурсивные определения). Взаимно рекурсивные определения устанавливают циклы в куче, которые выглядят так:

foo bar let rec

Инициализация MVar на самом деле ничего не меняет. 

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 ()
5 голосов
/ 28 апреля 2011

Дон ответил на вопрос как на вопрос, но чуть более интересный вопрос - как поступить с 

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

Теперь два MVars - не просто свидетели рекурсии, они сообщники.

Это может быть сделано двумя способами:

1.) Либо делая то, что вы делаете на императивном языке, таком как 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.), Либо используя DoRec (ранее RecursiveDo) и mfix, а за кулисами завязываем узел: 

{-# LANGUAGE DoRec #-} 

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

Это означает нечто аналогичное: 

mutual = do
   (foo, bar) <- mfix $ \(foo, bar) -> do
       foo <- newMVar (Foo bar "foo")
       bar <- newMVar (Bar foo "foo")
       return (foo, bar)
  return (foo, bar)
0 голосов
/ 28 апреля 2011

Следующее работает отлично благодаря ленивости Haskells. 

data Foo = Foo Bar String deriving Show
data Bar = Bar Foo String deriving Show

test = let
  foo = Foo bar "foo"
  bar = Bar foo "bar"
  in foo
...