Skip to content

Instantly share code, notes, and snippets.

@iblech

iblech/2566.hs

Last active Mar 6, 2017
Embed
What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment