haskell - Haskellで式を処理する方法は？

Question

私が持っているとしましょう：

f :: Double -> Double
f x = 3*x^2 + 5*x + 9

この関数の導関数を計算して書きたい

derivate f

となることによって

derivate f == \x -> 6*x + 5

しかし、どのように定義するのderivateですか？

derivate :: (a -> a) -> (a -> a)
derivate f = f' -- how to compute f'?

これを行うためのネイティブな方法がないことは承知していますが、それができるライブラリはありますか？

これを実現するには、「メタ」データ型に依存する必要がありますか？

data Computation = Add Exp Expr | Mult Expr Expr | Power Expr Expr -- etc

では、関数ごとに対応するコンストラクターを作成するのは面倒ではありませんか？ただし、データ型は関数を表すべきではありません（パーサーを除く）。

Pureは、用語書き換え機能があるため、優れた代替手段ですか？欠点もありませんか？

リストは手頃な価格ですか？

f :: [Double]
f = [3, 5, 9]

derivate :: (a -> [a])
derivate f = (*) <$> f <*> (getNs f)

compute f x = sum $
    ((*) . (^) x) <$> (getNs f) <*> f

getNs f = (reverse (iterate (length f) [0..]))

Haskellは、構文が適切でないLISPに依存しているように見えます。一緒に使用されるのを待っている関数と引数は、データ型にかなり格納されています。さらに、それはあまり自然ではありません。

derivateそれらは、同形異義語関数などの多項式以外の関数を実行できるほど「柔軟」ではないようです。

たとえば、今はゲームに派生物を使用したいと思います。キャラクターは機能を使って作られた床の上を走っていますが、床が十分に急な場合はスライドさせてもらいたいです。

また、さまざまな目的で方程式を解く必要があります。いくつかの例：

私は宇宙船で、昼寝をしたいです。睡眠中に注意深く身を置くと、重力のために惑星に衝突する可能性があります。天体から遠く離れるのに十分なガスがなく、地図もありません。ですから、私はこの領域のオブジェクトの間に身を置いて、それらの重力による私への影響の合計がキャンセルされるようにする必要があります。 xとyは私の座標です。gravityは、2つのオブジェクトを受け取り、それらの間の重力のベクトルを返す関数です。私のほかに、地球と月の2つのオブジェクトがある場合、どこに行くかを見つけるために私がしなければならないのは、解決することだけです。

gravity earth spaceship + gravity moon spaceship == (0, 0)

新しい関数を最初から作成するよりもはるかに簡単で高速equigravityPoint :: Object -> Object -> Object -> Pointです。

私のほかに3つのオブジェクトがある場合でも、それは単純です。

gravity earth spaceship + gravity moon spaceship + gravity sun spaceship == (0, 0)

4、nについても同じです。オブジェクトのリストの処理は、この方法よりもはるかに簡単equigravityPointです。

他の例。私を撃つ敵ボットをコーディングしたい。彼が私の現在の位置を狙って撃っただけなら、私が私に向かって走れば彼は私を捕まえるでしょうが、私がジャンプして彼に落ちると彼は私を恋しく思うでしょう。より賢いボットは次のように考えています。「まあ、彼は壁から飛び降りました。彼が今いる場所をターゲットに撮影すると、それまで動いていたので、弾丸は彼を捕まえません。だから、彼がどこに行くのかを予想します。数秒以内に、弾丸と彼が同時にこのポイントに到達するように、そこで撃ちます。」基本的に、私は軌道を計算する能力が必要です。たとえば、この場合、trajectoryBullet == trajectoryCharacter線と放物線が交わる点を与える、の解が必要です。

速度を含まない同様の単純な例。私は消防士のボットで、建物が燃えています。消防士の別のチームは、水鉄砲で火と戦っています。私はそうです、そしてからジャンプする人々がいます。友達が水を撃っている間、トランポリンを持っています。私は人々が落ちる前に人々が落ちるところに行く必要があります。だから私は軌道と方程式を解く必要があります。

Answer 1

これを行う1つの方法は、シンボリック微分の代わりに自動微分を行うことです。これは、1回の計算でf（x）とf ′（x ）の両方を同時に計算するアプローチです。自動微分に関するDan"sigfpe"Piponiの優れたブログ投稿から学んだ二重数を使用してこれを行う本当にクールな方法があります。あなたはおそらくそれを読みに行くべきですが、ここに基本的な考え方があります。実数（または、それらのお気に入りの（？）ファクシミリ）を操作する代わりに、新しい要素εをℝに隣接させて、ε2となるように、新しいセットを定義します。これをDと^{呼びます。}Double=0。これは、 i ² =-1となるように新しい要素iをℝに隣接させることによって複素数ℂを定義する方法とよく似ています。^{（代数が好きなら、これはD=ℝ[x] /} ⟨x2⟩と言うのと同じです。）したがって、Dのすべての要素はa + bεの形式になります。ここで、aとbは実数です。二重数の算術演算は、期待どおりに機能します。

• （a + bε）±（c + dε）=（a + c）±（b + d）ε ; と
• （a + bε）（c + dε）= ac + bcε + adε + bdε2 = ac ⁺（bc + ad）ε。

（ε2 ⁼ 0であるため、除算はより複雑になりますが、複素数で使用する共役による乗算のトリックは引き続き機能します。詳細については、ウィキペディアの説明を参照してください。）

さて、なぜこれらは便利なのですか？直感的には、εは微小のように機能し、それを使用して導関数を計算できます。確かに、異なる名前を使用して乗算のルールを書き直すと、次のようになります。

• （f + f '<i>ε）（g + g '<i>ε）= fg +（f '<i> g + fg '）ε

そして、そこにあるεの係数は、関数の積を微分するための積の法則によく似ています！

それでは、1つの大きなクラスの関数で何が起こるかを考えてみましょう。上記の除算を無視したので、べき級数で定義された関数f ：ℝ→ℝがあるとします（おそらく有限であるため、sin（ x）、cos（x）、e ^xのように、任意の多項式で問題ありません。 ）。次に、新しい関数f _D ：D→Dを明白な方法で定義できます。実数を追加する代わりに、二重数などを追加します。次に、f _D（x + ε）= f（x）と主張します。 + f ′（x）ε。まず、帰納法により、任意の自然数iに対して、（ x + ε）ⁱ = x ⁱ + ixi ^{- 1ε} ;の場合であることを示すことができます。これにより、 f（x）= xkの場合の微分結果が確立され^ます。基本ケースでは、この等式はi = 0のときに明らかに成り立ちます。次に、iについて成り立つと仮定すると、次のようになります。

• （x + ε）^{i +1} =（x + ε）（x + ε）ⁱ （ x + ε）の1つのコピーを因数分解することにより
• =（x + ε）（x ⁱ + ix ^{i -} 1ε）帰納的仮説による
• = x ^{i + 1} +（x ⁱ + x（ix ^{i -1}））ε二重数乗算の定義による
• = x ^{i + 1} +（ⁱ + 1）xiε単純な代数による。

そして確かに、これは私たちが望んでいたことです。さて、べき級数fを考えると、次のことがわかります。

• f（x）= a ₀ + a ₁ x + a ₂ x2 ⁺ …+ _ai xi ⁺ … </li>

次に、

• f _D（x + ε）= a ₀ + a ₁（x + ε）+ a ₂（x + ε）² +…+ a _i（x + ε）ⁱ +…</li>
• = a ₀ +（a ₁ x + _a1ε）+（a ₂ x ² + ₂ a2xε）+…+（a _i x ⁱ + ia _i x ^{i -} 1ε）+…上記の補題による
• =（a ₀ + a ₁ x + a ₂ x2 ⁺ …+ ai x _i +…）+（^a1ε + _2a2xε + … + _iai x _i ^- 1ε + ^…）可換性による
• =（a ₀ + a ₁ x + a ₂ x2 ⁺ …+ ^ai x _i +… ）+（a ₁ + 2 a _2x + … + iai x _i ^-1 + … ^） ε
• = f（x）+ f ′（x）ε定義による。

素晴らしい！したがって、二重数（少なくともこの場合は、結果は一般的に当てはまります）は、微分を行うことができます。私たちがしなければならないのは、実数xではなく、二重数x + εに元の関数を適用し、結果として得られるεの係数を抽出することだけです。そして、Haskellでこれをどのように実装できるかがわかると思います。

data Dual a = !a :+? !a deriving (Eq, Read, Show)
infix 6 :+?

instance Num a => Num (Dual a) where
  (a :+? b) + (c :+? d) = (a+c) :+? (b+d)
  (a :+? b) - (c :+? d) = (a-c) :+? (b-d)
  (a :+? b) * (c :+? d) = (a*c) :+? (b*c + a*d)
  negate (a :+? b)      = (-a) :+? (-b)
  fromInteger n         = fromInteger n :+? 0
  -- abs and signum might actually exist, but I'm not sure what they are.
  abs    _              = error "No abs for dual numbers."
  signum _              = error "No signum for dual numbers."

-- Instances for Fractional, Floating, etc., are all possible too.

differentiate :: Num a => (Dual a -> Dual a) -> (a -> a)
differentiate f x = case f (x :+? 1) of _ :+? f'x -> f'x

-- Your original f, but with a more general type signature.  This polymorphism is
-- essential!  Otherwise, we can't pass f to differentiate.
f :: Num a => a -> a
f x = 3*x^2 + 5*x + 9

f' :: Num a => a -> a
f' = differentiate f

そして、見よ、見よ：

*Main> f 42
5511
*Main> f' 42
257

Wolfram Alphaが確認できるように、これはまさに正しい答えです。

このようなものについてのより多くの情報は間違いなく利用可能です。私はこれに関する専門家ではありません。アイデアは本当にクールだと思うので、この機会に私が読んだものをオウムにして、簡単な証明を1つか2つ作成します。ダン・ピポーニは、特に偏導関数を可能にするより一般的な構造を示す投稿を含め、二重数/自動微分について詳しく書いています。コナル・エリオットは、同様の方法で微分タワー（f（x）、f ′（x）、f ″（x）、…）を計算する方法を示す投稿をしています。上にリンクされている自動微分に関するウィキペディアの記事他のいくつかのアプローチを含め、さらに詳細に説明します。（これは明らかに「順モード自動微分」の形式ですが、「逆モード」も存在し、明らかに高速になる可能性があります。）

最後に、自動微分に関するHaskell wikiページがあります。これは、いくつかの記事、そして重要なことに、いくつかのHackageパッケージにリンクしています。私はこれらを使用したことはありませんが、adEdward Kmettによるパッケージが最も完全で、自動微分を行う複数の異なる方法を処理しているようです。彼は、別のStack Overflowに適切に応答するために、パッケージを作成した後にそのパッケージをアップロードしたことがわかりました。質問。

---

もう1つ追加したいと思います。「ただし、データ型は関数を表すべきではありません（パーサーを除く）」とあなたは言います。私はそこで意見を異にする必要があります。関数をデータ型に具体化することは、このようなあらゆる種類のことにとって素晴らしいことです。（とにかく、パーサーを特別なものにしているのは何ですか？）イントロスペクトしたい関数があるときはいつでも、それをデータ型として具体化することは素晴らしいオプションです。たとえば、上記の自動微分のエンコーディングとよく似た、記号微分のエンコーディングを次に示します。

data Symbolic a = Const a
                | Var String
                | Symbolic a :+: Symbolic a
                | Symbolic a :-: Symbolic a
                | Symbolic a :*: Symbolic a
                deriving (Eq, Read, Show)
infixl 6 :+:
infixl 6 :-:
infixl 7 :*:

eval :: Num a => (String -> a) -> Symbolic a -> a
eval env = go
  where go (Const a) = a
        go (Var   x) = env x
        go (e :+: f) = go e + go f
        go (e :-: f) = go e - go f
        go (e :*: f) = go e * go f

instance Num a => Num (Symbolic a) where
  (+)         = (:+:)
  (-)         = (:-:)
  (*)         = (:*:)
  negate      = (0 -)
  fromInteger = Const . fromInteger
  -- Ignoring abs and signum again
  abs         = error "No abs for symbolic numbers."
  signum      = error "No signum for symbolic numbers."

-- Instances for Fractional, Floating, etc., are all possible too.

differentiate :: Num a => Symbolic a -> String -> Symbolic a
differentiate f x = go f
  where go (Const a)             = 0
        go (Var   y) | x == y    = 1
                     | otherwise = 0
        go (e :+: f)             = go e + go f
        go (e :-: f)             = go e - go f
        go (e :*: f)             = go e * f + e * go f

f :: Num a => a -> a
f x = 3*x^2 + 5*x + 9

f' :: Num a => a -> a
f' x = eval (const x) $ differentiate (f $ Var "x") "x"

そしてもう一度：

*Main> f 42
5511
*Main> f' 42
257

fこれらのソリューションの両方（またはとにかくその一部）の美しさは、オリジナルが多形性（タイプNum a => a -> aまたは類似のもの）である限り、変更する必要がないことfです！導関数関連のコードを配置する必要がある唯一の場所は、新しいデータ型の定義と微分関数です。既存の関数の派生物を無料で入手できます。

Answer 2

数値微分は簡単に行うことができます：

derive f x = (f (x + dx) - f (x - dx)) / (2 * dx) where dx = 0.00001

ただし、シンボリックデリバティブの場合は、ASTを作成してから、ASTのマッチングと書き換えを通じて派生ルールを実装する必要があります。

Answer 3

カスタムデータ型の使用に関する問題がわかりません

data Expr = Plus Expr Expr 
           | Times Expr Expr 
           | Negate Expr 
           | Exp Expr Expr 
           | Abs Expr
           | Signum Expr
           | FromInteger Integer
           | Var

instance Num Expr where
   fromInteger = FromInteger
   (+) = Plus
   (*) = Times
   negate = Negate
   abs = Abs
   signum = Signum

toNumF :: Num a => Expr -> a -> a
toNumF e x = go e where
  go Var = x
  go (FromInteger i) = fromInteger i
  go (Plus a b) = (go a) + (go b)
  ...

その後、これを同じように使用できます。IntまたはDouble、すべてが正常に機能します。関数を定義できます

deriveExpr :: Expr -> Expr

これにより、次の（RankN）関数を定義できます。

derivate :: Num b => (forall a. Num a => a -> a) -> b -> b
derivate f = toNumF $ deriveExpr (f Var)

これを拡張して、数値階層の他の部分と連携させることができます。