スポンサーサイト

上記の広告は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が演算子として使えればもう少しコードがきれいになるのにな…
# つーかこの例は非決定的計算の例として適当なのだろうか

スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

minoki

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

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