スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Listモナドで非決定的計算をしよう

Haskellでは、Listモナドを使うことにより、非決定的計算ができるらしい。どういうことか?

実数xの平方根±√xについて考えてみよう。±√xはxの値によってありうる値が異なる。

  • x>0: 2個の値(±√x)
  • x=0: 1個の値(0)
  • x<0: なし

これをHaskellで表現するとこうなる:

sqrt' :: RealFloat a => a -> [a]
sqrt' x | x >  0 = [sqrt x,-sqrt x]
        | x == 0 = [0]
        | x <  0 = []

このsqrt'を使って2次方程式 a*x^2+b*x+c=0 の解を返す関数を定義する:

import Monad
solution :: RealFloat a => a -> a -> a -> [a]
solution a b c = ((-b)+sqrt'(b^2-4*a*c))/(2*a)
  where
    (+) = liftM . (Prelude.+)
    (/) = flip (liftM . flip (Prelude./))

これだけで、この関数solutionはあり得る解を全て返すようになる。試してみよう。

*Main> solution 1 0 1       -- x^2+1=0
[]
*Main> solution 1 (-2) 1    -- x^2-2*x+1=0
[1.0]
*Main> solution 1 (-1) (-1) -- x^2-x-1=0
[1.618033988749895,-0.6180339887498949]
*Main> 

複素数の場合はsqrtは常に値を持つので、±を定義すればお馴染みの公式をHaskellで表現できる。

infixl 6 ±
(±) :: Num a => a -> a -> [a]
a ± b | b /= 0 = [a+b,a-b]
      | b == 0 = [a]

csolution :: Floating a => a -> a -> a -> [a]
csolution a b c = ((-b)±sqrt(b^2-4*a*c))/(2*a)
  where
    (/) = flip (liftM . flip (Prelude./))
*Main> import Complex
*Main Complex> (csolution 1 0 1)::[Complex Double]   -- x^2+1=0
[0.0 :+ 1.0,(-0.0) :+ (-1.0)]
*Main Complex> (csolution 1 1 1)::[Complex Double]   -- x^2+x+1=0
[(-0.5) :+ 0.8660254037844386,(-0.5) :+ (-0.8660254037844386)]
*Main Complex> 

# U+2062 INVISIBLE TIMESが演算子として使えればもう少しコードがきれいになるのにな…
# つーかこの例は非決定的計算の例として適当なのだろうか

スポンサーサイト

テーマ : プログラミング | ジャンル : コンピュータ

wxStyledTextCtrlでの日本語入力のその後

おとといの記事を書いてからwxStyledTextCtrlでの日本語入力 @ ウィキを立ち上げたわけだが、その後の報告。

まず、2種類の問題があることが分かった。で、Macを使っている自分にとってより優先度の高い方(確定できない)を調べることにした。その結果、原因は分かった。対策も分かった。あとは本家のTracに報告して、パッチが取り込まれるのを待てばOK…と言いたいところだが、微妙に問題があって、そこもなんとかしないと取り込まれないかもしれない。その新たな問題への対処方針は考えてあるんだが、効率的な方法が思いつかない。その新たな問題も含めて報告すればいいのかもしれないが、問題を抱えているパッチが取り込まれるとは思えない。やはり完全解決をしてから報告したい。

手詰まりになってしまったので、もう一つの問題(インライン入力、Windowsを使ってる人が問題にしてるのはこっち)にも取りかかってみた。取りかかるといっても、Input Methodを扱うプログラミングはしたことがなかったので、情報収集から始めた。プラットフォームごとに異なるAPIを把握するのは疲れる。妥協して、Mac上のwxSTCだけでも対策をしようかと思い、コードを書きはじめるが、必要な情報(キャレット位置)をScintillaから得るためにはどうすればいいのかで悩む。本家Scintillaも同じことをしているので、それを写せばいいのだが、そんなことをするくらいなら本家のExtInput.cppをそのままコピーすればいいじゃん、と思った(実際、過去にExtInput.cppを利用してMacのwxSTCの日本語入力をなんとかしようと思い、試したことがある。その時はうまく動かなくて挫折したが、今思うと、確定できない問題がそのままだったから失敗したのかもしれない)。

ここまでで書いたように、いろいろやってみた。しかし、やはり自分一人の力と知識とモチベーションと時間では限界がある。というわけでwxWidgetsに詳しい方、WindowsのIMEに詳しい方、MacやGTKのIMに詳しい方の協力をお待ちしております。

ちなみに、動機を含めたこれまでの経過↓

続きを読む

テーマ : プログラミング | ジャンル : コンピュータ

wxStyledTextCtrlでの日本語入力に難がある件について

wxStyledTextCtrl(および、それを使用するアプリケーション、例えばEditraなど)で日本語が入力できない/難のある問題には、今まで何人もの人が気づいてるんだけど直せないでいる。自分も何年も前から知っているが、直せないでいる。根が深いのだ。しかし、誰かが直さなければ、wxStyledTextCtrlを使うアプリケーション(Editraとか)が、いつまでたっても「日本語入力ができない/難のあるクソソフト」と呼ばれることになる。どうすればいいのか。

いままでは各自が自分のブログに書いていたので、情報が分散していた。各自が別々に調べ、修正しようとしてその度に挫折していた訳だ。これは効率が悪い。そこでまず、その情報をまとめる場所が必要だと思う。Wikiか何かがあればいいと思う。情報を集めたって解決するかは分からないが、問題ははっきりするだろう。いずれ、その情報を元にして、実際に解決する人が出てくるかもしれない。

Wikiを作るとして、書くべき内容:

  • プラットフォームごとの症状の違い
    • Windows: インライン入力ができない
    • Mac: 文字が確定できない→使い物にならない
  • 問題を抱えているコンポーネント
    • wxStyledTextCtrl,wxRichTextCtrl
  • 上に挙げたコンポーネントを使っているアプリケーション
    • Editra
  • 参考リンク
    • 言及してきたサイト・ブログなど
  • 技術情報
    • wxWidgetsやアプリケーションのソースの取得・ビルド方法
    • パッチの当て方
  • 目的
    • 当面の解決策を探る
    • 抜本的な解決策を探る
      • wxWidgetsにIME/Input Methodを扱うクラスを追加する(?)
      • 本家に取り込んでもらう
      • かなりハードルが高い
  • 協力者募集
    • 各自で調べて分かっていることがあれば教えてほしい
    • 自分はMacなもんで、WindowsやLinuxの人も協力してくれるとうれしい

追記: @wikiにWiki作った。

テーマ : プログラミング | ジャンル : コンピュータ

Haskell の Parsec で JavaScript パーサを書いた

前にも書いたようにJavaScriptによるJavaScriptのパーサを書いてたんだが、JavaScriptでは速度にも記述性にも限界を感じ、HaskellでParsecを使い書き直す事にした。Haskellには代数データ型もパターンマッチもあるので、パース後のASTを変換するのもHaskellの方がやりやすいはずだ。また、静的型付けなのでバグも減るだろう。

というわけでParsecで(自分にとって初めての、Parsecを使う実用目的の)パーサを書いた。JavaScriptでは改行が意味を持つので、改行を読んだかどうかをパーサの状態に持たせる事にした。そのためにはwhiteSpace相当のものを自分で実装する必要がある。その場合、Text.ParserCombinators.Parsec.Tokenを使うことはできないので、Text.ParserCombinators.Parsec.Tokenにあるような関数を自作した。

いくつかのファイル(数百行)をパースしてみたが、意外に時間が掛かる。プロファイルをとってみるとwhiteSpaceで時間が掛かっているようだ。JavaScriptで書いていた時も字句解析の部分に時間が掛かっていた気がする。

テーマ : プログラミング | ジャンル : コンピュータ

GNUstepのWindowsバイナリをMacからクロスコンパイル

幾度とない失敗を乗り越え、ようやく成功した。

必要な物

  • GNUstep
    svnで取得する。ビルドしたのはr29897。
  • クロスコンパイラ(i386-mingw32-*)
    MacPortsで取得する。
  • GNUstepが依存するライブラリ(バージョンはビルドに使ったもの)
    • pthread-win32 2.8.0 → gnustep-baseに必要。
    • libffi 3.0.8 → gnustep-baseに必要。ローカルにあった物を使ったけど、サイトを見るといつのまにか3.0.9が出ていた件。
    • libgpg-error 1.7 → libgcryptに必要。
    • libgcrypt 1.4.5 → gnutlsに必要。
    • libtasn1 2.4 → gnutlsとgnustep-baseに必要。
    • gnutls 2.8.5 → gnustep-baseに必要。
    • libxml2 2.7.6 → gnustep-baseに必要。
    • libjpeg 8a → gnustep-guiに必要。
    • libtiff 3.9.2 → gnustep-guiに必要。
    • zlib 1.2.3 → libpngに必要。
    • libpng 1.4.1 → gnustep-guiに必要。
    • sqlite3 3.6.23 → gworkspaceに必要。
    • gmpとかiconvとかopensslもあればいいのかもしれないけどよくわからん。
  • Wine
    楽をするために必要。

続きを読む

テーマ : プログラミング | ジャンル : コンピュータ

tag : GNUstep

プロフィール

minoki

Author:minoki
好きなプログラミング言語:
Haskell,Lua
GitHubアカウント
Twitter

最新記事
月別アーカイブ
カテゴリ
検索フォーム
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。