Seiten

Samstag, 5. Mai 2012

Lazy Levenshtein Visualisation. F# WPF MVVM.

Hier habe ich eine F# WPF(MVVM) Anwendung geschrieben um den Lazy Levenshtein Algorithmus zu visualisieren.



Code on GitHub

Ein paar Sätze, wie man das "Spielfeld" mit dem WPF-MVVM implementieren kann. Ich habe dazu ein empfehlenswertes F# MVVM Template genommen.
Als erstes die ViewModelBase-Klasse auf die Implementierung mit F# Quotations umgestellt.
//ViewModelBase.fs
namespace LazyLevenshteinMVVM.ViewModel

open System

open System.ComponentModel
open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
// implement the INotifyPropertyChanged interface with F# quotations.
type ViewModelBase() =
    let propertyChangedEvent = new Event<PropertyChangedEventHandler, PropertyChangedEventArgs>()
    interface INotifyPropertyChanged with
        [<CLIEvent>]
        member x.PropertyChanged = propertyChangedEvent.Publish
    member x.OnPropertyChanged (expr: Expr) = 
        match expr with
        | PropertyGet(_, methodInfo, _) ->
            let propertyName = methodInfo.Name
            propertyChangedEvent.Trigger(x, new PropertyChangedEventArgs(propertyName))
        | other -> failwith "not implemented" 
Als nächstes brauchen wir zwei View Model Klassen: eine für eine Zelle des Spielfeldes und eine für das Spielfeld selbst.
//BoardViewModel.fs
namespace LazyLevenshteinMVVM.ViewModel

open System
open System.Windows
open System.Windows.Threading
open System.Windows.Input
open System.ComponentModel
open System.Collections.ObjectModel
open LazyLevenshteinMVVM.Model

//View Model for a board cell.
type BoardCell() =
    inherit ViewModelBase()
    let mutable cellValue = ""
    let mutable isEvaluated = false
    let mutable isEvaluatedFrom =false
    let mutable isEvaluate = false
    let mutable isThunk = false
    let mutable isDiagStep = false
    let mutable evaluateText = String.Empty
    let mutable evaluatedFrom = String.Empty

    member x.FromPoint (point : LazyLevenshteinMVVM.Model.Point) =
        match x.IsEvaluated with
        | true -> 
            match point.isDiagonalStep, point.isEvaluatedFrom with 
            | true, true ->
                x.IsDiagStep <- true
                x.IsEvaluatedFrom <- true
            | true, false ->  x.IsDiagStep <- true
            | false, true ->  x.IsEvaluatedFrom <- true
            | _ -> ()
        | false ->
            x.IsEvaluate <- point.isEvaluate
            x.IsDiagStep <- point.isDiagonalStep
            x.IsThunk <- point.isThunk
            match point.value with
            | Some v -> 
                match point.isEvaluate, point.isEvaluated, point.isEvaluatedFrom, point.isThunk with
                | true, _, _, _ ->   x.EvaluateText <- v
                | _, true, _, _ -> 
                    x.IsEvaluated <- point.isEvaluated
                    x.EvaluatedFrom <- point.evaluatedFrom
                    x.CellValue <- v
                |_, _, true, _ ->    
                    x.IsEvaluatedFrom <- point.isEvaluatedFrom
                | _, _, _, true -> 
                    x.IsThunk <- point.isThunk
                    x.CellValue <- v
                |_->()
            | None -> ()
    member x.IsEvaluated 
        with get() = isEvaluated
        and set value = 
            isEvaluated <- value
            x.OnPropertyChanged(<@x.IsEvaluated@>)
    member x.IsEvaluate 
        with get() = isEvaluate
        and set value = 
            isEvaluate <- value
            x.OnPropertyChanged(<@x.IsEvaluate@>)
    member x.IsThunk 
        with get() = isThunk
        and set value = 
            isThunk <- value
            x.OnPropertyChanged(<@x.IsThunk@>)
    member x.IsDiagStep 
        with get() = isDiagStep
        and set value = 
            isDiagStep <- value
            x.OnPropertyChanged(<@x.IsDiagStep@>)
    //computed edit distance for given letters from string A and B.
    member x.CellValue
        with get() = cellValue
        and set value = 
            cellValue <- value
            x.OnPropertyChanged(<@x.CellValue@>)
    //shows the letters for which a calculation should evaluate.
    member x.EvaluateText
        ...
    //describes how the value was computed. 
    //An element depends only on the elements to the west, north-west and north
    member.EvaluatedFrom
        ....    
    member x.IsEvaluatedFrom
        ...
Das Spielfeld.
Wenn man den Text in Eingabefelder ändert, wird das Bord sofort über den Aufruf von der BuildBoard-Methode neu erstellt und die Animation mit der Hilfe von DispatcherTimer neu gestartet. Über die GridRows-Eigenschaft werden die Änderungen an das View weitergeleitet.
// View Model for a board.
type Board() as x =
    inherit ViewModelBase()
        
    let mutable rows = new ObservableCollection<ObservableCollection<BoardCell>>()
    let mutable sizex = 0
    let mutable sizey = 0
    let mutable textA = String.Empty
    let mutable textB = String.Empty

    let model = LevenshteinModel.Empty
    let mutable timer = new DispatcherTimer(DispatcherPriority.Normal)
    let mutable distance = 0
    let pointToCell (point : LazyLevenshteinMVVM.Model.Point)  =
                let col = rows.[snd point.xy + 2] 
                let cell = col.[fst point.xy + 2]
                cell.FromPoint point
                cell.IsEvaluatedFrom <- false
                cell.IsDiagStep <- false
                col.[fst point.xy + 2] <- cell
                rows.[snd point.xy + 2] <- col       
    do
        timer.Interval <- new TimeSpan(0, 0, 0, 0, 1500)
        timer.Tick.Add(fun _  -> x.AnimateOneStep () )    
    
    member x.AnimateOneStep () = 
        match rows.Count, model.OneStep () with 
        | _, [] -> timer.Stop()
        | 0, _ -> timer.Stop()
        | _, points ->
            points |> List.iter pointToCell 
            x.OnPropertyChanged(<@x.GridRows@>)
    //build the board.
    member private x.BuildBoard  =
        [for i in 0..sizex-2 do
                rows.[0].[i+2].CellValue <- textA.[i].ToString()
                rows.[1].[i+2].CellValue <- (i+1).ToString() 
                rows.[1].[i+2].IsEvaluated<-true
        ] |> ignore

        rows.[1].[1].CellValue <- "0" 
        [for j in 2..sizey do  
              let c = rows.[j].[0]
              let n = rows.[j].[1]
              c.CellValue <- textB.[j-2].ToString()
              n.CellValue <- (j - 1).ToString()
              n.IsEvaluated<-true
        ] |> ignore
        timer.Stop()

        model.Run(textA, textB)
        match model.distance with
        | None -> x.Distance <- 0
        | Some v -> x.Distance <- v
        x.OnPropertyChanged(<@x.GridRows@>)
        timer.Start()

    member x.TextA
        with get() = textA
        and set value = 
            textA <- value
            x.SizeX <- (if textA.Length > 0 then textA.Length + 1 else 0)
            x.BuildBoard
            x.OnPropertyChanged(<@x.TextA@>)
            
    member x.TextB
        with get() = textB
        and set value = 
            textB <- value
            x.SizeY <- (if textB.Length > 0 then textB.Length + 1 else 0)
            x.BuildBoard
            x.OnPropertyChanged(<@x.TextB@>)
    member x.Distance 
        with get() = distance
        and set value = 
            distance <- value
            x.OnPropertyChanged(<@x.Distance@>)

    member x.GridRows = rows

    member private x.Size =
        sizex <- (if sizex > 0 then sizex else (if sizey > 0 then 1 else 0))
        sizey <- (if sizey > 0 then sizey else (if sizex > 0 then 1 else 0))
        [   for i in 0..sizey do
                let col = new ObservableCollection<BoardCell>()
                for j in 0..sizex do
                    let c = new BoardCell()
                    c.CellValue <-""
                    col.Add(c)

                rows.Add(col) ] |> ignore  
    member x.SizeY
        with get() = sizey
        and set value = 
            sizey <- value
            rows <- new ObservableCollection<ObservableCollection<BoardCell>>()
            x.Size
            x.OnPropertyChanged(<@x.SizeY@>)
    member x.SizeX
        with get() = sizex
        and set value = 
            sizex <- value
            rows <- new ObservableCollection<ObservableCollection<BoardCell>>()
            x.Size
            x.OnPropertyChanged(<@x.SizeX@>)
Das View.
<!--Board.xaml--> 
<UserControl 
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:ViewModel="clr-namespace:LazyLevenshteinMVVM.ViewModel;assembly=App"
 HorizontalAlignment ="Stretch"
 HorizontalContentAlignment ="Stretch"
 VerticalAlignment ="Stretch"
 VerticalContentAlignment ="Stretch"
 Foreground="White">
    <UserControl.DataContext>
        <ViewModel:Board> </ViewModel:Board>
    </UserControl.DataContext>
    <UserControl.Resources>
        <Storyboard x:Key="selectedStory">
            <DoubleAnimation Storyboard.TargetName="TextBlock"
                                  Storyboard.TargetProperty="Opacity"
                                  From="0"
                                  To="0.8"
                                  Duration="0:0:0.8"/>
        </Storyboard>
        <LinearGradientBrush x:Key="BoardBackground" StartPoint="0,0" EndPoint="1,0">
            ...
        </LinearGradientBrush>
        <DataTemplate x:Key ="CellTemplate" >
                <Border x:Name ="Border" BorderBrush ="DimGray" BorderThickness ="1">
                    <Border.Background>
                       ...
                    </Border.Background>
                <StackPanel Orientation="Vertical" >
                    <TextBlock x:Name="evaluateText" Text="{Binding Path=EvaluateText}"/>
                    <TextBox x:Name ="TextBlock" Margin="3"
                     FontWeight ="Bold" FontSize ="12"  Text ="{Binding Path=CellValue}" 
                     HorizontalAlignment ="{Binding ElementName=Border, Path=HorizontalAlignment}" 
                     VerticalAlignment ="Center"
                             Focusable ="False" Opacity="0.8" Background="White">
                        <TextBox.BitmapEffect>
                            <DropShadowBitmapEffect/>
                        </TextBox.BitmapEffect>
                    </TextBox>
                    <TextBlock x:Name="evaluateFrom" Text="{Binding Path=EvaluatedFrom}" 
                                  FontSize="11" />
                </StackPanel>
            </Border>             
            <DataTemplate.Triggers>        
                <DataTrigger Binding ="{Binding IsEvaluated}" Value ="True">
                    <Setter TargetName ="TextBlock" Property ="Foreground" Value="Red"/>
                    <Setter TargetName ="TextBlock" Property ="Background" Value="Blue"/>
                    <DataTrigger.EnterActions>
                        <BeginStoryboard Storyboard="{StaticResource selectedStory}">
                        </BeginStoryboard>
                        <BeginStoryboard x:Name="evaluatedStory">
                            <Storyboard>
                                <DoubleAnimation Storyboard.TargetName="TextBlock"
                                  Storyboard.TargetProperty="FontSize"
                                  From="12"
                                  To="22"
                                  Duration="0:0:0.8" AutoReverse="True" />
                            </Storyboard>
                        </BeginStoryboard>
                    </DataTrigger.EnterActions>
                </DataTrigger>
                
                <DataTrigger Binding ="{Binding IsThunk}" Value ="True">
                    <Setter TargetName ="TextBlock" Property ="Background" Value="LightGreen"/>
                </DataTrigger>
                
                <DataTrigger Binding="{Binding IsEvaluatedFrom}" Value="True">
                    ...
                </DataTrigger>
                
                <DataTrigger Binding="{Binding IsEvaluate}" Value="True">
                    ...
                </DataTrigger>
                
                <DataTrigger Binding="{Binding IsDiagStep}" Value="True">
                    ...
                </DataTrigger>
            </DataTemplate.Triggers>
        </DataTemplate>
        <DataTemplate x:Key ="BoardTemplate">
            <ItemsControl ItemTemplate ="{StaticResource CellTemplate}" ItemsSource ="{Binding}">
                <ItemsControl.ItemsPanel>
                    <ItemsPanelTemplate>
                        <UniformGrid Rows ="1"/>
                    </ItemsPanelTemplate>
                </ItemsControl.ItemsPanel>
            </ItemsControl>
        </DataTemplate>        
    </UserControl.Resources>
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="6*" />
            <ColumnDefinition Width="1*" />
        </Grid.ColumnDefinitions>
        <ItemsControl Grid.Column="0" ItemTemplate ="{StaticResource BoardTemplate}" 
                         ItemsSource ="{Binding Path=GridRows}" x:Name ="MainList">
            <ItemsControl.ItemsPanel>
                <ItemsPanelTemplate>
                    <UniformGrid Columns ="1" Background="{StaticResource BoardBackground}"/>
                </ItemsPanelTemplate>
            </ItemsControl.ItemsPanel>
        </ItemsControl>
        <StackPanel Grid.Column="1" Orientation="Vertical" Margin="5">
            <Label Content="Text 1" />
            <TextBox MinWidth="10" MaxHeight="25" MaxLength="12" MaxWidth="200" 
                        Text="{Binding Path=TextA,UpdateSourceTrigger=PropertyChanged}"></TextBox>
            <Label Content="Text 2" />
            <TextBox MinWidth="10" MaxHeight="25" MaxLength="12" MaxWidth="200" 
                        Text="{Binding Path=TextB,UpdateSourceTrigger=PropertyChanged}"></TextBox>
            <Label  Content="N - North" />
            <Label Content="W - West" />
            <Label Content="NW - North West" />
            <Label Content="Distance"  Margin="5" />
            <TextBox  Margin="5" Text="{Binding Path=Distance}" />
        </StackPanel>
    </Grid>
</UserControl>

Donnerstag, 19. April 2012

F#. Lazy Levenshtein Distance.

Update : Hier die Visualisierung.

Jetzt ist mir endlich gelungen den Lazy Levenshtein Distance Algorithmus aus dem letzten Post in F# zu implementieren.
// levenshtein.fs
// According to the article, the worst-case complexity is O(|A|*|B|).
// In this case, the array version is much faster, which is probably due to the overhead 
// of the use of Lazy and LazyList delayed methods in F#.
// However, if A=B the complexity is now O(|A|) because only the main diagonal is evaluated.
// In this case, lazy version is faster.
    //from http://www.haskell.org/haskellwiki/Edit_distance.
    // "An entry depends on three neighbours which lie on the diagonal below, the current diagonal and the diagonal above.
    //  Each diagonal therefore depends on the diagonal below and the diagonal above where a row depends only on the row above"    
    let inline editDist sa sb =
        let min3 x y z = if x < y then x else min y (LazyList.head z)
        let lab = List.length sa - List.length sb
        let rec mainDiag:_ Lazy = 
            lazy(oneDiag sa sb (LazyList.delayed (fun () -> LazyList.head uppers.Value)) 
                               (LazyList.consDelayed -1 (fun ()-> LazyList.head lowers.Value)))
        //upper diagonals
        and uppers : _ Lazy = lazy(eachDiag sa sb (LazyList.consDelayed (mainDiag.Value) (fun ()-> uppers.Value)))
        //lower diagonals. note swap sb sa !
        and lowers : _ Lazy = lazy(eachDiag sb sa (LazyList.consDelayed (mainDiag.Value) (fun ()-> lowers.Value)))
        // 'a list -> 'a list -> LazyList<LazyList<int>>
        and eachDiag a b diag = 
            match a, b, diag with
            | _, [], _ -> LazyList.empty
            | a, (bch :: bs), ( LazyList.Cons (lastDiag, diags)) -> 
                let nextDiag = LazyList.delayed (fun () -> LazyList.head (LazyList.tail diags))
                LazyList.consDelayed (oneDiag a bs nextDiag lastDiag) (fun ()-> (eachDiag a bs diags))
        // 'a list -> 'a list -> LazyList<int> -> LazyList<int> -> LazyList<int>
        and oneDiag a b diagAbove diagBelow  = 
            // nw - north-west, n - north, w - west.
            // 'a list -> 'a list -> int -> LazyList<int> -> LazyList<int> -> LazyList<int>
            let rec doDiag a b nw n w = 
                match a, b with
                | [], _ -> LazyList.empty
                | _, [] -> LazyList.empty 
                | (ach :: achs), (bch :: bchs) -> 
                    
                    let me  = if ach = bch then nw else 1 + min3 (LazyList.head w) nw n
                    LazyList.consDelayed me (fun () -> 
                                                doDiag achs bchs me                         // hope these
                                                    (LazyList.delayed (fun () -> LazyList.tail n))  // <---    
                                                    (LazyList.delayed (fun () -> LazyList.tail w))) // <--- not evaluated.
               
            let firstelt = 1 + (LazyList.head diagBelow)
            LazyList.consDelayed firstelt (fun ()-> doDiag a b firstelt diagAbove (LazyList.tail diagBelow))

        if lab = 0      then mainDiag.Value
        else if lab > 0 then (LazyList.toArray lowers.Value).[lab - 1]
        else                 (LazyList.toArray (uppers.Value)).[-1 - lab]

    let inline lazyDist (s1:string) (s2:string) =
        match s1.Length,s2.Length with
        |0, l2 -> l2
        |l1, 0 -> l1
        | _ -> 
            let res = editDist (List.ofSeq s1) (List.ofSeq s2) |> LazyList.toArray
            res.[res.Length - 1]
let inline timeExec f a b s =
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    let res = f a b
    timer.Stop()
    printfn "%A." s
    printfn "distance = %A: Ellapsed Time: %A ticks, %A ms." res timer.ElapsedTicks timer.ElapsedMilliseconds

let str1 = String.replicate 500 "abcd" 
let str2 = String.replicate 500 "defg"  
let str3 = String.replicate 1000 "a"  
let str4 = (String.replicate 20 "aba")+(String.replicate 500 "aa") + "aaa" + (String.replicate 500 "aa") + (String.replicate 20 "aba") 
let str5 = (String.replicate 20 "aca")+(String.replicate 500 "aa") + "bbb" + (String.replicate 500 "aa") + (String.replicate 20 "aca")

[0..10] |> List.map (fun _ -> 
    printfn "-----------------------"
    timeExec levenshteinDistanceArray str1 str2 "levenshtein Distance with Array. worst-case."
    timeExec lazyDist str1 str2 "lazy levenshtein Distance. worst-case."
    timeExec levenshteinDistanceArray str3 str3 "levenshtein Distance with Array. special case of similar strings."
    timeExec lazyDist str3 str3 "lazy levenshtein Distance. special case of similar strings."
    timeExec levenshteinDistanceArray str4 str5 "levenshtein Distance with Array."
    timeExec lazyDist str4 str5 "lazy levenshtein Distance."
    )|>ignore

-----------------------
"levenshtein Distance with Array. worst-case.".
distance = 1502: Ellapsed Time: 3858477L ticks, 269L ms,
"lazy levenshtein Distance. worst-case.".
distance = 1502: Ellapsed Time: 147370307L ticks, 10292L ms.
"levenshtein Distance with Array. special case of similar strings."
distance = 0: Ellapsed Time: 1072085L ticks, 74L ms.
"lazy levenshtein Distance. special case of similar strings.".
distance = 0: Ellapsed Time: 115395L ticks, 8L ms.
"levenshtein Distance with Array.".
distance = 43: Ellapsed Time: 4217920L ticks, 294L ms.
"lazy levenshtein Distance.".
distance = 43: Ellapsed Time: 3744706L ticks, 261L ms.
-----------------------
"levenshtein Distance with Array. worst-case.".
distance = 1502: Ellapsed Time: 3896606L ticks, 272L ms.
"lazy levenshtein Distance. worst-case.".
distance = 1502: Ellapsed Time: 146242131L ticks, 10213L ms.
"levenshtein Distance with Array. special case of similar strings."
distance = 0: Ellapsed Time: 1038478L ticks, 72L ms.
"lazy levenshtein Distance. special case of similar strings.".
distance = 0: Ellapsed Time: 10024L ticks, 0L ms.
"levenshtein Distance with Array.".
distance = 43: Ellapsed Time: 4204501L ticks, 293L ms.
"lazy levenshtein Distance.".
distance = 43: Ellapsed Time: 3610026L ticks, 252L ms.
-----------------------
"levenshtein Distance with Array. worst-case.".
distance = 1502: Ellapsed Time: 4039147L ticks, 282L ms.
"lazy levenshtein Distance. worst-case.".
distance = 1502: Ellapsed Time: 145049786L ticks, 10130L ms.
"levenshtein Distance with Array. special case of similar strings."
distance = 0: Ellapsed Time: 1180816L ticks, 82L ms.
"lazy levenshtein Distance. special case of similar strings.".
distance = 0: Ellapsed Time: 27104L ticks, 1L ms.
"levenshtein Distance with Array.".
distance = 43: Ellapsed Time: 4247992L ticks, 296L ms.
"lazy levenshtein Distance.".
distance = 43: Ellapsed Time: 3652880L ticks, 255L ms.

Update
Write "min3" and "let me = if ach = bch then nw else 1 + min3 (LazyList.head w) nw n" explicitly
in order to avoid the unnecessary delay.
give an additional performance gain.
// levenshtein.fs 
    let inline editDist sa sb =
        //let min3 x y z = if x < y then x else min y (LazyList.head z)
        let lab = List.length sa - List.length sb
        let rec mainDiag:_ Lazy = 
            lazy(oneDiag sa sb (LazyList.delayed (fun () -> LazyList.head uppers.Value)) 
                               (LazyList.consDelayed -1 (fun ()-> LazyList.head lowers.Value)))
        //upper diagonals
        and uppers : _ Lazy = lazy(eachDiag sa sb (LazyList.consDelayed (mainDiag.Value) (fun ()-> uppers.Value)))
        //lower diagonals. note swap sb sa !
        and lowers : _ Lazy = lazy(eachDiag sb sa (LazyList.consDelayed (mainDiag.Value) (fun ()-> lowers.Value)))
        // 'a list -> 'a list -> LazyList<LazyList<int>>
        and eachDiag a b diag = 
            match a, b, diag with
            | _, [], _ -> LazyList.empty
            | a, (bch :: bs), ( LazyList.Cons (lastDiag, diags)) -> 
                let nextDiag = LazyList.delayed (fun () -> LazyList.head (LazyList.tail diags))
                LazyList.consDelayed (oneDiag a bs nextDiag lastDiag) (fun ()-> (eachDiag a bs diags))
        // 'a list -> 'a list -> LazyList<int> -> LazyList<int> -> LazyList<int>
        and oneDiag a b diagAbove diagBelow  = 
            // nw - north-west, n - north, w - west.
            // 'a list -> 'a list -> int -> LazyList<int> -> LazyList<int> -> LazyList<int>
            let rec doDiag a b nw n w = 
                match a, b with
                | [], _ -> LazyList.empty
                | _, [] -> LazyList.empty 
                | (ach :: achs), (bch :: bchs) -> 
                    if (ach  = bch) then 
                //case if ach = bch then nw
                        LazyList.consDelayed nw (fun ()-> 
                                                    doDiag achs bchs nw 
                                                        (LazyList.delayed (fun ()-> LazyList.tail n)) 
                                                        (LazyList.delayed (fun ()-> LazyList.tail w)))
                // case else 1 + min3 (LazyList.head w) nw n
                    else if (LazyList.head w) < nw then
                    // case let min3 x y z = if x < y then x ...
                        let me = 1 + (LazyList.head w)
                        LazyList.consDelayed me (fun ()-> 
                                                    doDiag achs bchs me 
                                                        (LazyList.delayed (fun ()-> LazyList.tail n)) 
                                                        (LazyList.tail w))
                    // case let min3 x y z = ... else min y (LazyList.head z)
                    else
                        let me = 1 + min nw (LazyList.head n)
                        LazyList.consDelayed me (fun ()-> 
                                                    doDiag achs bchs me 
                                                        (LazyList.tail n)
                                                        (LazyList.tail w))               
            let firstelt = 1 + (LazyList.head diagBelow)
            LazyList.consDelayed firstelt (fun ()-> doDiag a b firstelt diagAbove (LazyList.tail diagBelow))

        if lab = 0      then mainDiag.Value
        else if lab > 0 then (LazyList.toArray lowers.Value).[lab - 1]
        else                 (LazyList.toArray (uppers.Value)).[-1 - lab]

    let inline lazyDist (s1:string) (s2:string) =
        match s1.Length,s2.Length with
        |0, l2 -> l2
        |l1, 0 -> l1
        | _ -> 
            let res = editDist (List.ofSeq s1) (List.ofSeq s2) |> LazyList.toArray
            res.[res.Length - 1]

Freitag, 13. April 2012

F# Type-directed memoization. IntTrie, knapsack problem and levenshtein distance.

Nach wochenlangem Bewerbungsstress und Frustration darüber, dass es wohl kaum F#-Jobstellen auf dem Markt gibt und die wenigen, die da sind, richten sich ausschlislich an Hochschulabsolventen, habe ich mich weiter mit der "Type-directed Memoization" beschäftigt. Dabei endeckte ich eine interessante OCaml Implementation.
Ich suchte nach konkreten praktischen Beispielen und merkte sehr schnell, dass in diesem Zusammenhang oft zwei Algorithmen genannt werden. Das Knapsack Problem
und die Levenshtein-Distanz. Hier ein paar Links zu diesen Themen.
Solving the 0-1 knapsack problem using continuation-passing style with memoization in F#.
    Haskell Version.
    Haskell Version mit der IntTrie-Datenstruktur.
    Die Levenshtein-Distanz auf Rosetta Code Seite.
    "Haskell function computes the edit distance in O(length a * (1 + dist a b)) time complexity".
    Lazy Levenshtein Distanz.
Von IntTrie war ich sofort begeistert und versuchte die abgespeckte Version - also nur positive Integers - nach F# zu übertragen.
// TypeMemo.fs
namespace TypeMemoization
// from http://hackage.haskell.org/packages/archive/data-inttrie/0.0.7/doc/html/src/Data-IntTrie.html
module BitTrie =
    
    type BitTrie<'a> = BitTrie of Lazy<'a> * Lazy<BitTrie<'a>> * Lazy<BitTrie<'a>>
    // A trie from positiv integers to values of type a. 
    type IntTrie<'a> = IntTrie of Lazy<'a> * BitTrie<'a>
    
    let inline testBit x = (x &&& 1) <> 0

    let rec fmap f (BitTrie (x, l, r)) = 
        BitTrie( lazy(f x.Value), 
                 lazy(fmap f l.Value), 
                 lazy(fmap f r.Value) )

    let identityPositive = 
        let rec go x = 
            BitTrie (x, 
                     lazy(fmap (fun n-> n <<< 1) (go x)), 
                     lazy(fmap (fun n -> (n <<< 1) ||| 1) (go x)))
        go (lazy(1))

    let inline fmapi f (IntTrie(z, pos)) = 
        IntTrie(lazy(f z.Value), fmap f pos)

    //The identity trie.
    let identity = IntTrie (lazy(0), identityPositive)

    let inline toTrie f  =  fmapi f identity

    let rec applyPositive (BitTrie (one, even, odd)) x =
        match x with
        | i when i = 1 ->       one
        | i when testBit i  ->  applyPositive odd.Value (x >>> 1) 
        | otherwise   ->        applyPositive even.Value (x >>> 1)

    // Apply the trie to an argument.
    let inline apply (IntTrie(z, pos)) x =
        match x with
        | 0 -> z.Value
        |_ -> (applyPositive pos x).Value 
    
    let inline memo f = apply (toTrie f)

    // Memoize a two argument function (just apply the table directly for
    // single argument functions).
    let inline memo2 f = memo (memo << f)
//knapsack.fs
namespace TypeMemoization

module knapsack =
    open System

    let inline genItems n = 
        match n with
        | 0 -> Array.empty 
        | _ -> Array.init n 
                        ( fun i ->
                            let weight = i % 5
                            let value = (float)(weight * i)
                            weight, value )
    let inline max (x:float) (y:float) = max x y 

    let inline knapsackOriginal desiredWeight (items:_[]) =               
        let inline weightOf i = fst items.[i-1]
        let inline valueOf i = snd items.[i-1] 

        let rec knapsack' i w  = 
            match i, w  with
            | 0, _ | _, 0 -> 0.
            | i, w    -> 
                match i with
                | i' when (weightOf i') > w -> 
                    knapsack' (i' - 1) w           
                | _ -> 
                    max (knapsack' (i - 1) w)  ((knapsack' (i - 1) (w - weightOf i)) + valueOf i)
                    
        knapsack' items.Length desiredWeight

    let inline knapsack weight (value:int->float) =                
        
        let rec knapsack' i w  = 
            match i, w  with
            | 0, _ | _, 0 -> 0.
            | i, w    -> 
                match i with
                | i' when (weight i') > w ->
                    knapsackMemo (i' - 1) w           
                | _ -> 
                    max (knapsackMemo (i - 1) w)  ((knapsackMemo (i - 1) (w - weight i)) + value i)
                    
        and knapsackMemo  = BitTrie.memo2 knapsack'
        knapsackMemo  

    let inline knapsackMemoized desiredWeight (items:_[]) =
        let inline weightOf i = fst items.[i-1]
        let inline valueOf i = snd items.[i-1] 

        knapsack weightOf valueOf (items.Length) (desiredWeight)
Zwar ist die "memoized" Version schneller als der originale Knapsack-Algorithmus, aber leider viel langsamer als Zach Bray's Version und folglich um X-faches langsamer als die imperative Variante. Es kann aber auch sein, dass meine F# Implementierung von IntTrie nicht die beste ist.

Mit der Levenshtein Distanz sieht es noch schlimmer aus. Wieder ist die "memoized" Variante besser als die naive Version, aber mit der Array-Lösung kann sie überhaupt nicht mithalten. Interessant ist der bereits erwähnte Lazy Levenshtein Algorithmus. Dieser in F# zu übertragen ist mir leider nicht gelungen.
Also ist mein Frust nur noch tiefer geworden.
// 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 BitTrie =
    ...
module TypeMemo =
    open BitTrie

    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

    type CharTable<'w> =
        | CharTable of IntTrie<'w>  
        interface IFromTable<char, 'w> with
            member inline x.fromTable c =
                match x with
                | CharTable t ->  apply t (int c)
    let inline charToTable f = 
        CharTable (toTrie (f << char))
    
    let inline memoCharList2 f = 
        let memo g =
            listToTable g charToTable  |> fromTable
        memo (memo << f)
Levenshtein Distanz.
//levenshtein .fs
namespace TypeMemoisation
module levenshtein =
    open System
    
    let inline private naiveLevenshteinDistance del sub ins  =  
        let rec inner s1 s2 =
            match s1, s2 with
            | s1,     []     -> ins * List.length s1 
            | [],     s2     -> ins * List.length s2 
            | x :: xs, y :: ys ->
                match x = y with
                | true -> inner xs ys
                | _ -> List.min [ del + inner xs s2; 
                                 sub + inner s1 ys; 
                                 ins + inner xs ys] 
        inner

    let inline runNaiveLevenshteinDistance (s1:string) (s2:string) =
        naiveLevenshteinDistance 1 1 1 (List.ofSeq s1) (List.ofSeq s2)
    //memoized version.
    let inline private levenshteinDistance del sub ins  =  
        let rec inner s1 s2 =
            match s1, s2 with
            | s1,     []     -> ins * List.length s1 
            | [],     s2     -> ins * List.length s2 
            | x :: xs, y :: ys ->
                match x = y with
                | true -> memo xs ys
                | _ -> min (del + memo xs s2)   
                                 (min (sub + memo s1 ys) (ins + memo xs ys)) 
        and memo = 
                TypeMemo.memoCharList2 inner
        memo

    let inline levenshteinDistanceMemoized (s1:string) (s2:string) =
        levenshteinDistance 1 1 1 (List.ofSeq s1) (List.ofSeq s2)
    
    //array version.
    let inline levenshteinDistanceArray (s1:string) (s2:string) =
         let sa, sb:char [] * char [] = s1.ToCharArray(), s2.ToCharArray()
         let len = Array.length sa
         let m = len - 1

         let inline compute z xc = min (z+1) xc

         let inline transform (narr : int []) chb =
              Array.zip3 sa.[..m] narr.[..m] narr.[1..m+1] 
              |> Array.map (fun (cha, x, y) -> min (y + 1) (x + abs(compare cha chb)) )
              |> Array.scan compute (narr.[0] + 1)
         let result = Array.fold transform [|0..len|] sb
         result.[result.Length - 1]

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.