时间戳

首页 > 解决方案 > F# 和递归问题

recursion - F# 和递归问题

问题描述

我有两个问题，一个与编译器的行为有关，一个是我简单地让我对自己的代码视而不见，需要一些帮助来进行错误跟踪

对不起，相当大的代码块。

第一个问题 Right 函数将编译，因为它确实遵循类型系统，但在运行时它会抛出堆栈溢出。

RightAssociative 不会抛出堆栈溢出有什么区别？

第二个问题：下面的测试返回“abbaa”而不是“abba”，我已将其添加到 RightAssociative 函数中，即使它以“Or”（<|>）的单个部分结尾仍然使用地图

let  error msg = 
    sprintf "Parsing error:\t\n%s" msg
    |> Error

type 'I Iter =
    abstract member Next : Result<'I,string> 
    abstract member Prev : unit              
    abstract member Show : unit // print for debugging

type  Parser<'output> = Parser of (char Iter -> Result<'output, string>)


let  run (Parser p) = p

let inline Atom expects =
    fun (input : char Iter) ->
        match input.Next with
        | Ok a when expects a ->
            Ok (string a)
        | Ok a ->
            input.Prev 
            sprintf "faild to parse %A" a
            |> error
        
        | Error msg -> 
            input.Prev
            msg 
            |> error
    |> Parser

let Or pat1 pat2 =
    fun input ->
        match run pat1 input with
        | Ok a -> Ok a 
        | Error _ ->
            match run pat2 input with
            | Ok a -> Ok a
            | Error msg -> 
                Error msg
    |> Parser

let  (<|>) = Or 


let And pat1 pat2 =
    fun input ->
        match run pat1 input with
        | Error msg -> Error msg
        | Ok a1 ->            
            match run pat2 input with
            | Ok a2 -> Ok (a1,a2)
            | Error msg -> 
                input.Prev
                Error msg
    |> Parser   

let ( <&> ) = And

let  Map f pat =
    fun input ->
        match run pat input with
        | Error msg -> Error msg 
        | Ok ret -> Ok (f ret)
    |> Parser

let rec Right pattern = pattern <&> (Right pattern) |> Map (fun (x : string, y) -> x + y) <|> pattern

let rec RightAssociative parser =
    let rec right (input: char Iter) = 
        (Map (fun (reg1 : string, reg2) -> reg1 + reg2) (parser <&> (Parser right))) <|> parser
        |> fun pattern -> run pattern input
    
    Parser right 
    

let aOrb = Atom (fun x -> x = 'a') <|> Atom (fun x -> x = 'b')

type iter =
    {   
        mutable prevs : char list
        mutable buffer : char list 
    }
with
    interface char Iter with
        member I.Next = 
            let n = List.tryHead I.buffer
            match n with 
            | None -> Error "reach end of stream"
            | Some c ->
                I.buffer <- I.buffer.Tail
                I.prevs <- c :: I.prevs
                Ok c
        
        member I.Prev =
            let p = List.tryHead I.prevs
            match p with
            | Some p -> 
                 I.buffer <- p :: I.buffer
                 I.prevs <- I.prevs.Tail
            | None -> ()

        member I.Show =
            printfn "prevs: %A" I.prevs
            printfn "buffer: %A" I.buffer

let right = RightAssociative aOrb
let test = { prevs = []; buffer = [for c in "abba" -> c] }

[<EntryPoint>]
let main _ =
    match run right test with
    | Ok(asAndbs) -> printfn "Test passed with %s" asAndbs
    | Error(msg) -> printfn "Test on right failed with %s" msg

    1

标签： recursionf#

解决方案

要回答您的第一个问题，问题是Right无条件地Right递归调用。这是因为在调用之前需要评估左右参数<&>：

let rec Right pattern = 
  pattern <&> Right pattern // <-- Calls 'Right' unconditionally here
  |> Map (fun (x : string, y) -> x + y) <|> pattern

您可以通过定义一个帮助器来解决此问题，该帮助器Delay将调用包装在一个函数中，并且仅在使用某些输入实际调用它时才获取解析器：

let Delay f = 
  Parser(fun i -> 
    let (Parser p) = f() 
    p i)

let rec Right pattern = 
  pattern <&> (Delay (fun () -> Right pattern))
  |> Map (fun (x : string, y) -> x + y) <|> pattern

我不确定第二个问题，但它与递归无关 - 你的<&>和<|>运算符一定有问题。尝试以下操作：

let right = (aOrb <&> (aOrb <|> aOrb))
let test = { prevs = []; buffer = ['a'] }
run right test

这成功并返回("a", "a")，这对我来说听起来不正确。如果您aOrb <|> aOrb在上面替换为 just aOrbthen 解析器会按预期失败，所以我怀疑存在一些与<|>.

推荐阅读