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>

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]