Seiten

Donnerstag, 2. Februar 2012

F# Transaction Monad. Examples.

Ich habe jetzt bei der Arbeit so ein Fall, wo Transaction Monad alternativ zur aktuellen Programmlogik eingesetzt werden könnte, vorausgesetzt wir verwenden F#.
Es sind zwei unterschiedliche Datenbanksysteme im Einsatz und die Programmlogik sollte für die richtige Transaktionabwicklung sorgen.
Daraus ergeben sich zwei Transaktion Fällen.

1. Innere Transaktion.

open TransactionM.Type
open TransactionM.Builder
open TransactionM.Helpers
open System.Data
open System.Data.SqlClient
open System.Threading.Tasks


type Params = {conn : SqlConnection; statements : string list; simulateCancel : bool}
type Either<'a,'b> = 
    | Result of 'a
    | Fail of 'b

let dbCommit (tr:SqlTransaction) =
    tr.Commit()
    tr

let dbRollback (tr:SqlTransaction) =
    tr.Rollback()
    tr

let beginDBTransaction (cnn:SqlConnection) cancel = 
    match cancel with
    | false -> cnn.BeginTransaction()
    | true -> failwith "error beginDBTransaction"

//check : string -> string -> string -> string -> seq<'a * 'b>
// select data from table to the seq.
let inline check dataSource db userId pswd = seq{
    let connStr =   
        new SqlConnectionStringBuilder(DataSource = dataSource,
                InitialCatalog = db, UserID = userId, Password = pswd)
    use conn = new SqlConnection(connStr.ConnectionString)
    conn.Open()
    use comm = new SqlCommand("SELECT Value1, Value2 FROM TEST_TABLE", conn)
    use reader = comm.ExecuteReader()
    while reader.Read() do
        yield unbox reader.["Value1"], unbox reader.["Value2"] }

let inline execNonQuery conn tr s=
    use comm = new SqlCommand(s, conn, tr)
    let res = comm.ExecuteNonQuery() 
    res

let inline deleteAll dataSource db userId pswd = 
    let connStr =   
        new SqlConnectionStringBuilder(DataSource = dataSource,
                InitialCatalog = db, UserID = userId, Password = pswd)
    use conn = new SqlConnection(connStr.ConnectionString)
    conn.Open()
    use comm = new SqlCommand("DELETE FROM TEST_TABLE", conn)
    comm.ExecuteNonQuery()    

//createTransaction: Params -> TransactionM<'a,'b,TransactionState<string,SqlTransaction>>
let createTransaction p =
    transaction {
                    try 
                        let tr = beginDBTransaction p.conn p.simulateCancel
                        try
                            match Seq.forall (((<) 0) << execNonQuery p.conn tr) p.statements with
                            | true -> 
                                return Commit tr
                            | false ->                
                                return Rollback tr
                        with
                        | e ->   
                            printfn " catch %A" (e.Message)
                            return Rollback tr
                    with
                        | e ->   
                            printfn " catch %A" (e.Message)
                            return Abort (Some e.Message)
                }

//createTransactionWithResult: Params -> TransactionM<'a,'b,TransactionState<string,(SqlTransaction * int)>>
let createTransactionWithResult p  = transaction {
        try 
            let tr = beginDBTransaction p.conn p.simulateCancel
            try
                let l = List.map (execNonQuery p.conn tr) p.statements
                match Seq.forall ((<) 0) l with
                | true -> 
                    return Commit (tr, List.rev l |> List.head)
                | _ ->             
                    return Rollback (tr, 0)
            with
            | e ->   
                printfn " catch %A" (e.Message)
                return Rollback (tr, 0)
        with
            | e ->   
                printfn " catch %A" (e.Message)
                return Abort (Some e.Message)

    }

//createOuterTransaction: 
//  TransactionM<'a,'b,TransactionState<'c,('d * 'e)>> -> 
//      Params -> 
//          TransactionHandle<'a,'b,TransactionState<string,(Either<SqlTransaction,'f> * Either<'d,'c option>)>> -> 
//              TransactionM<'a,'b,('g -> 'g)>
let createOuterTransaction inner parms handle =
    transaction 
        {
            try
                //begin outer DB transaction.
                let outer = (beginDBTransaction parms.conn parms.simulateCancel)
                try
                    // start statement from outer transaction. 
                    match execNonQuery parms.conn outer (parms.statements.Item 0)  with
                    | r when r > 0 -> 
                        //get inner transaction monad.
                        let! innerTransactionState = inner
                        match innerTransactionState with
                        | Commit (innerTransaction, result) -> 
                            // final statement from outer transaction.
                            match execNonQuery parms.conn outer ((parms.statements.Item 1).Replace("$$", result.ToString())) with
                            |  r when r > 0 -> 
                                //commit outer and inner transaction.
                                return! commit handle (Result outer, Result innerTransaction)
                            | _ -> 
                                return! rollback handle (Result outer, Result innerTransaction)
                        | Abort m ->
                            return! rollback handle (Result outer, Fail m)
                        | Rollback (innerTransaction, _) -> 
                            return! rollback handle (Result outer, Result innerTransaction)
                        | _ ->
                            return! rollback handle (Result outer, Fail None)
                    | _ -> 
                        return! rollback handle (Result outer, Fail None)
                with
                | e ->   
                    printfn " catch outer %A" (e.Message)
                    return! rollback handle (Result outer, Fail None)
            with
            | e ->   
                printfn " catch %A" (e.Message)
                return! abort handle (Some e.Message)
        }
//runOuterInnerTransaction : string list -> bool -> string list -> bool -> string
let runOuterInnerTransaction innerStatements innerCancel outeStatements outerCancel =
    let connStr =   
        new SqlConnectionStringBuilder(DataSource = "SOURCE1",
                InitialCatalog ="TESTDB",UserID="USER",Password="PWD")
    let connStr1 =   
        new SqlConnectionStringBuilder(DataSource = "SOURCE2",
                InitialCatalog ="TESTDB",UserID="USER",Password="PWD")
    use con = new SqlConnection(connStr.ConnectionString)
    con.Open()

    use con1 = new SqlConnection(connStr1.ConnectionString)
    con1.Open()

    let innerTr = createTransactionWithResult {conn     =       con ; 
                            statements =     innerStatements;
                            simulateCancel = innerCancel }  
    let outerTr = beginT (createOuterTransaction innerTr {conn     =       con1 ; 
                                                           statements =     outeStatements;
                                                           simulateCancel = outerCancel })
    match runTransactionState outerTr () with
    | Commit (Result outer, Result inner)-> 
        dbCommit inner |> ignore
        dbCommit outer |> ignore  
        "commit."
    | Rollback (Result outer, Result inner)-> 
        dbRollback inner |> ignore
        dbRollback outer |> ignore
        "rollback inner and outer."
    | Rollback (Result outer, Fail (Some m)) ->
        dbRollback outer |> ignore
        "rollback outer." + m
    | Rollback (Result outer, Fail None) ->
        dbRollback outer |> ignore
        "rollback outer." 
    | Rollback (Fail _, Result inner) ->
        failwith "rollback inner without outer."  
    | Abort (Some message) -> 
        message + " abort outer." 
    | Abort None ->
        "abort outer." 
    | _ -> failwith "error."
2. Parallele Transaktionen.
//parallelTasksTransaction : Params -> Params -> bool * string
let parallelTasksTransaction p1 p2 =
    let task p = Task.Factory.StartNew(fun () -> runTransactionState (createTransaction p) ())
    let tasks = [task p1; task p2] |> List.toArray
    let result = 
        Task.Factory.ContinueWhenAll(
                    tasks,
                    (fun (ts:Task<TransactionState<string, SqlTransaction>> []) -> 
                        match ts.[0].Result, ts.[1].Result with
                        | Commit t1, Commit t2 -> 
                            dbCommit t1|>ignore
                            dbCommit t2|>ignore
                            true, "commit."
                        | Commit t1, Rollback t2 -> 
                            dbRollback t1|>ignore
                            dbRollback t2|>ignore
                            false, "rollback. (commit task 1, rollback task 2)"
                        | Rollback t1, Commit t2 -> 
                            dbRollback t1|>ignore
                            dbRollback t2|>ignore
                            false, "rollback. (rollback task 1, commit task 2)"
                        | Rollback t1, Rollback t2 -> 
                            dbRollback t1|>ignore
                            dbRollback t2|>ignore
                            false, "rollback. (rollback task 1, rollback task 2)"
                        | Rollback t1, Abort (Some m) -> 
                            dbRollback t1|>ignore
                            false, "rollback. (rollback task 1, abort task 2)" + m
                        | Abort (Some m), Rollback t2 -> 
                            dbRollback t2|>ignore    
                            false, "rollback. (abort task 1, rollback task 2)." + m
                        | Commit t1, Abort (Some m) -> 
                            dbRollback t1|>ignore
                            false, "rollback. (Commit task 1, abort task 2)" + m
                        | Abort (Some m), Commit t2 -> 
                            dbRollback t2|>ignore    
                            false, "rollback. (abort task 1, Commit task 2)." + m
                        | Abort (Some m1), Abort (Some m2) ->   
                            false, "abort." + m1 + ". " + m2
                        | _ -> failwith "execution error."))
    result.Result

//runParallelTasksTransaction : string list -> bool -> string list -> bool -> bool * string
let runParallelTasksTransaction statements1 cancel1 statements2 cancel2= 
    let connStr =   
        new SqlConnectionStringBuilder(DataSource = "SOURCE1",
                InitialCatalog ="TESTDB",UserID="USER",Password="PWD")
    let connStr1 =   
        new SqlConnectionStringBuilder(DataSource = "SOURCE2",
                InitialCatalog ="TESTDB",UserID="USER",Password="PWD")
    use con = new SqlConnection(connStr.ConnectionString)
    con.Open()

    use con1 = new SqlConnection(connStr1.ConnectionString)
    con1.Open()
    parallelTasksTransaction {conn = con; statements = statements1; simulateCancel = cancel1} 
                             {conn = con1 ; statements = statements2; simulateCancel = cancel2}
Ein Paar Tests.
//test : ('a -> 'b -> 'c -> 'd -> 'e) -> 'a -> 'b -> 'c -> 'd -> unit
let test f a b c d =
    deleteAll "SOURCE1" "TESTDB" "USER" "PWD" |>ignore
    deleteAll "SOURCE2" "TESTDB" "USER" "PWD"  |>ignore
    let res = f a b c d
    let check1 = check "SOURCE1" "TESTDB" "USER" "PWD"
    let check2 = check "SOURCE2" "TESTDB" "USER" "PWD"
    printfn "result: %A" res
    printfn "check data in db1: %A" check1
    printfn "check data in db2: %A" check2
    printfn "%s" (String.replicate 30 "+")

printfn "%s" (String.replicate 50 "-")
printfn "run inner transaction tests."
printfn "test Commit." 
test runOuterInnerTransaction ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (2, 'start inner 2') ";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (3, 'start inner 3')";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (2, 'start inner 4')";
                               "UPDATE TEST_TABLE  SET Value1 = 5, Value2 ='end inner 5'  WHERE Value1 =2"] 
                              false
                              ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (10, 'start outer')";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES ($$, 'end outer. inner updated $$.') " ] 
                              false
printfn "test Rollback 1." 
test runOuterInnerTransaction ["INSERT INTO NONE"] 
                              false
                              ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (10, 'outer 10')";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (20, 'outer 20') " ] 
                              false


printfn "test Rollback 2." 
test runOuterInnerTransaction ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (2, 'inner 2') "] false
                              ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (10, 'outer 10')";
                               "INSERT INTO NONE " ] false
// simulate error in BeginTransaction.
printfn "test Abort inner." 
test runOuterInnerTransaction ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (2, 'inner 2') "] true
                              ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (10, 'outer 10')";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (20, 'outer 20') " ] false
// simulate error in BeginTransaction.
printfn "test Abort outer." 
test runOuterInnerTransaction ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (2, 'start inner 2') ";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (3, 'start inner 3')";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (2, 'start inner 4')";
                               "UPDATE TEST_TABLE  SET Value1 =5, Value2 ='end inner 5'  WHERE Value1 =2"] 
                              false
                              ["INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (10, 'start outer')";
                               "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES ($$, 'end outer. inner updated $$.') " ] 
                              true

printfn "%s" (String.replicate 50 "-")
printfn "run parallel tasks tests."
printfn "test Commit." 
test runParallelTasksTransaction 
        [for i in 0..100 -> 
            "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (" + i.ToString() + ", 'Task 1 (" + i.ToString() + ")')"] 
        false
        [for i in 100..150 -> 
            "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (" + i.ToString() + ", 'Task 2 (" + i.ToString() + ")')"] 
        false

printfn "test Rollback 1." 
test runParallelTasksTransaction 
        ["INSERT INTO NONE"] 
        false
        [for i in 100..150 -> 
            "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (" + i.ToString() + ", 'Task 2 (" + i.ToString() + ")')"] 
        false

printfn "test Rollback 2." 
test runParallelTasksTransaction 
        [for i in 100..200 -> 
            "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (" + i.ToString() + ", 'Task 1 (" + i.ToString() + ")')"] 
        false
        ["INSERT INTO NONE"] 
        false
// simulate error in BeginTransaction.
printfn "test Abort." 
test runParallelTasksTransaction 
        [for i in 0..100 -> 
            "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (" + i.ToString() + ", 'Task 1 (" + i.ToString() + ")')"] 
        false
        [for i in 100..150 -> 
            "INSERT INTO TEST_TABLE  (Value1,Value2 ) VALUES (" + i.ToString() + ", 'Task 2 (" + i.ToString() + ")')"] 
        true
--------------------------------------------------
run inner transaction tests.
test Commit.

result: "commit."
check data in db1: seq [(5, "end inner 5"); (3, "start inner 3"); (5, "end inner 5")]
check data in db2: seq [(10, "start outer"); (2, "end outer. inner updated 2.")]

++++++++++++++++++++++++++++++
test Rollback 1.

 catch "Falsche Syntax in der Nähe von 'NONE'."
result: "rollback inner and outer."
check data in db1: seq []
check data in db2: seq []

++++++++++++++++++++++++++++++
test Rollback 2.

 catch "Falsche Syntax in der Nähe von 'NONE'."
result: "rollback inner and outer."
check data in db1: seq []
check data in db2: seq []

++++++++++++++++++++++++++++++
test Abort inner.

 catch "error beginDBTransaction"
result: "rollback outer.error beginDBTransaction"
check data in db1: seq []
check data in db2: seq []

++++++++++++++++++++++++++++++
test Abort outer.

 catch "error beginDBTransaction"
result: "error beginDBTransaction abort outer."
check data in db1: seq []
check data in db2: seq []

++++++++++++++++++++++++++++++
--------------------------------------------------
run parallel tasks tests.
test Commit.

result: (true, "commit.")
check data in db1: seq
  [(0, "Task 1 (0)"); (1, "Task 1 (1)"); (2, "Task 1 (2)"); (3, "Task 1 (3)");
   ...]
check data in db2: seq
  [(100, "Task 2 (100)"); (101, "Task 2 (101)"); (102, "Task 2 (102)");
   (103, "Task 2 (103)"); ...]

++++++++++++++++++++++++++++++
test Rollback 1.

 catch "Falsche Syntax in der Nähe von 'NONE'."
result: (false, "rollback. (rollback task 1, commit task 2)")
check data in db1: seq []
check data in db2: seq []

++++++++++++++++++++++++++++++
test Rollback 2.

 catch "Falsche Syntax in der Nähe von 'NONE'."
result: (false, "rollback. (commit task 1, rollback task 2)")
check data in db1: seq []
check data in db2: seq []

++++++++++++++++++++++++++++++
test Abort.

 catch "error beginDBTransaction"
result: (false, "rollback. (Commit task 1, abort task 2)error beginDBTransaction
")
check data in db1: seq []
check data in db2: seq []

++++++++++++++++++++++++++++++

Montag, 16. Januar 2012

F# Type-directed memoization. recursive types.

Endlich habe ich es geschafft, was ich seit dem Posting fast schon aufgegeben habe. An der Stelle noch einmal der Verweis zu einem sehr interessanten und einleuchtenden Artikel "Fun with type functions".
In erste Linie ging es mir um die Memoisation einer Funktion von einem rekursiven Typ-Parameter (z.B. List). Ausserdem wollte ich die polymorphe memoization-Funktion in F# umsetzen.
Das Ergebnis sieht dann folgend aus.
//function with some long computations.
// val boolFunc : bool-> int list
let boolFunc b = 
    match b with
    | true -> 
        printfn "call boolFunc: true part." 
        List.init 1000 (fun i -> i * i)
    |false -> 
        printfn "call boolFunc: false part."
        List.init 1000 (fun i-> -1 * i * i)

// function of list type artgument.
// val testListFunc : bool list -> int list
let testListFunc l = List.map boolFunc l |> List.concat

// val memoizedFunc : (bool list -> int list)
let memoizedFunc = memoization testListFunc 

let test = (memoizedFunc [true;false;false;]) @  (memoizedFunc [true;false;false;])
printfn "run %A" test

call boolFunc: true part.
call boolFunc: false part.
call boolFunc: false part.

run [0; 1; 4; 9; 16; 25; 36; 49; 64; 81; 100; 121; 144; 169; 196; 225; 256; 289;
 324;
 361; 400; 441; 484; 529; 576; 625; 676; 729; 784; 841; 900; 961; 1024; 1089;
 1156; 1225; 1296; 1369; 1444; 1521; 1600; 1681; 1764; 1849; 1936; 2025; 2116;
 2209; 2304; 2401; 2500; 2601; 2704; 2809; 2916; 3025; 3136; 3249; 3364; 3481;
 3600; 3721; 3844; 3969; 4096; 4225; 4356; 4489; 4624; 4761; 4900; 5041; 5184;
 5329; 5476; 5625; 5776; 5929; 6084; 6241; 6400; 6561; 6724; 6889; 7056; 7225;
 7396; 7569; 7744; 7921; 8100; 8281; 8464; 8649; 8836; 9025; 9216; 9409; 9604;
 9801; ...]

Hier ist meine Implementierung. Als Kommentare habe ich einfach die Zitate aus dem Artikel verwendet.
// TypeMemo.fs
// from http://research.microsoft.com/en-us/um/people/simonpj/papers/assoc-types/fun-with-type-funs/typefun.pdf.
// chapter "3.1 Type-directed memoization".
namespace TypeMemoization
module TypeMemo =

    type IFromTable<'a,'w > =
        abstract inline fromTable : 'a->'w
    
    let inline fromTable t = (t :> IFromTable<_,_>).fromTable

    // "we can memoise any function from Bool by storing its two
    // return values as a lazy pair. This lazy pair is the memo table."
    type BoolTable<'w> = 
        | BTable of Lazy<'w> * Lazy<'w> 
        interface IFromTable<bool,'w> with
            member inline x.fromTable b = 
                match x with
                | BTable(x,y) -> if b then x.Force() else y.Force()
    
    let inline boolToTable f = 
        BTable (lazy(f true), lazy(f false))
    
    
    //"memoise functions from any sum type, such as the type Either."
    type Either<'a,'b>= 
        |Left of 'a
        |Right of '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 DiscriminatedUnionTable<'a,'b,'w> = 
        | STable of IFromTable<'a,'w> * IFromTable<'b,'w> 
        interface IFromTable<Either<'a,'b>,'w> with
            member inline x.fromTable e = 
                match x, e with
                | STable (t,_), Left  v   -> t.fromTable v
                | STable (_,t), Right v   -> t.fromTable v
    
    let inline discriminatedUnionToTable f fa fb =
        STable (fa (f<<Left),fb (f<<Right))
    
    
    // "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."
    type ProductTable<'a,'b,'w> = 
        | PTable of IFromTable<'a, IFromTable<'b,'w>>
        interface IFromTable<('a*'b),'w> with
            member inline x.fromTable p = 
                match x, p with
                | PTable t,(a,b)-> (t.fromTable a).fromTable b

    let inline productToTable f fa fb = 
        PTable ((fa (fun a -> fb (fun b -> f (a, b)) :> IFromTable<_,_> )) :> IFromTable<_,_>)   
   

    // "A list is a combination of a sum, a product, and recursion.
    // Since a list is either empty or not, ListTable<'a,'w> is represented by a pair, whose first component is the result of applying
    // the memoised function f to the empty list, and whose second component
    // memoises applying f to non-empty lists."
    type ListTable<'a,'w> =
        | LTable of Lazy<'w> * IFromTable<'a, IFromTable<'a list, 'w>>
        interface IFromTable<'a list,'w> with
            member inline x.fromTable l =
                match x, l with
                | LTable(t, _), [] -> t.Force() 
                | LTable(_, t), x :: xs -> fromTable (fromTable t x ) xs
                    
    let rec listToTable f fa =
        LTable (lazy(f []), fa (fun x -> listToTable (fun xs ->  f (x::xs)) fa :> IFromTable<_,_>) :> IFromTable<_,_>)
    let inline flip1 f a b c = f c a b
Für jeden Typ, den wir als Funktions-Typ-Parameter später benutzen wollen, sollte eine statische Operatorüberladung im MemoTable-Typ definiert werden. Hier bediene ich den Operatorüberladung-Trick als Ersatz für Type Class in F#.
type MemoTable = MemoTable with
            static member  (|>|) (MemoTable, f) =
                productToTable f (flip1 discriminatedUnionToTable boolToTable boolToTable) boolToTable
            static member  (|>|) (MemoTable, f) =
                productToTable f boolToTable (flip1 discriminatedUnionToTable boolToTable boolToTable)
            static member  (|>|) (MemoTable, f) =
                productToTable f boolToTable boolToTable
            static member  (|>|) (MemoTable, f) =
                discriminatedUnionToTable f (flip1 productToTable boolToTable boolToTable) boolToTable 
            static member  (|>|) (MemoTable, f) =
                discriminatedUnionToTable f boolToTable boolToTable) 
            static member  (|>|) (MemoTable, f) =
                discriminatedUnionToTable f boolToTable (flip1 discriminatedUnionToTable boolToTable boolToTable) 
            static member  (|>|) (MemoTable, f) =
                boolToTable f

            // functions from recursive types, like lists
            static member (|>|) (MemoTable, (f:(bool list->'a))) = 
                listToTable f ((|>|) MemoTable ) |> fromTable  
            static member (|>|) (MemoTable, (f:((bool*bool) list->'a))) = 
                listToTable f ((|>|) MemoTable ) |> fromTable
            static member (|>|) (MemoTable, (f:(Either<bool,bool> list->'a))) = 
                listToTable f ((|>|) MemoTable ) |> fromTable
            static member (|>|) (MemoTable, (f:((Either<bool,bool> * bool) list->'a))) = 
                listToTable f ((|>|) MemoTable ) |> fromTable
                             
    let inline memoization f = MemoTable |>| f


Wie man sieht, sind die vier letzten Methoden redundant. Versuchen wir mal mit "inline" und lassen die Typangabe weg.

Geht leider nicht. Dann ändern wir die Funktion ein bisschen ...

und es kompiliert. Jetzt gibt es einen kleinen Nachteil auf der Aufrufer-Seite, dass bei der Memoisation von Funktionen mit einem List-Parameter stets MemoTable als "dummy" Parameter angegeben werden soll.

Ein paar Tests.
// Script.fsx
#load "TypeMemo.fs"
open TypeMemoisation.TypeMemo
open System

let boolFunc1 b = 
    match b with
    | true -> 
        printfn "call boolFunc1: true part. Value = 10" 
        10
    |false -> 
        printfn "call boolFunc1: false part. Value = -10"
        -10
//function with long computations.
// val boolFunc : boo l-> int list
let boolFunc b = 
    match b with
    | true -> 
        printfn "call boolFunc: true part" 
        List.init 1000 (fun i->i*i)
    |false -> 
        printfn "call boolFunc: false part"
        List.init 1000 (fun i-> -1*i*i)

let eitherFunc e =
        match e with
        | Left a  -> 
            printfn "call eitherFunc: Left %A" a
            ((boolFunc a)|>List.sum) *(-2)
        | Right b ->  
            printfn "call eitherFunc: Right %A" b
            ((boolFunc b)|>List.sum) * 2
let eitherFunc1 e =
        match e with
        | Left a  -> 
            printfn "call eitherFunc: Left %A" a
            ((boolFunc a)|>List.sum) *(-2)
        | Right b ->  
            printfn "call eitherFunc: Right %A" b
            (eitherFunc b) * 2
let productFunc p =
        let x=
            printfn "call productFunc: first"
            (boolFunc1 (fst p))-3
        let y =
            printfn "call productFunc: second "
            (boolFunc1 (snd p))*2
        x + y

let productEitherFunc (e, b) =
        let x =
            printfn "call productEitherFunc: first %A" e
            (eitherFunc e)-3
        let y =
            printfn "call productEitherFunc second %A" b
            (boolFunc1 b) * 2
        x+y

//function of list type artgument.
let rec listFuncTest l  =
        match l with
        |[] -> 
            printfn "listFuncTest Empty"
            0
        |x :: xs -> 
            printfn "listFuncTest %A" x
            ((boolFunc x)|>List.sum) + listFuncTest xs

let inline memoizationSimpleType f =
    memoization f |> fromTable

// val memoizedFunc : (bool -> int)
let memoizedFunc  = memoizationSimpleType boolFunc1 
// val memoizedFunc1 : (Either<bool,bool> -> int)
let memoizedFunc1 = memoizationSimpleType eitherFunc
// val memoizedFunc2 : (bool * bool -> int)
let memoizedFunc2 = memoizationSimpleType productFunc 
// val memoizedFunc3 : (Either<bool,bool> * bool -> int)
let memoizedFunc3 = memoizationSimpleType productEitherFunc 
// val memoizedFunc4 : (Either<bool, Either<bool, bool>> -> int)
let memoizedFunc4 = memoizationSimpleType eitherFunc1

printfn "test (Either<bool,bool> -> int): "
let runSimple1= memoizedFunc1 (Left true) +  memoizedFunc1 (Left true)

printfn "runSimple1 %A" runSimple1
printfn "-------------------------------------------------------"

printfn "test (bool * bool -> int): "
let runSimple2= memoizedFunc2 (false, true) +  memoizedFunc2 (false, true)
printfn "runSimple2 %A" runSimple2
printfn "-------------------------------------------------------"

printfn "test (Either<bool,bool> * bool -> int): "
let runSimple3= memoizedFunc3 (Left true, false) +  memoizedFunc3 (Left true, false)
printfn "runSimple3 %A" runSimple3
printfn "-------------------------------------------------------"

let rec listFunc g l  =
        match l with
        |[] -> 
            printfn "call listFunc: Empty"
            0
        |x :: xs -> 
            printfn "call listFunc: %A" x
            (g x) + listFunc g xs 
printfn "test (bool * bool list -> int): "
let memoTest1  = memoization (listFunc productFunc) MemoTable
let run1 = (memoTest1 [(true,false);(false,true)]) +  (memoTest1 [(true,false);(false,true)])
printfn "run1 %A" run1
printfn "-------------------------------------------------------"

printfn "test (Either<bool,bool> * list -> int): "
let memoTest2  = memoization (listFunc eitherFunc) MemoTable
let run2= (memoTest2 [Left true; Right false]) +  (memoTest2 [Left true; Right false])
  
printfn "run2 %A" run2
type MemoTable =
    | MemoTable
    with
      static member
        ( |>| ) : MemoTable:MemoTable * f:(Either<bool,bool> * bool -> 'a) ->
                    ProductTable<Either<bool,bool>,bool,'a>
      static member
        ( |>| ) : MemoTable:MemoTable * f:(bool * Either<bool,bool> -> 'a) ->
                    ProductTable<bool,Either<bool,bool>,'a>
      static member
        ( |>| ) : MemoTable:MemoTable * f:(bool * bool -> 'a) ->
                    ProductTable<bool,bool,'a>
      static member
        ( |>| ) : MemoTable:MemoTable * f:(Either<(bool * bool),bool> -> 'a) ->
                    DiscriminatedUnionTable<(bool * bool),bool,'a>
      static member
        ( |>| ) : MemoTable:MemoTable * f:(Either<bool,bool> -> 'a) ->
                    DiscriminatedUnionTable<bool,bool,'a>
      static member
        ( |>| ) : MemoTable:MemoTable *
                  f:(Either<bool,Either<bool,bool>> -> 'a) ->
                    DiscriminatedUnionTable<bool,Either<bool,bool>,'a>
      static member
        ( |>| ) : MemoTable:MemoTable * f:(bool -> 'a) -> BoolTable<'a>
      static member
        ( |>| ) : MemoTable:MemoTable * f:('a list -> 'b) ->
                    ( ^_arg1 -> 'c list -> 'b)
                    when ( ^_arg1 or ('a -> IFromTable<'c list,'b>)) : (static
                                                                        member
                                                                        ( |>| ) :  ^_arg1 *
                                                                                  ('a ->
                                                                                     IFromTable<'c list,
                                                                                                'b>)
                                                                                    ->
                                                                                     ^d) and
                          ^d :> IFromTable<'c,IFromTable<'c list,'b>>
    end
  val inline memoization :
     ^a ->  ^_arg6
      when (MemoTable or  ^a) : (static member ( |>| ) : MemoTable *  ^a ->
                                                            ^_arg6)

test (Either<bool,bool> -> int): 
call eitherFunc: Left true
call boolFunc: true part
runSimple1 -1331334000
-------------------------------------------------------
test (bool * bool -> int): 
call productFunc: first
call boolFunc1: false part. Value = -10
call productFunc: second 
call boolFunc1: true part. Value = 10
runSimple2 14
-------------------------------------------------------
test (Either<bool,bool> * bool -> int): 
call productEitherFunc: first Left true
call eitherFunc: Left true
call boolFunc: true part
call productEitherFunc second false
call boolFunc1: false part. Value = -10
runSimple3 -1331334046
-------------------------------------------------------
test (bool * bool list -> int): 
call listFunc: (true, false)
call productFunc: first
call boolFunc1: true part. Value = 10
call productFunc: second 
call boolFunc1: false part. Value = -10
call listFunc: (false, true)
call productFunc: first
call boolFunc1: false part. Value = -10
call productFunc: second 
call boolFunc1: true part. Value = 10
call listFunc: Empty
run1 -12
-------------------------------------------------------
test (Either<bool,bool> * list -> int): 
call listFunc: Left true
call eitherFunc: Left true
call boolFunc: true part
call listFunc: Right false
call eitherFunc: Right false
call boolFunc: false part
call listFunc: Empty
run2 1632299296
val boolFunc1 : bool -> int
val boolFunc : bool -> int list
val eitherFunc : TypeMemoisation.TypeMemo.Either<bool,bool> -> int
val eitherFunc1 :
  TypeMemoisation.TypeMemo.Either<bool,
                                   TypeMemoisation.TypeMemo.Either<bool,bool>> ->
    int
val productFunc : bool * bool -> int
val productEitherFunc :
  TypeMemoisation.TypeMemo.Either<bool,bool> * bool -> int
val listFuncTest : bool list -> int
val inline memoizationSimpleType :
   ^a -> ('c -> 'd)
    when (TypeMemoisation.TypeMemo.MemoTable or  ^a) : (static member ( |>| ) : TypeMemoisation.TypeMemo.MemoTable *
                                                                                  ^a
                                                                                   ->
                                                                                    ^b) and
          ^b :> TypeMemoisation.TypeMemo.IFromTable<'c,'d>
val memoizedFunc : (bool -> int)
val memoizedFunc1 : (TypeMemoisation.TypeMemo.Either<bool,bool> -> int)
val memoizedFunc2 : (bool * bool -> int)
val memoizedFunc3 :
  (TypeMemoisation.TypeMemo.Either<bool,bool> * bool -> int)
val memoizedFunc4 :
  (TypeMemoisation.TypeMemo.Either<bool,
                                    TypeMemoisation.TypeMemo.Either<bool,bool>> ->
     int)
val runSimple1 : int = -1331334000
val runSimple2 : int = 14
val runSimple3 : int = -1331334046
val listFunc : ('a -> int) -> 'a list -> int
val memoTest1 : ((bool * bool) list -> int)
val run1 : int = -12
val memoTest2 : (TypeMemoisation.TypeMemo.Either<bool,bool> list -> int)
val run2 : int = 1632299296

Seltsamerweise funktioniert es in F#-Interactive und im Release-Modus, aber im Debug bekomme ich folgende Fehlermeldung.

Mittwoch, 21. Dezember 2011

F# Type Level Smart Constructor.

Es ist möglich, dank Phantom-Type und der Operatorenüberladung, die nummerische Prüfung bereits zur Kompilierungszeit durchzuführen.
Als Beispiel, wir wollen ausschlißlich den Widerstand von der Größe 2 oder 3 zulassen.
Der Funktionsparameter vom metalResistor-Smart Constructor wird in einen Phantom-Typ geändert. Da aber der Phantom-Typ-Konstruktor als privat deklariert ist, kann der Aufrufer an der metalResistor-Funktion nur einen von möglichen vordefinierten Werten - I,II,III,IV - übergeben.
//Resistor.fs
namespace SmartConstructors
open System
module Resistor  =
    
    type Bands = int

    type Resistor = private Metal of Bands | Ceramic of Bands with
        override x.ToString()= 
            match x with
            | (Metal v) -> "Metal " + v.ToString() 
            | (Ceramic v) -> "Ceramic " + v.ToString()

    type Zero = Zero

    type  Succ<'a> = private Succ of 'a with
        static member (|!|) (Zero, b:Succ<Succ<Zero>>) = Zero
        static member (|!|) (Zero, b:Succ<Succ<Succ<Zero>>>) = Zero |!| (Succ (Succ Zero))

    type Phantom<'a,'l> = private Phantom of 'a 

    let private nil : Phantom<int, Zero> = Phantom 0

    let inline private cons ((Phantom l ): Phantom<int,'l>) : Phantom<int, Succ<'l>> =
        Phantom (1 + l)

    let I = cons nil
    let II = cons (cons nil)
    let III = cons (cons (cons nil))
    let IV = cons (cons (cons (cons nil)))
    
    //run time check with assert.
    let metalResistor (Phantom b) =
        assert ( b >= 2 && b <= 3)
        Metal b

    let (|Metal|Ceramic|) n =
        match n with
        | (Metal v) -> Metal v
        | (Ceramic v) -> Ceramic v 
So weit, so gut, aber die Prüfung geschieht immer noch zur Laufzeit.
Jetzt kommt die Operatorenüberladung ins Spiel.
//compile time check.
    let inline typeLevelResistor (p : Phantom<int,'l>)  =
        Zero |!| (Unchecked.defaultof<'l>) |> ignore
        metalResistor p 

type Zero = | Zero
  type Succ<'a> =
    private | Succ of 'a
    with
      static member ( |!| ) : Zero:Zero * b:Succ<Succ<Zero>> -> Zero
      static member ( |!| ) : Zero:Zero * b:Succ<Succ<Succ<Zero>>> -> Zero
    end
  type Phantom<'a,'l> = private | Phantom of 'a
  val private nil : Phantom<int,Zero>
  val inline private cons : Phantom<int,'l> -> Phantom<int,Succ<'l>>
  val I : Phantom<int,Succ<Zero>>
  val II : Phantom<int,Succ<Succ<Zero>>>
  val III : Phantom<int,Succ<Succ<Succ<Zero>>>>
  val IV : Phantom<int,Succ<Succ<Succ<Succ<Zero>>>>>
  type Bands = int
  type Resistor =
    private | Metal of Bands
            | Ceramic of Bands
    with
      override ToString : unit -> string
    end
  val metalResistor : Phantom<int,'a> -> Resistor
  val inline typeLevelResistor :
    Phantom<int, ^l> -> Resistor
      when (Zero or  ^l) : (static member ( |!| ) : Zero *  ^l ->  ^a)
  val ( |Metal|Ceramic| ) : Resistor -> Choice<Bands,Bands>
Wenn man diesen Smart Constructor benutzt, wird die Prüfung zur Kompilierungszeit durchgeführt.

//Program.fs
open Resistor  
let resistor1 = metalResistor  II

let resistor2 = metalResistor  I

let typeLevelResistor1 = typeLevelResistor II
let typeLevelResistor2 = typeLevelResistor III

printfn "resistor1 %A" (resistor1.ToString())
printfn "resistor2 %A" (resistor2.ToString())

printfn "typeLevelResistor1 %A" (typeLevelResistor1.ToString())
printfn "typeLevelResistor2 %A" (typeLevelResistor2.ToString())

resistor1 "Metal 2" ---- DEBUGASSERTIONSFEHLER ----
---- Kurze Assertionsmeldung ----

---- Lange Assertionsmeldung ----


at Resistor.metalResistor(Phantom`2 _arg5) C:\Users\...\Documents\Visual Studio 2010\Projects\...\Resistor.fs(36)
at $Program.main@() C:\Users\...\Documents\Visual Studio 2010\Projects\...\TestSmart\Program.fs(6)
typeLevelResistor1 "Metal 2"
typeLevelResistor2 "Metal 3"

Zwar ist es nicht so schön wie in Haskell und die metalResistor-Funktion ist immer noch aufrufbar, aber immerhin.

Mittwoch, 23. November 2011

F# Smart Constructors for Union Type.

Neulich über Hakell Smart Constructors gelesen.
Das funktioniert teilweise auch mit F# Union Type.

Die Signaturdatei mit verdeckten Resistor Konstruktoren.
//Resistor.fsi 
namespace SmartConstructors
module Resistor =
    type Bands = int

    // Union Type with hiding constructors
    type Resistor = private Metal of Bands | Ceramic of Bands
    //smart constructor.
    val metalResistor : Bands -> Resistor
    val (|Metal|Ceramic|) : Resistor -> Choice<Bands,Bands> 
Implementierung.
//Resistor.fs
namespace SmartConstructors
open System
module Resistor  =
    type Bands = int
    
    type  Resistor = Metal of Bands | Ceramic of Bands with
        override x.ToString()= 
            match x with
            | (Metal v) -> "Metal " + v.ToString() 
            | (Ceramic v) -> "Ceramic " + v.ToString()
    //smart constructor.
    let metalResistor (b:Bands) =
        assert ( b >= 4 && b <= 8)
        Metal b
    let (|Metal|Ceramic|) n =
        match n with
        | (Metal v) -> Metal v
        | (Ceramic v) -> Ceramic v
Aufrufen.
// other F# Console Project
// with reference to SmartConstructors.dll
// Program.fs
open SmartConstructors.Resistor

//don't compile
//let failResistor = Metal 5

//only way to build a metal resistor
let resistor6 = metalResistor 6

let getBands r = 
    match r with
    | Metal v -> v
    | Ceramic v -> v
printfn "%A" (resistor6.ToString())
printfn "%A" (getBands resistor6)

//Assertion failed
let resistor10 = metalResistor 10
printfn "%A" (resistor10.ToString())

Freitag, 18. November 2011

F# Wpf MVVM. Mouse Tracking with AttachedProperty.

Seit letztem Beitrag habe ich überlegt, wie man die Hindernisse einfach per Maus ziehen (bei gedrückter linker Maustaste) erstellen kann.
Die zweite Herausforderung bestand in der Mausklick-Verarbeitung im Zusammenhang mit der Positionsbestimmung des Mauszeigers. Man sollte per Mausklick entweder ein Chip auswählen können oder ein Hindernis an der entsprechenden Position zu zeichnen oder zu löschen.
Nicht zu vergessen wir sind im MVVM-Land und Code-Behind ist nicht erwünscht. In diesem Fall kann die AttachedProperty eine mögliche Option sein.
...
<Canvas Name="canvas" Grid.Column="0"
 AttachedProperty:TrackMouseBehavior.TrackPosition="{Binding TrackMouseMove}">
...
</ Canvas> 
<Canvas.InputBindings> <MouseBinding MouseAction="RightClick" Command="{Binding RightClickCommand}" /> <MouseBinding MouseAction="LeftClick" Command="{Binding LeftClickCommand}" /> </Canvas.InputBindings> Mouse Tracking mittels AttachedProperty.
//MouseTrack.fs 
//NO GUARANTEE. I'm not sure that using of the Event class at this point is allowed.
namespace FSharpWpfMvvmTemplate.AttachedProperty

open System.Windows
open System.Windows.Input

// The type represents just the action that should be executed 
// upon the occurrence of PreviewMouseMove event.
type TrackMouse  = {action : Point -> unit}

type TrackMouseBehavior() =
    let mutable startTrack = false
    let mutable endTrack = true
    static let mutable TrackPositionProperty : DependencyProperty = 
        DependencyProperty.RegisterAttached
            ("TrackPosition", typeof<TrackMouse>, typeof<TrackMouseBehavior>,
                                            new PropertyMetadata(null, new PropertyChangedCallback(TrackMouseBehavior.OnPropertyChanged)))

    static member OnPropertyChanged (d:DependencyObject) (e:DependencyPropertyChangedEventArgs) =
        let element = d :?> UIElement
        if e.NewValue <> null then
            let trackMouse = e.NewValue :?> TrackMouse
            let trackFunc = TrackMouseBehavior.MouseTrack trackMouse element
            // First when the left mouse button is already pressed and the mouse is moved,
            // until the left mouse button is released.
            element.PreviewMouseLeftButtonDown
               |> Event.map (fun args -> args :> MouseEventArgs)
               |> Event.merge element.PreviewMouseMove
               |> Event.filter (fun args -> args.LeftButton =  MouseButtonState.Pressed)
               |> Event.add (fun args -> func(args))

    static member GetTrackPosition(d:DependencyObject) =
        d.GetValue(TrackPositionProperty) :?> TrackMouse
    static member SetTrackPosition(d:DependencyObject, value : TrackMouse) =
        d.SetValue(TrackPositionProperty, value)
    
    static member MouseTrack(trackPos : TrackMouse) (element:UIElement) (mouseEventArgs : MouseEventArgs ) =   
            let point = mouseEventArgs.GetPosition(element)
            trackPos.action point
Im ViewModel wird die AddPoint-Methode definiert, die im TrackMouse-Type gekapsellt an der TrackMouseMove-AttachedProperty übergeben wird.
// JumpSearchViewModel.fs
type JumpSearchViewModel() as x=   
    class
...
        let mutable mazePath = String.Empty
        let mutable obstacles = set[]
        let mutable env : MazeEnvironment = empty
...
        let AddPointToPath (x, y) wallSize =
            let xf, yf = (float x) * wallSize, (float y) * wallSize
            let v = sprintf "M%f,%fV%f" xf yf  (yf + wallSize)
            let h= sprintf " H%fV%fH%f" (xf + wallSize) yf xf
            sprintf "%s%s%s" mazePath v h

        member x.AddPoint (point : Point) =
            if not env.IsEmpty && not timer.IsEnabled && x.VerifyX() = null && x.VerifyY() = null then
                let cellPos (posx, posy) = (posx / 20.0 |> int), (posy / 20.0 |> int)
                let pointX, pointY = cellPos (point.X, point.Y)
                if pointX <= x.MazeX - 1 && pointY <= x.MazeY - 1 then
                    //check if the mouse click hit the start or the finish coin position.
                    match (pointX, pointY) = cellPos (env.coinX, env.coinY),  (pointX, pointY) = cellPos (env.targetX, env.targetY) with
                    | true, _ -> selectedCoin <- Start (env.coinX, env.coinY)
                    |_, true -> selectedCoin <- Finish (env.targetX, env.targetY)
                    | _ ->
                        obstacles <- Set.add (pointX, pointY) obstacles
                        mazePath <- AddPointToPath (pointX, pointY) x.WallSize
                        x.MazeData <- Geometry.Parse(mazePath)

        //maze path geometry.   
        member x.MazeData  
            with get () =  mazeGeometry
            and set value = 
                mazeGeometry <- value
                base.RaisePropertyChangedEvent(<@x.MazeData@>) 
        
        // Get the TrackMouse action that should be executed. 
        member x.TrackMouseMove
            with get () =  {action = x.AddPoint}
...
Der Code.

Freitag, 11. November 2011

A* Star Pathfinding with Jump Point Search. F#, Wpf and Visualisation.

Im letzten Beitrag habe ich meiner Implementierung vom Jump Point Search Algorithmus gezeigt. Hier geht es in erster Linie um F# und Wpf.
Da es in Visual Studio bereits eine Projekt-Vorlage für F# Wpf gibt, habe ich sie auch genommen. Und zwar handelt es sich dabei um eine MVVM-Vorlage. Daher veruschte ich im Rahmen vom MVVM-Pattern zu bleiben.

Typen für das Model und
//JumpSearchModel.fs
//MVVM Model Types.
module JumpMazeModelType =
    open Maze.JumpPointSearchType
    type SelectedCoin =
        | Start of float * float
        | Finish of float * float

    type MazeEnvironment = 
        { maze : JumpPointEnvironment; obstacles : Set<(int * int)>; 
          wallSize : float; coinX : float; coinY : float; targetX : float; targetY : float}
        member this.IsEmpty = Map.isEmpty <| this.maze.grid

    let empty = { maze = empty; obstacles = Set.empty;
                  wallSize = 20.0; coinX = 0.0; coinY = 0.0;targetX = 0.0; targetY = 0.0 }
das ViewModel.
//JumpSearchViewModel.fs
//MVVM ViewModel Class Type
type JumpSearchViewModel() as x =   
    class
        inherit ViewModelBase()
        let mutable env : MazeEnvironment  = JumpMazeModel.empty
        let mutable selectedCoin : SelectedCoin = Start (0.0, 0.0)
        ...
    end
DataContext vom View.
<Window.DataContext>
        <ViewModel:JumpSearchViewModel></ViewModel:JumpSearchViewModel>
</Window.DataContext>
Ich habe nichts besseres gefunden, als das Canvas-Element im CommandParameter-Binding vom Button-Element anzugeben, um es später im ViewModel für den Aufruf von Mouse.GetPosition und für den Zugriff auf die Children-Auflistung des Canvas-Elementes zu verwenden.
...
<Button Command="{Binding CreateMazeCommand}"  CommandParameter="{Binding ElementName=canvas}" >Init Maze</Button>
...
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x=   
    class
        ...
        let mutable canvas : Canvas = null
        
        member x.CreateMazeCommand = 
            new RelayCommand ((fun canExecute ->  x.VerifyX() = null &&  x.VerifyY() = null), (fun element -> x.CreateMaze(element)))

        member x.CreateMaze(element) =
            canvas <- element :?> Canvas
...
Die erste Herausforderung war die Start- und Ziel-Spielmarke mit der Tastatur auf dem Labyrinthbrett zu bewegen. Genauer gesagt wird einen von beiden Chips per Mausklick ausgewählt und dann mit einer Pfeiltaste auf die nächste Zelle bewegt, wenn es da gerade kein Hindernis gibt.
...
<!--coins moving with keys-->
<Window.InputBindings>
        <KeyBinding Command="{Binding CoinMoveCommand}" Key="Down" >
            <KeyBinding.CommandParameter>
                <i:Key>Down</i:Key>
            </KeyBinding.CommandParameter>
        </KeyBinding>
        <KeyBinding Command="{Binding CoinMoveCommand}" Key="Up">
            <KeyBinding.CommandParameter>
                <i:Key>Up</i:Key>
            </KeyBinding.CommandParameter>
        </KeyBinding>
        <KeyBinding Command="{Binding CoinMoveCommand}" Key="Left">
            <KeyBinding.CommandParameter>
                <i:Key>Left</i:Key>
            </KeyBinding.CommandParameter>
        </KeyBinding>
        <KeyBinding Command="{Binding CoinMoveCommand}" Key="Right">
            <KeyBinding.CommandParameter>
                <i:Key>Right</i:Key>
            </KeyBinding.CommandParameter>
        </KeyBinding>
</Window.InputBindings>
...
<!--start and finish coin-->
<Canvas>
    ...
    <Ellipse Name="coin" Fill="Blue"                     
     Canvas.Left="{Binding Path=CoinX }"  
                     Canvas.Top="{Binding Path=CoinY }" />
    <Ellipse Name="target" Canvas.Left="{Binding Path=TargetX}"  
                     Canvas.Top="{Binding Path=TargetY}" />
...
</Canvas>
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x =   
    class
        ...
        member x.CoinX 
            with get () =  
                env.coinX   
            and set value = 
                env <- JumpMazeModel.setCoinX env value coin
                base.RaisePropertyChangedEvent(<@x.CoinX@>) 
    
        member x.CoinY 
            ...
        member x.TargetX 
            with get () =  
                env.targetX   
            and set value = 
                env <- JumpMazeModel.setCoinX env value coin
                base.RaisePropertyChangedEvent(<@x.TargetX@>) 
    
        member x.TargetY 
            ...
        member x.CoinMoveCommand =
            new RelayCommand ((fun _ -> not env.IsEmpty && not timer.IsEnabled && x.Verify "MazeX" = null && x.Verify "MazeY" = null), 
                                (fun key -> x.CoinMove(key)))
        member x.CoinMove(k)= 
            env <- JumpMazeModel.moveCoin {env with obstacles=obstacles} (k :?> Key) selectedCoin 
            match selectedCoin with
            | Start _ ->
                selectedCoin <- Start (env.coinX, env.coinY)
                base.RaisePropertyChangedEvent(<@x.CoinX@>)
                base.RaisePropertyChangedEvent(<@x.CoinY@>)
            | Finish _ ->
                selectedCoin <- Finish (env.targetX, env.targetY)
                base.RaisePropertyChangedEvent(<@x.TargetX@>)
                base.RaisePropertyChangedEvent(<@x.TargetY@>)
...
//JumpSearchModel.fs
...
    let moveCoin (mazeEnv : MazeEnvironment) key selectedCoin =
        let move (coinX, coinY) =
            let cx, cy = (int coinX) / int mazeEnv.wallSize , (int coinY) / int mazeEnv.wallSize
            match key, mazeEnv.IsEmpty with
            | _, true -> coinX, coinY
            | Key.Down, false ->             
                if cy >= mazeEnv.maze.h - 1 || (Set.exists ( fun w -> w = (cx, cy + 1)) mazeEnv.obstacles ) then
                    coinX, coinY
                else
                    coinX, coinY + mazeEnv.wallSize
            | Key.Up, false -> 
                if cy = 0 || (Set.exists ( fun w -> w = (cx, cy - 1)) mazeEnv.obstacles) then
                    coinX, coinY
                else
                    coinX, coinY - mazeEnv.wallSize
            | Key.Right, false -> 
                if cx >= mazeEnv.maze.w - 1 || (Set.exists ( fun w -> w = (cx + 1, cy)) mazeEnv.obstacles) then
                    coinX, coinY
                else
                    coinX + mazeEnv.wallSize, coinY
            | Key.Left, false -> 
                if cx = 0 || (Set.exists ( fun w -> w = (cx - 1, cy)) mazeEnv.obstacles) then
                    coinX, coinY
                else
                    coinX - mazeEnv.wallSize, coinY
            | _, false -> coinX, coinY
        match selectedCoin with
        | Start (dx, dy) -> 
            let moveX, moveY = move (dx, dy)
            {mazeEnv with coinX = moveX; coinY = moveY}
        | Finish (dx, dy) -> 
            let moveX, moveY = move (dx, dy)
            {mazeEnv with targetX = moveX; targetY = moveY}

    let setCoinX (mazeEnv : MazeEnvironment) x selectedCoin = 
        if mazeEnv.IsEmpty |> not && x < float (mazeEnv.maze.w * int mazeEnv.wallSize)  then
               match selectedCoin with
               | Start _ -> {mazeEnv with coinX = x}
               | Finish _ -> {mazeEnv with targetX = x}
        else
            mazeEnv
    
    let setCoinY (mazeEnv : MazeEnvironment) y selectedCoin = 
        ...
Die zweite Herausforderung bestand in der Mausklick-Verarbeitung im Zusammenhang mit der Positionsbestimmung des Mauszeigers. Man sollte per Mausklick entweder ein Chip auswählen können oder ein Hindernis an der entsprechenden Position zu zeichnen oder zu löschen.
...
<Canvas.InputBindings>
                <MouseBinding MouseAction="LeftClick" Command="{Binding LeftClickCommand}" />
                <MouseBinding MouseAction="RightClick"  Command="{Binding RightClickCommand}" />
</Canvas.InputBindings>
...
Wie oben schon erwähnt, wird die Position über den Aufruf von Mouse.GetPosition ermittelt. Die Hindernis-Positionen werden in einer Liste gespeichert und mit der Hilfe von Path-Geometry auf dem Canvas-Element abgebildet.
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x =  
...
        let mutable obstacles = set[]
        let mutable mazeGeometry = Geometry.Parse("")
...
        //maze path geometry.   
        member x.MazeData  
            with get () =  mazeGeometry
            and set value = 
                mazeGeometry <- value
                base.RaisePropertyChangedEvent(<@x.MazeData@>) 

        member x.LeftClickCommand  = 
            // if the mouse position hit the start or the finish coin position,
            // then select a coin. Otherwise add obstacle at mouse position.
            new RelayCommand ((fun canExecute -> not env.IsEmpty && not timer.IsEnabled && x.Verify "MazeX" = null && x.Verify "MazeY" = null), 
                                (fun element -> 
                                    let pos = Mouse.GetPosition(element :?> UIElement)
                                    let cellPos (posx, posy) = (posx / 20.0 |> int), (posy / 20.0 |> int)
                                    //check if the mouse click hit the start or the finish coin position.
                                    match cellPos (pos.X, pos.Y) = cellPos (env.coinX, env.coinY),  cellPos (pos.X, pos.Y) = cellPos (env.targetX, env.targetY) with
                                    | true, _ -> selectedCoin <- Start (env.coinX, env.coinY)
                                    |_, true -> selectedCoin <- Finish (env.targetX, env.targetY)
                                    | _ ->
                                        obstacles <- Set.add (cellPos (pos.X, pos.Y)) obstacles
                                        x.MazeData <- Geometry.Parse(JumpSearchViewModel.CreateMazePath (x.MazeX |> float)  (x.MazeY |> float) x.WallSize obstacles)))
        member x.RightClickCommand  =
            //Remove obstacle at mouse position.
            new RelayCommand ((fun canExecute -> not env.IsEmpty && not timer.IsEnabled && x.Verify "MazeX" = null && x.Verify "MazeY" = null), 
                                (fun element -> 
                                    let pos = Mouse.GetPosition(element :?> UIElement)
                                    let posx, posy = (pos.X/20.0 |> int), (pos.Y / 20.0 |> int)
                                    obstacles <- Set.remove (posx, posy) obstacles
                                    x.MazeData <- Geometry.Parse(JumpSearchViewModel.CreateMazePath (x.MazeX |> float)  (x.MazeY |> float) x.WallSize obstacles)))
...
Das Labyrinth und der Ergebnispfad.
<!--Labirynth and solver result path-->
<Path Name="mazePath" Stroke="Black" Data="{Binding Path=MazeData}" StrokeThickness="4" ></Path>
<Path Name="solverPath" Stroke="Purple"  Data="{Binding Path=SolverData}"  StrokeDashArray="4 2"  StrokeThickness="3" ></Path>
...
<Button Command="{Binding CreateMazeCommand}"  CommandParameter="{Binding ElementName=canvas}"   >Init Maze</Button>
<Button Name="AStar" Command="{Binding CreateAStarCommand}">A* Jump Points Search</Button>
Die komplexe Pfade lassen sich leicht mit der Hilfe von der Markup-Syntax beschreiben.
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x =  
...
        let mutable mazeGeometry = Geometry.Parse("")
        let mutable solverPath = Geometry.Parse("")
...
        static member CreateMazePath w h wallSize points =
        
            let builder = StringBuilder()
        
            let folder (acc : StringBuilder) wall  =
                match wall with
                | (x, y) ->
                    let xf, yf = (float x) * wallSize, (float y) * wallSize
                    acc.Append(sprintf "M%f,%fV%f" xf yf  (yf + wallSize))|>ignore
                    acc.Append(sprintf " H%fV%fH%f" (xf + wallSize) yf xf) 
        
            builder.Append(sprintf "M%f,%f" 0.0 0.0)|>ignore
            builder.Append(sprintf "L%f,%f %f,%f" 0.0   0.0     0.0     (h * wallSize)) |> ignore
            builder.Append(sprintf " %f,%f %f,%f" 0.0   (h * wallSize)  (w * wallSize)  (h * wallSize)) |>ignore
            builder.Append(sprintf " %f,%f %f,%f" (w * wallSize)  (h * wallSize)    (w * wallSize)    0.0) |>ignore
            builder.Append(sprintf " %f,%f %f,%f" (w * wallSize)  0.0   0.0     0.0)|>ignore
            (points |> PSeq.fold folder builder).ToString()
        member x.SolverData  
            with get () =  solverPath
            and set value = 
                solverPath <- value
                base.RaisePropertyChangedEvent(<@x.SolverData@>)

        member x.CreateMazeCommand = 
            new RelayCommand ((fun canExecute -> x.VerifyX = null && x.VerifyY = null), (fun element -> x.CreateMaze(element)))

        member x.CreateMaze(element) =
            ...
            x.MazeData <- Geometry.Parse("")
            x.SolverData <- Geometry.Parse("")
            env <- JumpMazeModel.createMaze x.MazeX x.MazeY x.WallSize
            selectedCoin <- Finish (env.targetX, env.targetY)
            x.TargetX <- env.targetX
            x.TargetY <- env.targetY
            obstacles <- env.obstacles
            x.MazeData <- Geometry.Parse(JumpSearchViewModel.CreateMazePath (x.MazeX |> float)  (x.MazeY |> float) x.WallSize obstacles)

        member x.CreateAStarCommand =
            new RelayCommand (
                                (fun canExecute -> true),
                                 (fun _ -> 
                                     if x.VerifyX = null && x.VerifyY = null then x.CreateAStar()))
        //create solver path.
        member x.CreateAStar() =
            ...
            let jumpPoints = JumpMazeModel.run {env with obstacles = obstacles}
            x.SolverData <- Geometry.Parse(jumpPoints |> JumpMazeModel.resultPath |> JumpMazeModel.solverToPath x.WallSize )
Das Schwierigste war für mich die Visualisierung. Es geht bestimmt irgendwie besser und anders. Meine Lösung ist die Verwendung von der DispatcherTimer-Klasse. Die Positionen von den besuchten Zellen mitsamt Positionen von Vater-Zellen werden in einer Liste - animatePoints - gespeichert. Bei jedem Tick-Ereignis wird ein Listenelement aus der Liste genommen und als ein Ellipse-Element in der Children-Eigenschaft von Canvas gespeichert. Zusätzlich wird der Weg von der Vater-Zelle zu der aktuellen Zelle gezeichnet.
<Canvas Name="canvas">
    ...
    <Path Stroke="BurlyWood" Data="{Binding Path=AnimateData}" StrokeThickness="2"></Path>
    ...
</Canvas>
...
<Button Command="{Binding AnimateCommand}" >Animate</Button>
...
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x=   
    class
...
        let mutable animateData = String.Empty
        let mutable animateResult = String.Empty
        let mutable timer = new DispatcherTimer(DispatcherPriority.Normal)
         //( (int * int) * ((int * int) * Direction) ) list. 
         //( jumpPoint   * (parent      * direction)) list 
        let mutable animatePoints = []
        let mutable undo = []
        let mutable canvas : Canvas = null
        do 
            timer.Interval <- new TimeSpan(0, 0, 0, 0, 400)
            
            timer.Tick.Add(fun _  -> x.AnimateOneStep () )   
...
        member x.AnimateData  
            with get () =  Geometry.Parse(animateData)
            and set value = 
                solverPath <-  Geometry.Parse(value)
                base.RaisePropertyChangedEvent(<@x.AnimateData@>)  
        
        member x.AnimateCommand =
            new RelayCommand ((fun _ -> true), 
                                        (fun _ ->  
                                            match not env.IsEmpty && x.Verify "MazeX" = null && x.Verify "MazeY" = null with
                                            | false -> ()
                                            | true -> 
                                                x.SolverData <- Geometry.Parse("")
                                                x.ResetAnimateData() 
                                                selectedCoin <- Start (env.coinX, env.coinY)
                                                let animateRun =  JumpMazeModel.run {env with obstacles = obstacles}
                                                animateResult <- animateRun |> JumpMazeModel.resultPath |> JumpMazeModel.solverToPath x.WallSize
                                                animatePoints <- animateRun |> JumpMazeModel.animatePoints |> Seq.toList
                                                timer.Start()))

        member x.AnimateOneStep () =
            match animatePoints with
            | [] -> timer.Stop()
            | [((currx, curry),(x',y'), d)] ->
                let x2, y2, x1, y1 = (currx |> float) * env.wallSize + env.wallSize / 2.0, (curry |> float) * env.wallSize + env.wallSize / 2.0, (x' |> float) * env.wallSize + env.wallSize / 2.0, (y' |> float) * env.wallSize + env.wallSize / 2.0
                animateData <- sprintf "%sM%f,%fL%f,%f %f,%f%s" animateData x1 y1 x1 y1 x2 y2 (x.DrawArrow (x2, y2, d))
                x.AnimateData <- animateData
                x.SolverData <-  Geometry.Parse(animateResult)
                timer.Stop()
            | ((currx, curry),(x',y'), d) :: ts->
                let x2, y2, x1, y1 = (currx |> float) * env.wallSize + env.wallSize / 2.0, (curry |> float) * env.wallSize + env.wallSize / 2.0, (x' |> float) * env.wallSize + env.wallSize / 2.0, (y' |> float) * env.wallSize + env.wallSize / 2.0
                // add new Point to Path and draw a line with arrows
                // from the last point to the new point.
                animateData <- sprintf "%sM%f,%fL%f,%f %f,%f%s" animateData x1 y1 x1 y1 x2 y2 (x.DrawArrow (x2, y2, d))
                x.AnimateData <- animateData
                // move the start coin.
                x.CoinX <- x2
                x.CoinY <- y2
                // add new jump point to canvas children collection.
                if canvas <> null then
                    let e = new Ellipse(Width = 6.0, Height= 6.0, Fill = Brushes.Blue)
                    canvas.Children.Add(e)|>ignore
                    Canvas.SetLeft(e, x2 )
                    Canvas.SetTop(e, y2 )
                    //add remove function to undo functon list.
                    undo <- [(fun _ -> canvas.Children.Remove e;)] @ undo

                animatePoints <- ts

        member x.CreateAStar() =
            x.ResetAnimateData()
            ...
        member x.CreateMaze(element) =
            x.ResetAnimateData()
            ...
        member private x.ResetAnimateData() =
            if timer.IsEnabled then
                timer.Stop()
            // Remove all added ellipses.
            List.map (fun f -> f ()) undo|>ignore
            animateData <- String.Empty
            x.AnimateData <- animateData
            ...
Der Code.

Mittwoch, 9. November 2011

F#. A* Star Pathfinding with Jump Point Search.



Das gesamte Projekt ist auf dem GitHub unter "Maze-Generator-and-Maze-Solver".

"Jump Point Search" Algorithmus ist ein sehr interessanter, einfacher und effizienter Algorithmus, der die A * Suche dadurch beschleunigt, dass letztendlich weniger Nodes besucht wird. Ich kann nur empfehlen den Blog-Eintrag und die ausführliche Beschreibung zu lesen, da die ganze Deatils zur Implementierung der Algorithmus dort ganz gut erklärt sind.
Es gibt bereits eine C++ Implementierung.

Die angepasste A* Suche Funktion.
//JumpPointsSearch.fs
...
   // return all jump points with parents and costs.  seq<jumpPoint   * (parent      * cost)> 
  //astarJump : int * int -> JumpPointEnvironment -> seq<(int * int) * ((int * int) * float)>
  let inline astarJump start env = 
      let inner (seen, q)  =
           match PriorityQueue.isEmpty q with
           | true -> failwith "No Solution."
           | false ->
               let ((currentCosts, next), dq) = PriorityQueue.deleteFindMin q
               let expanded, parent = next
               if currentCosts = 0.0 then None
               else 
                   match env.isGoal expanded with
                   | true -> Some ((expanded, (parent, currentCosts)),(seen, PriorityQueue.singleton 0.0 (expanded, expanded)))
                   | otherwise -> 
                       let succs = successors env.rooms expanded
                       let dir = directionToParent parent expanded
                       let jumpPoints= findJumpPoints env expanded dir succs  |> Set.ofSeq
 
                       let costs target = currentCosts + (env.stepCosts expanded target)  
                                            + (env.heuristic target) - (env.heuristic expanded) 

                       let q' = 
                           Set.difference jumpPoints seen |> Seq.map (fun a -> costs a, (a, expanded)) 
                           |> PriorityQueue.ofSeq |> PriorityQueue.merge dq
                       Some ((expanded, (parent, currentCosts)), ((Set.union seen jumpPoints), q'))
                   
      Seq.unfold inner ((Set.singleton start), (PriorityQueue.singleton (env.heuristic start) (start,start))) 
Typen und Hilfsfunktionen für das Jump Point Search Verfahren.
//
module JumpPointSearchType =
  open MazeType

  type StraightDirection = N  | S | E  | W  
  type DiagonalDirection = NE | NW | SE | SW
   
  type Direction =
    | Straight of StraightDirection * Cell
    | Diagonal of DiagonalDirection * Cell
    | NONE

  type JumpPointEnvironment = 
    { grid: Map<int * int, Direction list>;  //cells with avialiable Directions.
      w : int; h : int;     // Weight and Height
      isGoal : int * int -> bool;
      heuristic : int * int -> float;
      stepCosts : int * int -> int * int -> float}
        member x.successors point = 
          set[for direction in Map.find point x.grid  do
                  yield direction
              ]

  let empty = { grid = Map.empty; w = 20; h = 20; isGoal = (fun _ -> true);
                heuristic = (fun _ -> 0.0)
                stepCosts = (fun _ _-> 0.0)
               }

  let inline straightPosition direction =
    match direction with
    | N -> (0, -1)
    | S -> (0, 1)
    | E -> (1, 0)
    | W -> (-1, 0)
  
  let diagonalPosition direction =
    match direction with
    | NE -> (1,  -1)
    | SE -> (1,   1)
    | SW -> (-1,  1)
    | NW -> (-1, -1)
  
  let inline straight  direction = Straight (direction, straightPosition direction)
  let inline diagonal  direction = Diagonal (direction, diagonalPosition direction)

  type NotRule = Not of Direction

  let inline notRule direction = Not (straight direction)
  
  type PruningRule = 
      | StraightRule of (NotRule * Direction) 
      | DiagonalRule of Direction
  
  let inline straightRule notrule direction  = StraightRule (notrule, diagonal direction) 
  let inline diagonalRule direction  = DiagonalRule (straight direction)

  let inline flip f a b = f b a

  let inline inGrid w h cell =
            match cell with
            | x, y when (0 <= x && x <= w - 1 && 0 <= y && y <= h - 1) -> true
            | _  -> false
Jump Point Search Algorithm.
//  findJumpPoints : JumpPointEnvironment -> int * int -> Direction -> Set<Direction> -> (int * int) list
  let inline findJumpPoints env (x, y) direction neighbours  =
      let find naturalNeighbours forcedNeighboursRules =
          naturalNeighbours @ 
              (forcedNeighboursRules
               |> List.filter (not << flip Set.contains neighbours << fst)
               |> List.map snd)
          |> List.choose (jump env x y)
      //Neighbour Pruning Rules
      match direction with
      | Straight(N, _) -> 
          // add S neighbour to the pruned set of neighbours.
          // add SE neighbour only if E neighbour is obstacle.
          // add SW neighbour only if W neighbour is obstacle.
          find [straight S]
                    (List.zip   [straight E;     straight W] 
                                [diagonal SE;    diagonal SW])

      | Diagonal(NE, _) -> 
          find [diagonal SW; straight S; straight W]
                    (List.zip   [straight N;     straight E] 
                                [diagonal NW;    diagonal SE])

      | Straight(E, _) ->
          find [straight W]
                    (List.zip   [straight N;     straight S] 
                                [diagonal NW;    diagonal SW])
      | Straight(S, _) -> 
          find [straight N] 
                    (List.zip   [straight E;     straight W] 
                                [diagonal NE;    diagonal NW])
      | Diagonal(SE, _) -> 
          find [diagonal NW; straight N; straight W]   
                    (List.zip   [straight S;     straight E] 
                                [diagonal SW;    diagonal NE])
      | Straight(W, _) -> 
         find [straight E]           
                    (List.zip   [straight N;     straight S] 
                                [diagonal NE;    diagonal SE])
      | Diagonal(SW, _) -> 
          find [diagonal NE; straight N; straight E]   
                    (List.zip   [straight S;     straight W] 
                                [diagonal SE;    diagonal NW])
      | Diagonal(NW, _) -> 
          find [diagonal SE; straight S; straight E]
                   (List.zip   [straight N;     straight W] 
                               [diagonal NE;    diagonal SW])
      // return all neighbours as the pruned set of neighbours.
      | NONE -> directionsToPoints neighbours (x, y) |> Set.toList
Details
module JumpPointsSearch =
  open Microsoft.FSharp.Collections
  open Astar
  open JumpPointSearchType
  
  let sqrtTWO = 1.414213562
  
  let inline diagHeuristic (x1, y1) (x2, y2) =
    let diagonal = min (abs(x1 - x2)) (abs (y1 - y2)) |> float
    let straight = (abs (x1 - x2)) + (abs (y1 - y2)) |> float
    sqrtTWO * diagonal + (straight - 2.0 * diagonal)


  let inline stepCosts (x1,y1) (x2,y2) = 
        let xa, ya = abs(x1-x2), (abs(y1-y2))
        (sqrtTWO - 1.0) * (min xa ya |> float) + (max xa ya |> float) 

  // move with turning points rules in direction jumpDirection.
  // recursively apply the straight pruning rule or
  // the diagonal pruning rule.
  // jump : JumpPointEnvironment -> int -> int -> Direction -> (int * int) option
  let rec jump env x y jumpDirection =
          let generateSteps dx dy notObstacle =
                (x, y)
                |> Seq.unfold (fun cell -> 
                                    let nextCell = MazeUtils.addPoint cell (dx, dy)
                                    if inGrid env.w env.h nextCell && notObstacle cell then 
                                        Some(nextCell, nextCell) 
                                    else None) 
          let directionSteps direction = 
                match direction with
                | NONE -> Seq.empty
                | Straight(_,(dx, dy)) -> generateSteps dx dy (Set.contains direction << env.successors )
                | Diagonal(_,(dx, dy)) -> generateSteps dx dy (Set.contains direction << env.successors )          
          
          let move direction directionRules =
              //apply the pruning rules.
              let applayRules rules func (px, py) = 
                    Seq.map (fun rule -> 
                                    match rule with
                                    | StraightRule(Not a, b) -> (not <| func a) && func b 
                                    | DiagonalRule dir -> jump env px py dir |> Option.isSome) rules |> Seq.reduce (||)
              //all available steps in current direction.
              let steps = directionSteps direction 
              //try to find jump point p. 
              steps
              |> Seq.tryFind (fun p ->
                    env.isGoal p || applayRules directionRules (flip Set.contains (env.successors p)) p)
                        
          match jumpDirection with
          | NONE -> None
          
          | Straight(N, _) as dir -> 
            //(x, y) is a jump point if a NW neighbour exists which cannot be                                  
            // reached by a shorter path than one involving (x, y) or with other words W is obstacle or
            // if NE and not E
                                     move dir [straightRule (notRule W) NW; straightRule (notRule E) NE]

          | Straight(S, _) as dir -> move dir [straightRule (notRule W) SW; straightRule (notRule E) SE] 

          | Straight(E, _) as dir -> move dir [straightRule (notRule S) SE; straightRule (notRule N) NE]

          | Straight(W, _) as dir -> move dir [straightRule (notRule S) SW; straightRule (notRule N) NW]
          
          | Diagonal(NE, _) as dir -> 
            //(x, y) is a jump point if a SE neighbour exists which cannot be                                  
            // reached by a shorter path than one involving (x, y) or with other words S is obstacle or
            // if NW and not W or 
            // if we can reach other jump points by 
            // travelling vertically or horizontally.  
                                      move dir [straightRule (notRule S) SE; straightRule (notRule W) NW;
                                                diagonalRule N; diagonalRule E] 

          | Diagonal(SE, _) as dir -> move dir [straightRule (notRule W) SW; straightRule (notRule N) NE;
                                                diagonalRule S; diagonalRule E]
          | Diagonal(SW, _) as dir -> move dir [straightRule (notRule N) NW; straightRule (notRule E) SE;
                                                diagonalRule S; diagonalRule W]
          | Diagonal(NW, _) as dir -> move dir [straightRule (notRule E) NE; straightRule (notRule S) SW;
                                                diagonalRule N; diagonalRule W]
  
  // directionsToPoints : Set<Direction> -> int * int -> Set<int * int>
  let inline directionsToPoints directions (x, y)=
      let inner d = 
              match d with
              | Straight(_, (dx, dy)) ->    x + dx, y + dy
              | Diagonal(_, (dx, dy)) ->    x + dx, y + dy
              | NONE -> failwith "failed to determine direction."
      Set.map inner directions
Ausführen.
...
    open Maze.JumpPointSearchType
    open Maze.JumpPointsSearch

    type MazeEnvironment = 
        { maze : JumpPointEnvironment; obstacles : Set<(int * int)>; 
          wallSize : float; coinX : float; coinY : float; targetX : float; targetY : float}
        member this.IsEmpty = Map.isEmpty <| this.maze.grid

    let empty = { maze = empty; obstacles = Set.empty;
                  wallSize = 20.0; coinX = 0.0; coinY = 0.0;targetX = 0.0; targetY = 0.0 }
    // Create the grid from the obstacles set.
    // mapObstaclesToGrid : JumpPointEnvironment -> Set<int * int> -> JumpPointEnvironment
    let inline mapObstaclesToGrid mazeEnv obstacles =
        
        let notObstacleDiagonal straight pos =
            let isInGrid = List.forall (inGrid mazeEnv.w mazeEnv.h)  (pos :: straight)
            match isInGrid with
            | true -> not <| Set.contains pos obstacles && Set.intersect (Set.ofList straight) obstacles |> Set.count < 2
            | _  ->   false

        let notObstacle cell = 
            match inGrid  mazeEnv.w mazeEnv.h cell with
            | true -> not <| Set.contains cell obstacles 
            | false -> false

        let mkWall (x, y) =
            let add =  addPoint (x, y)
            (x,y), [straight W,   straightPosition W |> add |> notObstacle;
                    straight N,   straightPosition N |> add |> notObstacle;
                    straight E,   straightPosition E |> add |> notObstacle; 
                    straight S,   straightPosition S |> add |> notObstacle; 
                    diagonal NW,  diagonalPosition NW |> add |> notObstacleDiagonal [straightPosition N |> add; 
                                                                                     straightPosition W |> add ]; 
                    diagonal NE,  diagonalPosition NE |> add |> notObstacleDiagonal [straightPosition N |> add;
                                                                                     straightPosition E |> add ]; 
                    diagonal SW,  diagonalPosition SW |> add |> notObstacleDiagonal [straightPosition S |> add;
                                                                                     straightPosition W |> add ]; 
                    diagonal SE,  diagonalPosition SE |> add |> notObstacleDiagonal [straightPosition S |> add;
                                                                                     straightPosition E |> add ]]
            |> List.filter (id << snd)
            |> List.map fst
        {mazeEnv with 
            grid = Seq.map mkWall 
                        [ for x in [0..mazeEnv.w-1] do
                            for y in [0..mazeEnv.h-1] do
                            yield x, y] |> Seq.toList |> Map.ofList }
    
    // run : MazeEnvironment -> seq<(int * int) * ((int * int) * float)>    
    let run env = 
        let jumpPointEnv = mapObstaclesToGrid env.maze env.obstacles
        let start = env.coinX / env.wallSize |> int, env.coinY / env.wallSize |>int
        let finish = env.targetX / env.wallSize |> int, env.targetY / env.wallSize |> int
        astarJump start { jumpPointEnv with isGoal = ((=) finish); stepCosts = stepCosts;  heuristic = (diagHeuristic finish) }

    // jump points  seq<jumpPoint   * (parent      * cost)>  to path of points list.
    // resultPath : seq<(int * int) * ((int * int) * float)> -> (int * int) list
    let inline resultPath jumpPoints =
        jumpPoints
        |> Seq.groupBy (fst)
        |> Seq.map (fun (key, s)-> key, Seq.minBy (snd << snd) s |> snd |> fst) 
        |> Seq.toList |> List.rev
        |> List.fold (fun acc (curr, parent) -> 
                        match acc with
                        | [] -> [parent;curr;]
                        | x :: _ when x = curr-> parent :: acc
                        | _ -> acc) []
    
    let inline animatePath jumpPoints = jumpPoints |> Seq.map (fun (curr, (parent, _)) -> curr, parent, directionToParent curr parent)
Ehrlich gesagt habe ich die meiste Zeit mit WPF verbracht, um die halbwegs brauchbare Algorithmus-Animation zu erstellen.

Donnerstag, 25. August 2011

F# Transaction Monad.

Nachdem ich sehr interessante Beiträge über die verschiedensten F# Monads begeistert gelesen habe, überlegte ich mir, ob man so was wie eine Transaction Monad implementieren kann.
Und tatsächlich gibt es bereits eine Haskell Version. Hundertprozentig ist die Funktionsweise von der Monad für mich noch nicht klar, aber soweit ich es beurteilen kann ist die Transaktion ein Hybrid aus der Continuation und der State Monad.

Erstmal ein paar Tests:
open TransactionM
// 5 ways you can leave the monad.
// handle : transaction handle.
let test0 handle = 
    transaction {
      let! s = get
      do! set 99
      match s with
        | 0 -> return id
        | 1 -> return! abort    handle (Some s)
        | 2 -> return! dirty    handle (Some s.)
        | 3 -> return! rollback handle  "rollback!"
        | _ -> return! commit   handle  "commit"
    }
// return TransactionState<int,string> * int. second item is result of transaction.
let runTest0  = 
    let run = runTransaction_ (beginT test0)
    List.map run [0..4]
val test0 :
  TransactionM.TransactionHandle<'a,int,
                                 TransactionM.TransactionState<int,string>> ->
    TransactionM.TransactionM<'a,int,('b -> 'b)>

val runTest0 : (TransactionM.TransactionState<int,string> * int) list =

  [ (Abort null, 0); 
    (Abort (Some 1), 1); 
    (Dirty (Some 2), 99);
    (Rollback "rollback!", 3);
    (Commit "commit", 99) ]

Einfache Listenmanipulation als eine Transaktion.
// Simple list manipulation as transaction.
// p : some condition
// l : init list
// handle : transaction handle.
let testList p l handle = transaction {
        do! set l
        do! modify (fun xs-> 6::xs)
        do! modify (fun xs-> 7::xs)       
        match p  with
        | false -> return! rollback handle  "rollback!" 
        | true -> return! commit   handle   "commit."
    }
// Only if both transactions are successful then concatenate the two lists and commit all transactions.
// rollback otherwise.
// m1, m2 - transactions.
// handle : transaction handle.
let merge m1 m2 handle = 
    transaction {
            let! state1 = m1
            match state1 with
            | Commit a ->  
                let! firstList = get
                printfn "    first list: %A" firstList 

                let! state2 = m2
                match state2 with
                | Commit b   ->  
                    let! secondList = get
                    printfn "    second list: %A" secondList
                    do! set (firstList @ secondList)
                    return! commit   handle  b

                | Rollback b ->  return! rollback   handle  b
                | _          ->  return! abort      handle (Some "abort")

            | Rollback a    ->   return! rollback   handle  a                        
            | _             ->   return! abort      handle (Some "abort")
        }
//return TransactionState<string,'b> * 'c list. second item is result of transaction.
let runMerge i m1 m2 = 
    printfn "Start runMerge %A." i
    let m = beginT (merge m1 m2)
    runTransaction_ m [] 
// ls : list of list.
// return TransactionState<string,string> * int list. second item is result of transaction.
let runList ls = 
    printfn "Start runList."
    let m = List.fold (fun acc (l, p) -> beginT (merge acc (beginT (testList p l)))) (alwaysCommit "commit") ls
    runTransaction_ m []

printfn "runMerge 1: %A " (runMerge 1 (beginT (testList true  [0..3] )) (beginT (testList true  [10..13])))
printfn "runMerge 2: %A " (runMerge 2 (beginT (testList false [0..3] )) (beginT (testList true  [10..13])))

printfn "%A" (runList  [([0..3], true); ([10..13], true); ([20..23], true)])
printfn "%A" (runList  [([0..3], true); ([10..13], true); ([20..23], false)])
val testList :
  bool ->
    int list ->
      TransactionM.TransactionHandle<'a,int list,
                                     TransactionM.TransactionState<'b,string>> ->
        TransactionM.TransactionM<'a,int list,('c -> 'c)>
val merge :
  TransactionM.TransactionM<'a,'b list,TransactionM.TransactionState<'c,'d>> ->
    TransactionM.TransactionM<'a,'b list,TransactionM.TransactionState<'e,'d>> ->
      TransactionM.TransactionHandle<'a,'b list,
                                     TransactionM.TransactionState<string,'d>> ->
        TransactionM.TransactionM<'a,'b list,('f -> 'f)>
val runMerge :
  'a ->
    TransactionM.TransactionM<(TransactionM.TransactionState<string,'b> *
                               'c list),'c list,
                              TransactionM.TransactionState<'d,'b>> ->
      TransactionM.TransactionM<(TransactionM.TransactionState<string,'b> *
                                 'c list),'c list,
                                TransactionM.TransactionState<'e,'b>> ->
        TransactionM.TransactionState<string,'b> * 'c list
val runList :
  (int list * bool) list ->
    TransactionM.TransactionState<string,string> * int list

Start runMerge 1.
    first list: [7; 6; 0; 1; 2; 3]
    second list: [7; 6; 10; 11; 12; 13]
runMerge 1: (Commit "commit.", [7; 6; 0; 1; 2; 3; 7; 6; 10; 11; 12; 13]) 

Start runMerge 2.
runMerge 2: (Rollback "rollback!", []) 

Start runList.
    first list: []
    second list: [7; 6; 0; 1; 2; 3]
    first list: [7; 6; 0; 1; 2; 3]
    second list: [7; 6; 10; 11; 12; 13]
    first list: [7; 6; 0; 1; 2; 3; 7; 6; 10; 11; 12; 13]
    second list: [7; 6; 20; 21; 22; 23]
(Commit "commit.",
 [7; 6; 0; 1; 2; 3; 7; 6; 10; 11; 12; 13; 7; 6; 20; 21; 22; 23])

Start runList.
    first list: []
    second list: [7; 6; 0; 1; 2; 3]
    first list: [7; 6; 0; 1; 2; 3]
    second list: [7; 6; 10; 11; 12; 13]
    first list: [7; 6; 0; 1; 2; 3; 7; 6; 10; 11; 12; 13]
(Rollback "rollback!", [])
Interessant ist ob die Transaktionen asynchron ausgeführt werden können. Ich habe es leider nicht hingekriegt.

Hier ist meine F# Implementierung von der Transaktion Monad.
// from http://hackage.haskell.org/packages/archive/monad-tx/0.0.1/doc/html/Control-Monad-Tx.html
module TransactionM 

open System

// 'e : error type
// 'a : transaction state type
type TransactionState<'e,'a> =
    | Begin
    | Abort of ('e option)
    | Dirty of ('e option)
    | Rollback of 'a
    | Commit of 'a

// 's : state
// 'a : TransactionState
// 'r : result 
// ('s -> 'a -> 'r) : continuation
type TransactionM<'r, 's, 'a> = TransactionM of ('s -> ('s -> 'a -> 'r) -> 'r)

type TransactionHandle<'r, 's, 'a> = TransactionHandle of (('a * TransactionHandle<'r, 's, 'a>) -> TransactionM<'r, 's, unit>)

let inline runTransaction (TransactionM g) s k = g s k

// result is of type (TransactionState * state)
let inline runTransaction_ (TransactionM g) s = g s (fun s' a ->  (a, s'))
// result is of type TransactionState
let inline runTransactionState (TransactionM g) s = g s (fun _ a ->  a)

let inline withCommit f = 
    TransactionM (fun s k -> 
                    let (TransactionM g) = f (fun a -> TransactionM (fun s' _ ->  k s' a)) 
                    g s k)

let inline withRollback f = 
    TransactionM (fun s k -> 
                    let (TransactionM g) = (f (fun a -> TransactionM (fun _ _ -> k s a))) 
                    g s k)

let inline bind (TransactionM g) f = 
    TransactionM(fun s k -> 
                    g s (fun s' a ->
                            let (TransactionM g') = f a
                            g' s' k))
//computation workflow builder.
type TransactionBuilder() =
    member this.Return(a)                               = TransactionM(fun s k -> k s a) 
    member this.Bind(m, k)                              = bind m k
    member this.Zero ()                                 = this.Return ()
    member this.Combine(r1, r2)                         = this.Bind(r1, fun _ -> r2) 
    member this.ReturnFrom(m : TransactionM<_,_,_>)     = m
    member this.Delay(f)                                = this.Bind(this.Return (), f)
    
    member this.TryFinally(computation, compensation) =
        TransactionM(fun s k -> 
            try
                runTransaction computation s k
            finally
                compensation())

    member this.Using(res: #IDisposable, body) =
        this.TryFinally(body res,
            (fun () -> match res with null -> () | disp -> disp.Dispose()))

    member this.TryWith(computation, handler) =
        TransactionM(fun s k ->
            try
                runTransaction computation s k
            with e -> runTransaction (handler e) s k)

let transaction = new TransactionBuilder()

let inline bindM builder m f = (^M: (member Bind: 'd -> ('e -> 'c) -> 'c) (builder, m, f))

let inline (>>.) m n = bindM transaction m (fun _ ->  n)

let inline isBegin t =
    match t with
    | Begin -> true
    | _ -> false

let inline fmap f (TransactionM g) = TransactionM (fun s k -> g s (fun s' a -> k s' (f a)))
//begin transaction.
let inline beginT f =
    let checkpoint  = 
        withCommit (fun fcommit ->
            withRollback (fun frollback ->
                transaction {
                    let go (transactionState, handle) =
                        match transactionState with
                        | Begin         -> failwith     "nested"
                        | Abort e       -> frollback    (Abort e,       handle)
                        | Dirty e       -> fcommit      (Dirty e,       handle)
                        | Rollback a    -> frollback    (Rollback a,    handle)
                        | Commit a      -> fcommit      (Commit a,      handle)
                    return (Begin, TransactionHandle go) 
                    } ))

    withRollback (fun fabort ->
        transaction {
                    let! (transactionState, handle)  = checkpoint
                    if isBegin transactionState then
                        return!  (f  handle >>. fabort (Abort None))
                    return transactionState
                 })

//a bunch of helpers, which allow to access and manipulate transaction.

let inline alwaysCommit a = TransactionM(fun s k -> k s (Commit a))

let inline jump (TransactionHandle k) stat = 
    (k (stat, TransactionHandle k)) >>. TransactionM(fun s k -> k s id)

let inline abort    handle e = jump handle (Abort e)

let inline dirty    handle e = jump handle (Dirty e)

let inline rollback handle a = jump handle (Rollback a)

let inline commit   handle a = jump handle (Commit a)

let get = TransactionM (fun s k -> k s s)

let inline gets f = TransactionM (fun s k -> k s (f s))

let inline set s = 
    TransactionM (fun _ k -> k s ())

let inline modify f = TransactionM(fun s k -> k (f s) ())