3

私は次のような差別化された組合を持っています

type Dish = 
| Eggs
| Spam of Dish

これは基本的にリンクリストであり、コンテンツは含まれていませんSpam(Spam(Spam(Eggs)))。長さを数えるなど、この構造を厳密に計算して、その結果を記憶したいと思います。通常のタイプでは、クラスローカルletバインディングを使用しますが、それらは識別された共用体では使用できません。

これを行う1つの方法は、 

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

しかし、必要なデータが簡単に計算できる場合、これは本当に厄介ですが、それでも（外部の可変構造を使用せずに）より良い方法があることを願っています。

4

6 に答える 6

4

1つのオプションは、ユニオンケースをプライベートにして、キャッシュされた長さを非表示にすることです。

//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それを正しく行うには、バインドされた関数と破棄用のアクティブなパターンを備えた付属モジュールを作成します。

于 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

これが私が思いついたものです。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

あなたの場合、文字通りあなたのタイプの値の唯一の興味深いプロパティはその長さであることに注意してください、それであなたは代わりにあなたの表現として整数を使うほうがよいでしょう：

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"

あなたの本当の質問がより興味深いタイプに対してこれをどのように行うかである場合、1つのアプローチは相互再帰型を作成することであり、そのうちの1つに注釈が付けられています。

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 に答える
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 に答える