left associate an operation in haskell-CodePudding

I want to return the left association of an expression given (haskell), so if we have a (b c) the function has to return (a b) c, this also applies for the multiplication since these 2 operations are associative. taking onto consideration the other operations that are not associative therefor I have to put a condition to not left associate those expressions. so the leftAssociate function turns every expression given into an equivalent left-associated one with the same constants

the function is defined as follow :

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)

I have tried pattern matching but it's too overwhelming as there is a lot of possibilities and also I cannot specify the number of operations given as input as it's not limited.

CodePudding user response：

You say

we consider it left-balances [sic] if it has no subexpressions of shape App Op x ( App Op y z) and that's only when the operation is Addition or Multiplication

I therefore propose that you structure your function for fixing this defect in the way you described:

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

Presumably in the first three cases you will make recursive calls at some point to make sure that the x, y, and z subterms are also left-associated. This recursion will be the mechanism that allows you to handle arbitrarily large expressions.

CodePudding user response：

I find it easiest to conceptualize this like so: for each subtree rooted at an App op _ _ node with an op you want to re-associate, you can collect all the terms at the top of the subtree being combined with that same App op into a flattened list, and then create a left associated tree with a foldl1 from that list. This gives the following solution:

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

You can technically get rid of the intermediate flattened list by constructing the left associated tree directly and defining a concatenation function for left associated trees, and I think that would give you the sort of direct recursive solution being discussed in the other answer, but I found this version easier to write.

Here's a test case:

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