Структуры данных с циклическими зависимостями в haskell

Я пытаюсь реализовать простой парсер в haskell, используя библиотеку parsec (для учебных целей). Поэтому я написал кучу структур данных и связанных с ними функций, например:

data SourceElement 
    = StatementSourceElement Statement
    | FunctionSourceElement FunctionName FunctionBody

data Statement 
    = IfStatement Expr Statement Statement
    | WhileStatement Expr Statement

data FunctionBody = FunctionBody [SourceElement]

parseSourceElement :: Parser SourceElement
parseSourceElement = ...

parseFunctionBody :: Parser FunctionBody
parseFunctionBody = ...

Это работает нормально. Теперь я хочу разделить этот материал на два модуля, чтобы разделить структуры данных FunctionBody и Statement (из-за проблем с читаемостью). Но я не могу! Причина в циклической зависимости между SourceElement и FunctionBody.

Итак, есть ли способ решить эту проблему?


haskell cyclic-reference
person sergeyz    schedule 09.12.2012    source источник
comment
Ответ Луки хорош для общего случая удаления циклов в структурах данных, но в вашем случае я бы посмотрел на перепроектирование вашего синтаксического дерева. В языках OO иногда принято представлять синтаксис с общей древовидной структурой (например, ваш SourceElement) и использовать теги (например, ваше перечисление Statement) для его маркировки, но в функциональном языке с алгебраическими типами, такими как Haskell, вы можете представлять деревья напрямую.   -  person stephen tetley    schedule 09.12.2012
comment
Стивен Тетли: Общая древовидная структура - хорошая идея, но, к сожалению, это означает, что я могу создать (случайно) недопустимое синтаксическое дерево (если я правильно понял идею). В моей первоначальной реализации дерева любое построенное дерево является действительным синтаксическим деревом для анализируемого языка.   -  person sergeyz    schedule 11.12.2012
comment
@sergeyz, я думаю, ты неправильно понял @stephentetley. Я полагаю, что он предлагал data Statement = IfStatement Expr Statement Statement | WhileStatement Expr Statement и т. д., что на самом деле гарантирует, что вы можете создавать действительные деревья только в большей степени, чем это представление.   -  person luqui    schedule 12.12.2012

Ответы (2)


arrow_upward
13
arrow_downward

Типичный способ, которым я прерываю циклы зависимостей, заключается в параметризации чего-либо. В этом случае ваш модуль Function может выполнять синтаксические анализаторы функций для вашего языка, но выражен таким образом, что он может делать это независимо от того, на что похож остальной язык. Таким образом:

module Function where 

data FunctionBody e = FunctionBody [e]

parseFunctionBody :: Parser e -> Parser (FunctionBody e)

И

module AST where

data SourceElement
    = StatementSourceElement Statement
    | FunctionSourceElement FunctionName (FunctionBody SourceElement)

Таким образом, взаимная рекурсия абстрагируется в простую рекурсию + параметризацию. Я думаю, что параметризация не менее важна, чем разделение разных вещей по разным файлам, поэтому приятно (и немного раздражает), что одно навязывает другое.

person luqui    schedule 09.12.2012
comment
Я согласен с важностью параметризации, но она должна быть осмысленной и продуманной, а не случайной. - person Roman Cheplyaka; 09.12.2012
comment
Я согласен с вами лишь частично. Я считаю, что весь код должен быть осмысленным и продуманным, а выбор параметризации не более или менее. Нужно попробовать, чтобы понять, как выглядит правильное решение. Я бы предпочел использовать несовершенно параметризованный модуль, чем тот, который связан с его контекстом - по крайней мере, в первом случае есть надежда на кого-то, кто имеет в виду другое использование, даже если это некоторая работа. В последнем случае вы облажались. - person luqui; 10.12.2012
comment
@luqui, я параметризовал свои исходные структуры данных и теперь у меня есть несколько новых модулей: Statement, Выражение. Плохо то, что это выглядит как-то неряшливо. - person sergeyz; 15.12.2012
comment
@sergeyz, да, это выглядит довольно грязно. Жаль, что нам приходится идти на этот компромисс в текущем Haskell — в течение долгого времени я хотел, чтобы разделы в стиле Coq делали высокопараметрические вещи более привлекательными. - person luqui; 15.12.2012

arrow_upward
6
arrow_downward

На самом деле Haskell позволяет использовать рекурсивные модули, а GHC их поддерживает (с небольшими неудобствами, связанными с записью .hs-boot файлов). См. Как компилировать взаимно рекурсивные модули.

Я не вижу ничего плохого в использовании этой функции здесь.

person Roman Cheplyaka    schedule 09.12.2012
comment
Я не думаю, что .hs-boot это незначительное неудобство. Количество неудобств заставило меня, по крайней мере, переключаться на другую стратегию каждый раз, когда я пытался это сделать. Возможно, это мой идеализм — мне кажется, что файлы .hs-boot должны легко генерироваться автоматически, поэтому я расстраиваюсь, когда мне приходится писать их самому. - person luqui; 10.12.2012
comment
Вы можете найти #1409 интересное чтение. - person Roman Cheplyaka; 10.12.2012