2566.hs

module Main where

import Data.List
import Control.Monad

input  = [5,6,6,2]
target = 17

main :: IO ()
main = mapM_ (print . snd) $ filter ((== target) . fst) $ concatMap arb $ permutations input

-- Given a list `xs`, `arb xs` is the list of those syntax trees which
-- have the elements of `xs` at their leaves (in the same order as in `xs`).
-- Every element of `xs` occurs exactly once in those trees.
arb :: (Show a, Fractional a) => [a] -> [(a, String)]
arb []  = []
arb [x] = [(x, show x)]
arb xs  = do
    (as,bs) <- groups xs
    (left,left')   <- arb as
    (right,right') <- arb bs
    (op,op')       <- [((+), "+"), ((-), "-"), ((*), "*"), ((/), "/")]
    return (op left right, "(" ++ left' ++ ")" ++ op' ++ "(" ++ right' ++ ")")

-- Given a list `xs`, `groups xs` is the list of all possible ways
-- of splitting `xs` into two parts: a front part and a back part.
-- Both parts are not empty.
groups :: [a] -> [([a],[a])]
groups = tail . init . liftA2 zip inits tails