F# map 问题

Question

我在摸索 F# 的 Map 类时遇到问题。我创建了一个简单、朴素的 lambda 演算评估函数，

type Name = string
type Term =
    |   Var of Name 
    |   Lit of int
    |   App of Term * Term
    |   Lam of Name * Term

let rec lookup(v, e) =
    match e with
    |   (v1, t)::tl         -> if v1 = v then t else lookup(v, tl)
    |   []                  -> failwith "unknown variable %s" v

let rec eval(x, e) = 
    match x with
    |   Var x               -> lookup(x, e)
    |   Lit x               -> Lit x
    |   App (Lam(v, f), t2) -> eval(f, ((v, t2)::e))
    |   _                   -> failwith "Invalid"

对此的明显优化是将列表更改为 map ，所以我想出了，

let rec eval2(x, e: Map<Name,Term>) =
    match x with
    |   Var v               -> e.[v]
    |   Lit l               -> x
    |   App (Lam (v, f), t) -> eval2(f, e.Add(v, t))
    |   _                   -> failwith "Invalid term"

给定值，

let ident = Lam ("x", Var "x")
let prog = App (ident, Lit 3)

为什么会这样

let x = eval(prog, [])

成功了，但是，

let x2 = eval2(prog, Map [])

抛出未找到 key 异常？

Answer 1

我不会重现此行为(使用 F# 1.9.6.2，它对我有用):

#light

type Name = string
type Term =
    |   Var of Name
    |   Lit of int
    |   App of Term * Term
    |   Lam of Name * Term

let rec eval2(x, e: Map<Name,Term>) =
    match x with
    |   Var v               -> e.[v]
    |   Lit l               -> x
    |   App (Lam (v, f), t) -> eval2(f, e.Add(v, t))
    |   _                   -> failwith "Invalid term"

let ident = Lam ("x", Var "x")
let prog = App (ident, Lit 3)
let x2 = eval2(prog, Map [])
printfn "%A" x2   // Lit 3