Subexpresiones aritméticas

José A. Alonso

04-06-2020

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

P (N 2) (S (N 3) (N 7))

Definir la función

subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

λ> subexpresiones (S (N 2) (N 3))
fromList [N 2,N 3,S (N 2) (N 3)]
λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Soluciones

import Data.Set

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

subexpresiones :: Expr -> Set Expr
subexpresiones (N x)   = singleton (N x)
subexpresiones (S i d) =
  S i d `insert` (subexpresiones i `union` subexpresiones d)
subexpresiones (P i d) =
  P i d `insert` (subexpresiones i `union` subexpresiones d)