3

我有一个受歧视的工会，例如

type Dish = 
| Eggs
| Spam of Dish

这基本上是一个链表，没有任何内容，例如Spam(Spam(Spam(Eggs))). 我想对这个结构进行严格的计算，比如计算长度，并记住结果。在普通类型中，我会使用类本地let绑定，但这些在可区分的联合中不可用。

一种方法是， 

type Count = int
type Dish = 
| Eggs
| Spam of Dish * Count

但这真的很混乱，当我需要的数据很容易计算时，但我仍然希望有更好的方法（不使用外部可变结构）。

4

6 回答 6

4

一种选择是将联合案例设为私有以隐藏缓存的长度。

//the 'guts' of Dish -- entirely hidden
type private DishImpl = 
  | Eggs
  | Spam of DishImpl

// Dish wrapper type -- implementation hidden
type Dish = 
  private 
  | Dish of DishImpl * int
  with
    // O(1), just get the 'length' field
    member x.Length = let (Dish(_, len)) = x in len
    static member Eggs() = Dish(Eggs, 1)
    static member Spam(Dish(dish, len)) = Dish(Spam dish, len + 1)

let eggs = Dish.Eggs()
let spam = Dish.Spam(eggs)
printfn "%d" eggs.Length //outputs: 1
printfn "%d" spam.Length //outputs: 2

要做到这一点，请创建一个附带的模块，其中包含let-bound 函数和用于解构的活动模式。

于 2012-10-10T14:42:12.943 回答
3

如果你容忍一点内部可变状态，这里有一个memoize函数，它为每个函数创建一个字典：

let memoize f =
    let dict = Dictionary()
    fun n ->
        match dict.TryGetValue(n) with
        | (true, v) -> v
        | _ ->
            let res = f(n)
            dict.Add(n, res)
            res
// This function results in a warning though
let rec length = memoize (function Eggs -> 0 | Spam d -> 1 + length d)

由于隐藏了可变字典，因此该方法还不错。

一种纯粹的函数式方法可以Map用来保存值和一种State计算表达式来隐藏Map传递的值。请参阅此代码段以查看memoize计算表达式的外观。

于 2012-10-10T15:02:53.137 回答
3

还有备忘录功能，多型！拉尔夫·欣泽 (Ralph Hinze)（2000 年）。适应 F#：

type Dish =
    | Eggs
    | Spam of Dish

type DishTable<'T> =
    {
        Eggs : Lazy<'T>
        Spam : Lazy<DishTable<'T>>
    }

let rec tabulate (f: Dish -> 'T) : DishTable<'T> =
    {
        Eggs = lazy f Eggs
        Spam = lazy tabulate (f << Spam)
    }

let rec lookup (table: DishTable<'T>) (dish: Dish) : 'T =
    match dish with
    | Eggs -> table.Eggs.Value
    | Spam x -> lookup table.Spam.Value x

let memo (f: Dish -> 'T) : (Dish -> 'T) =
    lookup (tabulate f)

let rec len x =
    match x with
    | Eggs -> 0
    | Spam x -> 1 + len x

let l2 = memo len
于 2012-10-10T21:09:40.950 回答
2

这就是我想出的。这不是真正的 memoization，因为当您调用 mem 时它很重要，但可能会满足您的需求。

type Dish = 
| Eggs
| Spam of Dish 
| Memo of Dish * int
with 
    member d.length = 
        match d with 
        | Eggs        -> 1
        | Spam d      -> 1 + d.length
        | Memo (d, i) -> i
    member d.mem = 
        match d with 
        | Eggs        -> Memo(d, d.length)
        | Spam d2     -> Memo(d, d.length)
        | Memo(d2, i) -> d // no need to memo it again

let x = Spam (Spam(Spam Eggs))
let m = x.mem

x.length // val it : int = 4
m.length // val it : int = 4
于 2012-10-18T09:45:25.050 回答
1

在查看了答案之后，我决定使用一个对我来说似乎最不突兀的模型。我使用了一个修改过的对象来演示它如何在稍微复杂的场景中工作。

type StackDef<'a>(v : 'a, s : Stack<'a>) = 
    member val Length = s.Length + 1
    member val Inner = v, s 
and Stack<'a> = 
    | Empty
    | Stack of StackDef<'a>
    member this.Length = 
        match this with
        | Empty -> 0
        | Stack(def) -> def.Length

let Stack (v, s) = Stack(StackDef(v, s)) 
let (|Stack|Empty|) = function | Empty -> Empty | Stack(sd) -> Stack(sd.Inner)
//...
let example = Stack(1, Stack(2, Stack(3, Empty))).Length
  1. 它不包含任何外部可变状态。
  2. 有区别的联合Dish（或在示例中为Stack）继续存在。
  3. 该字段length根本没有出现在联合定义中，也没有由任何构造函数提供，就像它应该的那样。
  4. 记忆化的数据应该与实例相关联。

但是，考虑到这一点，通过使用像 Afterthought 这样的静态编织器，可能可以替换任何方法，例如：

Stack<'a> = 
    | Empty
    | Stack of 'a * Stack<'a>

    [<Lazy>] //custom attribute that would work with a static weaver
    member this.Length = 
        match this with
        | Empty -> 0
        | Stack(_, s) -> s.Length + 1

private readonly Lazy<int> __length在构造函数中使用执行上述代码的委托进行初始化，并将方法的实际内容更改为简单地调用__length.Value. 虽然 F# 不允许联合类型包含字段，但可能出于非常正当的原因，我非常怀疑 IL 会有这样的限制。
事实上，使用一些 IL 操作可以做很多事情。也许这是值得考虑的事情。

于 2012-10-12T12:30:37.627 回答
1

请注意，在您的情况下，从字面上看，您的类型值的唯一有趣属性是它的长度，因此您不妨只使用整数作为表示形式：

let Eggs = 0
let Spam n = 1 + n

let (|Eggs|Spam|) = function
| 0 -> Eggs
| n -> Spam(n-1)

let length = id

// example usage
let dish = Spam(Spam(Eggs))

let l = length dish

let kind =
    match dish with
    | Eggs -> "Eggs"
    | Spam(Eggs) -> "One Spam"
    | Spam(Spam _) -> "At least two Spams"

如果您真正的问题是如何为更有趣的类型执行此操作，那么一种方法是创建相互递归的类型，其中一个被注释：

type 'a AnnotatedDish = { dish : 'a Dish; value : 'a }
and 'a Dish =
| Eggs
| Spam of 'a AnnotatedDish

// "smart" constructors, given that you want to annotate with length
let eggs = { dish = Eggs; value = 0 }
let spam d = { dish = Spam d; value = 1 + d.value }

let length { value = l } : int = l

// active patterns
let (|Eggs|Spam|) = function
| { dish = Eggs } -> Eggs
| { dish = Spam d } -> Spam d


// example usage
let dish = spam(spam(eggs))

let l = length dish

let kind =
    match dish with
    | Eggs -> "Eggs"
    | Spam(Eggs) -> "One Spam"
    | Spam(Spam _) -> "At least two Spams"
于 2012-10-10T15:47:38.767 回答