如何在 F# 中表达可以选择自行递归（无限）的类型

发布于 2024-11-16 14:00:39 字数 1006 浏览 6 评论 0原文

作为学习练习，我试图为 graphviz 点语言实现一个解析器（DOT 语言) 使用函数解析器库 fparsec (FParsec)。该语言描述图形。

查看语言定义，我不得不写下以下定义：

let rec pstmt_list = opt(pstmt .>> opt(pchar ';') >>. opt pstmt_list)

其中 pstmt 和 pchar ';' 是解析器，.>> 和 >>. 将左解析器的出现与右解析器的出现组合起来，并且 opt 将其参数解析器的可选出现作为选项值进行解析。然而，这个定义不起作用，抱怨“......结果类型将是无限的......”。

通过查看上面链接的 DOT 语言，这个示例可能最容易理解。

我知道以下看似相关的问题：

但是我的如果它们适用于此，F# 知识可能还不足以翻译它们。

原文

As a learning exercise I am trying to implment a parser for the graphviz dot language (The DOT language) using the functional parser library fparsec (FParsec). The language describes graphs.

Looking at the language definition I was compelled to write down the following definition:

let rec pstmt_list = opt(pstmt .>> opt(pchar ';') >>. opt pstmt_list)

Where pstmt and pchar ';' are parsers, .>> and >>. combine an occurence of the left parser with an occurence of the right parser, and opt parsers an optional occurrence of its argument parser as an option value. However this definition does not work complaining "... the resulting type would be infinite ...".

This example is probably most easily understood by taking a look at the DOT language linked above.

I am aware of the following seemingly linked questions:

But my F# knowledge may not be sufficient to translate them yet, if they apply here at all.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

小耗子 2024-11-23 14:00:39

FParsec 提供了用于解析序列的特殊组合器。通常，您应该更喜欢这些组合器而不是使用递归函数重新实现它们。您可以在此处找到用于解析序列的可用组合器的概述：http ://www.quanttec.com/fparsec/reference/parser-overview.html#parsing-sequences

在此示例中，pstmt_list 是分隔的语句序列并可选择以分号结尾，因此您可以轻松地将解析器定义为

let pstmt_list = sepEndBy pstmt (pstring ";")

FParsec provides special combinators for parsing sequences. Normally you should prefer these combinators to reimplementing them with a recursive function. You can find an overview of the available combinators for parsing sequences here: http://www.quanttec.com/fparsec/reference/parser-overview.html#parsing-sequences

In this example pstmt_list is a sequence of statements separated and optionally ended by semicolons, so you could easily define the parser as

let pstmt_list = sepEndBy pstmt (pstring ";")

回复收藏 0 原文

面犯桃花 2024-11-23 14:00:39

问题是您的 pstmt_list 解析器会生成某种类型的某些值，但是当您在定义中使用它时，您会使用附加的 option 类型（使用opt 组合器）。

F# 编译器认为解析器返回的值的类型，例如 'a 应该与包装类型 option 'a 相同（当然，这不是可能的）。

无论如何，我不认为这正是您需要做的 - .>> 组合器创建一个解析器，返回第二个参数的结果，这意味着您将忽略到目前为止解析的所有 pstmt 结果。

我认为您可能需要这样的东西：

let rec pstmt_list : Parser<int list, unit> = 
  parse.Delay(fun () ->
    opt(pstmt .>> pchar ';') .>>. opt pstmt_list
    |>> (function Some(prev), Some(rest) -> prev::rest
                | Some(prev), _ -> [prev]
                | _, Some(rest) -> rest
                | _ -> [] ))

Delay 的额外用途是避免声明直接引用自身的值。

The problem is that your pstmt_list parser produces some values of some type, but when you use it in the definition, you wrap the values of this type with additional option type (using the opt combinator).

The F# compiler thinks that the type of the values returned by the parser e.g. 'a should be the same as the wrapped type option 'a (which is, of course, not possible).

Anyway, I don't think that this is quite what you need to do - the .>> combinator creates a parser that returns the result of the second argument, which means that you'll be ignoring all the results of pstmt parsed so far.

I think you probably need something like this:

let rec pstmt_list : Parser<int list, unit> = 
  parse.Delay(fun () ->
    opt(pstmt .>> pchar ';') .>>. opt pstmt_list
    |>> (function Some(prev), Some(rest) -> prev::rest
                | Some(prev), _ -> [prev]
                | _, Some(rest) -> rest
                | _ -> [] ))

The additional use of Delay is to avoid declaring a value that refers directly to itself.

回复收藏 0 原文

~没有更多了~