3

算術式を表すデータ型があります。

data E = Add E E | Mul E E | Var String

式を変数の積の合計に変換する展開関数を書きたいと思います (中かっこ展開のようなものです)。もちろん、再帰スキームを使用します。

「進歩と維持」の精神に則ったアルゴリズムしか思いつきませんでした。各ステップのアルゴリズムは、完全に展開された用語を構築するため、再チェックする必要はありません。

の処理にMul頭がおかしくなったので、直接行う代わりに の同形型を使用し、それを利用し[[String]]てconcatすでにconcatMap実装されていました。

type Poly = [Mono]
type Mono = [String]

mulMonoBy :: Mono -> Poly -> Poly
mulMonoBy x = map (x ++)

mulPoly :: Poly -> Poly -> Poly
mulPoly x = concatMap (flip mulMonoBy x)

だから私はちょうど使用しますcata：

expandList :: E -> Poly
expandList = cata $ \case
   Var x -> [[x]]
   Add e1 e2 = e1 ++ e2
   Mul e1 e2 = mulPoly e1 e2

そして元に戻す：

fromPoly :: Poly -> Expr
fromPoly = foldr1 Add . map fromMono where
   fromMono = foldr1 Mul . map Var

大幅に優れたアプローチはありますか?

更新：混乱はほとんどありません。

  1. このソリューションでは、複数行の変数名を使用できます。Add (Val "foo" (Mul (Val "foo) (Var "bar")))の表現ですfoo + foo * bar。私は何かを代表x*y*zしているわけではありませんVal "xyz"。スカラーがないため、「foo * foo * quux」などの繰り返し変数も完全に許可されていることに注意してください。

  2. 積の合計とは、一種の「カリー化された」積の n-ary 和を意味します。積和の簡潔な定義は、括弧のない式が必要であり、すべての括弧が結合性と優先順位によって表されるということです。

したがって(foo * bar + bar) + (foo * bar + bar)、中間+は合計の合計であるため、積の合計ではありません。

(foo * bar + (bar + (foo * bar + bar)))または対応する左結合バージョンは正しい答えですが、結合性が常に左または常に右であることを保証する必要があります。したがって、右結合ソリューションの正しいタイプは次のとおりです。

data Poly = Sum Mono Poly
          | Product Mono

これは、空でないリストに同型です: (の代わりにNonEmpty Poly注意してください)。空の合計または積を許可すると、使用したリスト表現のリストだけが得られます。Sum Mono PolySum Poly Poly

  1. また、パフォーマンスを気にしないでください。乗算は単なるようですliftA2 (++)
4

2 に答える 2