ようこそ。睡眠不足なプログラマのチラ裏です。

VB、C#、F#　それぞれのインデクサ。F# コンパイラのソースを読んで。

プログラミング F#3.0 F# C# VB.NET


F# コンパイラのソースを読んで


はぇ〜さん(@haxe) とtwitterにて、以下のようなやり取りがありました。

for m in Regex.Matches(input, pattern) do () で、 MatchCollection から Match に型が解決される件は、わたしがツイートしたとおり。typecheckerのソースを見ればわかるので、まあよし。



問題はその後。


読み返してみると、わたしの発言が支離滅裂なところがあり。そのせいもあって、話が噛み合っていなさすぎてやばい！（はぇ〜さんごめんなさい！）。自分の中ではだいたいわかって納得したような気になっていた・・・のです（ぇ　しかし、github の fsharp のソースをまじまじと見ていると、なんだか少しモヤっするものがあったので、改めて F# コンパイラのソースを舐め回すように見てみた。実際にコードも書いて確かめてみた。



すると...、いろいろ間違い（勘違い）をしていたようです（はずかしい）。C# と VBのインデクサの仕様、 C# と F# の仕様はそれぞれ異なるということは把握していたのだが、VB と F# のインデックス付きプロパティ（インデクサ）の挙動に差があることは把握できていませんでした。F# では、DefaultMemberAttribute が自動生成されないケースがあるんです。　ΩΩΩ<な、なんだってー！？




C# のインデクサ と VB のインデクサ

「C# のインデクサ」と 「VB のインデックス付きプロパティ（インデクサ）」については、岩永さんの「インデクサー(C# によるプログラミング入門) - ++C++」を参照で（丸投げ）。




C#のインデクサのサンプル：その１

public class IndexerSample1
{
    private int[] arr = new int[100];
    public int this[int index]
    {
        get
        {
            if (index < 0 || index >= 100)
            {
                return 0;
            }
            else
            {
                return arr[index];
            }
        }
        set
        {
            if (!(index < 0 || index >= 100))
            {
                arr[index] = value;
            }
        }
    }
}

var sample = new IndexerSample1();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType () == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault() ;
Debug.Assert(attr.MemberName == "Item");

特に細工をすることなくC#でインデクサ付きの型を作ると、"Item"というメンバ名で DefaultMemberAttribute が自動生成される。問題なし。





C#のインデクサのサンプル：その２

public class IndexerSample2
{
    private int[] arr = new int[100];
    [System.Runtime.CompilerServices.IndexerName("SpecialItem")]
    public int this[int index]
    {
        get
        {
            if (index < 0 || index >= 100)
            {
                return 0;
            }
            else
            {
                return arr[index];
            }
        }
        set
        {
            if (!(index < 0 || index >= 100))
            {
                arr[index] = value;
            }
        }
    }
}

var sample = new IndexerSample2();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
// IndexerNameAttributeで指定された名前で生成されている
Debug.Assert(attr.MemberName == "SpecialItem");


IndexerNameAttributeで指定した "SpecialItem" というメンバ名で DefaultMemberAttribute が自動生成される。問題なし。




C#のインデクサのサンプル：その３

[System.Reflection.DefaultMember("SpecialItem")]
public class IndexerSample3
{
    private int[] arr = new int[100];
    [System.Runtime.CompilerServices.IndexerName("SpecialItem")]
    public int this[int index]
    {
        get
        {
            if (index < 0 || index >= 100)
            {
                return 0;
            }
            else
            {
                return arr[index];
            }
        }
        set
        {
            if (!(index < 0 || index >= 100))
            {
                arr[index] = value;
            }
        }
    }
}


インデクサ付きの型に対して DefaultMember属性を明示的に指定することはできない。コンパイラに怒られます。




MSDNライブラリ - DefaultMemberAttribute クラス
http://msdn.microsoft.com/ja-jp/library/system.reflection.defaultmemberattribute(v=vs.110).aspx

プロパティは、そのプロパティに引数が存在し、かつ、プロパティ名またはそのいずれかのアクセサーが DefaultMemberAttribute で指定された名前と一致する場合、インデクサー (Visual Basic では既定のインデックス付きプロパティ) としてインポートされます。 格納している型に DefaultMemberAttribute が存在しない場合、その型にはインデクサーは存在しません。 C# コンパイラでは、インデクサーを含むすべての型について、DefaultMemberAttribute を出力します。 C# では、既にインデクサーが宣言されている型に対し、直接 DefaultMemberAttribute で属性を指定するとエラーになります。


MSDNにもそう書いてある。






続いて、VB のインデックス付きプロパティ（インデクサ）について見ていく。


VB のインデックス付きプロパティのサンプル：その１

Public Class IndexerSample4
    Private arr As Array = New Integer(100) {}
    Default Public Property Item(ByVal index As Integer) As String
        Get
            If index < 0 OrElse index >= 100 Then
                Return 0
            Else
                Return arr(index)
            End If
        End Get
        Set(ByVal Value As String)
            If Not (index < 0 OrElse index >= 100) Then
                arr(index) = Value
            End If
        End Set
    End Property
End Class

var sample = new IndexerSample4();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr.MemberName == "Item");

特に細工をすることなくVBでインデクサ付きの型を作ると、C# と同様に "Item"というメンバ名で DefaultMemberAttribute が自動生成される。問題なし。




VB のインデックス付きプロパティのサンプル：その２

Public Class IndexerSample5
    Private arr As Array = New Integer(100) {}
    <System.Runtime.CompilerServices.IndexerName("SpecialItem")> _
    Default Public Property Dummy(ByVal index As Integer) As String
        Get
            If index < 0 OrElse index >= 100 Then
                Return 0
            Else
                Return arr(index)
            End If
        End Get
        Set(ByVal Value As String)
            If Not (index < 0 OrElse index >= 100) Then
                arr(index) = Value
            End If
        End Set
    End Property
End Class


var sample = new IndexerSample5();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr.MemberName == "Dummy");


DefaultMember属性が暗黙的に生成されるが、IndexerName属性で指定した "SpecialItem" という名前は無視される。実際のプロパティ名(DisplayName)である"Dummy" で作られる。これは知ってた。





VB のインデックス付きプロパティのサンプル：その３

<System.Reflection.DefaultMember("Hoge")> _
Public Class IndexerSample6
    Private arr As Array = New Integer(100) {}
    <System.Runtime.CompilerServices.IndexerName("SpecialItem")> _
    Default Public Property Item(ByVal index As Integer) As String
        Get
            If index < 0 OrElse index >= 100 Then
                Return 0
            Else
                Return arr(index)
            End If
        End Get
        Set(ByVal Value As String)
            If Not (index < 0 OrElse index >= 100) Then
                arr(index) = Value
            End If
        End Set
    End Property
End Class



DefaultMember属性に、インデクサのプロパティ名と異なるメンバ名が指定されると競合が発生する。こんなの初めて書いたｗ




VB のインデックス付きプロパティのサンプル：その４

<System.Reflection.DefaultMember("Item")> _
Public Class IndexerSample7
    Private arr As Array = New Integer(100) {}
    <System.Runtime.CompilerServices.IndexerName("SpecialItem")> _
    Default Public Property Item(ByVal index As Integer) As String
        Get
            If index < 0 OrElse index >= 100 Then
                Return 0
            Else
                Return arr(index)
            End If
        End Get
        Set(ByVal Value As String)
            If Not (index < 0 OrElse index >= 100) Then
                arr(index) = Value
            End If
        End Set
    End Property
End Class


DefaultMember属性に、インデクサのプロパティ名と同様のメンバ名を指定すると問題ない。C# とは異なり、VB ではインデクサ付きの型でDefaultMember属性を明示的に指定することが可能。

var sample = new IndexerSample7();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが指定されているので、当然存在する
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr.MemberName == "Item");

DefaultMemberAttributeが明示的に指定されているので、当然存在する。メンバ名もそのまんま。ここまでは問題ないです。





F# のインデックス付きプロパティ（インデクサ）


F#のインデックス付きプロパティのサンプル：その１

type IndexerSample8 () =
    let arr : int [] =  Array.zeroCreate 100 
    member this.Item
      with get(index) = 
        if index < 0 || index >= 100 then
          0
        else 
          arr.[index]
      and set index value = 
        if not (index < 0 || index >= 100) then
          arr.[index] <- value

var sample = new IndexerSample8();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr.MemberName == "Item");


C#とVBと同じ。問題なし。




F#のインデックス付きプロパティのサンプル：その２

type IndexerSample9 () =
    let arr : int [] =  Array.zeroCreate 100 
    [<System.Runtime.CompilerServices.IndexerName("SpecialItem")>]
    member this.Item
      with get(index) = 
        if index < 0 || index >= 100 then
          0
        else 
          arr.[index]
      and set index value = 
        if not (index < 0 || index >= 100) then
          arr.[index] <- value

var sample = new IndexerSample9();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr.MemberName == "Item");


C#と異なり、VBと同じ挙動。知ってた。そりゃそーですよね。




F#のインデックス付きプロパティのサンプル：その３

[<System.Reflection.DefaultMember("Item")>]
type IndexerSample10 () =
    let arr : int [] =  Array.zeroCreate 100 
    [<System.Runtime.CompilerServices.IndexerName("SpecialItem")>]
    member this.Item
      with get(index) = 
        if index < 0 || index >= 100 then
          0
        else 
          arr.[index]
      and set index value = 
        if not (index < 0 || index >= 100) then
          arr.[index] <- value

var sample = new IndexerSample10();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr.MemberName == "Item");


VBと同じように、明示的にDefaultMember属性を指定することができる。






F#のインデックス付きプロパティのサンプル：その４

[<System.Reflection.DefaultMember("Hoge")>]
type IndexerSample11 () =
    let arr : int [] =  Array.zeroCreate 100 
    [<System.Runtime.CompilerServices.IndexerName("SpecialItem")>]
    member this.Item
      with get(index) = 
        if index < 0 || index >= 100 then
          0
        else 
          arr.[index]
      and set index value = 
        if not (index < 0 || index >= 100) then
          arr.[index] <- value

VBと同じように、競合が発生してエラーとなるかと思いきや・・・、コンパイルが通る！！！

var sample = new IndexerSample11();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr.MemberName == "Item");

DefaultMember属性のメンバ名に誤った名称が指定されている場合、それは無視される。実プロパティ名をメンバ名として DefaultMember属性 が自動生成される。これは予想外の動き！！！


しかし、この場合

let sample = new IndexerSample11()
let v = sample.[0]


なぜか、DefaultMember属性のメンバ名が"Hoge"だって言われる。なので、インデクサにアクセスできない。ど、どういうことだってばよ！？



確認のためのソースが悪かったorz

var sample = new IndexerSample11();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attrs2 = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>();
Debug.Assert(attrs2.Any( x => x.MemberName == "Hoge"));



DefaultMember属性が暗黙的に生成されているんだけど、明示的に指定したやつとだぶっちゃっている。あらまあ。



ってかこれ、バグっぽいちゃーバグっぽいゼ！？






F#のインデックス付きプロパティのサンプル：その５

type IndexerSample12 () =
    let arr : int [] =  Array.zeroCreate 100 
    [<System.Runtime.CompilerServices.IndexerName("SpecialItem")>]
    member this.Dummy
      with get(index) = 
        if index < 0 || index >= 100 then
          0
        else 
          arr.[index]
      and set index value = 
        if not (index < 0 || index >= 100) then
          arr.[index] <- value

var sample = new IndexerSample12();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成されない
Debug.Assert(!attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attr = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>().FirstOrDefault();
Debug.Assert(attr == null);


IndexerSample5のように、VBと同じ挙動をするかと思いきや、なんと、DefaultMemberAttributeが自動生成されないケースがここで発生。これは、F#のインデクサ付き型で、DefaultMemberAttributeが自動生成されないケースが存在すると言うよりも、「F# は、VB とは挙動が異なり、任意の名称のプロパティではでインデクサ付きの型とはならない」と言うのが正しいだろう。なんということでしょう。F# コンパイラによって「DefaultMemberAttributeが自動生成されない」ケースがあった！！！これは知らなかった。意図的なのかどうなのかわからないが、C#、VB いずれとも異なる挙動になるように作られている。




ってかこれ、バグっぽいちゃーバグっぽいゼ！？




F# でインデクサにアクセスすることができない。当然、こうなります。





F# コンパイラのソースを見てみようのコーナー

では、コンパイラの中で一体何が起こっているんでしょう。ソースを見てみる。


IL的に DefaultMemberAttribute を自動生成しているらしいこのあたりを引用する。
https://github.com/fsharp/fsharp/blob/master/src/fsharp/ilxgen.fs#L6239

        let defaultMemberAttrs = 
            // REVIEW: this should be based off tcaug_adhoc_list, which is in declaration order
            tycon.MembersOfFSharpTyconSorted
            |> List.tryPick (fun vref -> 
                let name = vref.DisplayName
                match vref.MemberInfo with 
                | None -> None
                | Some memberInfo -> 
                    match name, memberInfo.MemberFlags.MemberKind with 
                    | ("Item" | "op_IndexedLookup"), (MemberKind.PropertyGet  | MemberKind.PropertySet) when nonNil (ArgInfosOfPropertyVal cenv.g vref.Deref) ->
                        Some( mkILCustomAttribute cenv.g.ilg (mkILTyRef (cenv.g.ilg.mscorlibScopeRef,"System.Reflection.DefaultMemberAttribute"),[cenv.g.ilg.typ_String],[ILAttribElem.String(Some(name))],[]) ) 
                    | _ -> None)
            |> Option.toList


「// REVIEW: this should be based off tcaug_adhoc_list, which is in declaration order」のコメントも気になっちゃいますが、それは置いていおいて・・・。ここを起点に全体のソースを舐め回すように眺めてみる。ふむふむなるほど。F# コンパイラさん、IndexerName 属性はまったく見ていないご様子。そして、「let name = vref.DisplayName」を見ればわかるように、実プロパティ名を参照している。そして、実プロパティ名が、"Item" 、"op_IndexedLookup"のいずれかの場合に限り、実プロパティ名を使って DefaultMemberAttribute が暗黙的に生成されていることがわかります。




では、DisplayNameが "op_IndexedLookup"であるとき、とはどんな時か。次のサンプルのようなケースのときである。



F#のインデックス付きプロパティのサンプル：その６

[<System.Reflection.DefaultMember("Hoge")>]
type IndexerSample13 () =
    let arr : int [] =  Array.zeroCreate 100 
    [<System.Runtime.CompilerServices.IndexerName("Fuga")>]
    member this.Hoge
      with get(index) = 
        if index < 0 || index >= 100 then
          0
        else 
          arr.[index]
      and set index value = 
        if not (index < 0 || index >= 100) then
          arr.[index] <- value

var sample = new IndexerSample13();
var attrs = System.Attribute.GetCustomAttributes(sample.GetType());
// DefaultMemberAttributeが自動生成される
Debug.Assert(attrs.Any(x => x.GetType() == typeof(DefaultMemberAttribute)));
var attrs2 = attrs.Where(x => x.GetType() == typeof(DefaultMemberAttribute)).Cast<DefaultMemberAttribute>();
Debug.Assert(attrs2.Any( x => x.MemberName == "Hoge"));



DefaultMemberAttributeはダブっていない。もちろんIndexerName属性も華麗にスルーです。


当然、インデクサにF#からアクセスできる。






自分のためのまとめ

・F# コンパイラは、DefaultMember属性を暗黙的に生成するとき、C#とは異なり、IndexerName属性は華麗にスルーされる。VBと同じ。
・F#のインデックス付きプロパティと、VBのインデックス付きプロパティは違う。思い込みイクナイ。
・F# コンパイラは、インデックス付きプロパティがあっても DefaultMember 属性を暗黙的に生成しない場合がある（てゆーか、それインデクサ付きの型じゃないですしおすし）。
・VB、C#、F#　は、それぞれインデクサの仕様が異なるので気をつけましょう。
・ってかこれ、バグっぽいちゃーバグっぽいゼ！？(DefaultMember属性のダブりとかマジやべぇ)*1



気まぐれでサラッとだけ書くつもりだったのに。なんやかんやで無駄に長くなって疲れた（内容しょぼいのに！）。



お疲れ様でした。

*1:まぁ、ふつーにインデクサを使うだけなら問題にならないので、「仕様です」っちゃー仕様ですね

クリップボードの文字列を、「突然の死」テンプレートに置き換えるやつ

プログラミング F# ネタ 息抜き

元ネタ
「突然の死」をTwitterへ簡単に送り出せる「突然の死ジェネレータ」 - GIGAZINE 　
http://gigazine.net/news/20120703-suddenly-death/


突然の死ジェネレータ


クリップボードの文字列を、「突然の死」テンプレートに置き換えます（マルチライン対応）。


Totsuzen.fs

open System
open System.Text 
open System.Windows.Forms

let rc = "\r\n"
let length s = Encoding.GetEncoding(932).GetByteCount(s:string) |> fun len ->
  if len % 2 = 1 then (len + 1) / 2 else len / 2
let split (separator:string) (text:string) = text.Split([|separator|], StringSplitOptions.None)
let repeat s i = [1..i] |> Seq.map (fun _ -> s) |> Seq.fold (+) ""
let width f lines = lines |> Seq.map(fun s -> f s) |> Seq.max 

let centerAlign lines =
  let f line =
    let len = length line
    let lw, rw, pad =
      let maxw = width length lines 
      let lw = (maxw - len) / 2
      lw, maxw - lw - len, repeat "　"
    pad lw + line + pad rw
  lines |> Seq.map f

let border lines = 
  let header = "＿" + repeat "人" (width length lines + 2) + "＿" 
  let footer = "￣" + repeat "Y^" (width length lines) + "Y￣"
  let side lines =
    let f line = "＞　" + line + "　＜" + rc
    Seq.map f lines |> Seq.reduce (+)
  header + rc + (centerAlign lines |> side) + footer

[<STAThread>]
[<EntryPoint>]
let main args = 
  let (!) = function | "" -> "突然の死" | s -> s
  !Clipboard.GetText()
  |> split rc 
  |> border
  |> Clipboard.SetText
  0

＿人人人人人人人人人人人人＿
＞　暇つぶしにちょっと　　＜
＞　やってみたかっただけ　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y￣


とてもゴガツビョウです＼(^o^)／

マルコフ連鎖とビタビアルゴリズム(HMM)を F# で。

プログラミング F# 統計 機械学習 アルゴリズム ネタ


元ネタ

昼食時に店で流れていた、大事MANブラザーズバンド「それが大事」の歌詞が、あまりに繰り返しばかりなので、状態遷移図を作りました。どうぞご利用下さい。
http://youkoseki.com/soregadaiji/


「それが大事」にマルコフ連鎖を適用してみる
https://www.evernote.com/shard/s70/sh/71947f67-ee6c-405f-92a2-1d64fd631639/2d9397138827808cbc21c36c9389f642


マルコフ連鎖で「それが大事」っぽい歌詞を自動生成する
http://vilart.sakura.ne.jp/daijiman.html




自動生成された文字列が違和感なく連鎖するのがいいね！ネタのチョイスが面白くってちょっと書いてみたくなった。大事MANブラザーズバンドの大ヒット曲「それが大事」っぽい歌詞をマルコフ連鎖で自動生成。これを F# でやってみる。形態素解析には .NET で MeCabが簡単に使えるNMeCabを利用させてもらう。


open System
open System.Collections.Generic 
open NMeCab 
open Microsoft.FSharp
open Microsoft.FSharp.Core 

let tagger = MeCabTagger.Create ()
let parse format s = 
  tagger.OutPutFormatType <- format
  tagger.Parse s

let src = @"負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
駄目になりそうな時　それが一番大事
負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
涙見せてもいいよ　それを忘れなければ
Oh

高価な墓石を建てるより　安くても生きてる方がすばらしい
ここにいるだけで　傷ついてる人はいるけど
さんざん我侭言った後　あなたへの想いは　変わらないけど
見えてるやさしさに　時折負けそうになる

ここにあなたがいないのが　淋しいのじゃなくて
ここにあなたがいないと思う事が淋しい(でも)
負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
駄目になりそうな時　それが一番大事

高価なニットをあげるより　下手でも手で編んだ方が美しい
ここに無いものを　信じれるかどうかにある

今は遠くに離れてる　それでも生きていれば　いつかは逢える
でも傷つかぬように　嘘は繰り返される

ここにあなたがいないのが　せつないのじゃなくて
ここにあなたがいないと思う事がせつない

でも
負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
駄目になりそうな時　それが一番大事

負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
駄目になりそうな時　それが一番大事
負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
涙見せてもいいよ　それを忘れなければ

負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
駄目になりそうな時　それが一番大事
負けない事・投げ出さない事・逃げ出さない事・信じ抜く事
涙見せてもいいよ　それを忘れなければ"

// NMeCabで分かち書き
let wakati s = 
  if s = "" then [||] 
  else
    let split separators x = (x:string).Split(separators) 
    let wk = parse "wakati" s 
    split [|' '|] wk |> Array.toList |> List.toArray  

// N階マルコフ
let markov n source = 
  let model = new Dictionary<_,_> ()
  let add k (v:string) = 
    if not <| model.ContainsKey k then 
      model.Add(k,[])
    model.[k] <- model.[k]@[v]

  let mutable p = Array.create n "" |> Array.toList 
  for next in source do
    add (p) next
    p <- (List.tail p) @[next]
  let s = (List.tail p) |> List.reduce (fun x y -> x + y)
  let lst = (s).Replace("\r", "").Replace("\n", "")
  add (p@[lst]) null
  model

// N階マルコフ連鎖で文章生成
let generateMarkovChain n first source =
  let random = new Random ()
  let model = markov n source
  let keyValuePairs = (model.Keys :> seq<_>)
  let generate p = 
    let sentence = fun p -> 
      if model.ContainsKey(p) then 
        let candidate = model.[p]
        let next = candidate.[random.Next (candidate.Length)]
        Some (next,(List.tail p)@[next])
      else
        None
    Seq.unfold sentence p
    |> Seq.fold (fun a b -> a + b) "" 
  first (keyValuePairs) |> generate

wakati src
|> generateMarkovChain 2 (fun keys -> keys |> Seq.head) 
|> fun s -> s.Replace ("\r","\r\n") 
|> printfn "%s"

Console.ReadKey () |> ignore

元ネタと同じことができた。人工無能や twitter の bot を作る時なんかのたたき台くらいにはなりそう。やる予定ぜんぜんないけど。これといって見どころはありませんが、しいて言うなら単純マルコフ過程固定ではなく、N 階マルコフ過程な連鎖を表す関数にしてるところくらいでしょうか。で、好奇心がわいてきたのでなんとなーく関連情報をいろいろ漁っていく。すると、「マルコフ連鎖モンテカルロ法」、「隠れマルコフモデル」、「ビタビアルゴリズム」、「バウム・ウェルチアルゴリズム」などなどいろいろと面白そうなキーワードが出てくる。




マルコフ連鎖モンテカルロ法については、テラモナギさん(@teramonagi)　のスライドがとても面白かった。


マルコフ連鎖モンテカルロ法入門−1
http://d.hatena.ne.jp/teramonagi/20100913/1284387360



マルコフ連鎖モンテカルロ法入門−２
http://d.hatena.ne.jp/teramonagi/20101003/1286079803



統計や機械学習については完全に門外漢であるし、いろいろとわからないことだらけの私だが。面白いものは面白い。




隠れマルコフモデルとビタビアルゴリズム


尤度よりも犬度が。犬度よりも猫度が気になる今日このごろ。



遠くに住んでいる友達が、毎日何をしたかを電話で教えてくれます。友達は「散歩」、「買物」、「掃除」の３つのことにしか関心がありません。友達が住んでいるところの天気の明確な情報は持っていないが、友達が何をするかはその日の天気で決める傾向があることは知っている。たとえば「雨」だったら５０％の確率で「掃除」をするとか、「晴れ」だったら６０％の確率で「散歩」をするなどです。また、天気の状態は「雨」、「晴れ」のいずれかで、たとえば今日が雨だったら明日が晴れの確率は３０％、雨の確率は７０％という具合に、天気は離散マルコフ連鎖に従うとします。このとき、天気の状態は友達がする行動に隠れている(hidden)と見なすことができる。友達はその日の天気に従って「散歩」、「買い物」、「掃除」のいずれか１つだけ行動をとって教えてくれるので、これらは観測(observations)できる対象と見なせる。このとき、これは隠れマルコフモデル (HMM：Hidden Markov Model) 的である、と言う。


天気の傾向と、友達はどのような行動をとるかという傾向を知っているとき。言い換えると、隠れマルコフモデルのパラメータについて知っているということを意味していて、たとえば、友達が初日に散歩をして、２日目に買い物を。３日目に掃除を、というような順番に行動とったとき、その観測結果が得られる確率はいくらか？そして、このような観測結果がえられたとき３日間（とその翌日）の天気はどのようであったか？ということを予測したい。前者は前向きアルゴリズムを。後者はビタビアルゴリズム*1を用いることで求めることができる。



という内容の隠れマルコフモデルの例（コードはPython）がWikipediaに出ている。


隠れマルコフモデル - Wikipedia
http://goo.gl/oDu5k



ビタビアルゴリズム - Wikipedia
http://goo.gl/tbpnO




これを F# で書いてみる。



Program.fs

open HMM

// 状態（ラベル）：雨 | 晴れ
type States = Rainy | Sunny
// 観測されたもの：散歩 | 買い物 | 掃除
type Observations = Walk | Shop | Clean

// 初期確率
let startingProbs = [Rainy, 0.6; Sunny, 0.4] |> Map.ofList

// 状態（ラベル）の遷移確率
let transitionProbs = 
    [(Rainy,Rainy), 0.7; (Rainy,Sunny), 0.3
     (Sunny,Rainy), 0.4; (Sunny,Sunny), 0.6]
    |> Map.ofSeq

// それぞれの観測された行動に対する、状態（ラベル）の出力確率
let emissionProbs =
    [(Rainy, Walk), 0.1; (Rainy, Shop), 0.4;  (Rainy, Clean), 0.5
     (Sunny, Walk), 0.6; (Sunny, Shop), 0.3;  (Sunny, Clean), 0.1]
    |> Map.ofSeq

// 開始確率を取得します。
let startProbability s = startingProbs.[s]
// 遷移確率を取得します。
let transitionProbability spair = transitionProbs.[spair]
// 出力確率を取得します。
let emissionProbability sopair = emissionProbs.[sopair]

let obs = [Walk; Shop; Clean]
let states = [Rainy;Sunny]

let viterbi = Viterbi(obs, states, startProbability, transitionProbability, emissionProbability) 

assert (viterbi.TotalProb = 0.0336)
viterbi.TotalProb |> printfn "%A"
assert (viterbi.ViterbiPath = [Sunny;Rainy;Rainy;Rainy])
viterbi.ViterbiPath |> printfn "%A" 
assert (viterbi.ViterbiProb = 0.009408)
printfn "%A" viterbi.ViterbiProb


Viterbi.fs

namespace HMM
open System

type dict<'a, 'b> = Collections.Generic.Dictionary<'a,'b>

[<AutoOpen>]
module HMM = 
  type Viterbi<'o,'s when 's:equality>
    ( obs : seq<'o>,
      states : seq<'s>,
      sp : 's -> float,
      tp : 's * 's -> float,
      ep : 's * 'o -> float) as this =

    let mutable last = dict<'s, float * float>()
    let mutable current = [dict<'s, float * float>()]
    let viterbiPath = dict<'s,'s list>()

    let initialize (o,states) =
      for state in states do
        last.[state] <- ((sp state), (sp state) * ep(state,o))
        viterbiPath.[state] <- [state]
      current <- [last]

    let nextState f states =
      let next = dict<'s, float * float>()
      let add = fun (target, state, cp, prob) ->
        next.[target] <- (cp, prob)
        viterbiPath.[target] <- target::viterbiPath.[state]

      let junction = fun target ->
        states 
        |> Seq.map (fun state ->
          let _,sp = last.[state]
          let cp, prob = f state target sp
          target,state, cp, prob) 
        |> Seq.maxBy (fun (_,_,_,prob) -> prob)

      states 
      |> Seq.map (junction)
      |> Seq.iter(add)

      last <- next
      current <- next::current

    let lastViterbiState () = current.Head |> Seq.maxBy (fun kv -> kv.Value) 

    do
      this.Execute (obs, states)

    /// ビタビ経路の最後の状態
    member x.LastViterbiState = lastViterbiState ()

    /// 実行
    member private x.Execute(obs, states) =
      let f = fun o state target sp ->
        let cp = ep(target, o)
        cp, sp * cp * tp(state, target) 

      for i,o in (obs |> Seq.mapi (fun i x -> i,x)) do
        if i = 0 then 
          initialize (o, states)
        else
          nextState (f o) states

      let g = fun state target sp ->
        let lastViterbiState = x.LastViterbiState
        let cp = tp(lastViterbiState.Key, target)
        cp,  sp * cp
      // 与えられたパラメータから推察される次の状態
      nextState g states

    /// 与えられたパラメータに対する全体確率
    member x.TotalProb =
      x.ViterbiPathProb ()
      |> List.mapi (fun i (state,(ep,vp)) -> if i = 0 then vp else ep)
      |> Seq.reduce (fun x y -> x * y)

    member private x.ViterbiPathProb () = 
      let lastViterbiState = x.LastViterbiState
      viterbiPath.[lastViterbiState.Key] 
      |> List.mapi (fun i state -> state,current.[i].[state] )
      |> List.rev 

    /// ビタビ経路(最も尤もらしい並び。尤度が最も高い経路。)を取得します。
    member x.ViterbiPath = 
      x.ViterbiPathProb ()
      |> List.map (fun (state,(ep,vp)) -> state)

    /// ビタビ経路の確率
    member x.ViterbiProb = 
      let lastViterbiState = x.LastViterbiState
      let _,vp = current.Head.[lastViterbiState.Key]
      vp

    member x.Path = current

実行結果

0.0336
[Sunny; Rainy; Rainy; Rainy]
0.009408


F#で書いてみましたというだけで、特に面白みはない。
実行結果を見る限りは多分あっているぽい。けど、門外漢が適当に勘で書いたものなので鵜呑みはせぬようよろしくオナシャス。

*1:観測された事象系列を結果として生じる隠された状態の最も尤もらしい並びをビタビ経路と呼ぶ