我想回傳給定運算式 (haskell) 的左關聯，所以如果我們有 a (b c) 函式必須回傳 (a b) c，這也適用于乘法，因為這兩個操作是聯想的。考慮到其他不關聯的操作，因此我必須設定一個條件以不關聯這些運算式。所以 leftAssociate 函式將給定的每個運算式轉換為具有相同常量的等效左關聯運算式

該函式定義如下：

data Expr = Val Int | App Op Expr Expr

leftAssociate :: Expr -> Expr
leftAssociate (App Add (Val a) (App Add (Val b) (Val c))) = App Add (App Add (Val a) (Val b)) (Val c)

我已經嘗試過模式匹配，但由于有很多可能性，所以它太難以抗拒，而且我無法指定作為輸入給出的運算元，因為它不受限制。

uj5u.com熱心網友回復：

你說

如果它沒有形狀為 App Op x ( App Op yz) 的子運算式，我們認為它是左平衡 [原文如此]，并且只有當操作是加法或乘法時

因此，我建議您按照您描述的方式構建修復此缺陷的功能：

leftAssociate (App Add x (App Add y z)) = -- ...
leftAssociate (App Mul x (App Mul y z)) = -- ...
leftAssociate (App op x y) = -- ...
leftAssociate (Val n) = -- ...

據推測，在前三種情況下，您將在某個時候進行遞回呼叫，以確保x、y和zsubterms 也是左關聯的。此遞回將是允許您處理任意大運算式的機制。

uj5u.com熱心網友回復：

我發現這樣概念化最簡單：對于以App op _ _節點為根的每個子樹，op您想要重新關聯，您可以收集子樹頂部的所有術語，并將其組合App op到一個展平串列中，然后使用foldl1該串列中的 a 創建左關聯樹。這給出了以下解決方案：

data Expr = Val Int | App Op Expr Expr deriving (Show)
data Op = Add | Mul | Sub deriving (Show, Eq)

-- Identify which operators should be re-associated
isAssoc :: Op -> Bool
isAssoc Add = True
isAssoc Mul = True
isAssoc _ = False

leftAssociate :: Expr -> Expr
leftAssociate a@(App op _ _)
  | isAssoc op = foldl1 (App op) $ opTerms a
    where opTerms :: Expr -> [Expr]
          opTerms (App op' x' y') | op' == op = opTerms x'    opTerms y'
          opTerms e                           = [leftAssociate e]
leftAssociate (App op x y) = App op (leftAssociate x) (leftAssociate y)
leftAssociate e = e

您可以通過直接構建左關聯樹并為左關聯樹定義串聯函式，從技術上擺脫中間扁平化串列，我認為這會給您提供其他答案中討論的那種直接遞回解決方案，但我發現這個版本更容易寫。

這是一個測驗用例：

mul = App Mul
add = App Add
sub = App Sub
ex1 = leftAssociate (add (Val 1) (sub (mul (Val 2) (mul (Val 3) (Val 4)))
                                      (add (add (Val 5) (Val 6)) (add (Val 7) (Val 8)))))
main = print $ leftAssociate ex1

uj5u.com熱心網友回復：

長話短說：

而不是轉動：

進入

我建議將樹更改為非二進制：

更長的解釋

如果我們有a (b c)函式必須回傳(a b) c

我不會那樣做。我會選擇與Expr = Val Int | App Op Expr Expr. Expr因為二叉樹不是關聯的。怎么樣

data AssocExpr = AVal Int | AApp Op [Expr]

串列在設計上是關聯的。AssocExpr您可以保留這兩種資料結構并在需要關聯性時轉換為。如果你真的需要它，你仍然可以轉換回來，從而達到最初的目標。

要從轉換Expr為AssocExpr，您可以修改leftAssociateKA Buhr 的答案并消除foldl1：

associate :: Expr -> AssocExpr
associate a@(App op _ _)
  | isAssoc op = AApp op $ opTerms a
...

相關代碼審查（來自我自己）： https ://codereview.stackexchange.com/questions/254288/parametrize-by-type-constructor/254572#254572

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/536671.html

標籤：哈斯克尔

上一篇：通過在Haskell中添加該串列中下兩個元素的值來修改串列中的元素

下一篇：xor=(/=)是什么意思？

在haskell中左關聯一個操作

長話短說：

更長的解釋