英文:
Pattern(s) to avoid mutual recursion between functions and other objects?
问题
以下是已翻译的内容:
我正在开始编写一个玩具命令行数据存储器,只是为了好玩。我目前正在将我的解释器的所有命令存储在一个映射中,将命令的字符串名称作为键,将要执行的方法作为其值。然而,DisplayHelp
命令需要从 Commands
的 Map
中引用自己。DisplayHelp
方法、Commands
Map 和 InterpCommand
代码都如下所示:
let private DisplayHelp (shellState : ShellState) =
printfn "Available commands: "
Commands // <- 这是相互递归引用发生的地方
|> Map.map (fun k _ -> printfn "%s" k)
|> ignore
shellState
let private Commands =
[
"exit", Exit
"help", DisplayHelp // <- 这是另一个相互引用递归发生的地方
"store", StoreItem
"list", ListItems
]
|> Map.ofList
let private InterpCommand (shellState : ShellState) =
let nextState =
match Commands.Keys.Contains shellState.Command with
| true ->
shellState
|> Commands[shellState.Command]
| false ->
shellState
|> DisplayUnrecognizedCommand
// 返回
nextState
|> ResetStateInputs
正如您所看到的,DisplayHelp
方法和 Commands
映射之间存在相互递归。我尝试使用 and
关键字来相互定义它们,但似乎这是不良实践。在这里应该使用的正确模式是什么,或者问题本身是否以完全不同的方式解决了?
英文:
I'm starting to write a toy command line datastore for fun. I am currently storing all of my interpreter's commands in a map which maps the string name of the command as the key, and the method to execute as its value. However, the DisplayHelp
command needs to reference itself from the Map
of Commands
. The DisplayHelp
method, the Commands
Map, and the InterpCommand
code all looks like this:
let private DisplayHelp (shellState : ShellState) =
printfn "Available commands: "
Commands // <- This is where mutual recursive reference occurs
|> Map.map (fun k _ -> printfn "%s" k)
|> ignore
shellState
let private Commands =
[
"exit", Exit
"help", DisplayHelp // <- This is the other place where mutual reference recursion occurs
"store", StoreItem
"list", ListItems
]
|> Map.ofList
let private InterpCommand (shellState : ShellState) =
let nextState =
match Commands.Keys.Contains shellState.Command with
| true ->
shellState
|> Commands[shellState.Command]
| false ->
shellState
|> DisplayUnrecognizedCommand
// return
nextState
|> ResetStateInputs
As you can see, the mutual recursion happens between the DisplayHelp
method and the Commands
map. I was attempting to use the and
keyword to mutually define these but it seems like bad practice. What is the correct pattern to use here, or is the problem itself solved in a completely different manner?
答案1
得分: 1
以下是您要翻译的内容:
You can get rid of mutual recursion by using the approach suggested by @Fyodor Soikin, that it by abstracting concrete reference by introducing parameter for it. In our case - to abstract reference to Commands
from function DisplayHelp
:
let private DisplayHelp(shellState : ShellState, commands) = // introduce parameter commands
printfn "Available commands: "
commands
|> Map.map(fun k _->printfn "%s" k)
|> ignore
shellState
let rec private Commands =
[
"exit", Exit
"help", fun state -> DisplayHelp(state, Commands) // pass Commands to DisplayHelp as parameter
"store", StoreItem
"list", ListItems
]
|> Map.ofList
From theoretical standpoint it might also be interesting to eliminate recursion from Commands
definition. As an option, it can be done by using Fixed-point combinator. The idea is to introduce additional parameter (f
) to target function (createCommands
), which should be used instead of recursive calls. In this case it is required to wrap the target function (createCommands
) into fixed-point combinator (fix
). The function fix is recursive itself (at least in F# implementation) but it can be used universally to eliminate any kind of recursion in general way:
// Declare fixed point combinator
let rec fix' f = lazy f (fix' f)
let fix f = (fix' f).Value
let private DisplayHelp(shellState : ShellState, commands) =
printfn "Available commands: "
commands
|> Map.map(fun k _->printfn "%s" k)
|> ignore
shellState
let private createCommands (f: Lazy<_) () = // transform value to non-recursive function and add f parameter for self referncing
[
"exit", Exit
"help", fun state -> DisplayHelp(state, f.Value ()) // call f function (unwrapped from lazy) insted of recursive call
"store", StoreItem
"list", ListItems
]
|> Map.ofList
let Commands = fix createCommands () // wrap function with fixed point combinator and call it
英文:
You can get rid of mutual recursion by using the approach suggested by @Fyodor Soikin, that it by abstracting concrete reference by introducing parameter for it. In our case - to abstract reference to Commands
from function DisplayHelp
:
let private DisplayHelp(shellState : ShellState, commands) = // introduce parameter commands
printfn "Available commands: "
commands
|> Map.map(fun k _->printfn "%s" k)
|> ignore
shellState
let rec private Commands =
[
"exit", Exit
"help", fun state -> DisplayHelp(state, Commands) // pass Commands to DisplayHelp as parameter
"store", StoreItem
"list", ListItems
]
|> Map.ofList
From theoretical standpoint it might also be interesting to eliminate recursion from Commands
definition. As an option, it can be done by using Fixed-point combinator. The idea is to introduce additional parameter (f
) to target function (createCommands
), which should be used instead of recursive calls. In this case it is required to wrap the target function (createCommands
) into fixed-point combinator (fix
). The function fix is recursive itself (at least in F# implementation) but it can be used universally to eliminate any kind of recursion in general way:
// Declare fixed point combinator
let rec fix' f = lazy f (fix' f)
let fix f = (fix' f).Value
let private DisplayHelp(shellState : ShellState, commands) =
printfn "Available commands: "
commands
|> Map.map(fun k _->printfn "%s" k)
|> ignore
shellState
let private createCommands (f: Lazy<_>) () = // transform value to non-recursive function and add f parameter for self referncing
[
"exit", Exit
"help", fun state -> DisplayHelp(state, f.Value ()) // call f function (unwrapped from lazy) insted of recursive call
"store", StoreItem
"list", ListItems
]
|> Map.ofList
let Commands = fix createCommands () // wrap function with fixed point combinator and call it
答案2
得分: 1
我决定采纳@Fyodor Soikin的评论,但最终还是使用了一些递归定义,因为这有助于减少复杂性并为更灵活性铺平道路。@Gennadii Saltyshchak的答案确实很有趣,但经过一些思考,将ShellCommands
打包到ShellState
记录中还可以跟踪类似ShellConfig
的东西,其中某些命令可以切换各种配置标志,可以禁用命令等(这显然要求每个ShellCommand
最终都被转化为具有文本名称和可能有自己帮助信息的记录/对象类型,更加面向对象的编程范式)。我最终得到的代码没有避免递归,但仍然比我最初尝试创造的要更清晰。以下是代码:
type private ShellCommand = ShellState -> ShellState
and private ShellState =
{
PromptInput: string
Command: string
Arguments: string list
ItemsStored: string list
Running: bool
AvailableCommands: Map<string, ShellCommand>
}
with
static member init(availableCommands: Map<string, ShellCommand>) : ShellState =
{
PromptInput = ""
Command = ""
Arguments = []
ItemsStored = []
Running = true
AvailableCommands = availableCommands
}
/// ... 省略 ...
let private DisplayUnrecognizedCommand : ShellCommand = fun shellState ->
eprintf $"Command not recognized: {shellState.Command}"
shellState
let private DisplayHelp : ShellCommand = fun shellState ->
printfn "Available commands: "
shellState.AvailableCommands
|> Map.map (fun k _ -> printfn "%s" k)
|> ignore
shellState
let private InterpCommand (shellState : ShellState) =
let nextState =
match shellState.AvailableCommands.Keys.Contains shellState.Command with
| true ->
shellState
|> shellState.AvailableCommands[shellState.Command]
| false ->
shellState
|> DisplayUnrecognizedCommand
// 返回
nextState
|> ResetStateInputs
let private Prompt (shellState: ShellState) =
printf "> "
let input = Console.ReadLine().Trim()
{ shellState with
PromptInput = input }
let rec private Run (shellState : ShellState) =
if(shellState.Running) then
shellState
|> Prompt
|> ParseInput
|> InterpCommand
|> Run
else
()
let private AvailableCommands =
[
"exit", Exit
"help", DisplayHelp
"store", StoreItem
"list", ListItems
]
|> Map.ofList
let StartShell () =
Run(ShellState.init(AvailableCommands))
(然而,由于我没有避免递归,正如我在原始问题中所要求的那样,我将接受其他答案作为正确答案 :))
英文:
I decided to take @Fyodor Soikin 's comment but still ended up using some recursive definition because it cuts down on complexity and paves the way for more flexibility. @Gennadii Saltyshchak 's answer is really interesting, but after some thought, packing ShellCommands
into the ShellState
record paves the way to also keep track of something like a ShellConfig
where certain commands can flip various config flags on and off, commands can be disabled, etc (this obviously asks that each ShellCommand
be turned eventually into a record/object type of its own with text names and perhaps their own help info as well, moving in a somewhat more OOP paradigm). The code I ended up with did not avoid recursion, but it is still cleaner than what I was originally trying to carve out. Here's the code:
type private ShellCommand = ShellState -> ShellState
and private ShellState =
{
PromptInput: string
Command: string
Arguments: string list
ItemsStored: string list
Running: bool
AvailableCommands: Map<string, ShellCommand>
}
with
static member init(availableCommands: Map<string, ShellCommand>) : ShellState =
{
PromptInput = ""
Command = ""
Arguments = []
ItemsStored = []
Running = true
AvailableCommands = availableCommands
}
/// ... snip ...
let private DisplayUnrecognizedCommand : ShellCommand = fun shellState ->
eprintf $"Command not recognized: {shellState.Command}"
shellState
let private DisplayHelp : ShellCommand = fun shellState ->
printfn "Available commands: "
shellState.AvailableCommands
|> Map.map (fun k _ -> printfn "%s" k)
|> ignore
shellState
let private InterpCommand (shellState : ShellState) =
let nextState =
match shellState.AvailableCommands.Keys.Contains shellState.Command with
| true ->
shellState
|> shellState.AvailableCommands[shellState.Command]
| false ->
shellState
|> DisplayUnrecognizedCommand
// return
nextState
|> ResetStateInputs
let private Prompt (shellState: ShellState) =
printf "> "
let input = Console.ReadLine().Trim()
{ shellState with
PromptInput = input }
let rec private Run (shellState : ShellState) =
if(shellState.Running) then
shellState
|> Prompt
|> ParseInput
|> InterpCommand
|> Run
else
()
let private AvailableCommands =
[
"exit", Exit
"help", DisplayHelp
"store", StoreItem
"list", ListItems
]
|> Map.ofList
let StartShell () =
Run(ShellState.init(AvailableCommands))
(However since I did not avoid recursion as I had asked in the original question, I'll accept the other answer as the right one
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论