BinOpTree.hs

-- Copyright (c) 2020 Scott J Maddox
--
-- Licensed under either the Apache License, Version 2.0
-- (see https://www.apache.org/licenses/LICENSE-2.0),
-- or the ZLib license (see https://opensource.org/licenses/Zlib),
-- at your option.

module Data.BinOpTree
  ( BinOpTree (..),
    allFromList,
  )
where

-- | Binary Operator Tree
data BinOpTree a = Leaf a | Op (BinOpTree a) (BinOpTree a)

-- Return all possible BinOpTrees that can be generated from the given list.
-- Given an input list of length n, the length of the output list is given by
-- the nth Catalan number.
allFromList :: [a] -> [BinOpTree a]
allFromList [v] = [Leaf v]
allFromList [v1, v2] = [Leaf v1 `Op` Leaf v2]
allFromList vs = iter 1 []
  where
    iter n ts | n == length vs = ts
    iter n ts =
      let (lvs, rvs) = splitAt n vs
          (lts, rts) = (allFromList lvs, allFromList rvs)
          ts' = [Op lt rt | lt <- lts, rt <- rts]
       in iter (n + 1) (ts ++ ts')