Ich muss aber zugeben - eine praktische Anwendung wird es wohl kaum geben. Ich betrachte es als meiner eigene Haskell Cargo-Kult.
Hier so zu sagen Standart-F# Memoization Pattern und Monadic Memoization.
Da es in F# keine Typklasse gibt, könnte man mit einem abstrakten Interface kleine Abhilfe schaffen.
type ITable<'a,'w> =
abstract inline Table : ITable<'a,'w>
type BoolTable<'w> =
| BTable of Lazy<'w> * Lazy<'w>
interface ITable<bool,'w> with
member inline x.Table = x :> ITable<_,_>
//(bool -> 'a) -> BoolTable<'a>
let boolToTable f = BTable (lazy(f true), lazy(f false))
//BoolTable<'a> -> bool -> 'a
let boolFromTable (BTable (x,y)) b =
if b then x.Force() else y.Force()Weiter zitiere ich einfach aus dem Artikel (http://research.microsoft.com/en-us/um/people/simonpj/papers/assoc-types/fun-with-type-funs/typefun.pdf).
" To memoise a function f :: bool -> Int, we simply replace it by g:
g :: Bool -> Int
g = fromTable (toTable f)
The first time g is applied to True, the Haskell implementation computes
the first component of the lazy pair (by applying f in turn to True) and
remembers it for future reuse. Thus, if f is defined by
f True = factorial 100
f False = fibonacci 100
then evaluating (g True + g True) will take barely half as much time as
evaluating (f True + f True). "
let boolFunc b =
match b with
| true ->
printfn "true. Value = 10"
10
|false ->
printfn "false. Value = 5"
5val boolFunc : bool -> int > let memoized= boolFromTable (boolToTable boolFunc) val memoized : (bool -> int) > let res = memoized(true) + memoized(true) + memoized(false) + memoized(false) true. Value = 10 false. Value = 5 val res : int = 30
" Generalising the Memo instance for Bool above, we can memoise functions
from any sum type, such as the standard Haskell type Either:
data Either a b = Left a | Right b
We can memoise a function from Either a b by storing a lazy pair of a
memo table from a and a memo table from b. That is, we take advantage
of the isomorphism between the function type Either a b -> w and the
product type (a -> w, b -> w). "
type Either<'a,'b>=
|Left of 'a
|Right of 'b
type SumTable<'t1,'t2,'a,'b,'w when 't1:> ITable<'a,'w> and 't2:> ITable<'b,'w>> =
| STable of 't1 * 't2
interface ITable<Either<'a,'b>,'w> with
member inline x.Table = x :> ITable<Either<'a,'b>,'w>Leider unterstützt F# auch keine "type function". Also die entsprechende Funktionen müssen explizit übergeben werden.// sumToTable : (('a -> 'b) -> 'c) -> (('f -> 'b) -> 'g) -> (Either<'a,'f> -> 'b) ->
// SumTable<'c,'g,'d,'h,'e>
// when 'c :> ITable<'d,'e> and 'g :> ITable<'h,'e>
let sumToTable fa fb f=
STable (fa (f<<Left), fb (f<<Right))
// sumFromTable : ('a -> 'd -> 'e) -> ('f -> 'h -> 'e) -> SumTable<'a,'f,'b,'g,'c> ->
// Either<'d,'h> -> 'e
// when 'a :> ITable<'b,'c> and 'f :> ITable<'g,'c>
let sumFromTable fa fb tbl e =
match tbl, e with
| STable (t, _), Left v -> fa t v
| STable (_, t), Right v -> fb t v
let eitherFunc e =
match e with
| Left a ->
printfn "eitherFunc Left %A" a
(boolFunc a) - 3
| Right b ->
printfn "eitherFunc Right %A" b
(boolFunc b) * 2val eitherFunc : Either<bool,bool> -> int > let memoized= sumFromTable boolFromTable boolFromTable (sumToTable boolToTable boolToTable eitherFunc);; val memoized : (Either<bool,bool> -> int) > let res = memoized(Left true) + memoized(Left true) + memoized(Right false) + memoized(Right false);; eitherFunc Left true true. Value = 10 eitherFunc Right false false. Value = 5 val res : int = 34
" Dually, we can
memoise functions from the product type (a,b) by storing a memo table
from a whose entries are memo tables from b. That is, we take advantage
of the currying isomorphism between the function types (a,b) -> w and
a -> b -> w. "
type ProductTable<'t1,'t2,'a,'b,'w when 't1 :> ITable<'b,'w> and 't2 :> ITable<'a,'t1> > =
| PTable of 't2
interface ITable<'a * 'b,'w> with
member inline x.Table = x :> ITable<('a * 'b),'w>
// productToTable : (('a -> 'b) -> 'c) -> (('d -> 'c) -> 'e) -> ('d * 'a -> 'b) ->
// ProductTable<'g,'e,'f,'h,'i>
// when 'e :> ITable<'f,'g> and 'g :> ITable<'h,'i>
let productToTable fa fb f=
let p = fb (fun a -> fa (fun b -> f (a, b)))
PTable p
// productFromTable: ('a -> 'b -> 'c) -> ('d -> 'i -> 'a) -> ProductTable<'f,'d,'e,'g,'h> ->
// 'i * 'b -> 'c
// when 'd :> ITable<'e,'f> and 'f :> ITable<'g,'h>
let productFromTable fa fb tbl p =
match tbl,p with
| PTable t,(a,b)-> fa (fb t a) b
let productFunc pair =
let x=
printfn "productFunc first"
(boolFunc (fst pair))-3
let y =
printfn "productFunc second "
(boolFunc (snd pair))*2
x + y
let productEitherFunc (e, b) =
let x =
printfn "productEitherFunc first %A" e
(eitherFunc e) - 3
let y =
printfn "productEitherFunc second %A" b
(boolFunc b) * 2
x + y
val productFunc : bool * bool -> int val productEitherFunc : Either<bool,bool> * bool -> int > let memoized = productFromTable boolFromTable boolFromTable (productToTable boolToTable boolToTable productFunc);; val memoized : (bool * bool -> int) > let res = memoized (true, true) + memoized (true, true);; productFunc first true. Value = 10 productFunc second true. Value = 10 val res : int = 54 > let res = memoized (true, true) + memoized (false, false);; productFunc first false. Value = 5 productFunc second false. Value = 5 val res : int = 39 > let memoized = productFromTable boolFromTable (sumFromTable boolFromTable boolFromTable) (productToTable boolToTable (sumToTable boolToTable boolToTable) productEitherFunc);; val memoized : (Either<bool,bool> * bool -> int) > let res = memoized (Left true, true) + memoized (Left true, true);; productEitherFunc first Left true eitherFunc Left true true. Value = 10 productEitherFunc second true true. Value = 10 val res : int = 48 > let res = memoized (Left true, true) + memoized (Right false, false) + memoized (Left true, true);; productEitherFunc first Right false eitherFunc Right false false. Value = 5 productEitherFunc second false false. Value = 5 val res : int = 65
Leider ist mir nicht gelungen Memoization für rekursive Typen zu schreiben und ich vermute stark, dass dies in F# gar nicht möglich ist.
