data Expr a = Simple a | Seq (Expr a) (Expr a) | Or (Expr a) (Expr a) | And (Expr a) (Expr a) | Cond (Expr a) (Expr a) (Expr a)

npathsT :: Expr a -> Integer
npathsT (Simple _) = 1
npathsT (Seq x y) = npaths x * npathsT y
npathsT (Or x y) = npathsT x + npathsF x * npathsT y
npathsT (And x y) = npathsT x * npathsT y
npathsT (Cond b x y) = npathsT b * npathsT x + npathsF b * npathsT y

npathsF :: Expr a -> Integer
npathsF (Simple _) = 1
npathsF (Seq x y) = npaths x * npathsF y
npathsF (Or x y) = npathsF x * npathsF y
npathsF (And x y) = npathsF x + npathsT x * npathsF y
npathsF (Cond b x y) = npathsT b * npathsF x + npathsF b * npathsF y

npaths :: Expr a -> Integer
npaths (Simple _) = 1
npaths (Seq x y) = npaths x * npaths y
npaths (Or x y) = npathsT x + npathsF x * npaths y
npaths (And x y) = npathsF x + npathsT x * npaths y
npaths (Cond b x y) = npathsT b * npaths x + npathsF b * npaths y

pathsT :: Expr a -> [[a]]
pathsT (Simple x) = return [x]
pathsT (Seq x y) = do
  xp <- paths x
  yp <- pathsT y
  return (xp ++ yp)
pathsT (Or x y) = xPaths ++ xyPaths
  where
    xPaths = pathsT x
    xyPaths = do
      xp <- pathsF x
      yp <- pathsT y
      return (xp ++ yp)
pathsT (And x y) = do
  xp <- pathsT x
  yp <- pathsT y
  return (xp ++ yp)
pathsT (Cond b x y) = truePaths ++ falsePaths
  where
    truePaths = do
      tp <- pathsT b
      xp <- pathsT x
      return (tp ++ xp)
    falsePaths = do
      fp <- pathsF b
      yp <- pathsT y
      return (fp ++ yp)

pathsF :: Expr a -> [[a]]
pathsF (Simple x) = return [x]
pathsF (Seq x y) = do
  xp <- paths x
  yp <- pathsF y
  return (xp ++ yp)
pathsF (Or x y) = do
  xp <- pathsF x
  yp <- pathsF y
  return (xp ++ yp)
pathsF (And x y) = xPaths ++ xyPaths
  where
    xPaths = pathsF x
    xyPaths = do
      xp <- pathsT x
      yp <- pathsF y
      return (xp ++ yp)
pathsF (Cond b x y) = truePaths ++ falsePaths
  where
    truePaths = do
      tp <- pathsT b
      xp <- pathsF x
      return (tp ++ xp)
    falsePaths = do
      fp <- pathsF b
      yp <- pathsF y
      return (fp ++ yp)

paths :: Expr a -> [[a]]
paths (Simple x) = return [x]
paths (Seq x y) = do
  xp <- paths x
  yp <- paths y
  return (xp ++ yp)
paths (Or x y) = xPaths ++ xyPaths
  where
    xPaths = pathsT x
    xyPaths = do
      xp <- pathsF x
      yp <- paths y
      return (xp ++ yp)
paths (And x y) = xPaths ++ xyPaths
  where
    xPaths = pathsF x
    xyPaths = do
      xp <- pathsT x
      yp <- paths y
      return (xp ++ yp)
paths (Cond b x y) = truePaths ++ falsePaths
  where
    truePaths = do
      tp <- pathsT b
      xp <- paths x
      return (tp ++ xp)
    falsePaths = do
      fp <- pathsF b
      yp <- paths y
      return (fp ++ yp)

s = Simple

-- A?B:C
e1 = Cond (s 'A') (s 'B') (s 'C')
-- (A||B)?C:D
e2 = Cond (s 'A' `Or` s 'B') (s 'C') (s 'D')
-- (A?B:C)?D:E
e3 = Cond e1 (s 'D') (s 'E')
-- (A?B:C)?(D?E:F):G
e4 = Cond e1 (Cond (s 'D') (s 'E') (s 'F')) (s 'G')
-- ((A?(B&&C):(D||E))||F)?G:H
e5 = Cond ((Cond (s 'A') (s 'B' `And` s 'C') (s 'D' `Or` s 'E')) `Or` (s 'F')) (s 'G') (s 'H')