How to implement distributive property in Haskell recursive data type?

Question

I have a task to correct a fucntion expand.

infixl 6 :+:
infixl 7 :*:
data Expr = Val Int | Expr :+: Expr | Expr :*: Expr
    deriving (Show, Eq)

expand :: Expr -> Expr
expand ((e1 :+: e2) :*: e) = expand e1 :*: expand e :+: expand e2 :*: expand e
expand (e :*: (e1 :+: e2)) = expand e :*: expand e1 :+: expand e :*: expand e2
expand (e1 :+: e2) = expand e1 :+: expand e2
expand (e1 :*: e2) = expand e1 :*: expand e2
expand e = e

-- expression example: (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5)
-- which is equivalent to (1 + 2 + 3) * (4 + 5)

-- expression, that given fucntion evaluates our example to: 
--(Val 1 :+: Val 2) :*: (Val 4 :+: Val 5) :+: Val 3 :*: (Val 4 :+: Val 5)

-- expression that corrected function must evaluate our example to:
-- Val 1 :*: Val 4 :+: (Val 1 :*: Val 5 :+: (Val 2 :*: Val 4 :+: (Val 2 :*: Val 5 :+: (Val 3 :*: Val 4 :+: Val 3 :*: Val 5))))

-- answers like (Val 1 :*: Val 2) :+: (Val 3 :*: Val 4) 
-- and          (Val 4 :*: Val 3) :+: (Val 1 :*: Val 2)
-- are considered to be equal

It doesn't work right because it opens brackets only once. So, i modified it to this:

infixl 6 :+:
infixl 7 :*:
data Expr = Val Int | Expr :+: Expr | Expr :*: Expr
    deriving (Show, Eq)

expand :: Expr -> Expr
expand ((e1 :+: e2) :*: e) = (expand $ e :*: e1) :+: (expand $ e :*: e2)
expand (e :*: (e1 :+: e2)) = (expand $ e :*: e1) :+: (expand $ e :*: e2)
expand (e1 :+: e2) = expand e1 :+: expand e2
expand expr@(e1 :*: e2) = if isMul expr
                          then expr
                          else expand $ expand e1 :*: expand e2
expand e = e

isMul :: Expr -> Bool
isMul (Val a :*: expr) = isMul expr 
isMul (expr :*: Val a) = isMul expr
isMul (Val a) = True
isMul  _      = False

Function isMul added to find an edge condition: if our expression (e1 :*: e2) is in a form of Val 1 :*: Val 2 :*: Val 3 ..., then our function expand stops expanding and evaluates expression to itself, otherwise recursion continues.

It works fine~ish on my examples

exp0 = (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5)
exp1 = (Val 1) :*: ((Val 2) :+: (Val 3)) :*: (Val 4)
exp2 =  Val 1 :*: (Val 2 :*: (Val 3 :+: Val 4)) 
exp3 = ((Val 1) :+: (Val 2)) :*: ((Val 3) :+: (Val 4))
exp4 =  Val 2 :*: (Val 3 :+: Val 4)
exp5 = (Val 3 :+: Val 4) :*: Val 2
exp6 =  Val 3 :+: Val 4  :*: Val 2
exp7 =  Val 3 :*: (Val 4 :*: Val 2)
exp8 = (Val 3 :*: Val 4) :*: Val 2
exp9 =  (Val 1 :+: Val 2 :+: Val 3) :*: (Val 4 :+: Val 5) :*: (Val 6) :*: ((Val 7) :+: (Val 8)) :*: (Val 9)

yet fails to pass some test, due to time limit exceeded. I guess, recursion doesn't stop somewhere, where it has to, but i don't see where.

Answer 1

Mistake was in the function isMul: result of expression isMul ((Val 3 :*: (Val 4 :*: Val 2)) :*: ((Val 3 :*: Val 4) :*: Val 2)) was False. Is happened, because data Expr is essentially a tree, so expressions Val 1 :*: (Val 2 :*: (Val 3 :*: Val 4)) and (Val 1 :*: Val 2) :*: (Val 3 :*: Val 4) are in fact different. So, I wrote a more general realization for isMul:

isMul :: Expr -> Bool
isMul (e1 :*: e2) = isMul e1 && isMul e2
isMul (Val a) = True
isMul  _      = False

which made program work as intended.